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.
2008
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.
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