Π⁰₁ class

The set 2^<ω consists of all finite sequences of 0s and 1s, while the set 2^ω consists of all infinite sequences of 0s and 1s (that is, functions from ω = {0, 1, 2, ...} to the set {0,1}).

A tree on 2^<ω is a subset of 2^<ω that is closed under taking initial segments. An element f of 2^ω is a path through a tree T on 2^<ω if every finite initial segment of f is in T.

A (lightface) Π⁰₁ class is a subset C of 2^ω for which there is a computable tree T such that C consists of exactly the paths through T. A boldface Π⁰₁ class is a subset D of 2^ω for which there is an oracle f in 2^ω and a subtree tree T of 2^{< ω} from computable from f such that D is the set of paths through T.

The boldface Π⁰₁ classes are exactly the same as the closed sets of 2^ω and thus the same as the boldface Π⁰₁ subsets of 2^ω in the Borel hierarchy.

Lightface Π⁰₁ classes in 2^ω (that is, Π⁰₁ classes whose tree is computable with no oracle) correspond to effectively closed sets. A subset B of 2^ω is effectively closed if there is a recursively enumerable sequence ⟨σ_i : i ∈ ω⟩ of elements of 2^{< ω} such that each g ∈ 2^ω is in B if and only if there exists some i such that σ_i is an initial segment of B.

For each effectively axiomatized theory T of first-order logic, the set of all completions of T is a ${\displaystyle \Pi _{1}^{0}}$ class. Moreover, for each ${\displaystyle \Pi _{1}^{0}}$ subset S of ${\displaystyle 2^{\omega }}$ there is an effectively axiomatized theory T such that each element of S computes a completion of T, and each completion of T computes an element of S (Jockusch and Soare 1972b).

• Arithmetical hierarchy
• Basis theorem (computability)

• Cenzer, Douglas (1999), "${\displaystyle \Pi _{1}^{0}}$ classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math., vol. 140, Amsterdam: North-Holland, pp. 37 85, MR 1720779
• Jockush, Carl G.; Soare, Robert I. (1972a), "Degrees of members of ${\displaystyle \Pi _{1}^{0}}$ classes." (PDF), Pacific Journal of Mathematics, 40 (3): 605–616, doi:10.2140/pjm.1972.40.605
• Jockush, Carl G.; Soare, Robert I. (1972b), "${\displaystyle \Pi _{1}^{0}}$ Classes and Degrees of Theories", Transactions of the American Mathematical Society, 173: 33–56, doi:10.1090/s0002-9947-1972-0316227-0