We show that the first order theory of the $\Sigma^0_2$ $s$-degrees is undecidable. Via isomorphism of the $s$-degrees with the $Q$-degrees, this also shows that the first order theory of the $\Pi^0_2$ $Q$-degrees is undecidable. Together with a result of Nies, the proof of the undecidability of the $\Sigma^0_2$ $s$-degrees yields a new proof of the known fact (due to Downey, LaForte and Nies) that the first order theory of the c.e. $Q$-degrees is undecidable.
Affatato, M.L., Kent, T.F., Sorbi, A. (2008). Undecidability of local structures of s-degrees and Q-degrees. TBILISI MATHEMATICAL JOURNAL, 1, 15-32.
Undecidability of local structures of s-degrees and Q-degrees
SORBI, ANDREA
2008-01-01
Abstract
We show that the first order theory of the $\Sigma^0_2$ $s$-degrees is undecidable. Via isomorphism of the $s$-degrees with the $Q$-degrees, this also shows that the first order theory of the $\Pi^0_2$ $Q$-degrees is undecidable. Together with a result of Nies, the proof of the undecidability of the $\Sigma^0_2$ $s$-degrees yields a new proof of the known fact (due to Downey, LaForte and Nies) that the first order theory of the c.e. $Q$-degrees is undecidable.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
tmj1_2.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
285.79 kB
Formato
Adobe PDF
|
285.79 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
Utilizza questo identificativo per citare o creare un link a questo documento:
https://hdl.handle.net/11365/22902