In computability theory, there are a number of basis theorems.
These theorems show that particular kinds of sets always must have some members that are, in terms of Turing degree, not too complicated.
sets in the arithmetical hierarchy); these theorems are studied as part of classical computability theory.
Another family of basis theorems concern nonempty lightface analytic sets (that is,
in the analytical hierarchy); these theorems are studied as part of hyperarithmetical theory.
Effectively closed sets are a topic of study in classical computability theory.
These sets are closed, in the topological sense, as subsets of the Cantor space
Kleene proved in 1952 that there is a nonempty, effectively closed set with no computable point (Cooper 1999, p. 134).
Basis theorems show that there must be points that are not "too far" from being computable, in an informal sense.
is a basis for effectively closed sets if every nonempty effectively closed set includes a member of
Basis theorems show that particular classes are bases in this sense.
No two of the above three theorems can be combined for the set of consistent completions of PA (or just EFA; the Turing degrees are the same).
Turing degree that computes a consistent completion of PA is 0'.
These basis theorems are studied as part of hyperarithmetical theory.
The Gandy basis theorem shows that each nonempty