Low basis theorem
The low basis theorem in computability theory states that every nonempty class in (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 classes". The proof uses the method of forcing with classes (Cooper 2004:330).
References
- Cenzer, Douglas (1999). " 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 Sunday, June 07, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.