---
tag: NCCM3HXNDW
kind: statement
role: proposition
name: Basis theorem (computability)
sources:
  - wikipedia: en:53605449@r1232545569
    locator: Basis theorem (computability)
    note: adopted
    mention: wikipedia://en/53605449
    sections: [Statement]
same_as:
  wikidata: Q30716971
  wikipedia: Basis theorem (computability)
inventory: [ZGGTPPWSC9]
---

## 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.