Basis theorem (computability)

Statement

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 $\Pi^0_1$ 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, $\Sigma^1_1$ in the analytical hierarchy); these theorems are studied as part of hyperarithmetical theory.