Low basis theorem

The low basis theorem in computability theory states that every nonempty ${\displaystyle \Pi _{1}^{0}}$ class of ${\displaystyle 2^{\omega }}$ (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

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e