Clase Π01
En la 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 recursión y la teoría de conjuntos descriptiva eficaz . También se utilizan en la aplicación de la teoría de la recursión a otras ramas de las matemáticas (Cenzer 1999, p. 39).
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 todo 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 consta exactamente de los caminos a través de 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 < ω de 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 .
Lightface Π 0 1 clases en 2 ω (es decir, Π 0 1 clases cuyo árbol es computable sin oráculo) corresponden a conjuntos efectivamente cerrados . Un subconjunto B de 2 ω es 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 σ i es un segmento inicial de B. _
Para cada teoría T efectivamente axiomatizada de lógica de primer orden , el conjunto de todas las completaciones de T es una clase. Además, para cada subconjunto S de hay una teoría T efectivamente axiomatizada tal que cada elemento de S calcula un complemento de T , y cada complemento de T calcula un elemento de S (Jockusch y Soare 1972b).
