Π01 class

In computability theory, a Π 0 1 class is a subset of 2 ω of a certain form. These classes are of interest as technical tools within recursion theory and effective descriptive set theory. They are also used in the application of recursion theory to other branches of mathematics (Cenzer 1999, p. 39).

In computability theory, a Π 0 1 class is a subset of 2 ω of a certain form. These classes are of interest as technical tools within recursion theory and effective descriptive set theory. They are also used in the application of recursion theory to other branches of mathematics (Cenzer 1999, p. 39). A (lightface) Π 0 1 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 Π 0 1 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 Π 0 1 classes are exactly the same as the closed sets of 2 ω and thus the same as the boldface Π 0 1 subsets of 2 ω in the Borel hierarchy. Lightface Π 0 1 classes in 2 ω (that is, Π 0 1 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1364296798 under CC BY-SA 4.0; modifications have been made.