Low basis theorem

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

References

• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
• CG Jockusch, Jr and RI Soare, "Π(0, 1) Classes and Degrees of Theories" in Transactions of the American Mathematical Society (1972). JSTOR 1996261