Π01 class

{{DISPLAYTITLE:Π01 class}} In computability theory, a '''Π01 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).

== 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 {{nowrap|1=ω = {0, 1, 2, ...}}} to the set {{nowrap|1={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) '''Π01 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 Π01 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 Π01 classes are exactly the same as the closed sets of 2ω and thus the same as the boldface Π01 subsets of 2ω in the Borel hierarchy.

Lightface Π01 classes in 2ω (that is, Π01 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 &lang;σ''i'' : i ∈ ω&rang; 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''.

== Relationship with effective theories ==

For each effectively axiomatized theory ''T'' of first-order logic, the set of all completions of ''T'' is a <math>\Pi^0_1</math> class. Moreover, for each <math>\Pi^0_1</math> subset ''S'' of <math>2^\omega</math> 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).

== References ==

* {{Citation | last1=Cenzer | first1=Douglas | title=Handbook of computability theory | publisher=North-Holland | location=Amsterdam | series=Stud. Logic Found. Math. |mr=1720779 | year=1999 | volume=140 | chapter=<math>\Pi^0_1</math> classes in computability theory | pages=37 85}} * {{Citation | last1=Jockush | first1=Carl G. | last2=Soare | first2=Robert I. | title=Degrees of members of <math>\Pi^0_1</math> classes. | journal=Pacific Journal of Mathematics| volume=40 | issue=3 | year=1972a | pages=605–616 | doi=10.2140/pjm.1972.40.605| url=http://msp.org/pjm/1972/40-3/pjm-v40-n3-p09-s.pdf | doi-access=free }}  * {{Citation | last1=Jockush | first1=Carl G. | last2=Soare | first2=Robert I. | title = <math>\Pi^0_1</math> Classes and Degrees of Theories | journal=Transactions of the American Mathematical Society | volume=173 | year=1972b | pages=33–56 | doi=10.1090/s0002-9947-1972-0316227-0| doi-access=free }}

{{DEFAULTSORT:Pi01 Class}} Category:Computability theory