Low basis theorem

The low basis theorem in computability theory states that every nonempty $\Pi^0_1$ class in $2^\omega$ (see analytical hierarchy) contains a set of low degree. It was first proved by Carl Jockusch and Robert I. Soare in 1972 (Cenzer 1999:53; Nies 2009:57).

References

Cenzer, Douglas (1999). " $\Pi^0_1$ 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.
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.
Nies, André (2009). Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.
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.