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


This article is issued from Wikipedia - version of the Sunday, June 07, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.