Low basis theorem

The low basis theorem in computability theory states that every nonempty $\Pi _{1}^{0}$ class in $2^{\omega }$ (see arithmetical hierarchy) contains a set of low degree (Soare 1987:109). It was first proved by Carl Jockusch and Robert I. Soare in 1972 (Nies 2009:57). Cenzer (1993:53) describes it as "perhaps the most cited result in the theory of $\Pi _{1}^{0}$ classes". The proof uses the method of forcing with $\Pi _{1}^{0}$ classes (Cooper 2004:330).

References

Cenzer, Douglas (1999). " $\Pi _{1}^{0}$ classes in computability theory". In Griffor, Edward R. Handbook of computability theory. Stud. Logic Found. Math. 140. North-Holland. pp. 37–85. ISBN 0-444-89882-4. MR 1720779. Zbl 0939.03047. Theorem 3.6, p. 54.
Cooper, S. Barry (2004). Computability Theory. Chapman and Hall/CRC. ISBN 1-58488-237-9. .
Jockusch, Carl G., Jr.; Soare, Robert I. (1972). "Π(0, 1) Classes and Degrees of Theories". Transactions of the American Mathematical Society. 173: 33–56. doi:10.1090/s0002-9947-1972-0316227-0. ISSN 0002-9947. JSTOR 1996261. Zbl 0262.02041. The original publication, including additional clarifying prose.
Nies, André (2009). Computability and randomness. Oxford Logic Guides. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034. Theorem 1.8.37.
Soare, Robert I. (1987). Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-15299-7. Zbl 0667.03030.

This article is issued from Wikipedia - version of the 6/7/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.