Π01 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^{< ω} 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 does not exist 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 class. Moreover, for each subset S of 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).