View source for Congruence lattice problem

The '''low basis theorem''' in [[computability theory]] states that every nonempty <math>\Pi^0_1</math> class in <math>2^\omega</math> (see [[analytical hierarchy]]) contains a set of [[low (computability)|low degree]]. It was first proved by [[Carl Jockusch]] and [[Robert I. Soare]] in 1972 (Cenzer 1999:53; Nies 2009:57). 

== References ==
* {{cite book | first=Douglas | last=Cenzer | chapter=<math>\Pi^0_1</math> classes in computability theory | title=Handbook of computability theory | series=Stud. Logic Found. Math. | volume=140 | publisher=North-Holland | year=1999 | pages=37–85 | mr=1720779 | zbl=0939.03047 | editor-last=Griffor | editor-first=Edward R. | isbn=0-444-89882-4 }} 
* {{cite journal | first1=Carl G., jr | last1=Jockusch | first2=Robert I. | last2=Soare | title=&Pi;(0, 1) Classes and Degrees of Theories | journal=Transactions of the American Mathematical Society | year=1972 | jstor=1996261 | zbl=0262.02041 | volume=173 | pages=33-56 | issn=0002-9947 }}
*{{cite book | last=Nies | first=André | title=Computability and randomness | series=Oxford Logic Guides | volume=51 | location=Oxford | publisher=Oxford University Press | year=2009 | isbn=978-0-19-923076-1 | zbl=1169.03034 }}
* {{cite book | first=Robert I. | last=Soare | title=Recursively enumerable sets and degrees. A study of computable functions and computably generated sets | series=Perspectives in Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin | year=1987 | isbn=3-540-15299-7 | zbl=0667.03030 }}

{{Mathlogic-stub}}
[[Category:Computability theory]]