No CrossRef data available.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
${{\rm{\Sigma }}_2}$ THEORIES OF THE ARITHMETIC AND HYPERARITHMETIC DEGREES AS UPPERSEMILATTICESPublished online by Cambridge University Press: 09 January 2018
We establish the decidability of the 
${{\rm{\Sigma }}_2}$ theory of both the arithmetic and hyperarithmetic degrees in the language of uppersemilattices, i.e., the language with ≤, 0 , and 
$\sqcup$. This is achieved by using Kumabe-Slaman forcing, along with other known results, to show given finite uppersemilattices 
${\cal M}$ and 
${\cal N}$, where 
${\cal M}$ is a subuppersemilattice of 
${\cal N}$, that every embedding of 
${\cal M}$ into either degree structure extends to one of 
${\cal N}$ iff 
${\cal N}$ is an end-extension of 
${\cal M}$.
${\rm{\Sigma }}_1^1$
in every real in a
${\rm{\Sigma }}_1^1$
class of reals is
${\rm{\Sigma }}_1^1$
, Computability and Complexity, Essays Dedicated to Rodney Downey on the Occasion of his 60th Birthday (Day, A., Felows, M., Greenberg, N., Khoussainov, B., Melnikov, A., and Rosamond, F., editors), Springer-Verlag, Berlin, Heidelberg, 2017, pp. 455–468.Google Scholar
${{\rm{\Sigma }}_2}$
-theory of the upper semilattice of Turing degrees, this Journal, vol. 58 (1993), no. 1, pp. 193–204.Google Scholar