Basis theorem (computability)

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. One family of basis theorems concern nonempty effectively closed sets (that is, nonempty ${\displaystyle \Pi _{1}^{0}}$ 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, ${\displaystyle \Sigma _{1}^{1}}$ 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. An effectively closed set is the set of all paths through some computable subtree of the binary tree ${\displaystyle 2^{<\omega }}$. These sets are closed, in the topological sense, as subsets of the Cantor space ${\displaystyle 2^{\omega }}$, and the complement of an effective closed set is an effective open set in the sense of effective Polish spaces. Stephen Cole Kleene proved in 1952 that there is a nonempty, effectively closed set with no computable point (Cooper 1999, p. 134). There are basis theorems that show there must be points that are not "too far" from being computable, in an informal sense.

...
Wikipedia