Low basis theorem

From Wikipedia, the free encyclopedia

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

[edit] 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).[1]
 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.