{"history":[],"article":{"id":"c52acdf7-0c52-4d6b-83b4-700b088d2589","title":"Π01 class","slug":"01-class","content":":::summary\n:::\n\n# \nIn [computability theory](https://bliptext.com/articles/computability-theory), a **Π01 class** is a subset of 2ω of a certain form.\nThese classes are of interest as technical tools within [recursion theory](https://bliptext.com/articles/recursion-theory) and [effective descriptive set theory](https://bliptext.com/articles/effective-descriptive-set-theory).\nThey are also used in the application of recursion theory to other branches of mathematics (Cenzer 1999, p. 39).\n\n# Definition\nThe 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}).\nA [tree](https://bliptext.com/articles/tree-descriptive-set-theory) on 2<ω is a subset of 2<ω that is closed under taking initial segments.\nAn element f of 2ω is a **path** through a tree T on 2<ω if every finite initial segment of f is in T.\nA ([lightface](https://bliptext.com/articles/lightface)) **Π0_{1 class** is a subset C of 2ω for which there is a [computable](https://bliptext.com/articles/computable-set) tree T such that C consists of exactly the paths through T.\nA **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< ω from computable from f such that D is the set of paths through T.\n\n# As effectively closed sets\nThe 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](https://bliptext.com/articles/borel-hierarchy).\nLightface Π0_{1 classes in 2ω (that is, Π0_{1 classes whose tree is computable with no oracle) correspond to **effectively closed sets**.\nA subset B of 2ω is effectively closed if there is a [recursively enumerable](https://bliptext.com/articles/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.\n\n# Relationship with effective theories\nFor each effectively axiomatized theory T of [first-order logic](https://bliptext.com/articles/first-order-logic), the set of all completions of T is a \\Pi^0_1 class.\nMoreover, for each \\Pi^0_1 subset S of 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).","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T12:19:12.802Z","updated_at":"2025-01-26T12:19:12.802Z","search_vector":"'class':2 'π01':1","search_content":" \n \n\n# \nIn [computability theory](https://bliptext.com/articles/computability-theory), a **Π01 class** is a subset of 2ω of a certain form.\nThese classes are of interest as technical tools within [recursion theory](https://bliptext.com/articles/recursion-theory) and [effective descriptive set theory](https://bliptext.com/articles/effective-descriptive-set-theory).\nThey are also used in the application of recursion theory to other branches of mathematics (Cenzer 1999, p. 39).\n\n# Definition\nThe set 2 1 class** is a subset C of 2ω for which there is a [computable](https://bliptext.com/articles/computable-set) tree T such that C consists of exactly the paths through T.\nA **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 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](https://bliptext.com/articles/borel-hierarchy).\nLightface Π0 1 classes in 2ω (that is, Π0 1 classes whose tree is computable with no oracle) correspond to **effectively closed sets**.\nA subset B of 2ω is effectively closed if there is a [recursively enumerable](https://bliptext.com/articles/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.\n\n# Relationship with effective theories\nFor each effectively axiomatized theory T of [first-order logic](https://bliptext.com/articles/first-order-logic), the set of all completions of T is a \\Pi^0_1 class.\nMoreover, for each \\Pi^0_1 subset S of 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).","revisionCount":0},"hasMore":false,"nextCursor":null}}}}}}}

History