En teoría de la computabilidad , una clase Π 0 1 es un subconjunto de 2 ω de cierta forma. Estas clases son de interés como herramientas técnicas dentro de la teoría de la recursividad y la teoría descriptiva de conjuntos eficaz . También se utilizan en la aplicación de la teoría de la recursividad a otras ramas de las matemáticas (Cenzer 1999, p. 39).
El conjunto 2 <ω consta de todas las secuencias finitas de 0 y 1, mientras que el conjunto 2 ω consta de todas las secuencias infinitas de 0 y 1 (es decir, funciones desde ω = {0, 1, 2, ... } hasta el establecer {0,1 }).
Un árbol en 2 <ω es un subconjunto de 2 <ω que se cierra tomando segmentos iniciales. Un elemento f de 2 ω es un camino a través de un árbol T en 2 <ω si cada segmento inicial finito de f está en T .
Una clase ( lightface ) Π 0 1 es un subconjunto C de 2 ω para el cual existe un árbol computable T tal que C consiste exactamente en los caminos que pasan por T. Una clase Π 0 1 en negrita es un subconjunto D de 2 ω para el cual hay un oráculo f en 2 ω y un subárbol T de 2 < ω computable a partir de f tal que D es el conjunto de caminos a través de T .
Las clases en negrita Π 0 1 son exactamente las mismas que los conjuntos cerrados de 2 ω y, por lo tanto, las mismas que los subconjuntos en negrita Π 0 1 de 2 ω en la jerarquía de Borel .
Las clases Lightface Π 0 1 en 2 ω (es decir, las clases Π 0 1 cuyo árbol es computable sin oráculo) corresponden a conjuntos efectivamente cerrados . Un subconjunto B de 2 ω está efectivamente cerrado si existe una secuencia recursivamente enumerable ⟨σ i : i ∈ ω⟩ de elementos de 2 < ω tal que cada g ∈ 2 ω esté en B si y solo si existe algún i tal que σ i es un segmento inicial de B .
Para cada teoría T efectivamente axiomatizada de la lógica de primer orden , el conjunto de todas las terminaciones de T es una clase. Además, para cada subconjunto S de existe una teoría T efectivamente axiomatizada tal que cada elemento de S calcula una compleción de T , y cada compleción de T calcula un elemento de S (Jockusch y Soare 1972b).
