Low basis theorem

The low basis theorem in computability theory states that every nonempty $\Pi^0_1$ 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^0_1$ classes". The proof uses the method of forcing with $\Pi^0_1$ classes (Cooper 2004:330).

References

• Theorem 3.6, p. 54.
• .
• The original publication, including additional clarifying prose.
• Theorem 1.8.37.