Π01 class

Definition

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.

As effectively closed sets

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 σ_i is an initial segment of B.

Relationship with effective theories

For each effectively axiomatized theory T of first-order logic, the set of all completions of T is a Π 1 0 class. Moreover, for each Π 1 0 subset S of 2 ω 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).