## Undecidability of local structures of s-degrees and Q-degrees## M. L. Affatato, T. F. Kent, A. Sorbi
We show that the first order theory of the å
_{2}^{0}
s-degrees is undecidable. Via isomorphism of the s-degrees with the Q-degrees, this also shows that the first order
theory of the Õ_{2}^{0} Q-degrees is undecidable. Together with a result of Nies, the proof of the undecidability
of the å_{2}^{0} 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.
Tbilisi Mathematical Journal, Vol. 1(2008), pp. 15-32 |