Teorema de la base baja

El teorema de base baja es uno de varios teoremas de base en la teoría de la computabilidad , cada uno de los cuales muestra que, dado un subárbol infinito del árbol binario${\displaystyle 2^{<\omega }}$Es posible encontrar un camino infinito a través del árbol con propiedades de computabilidad particulares. El teorema de la base baja, en particular, muestra que debe existir un camino que sea bajo ; es decir, el salto de Turing del camino es Turing equivalente al problema de la parada.${\displaystyle \emptyset '}$.

El teorema de la base baja establece que todo conjunto no vacío${\displaystyle \Pi _{1}^{0}}$clase en${\displaystyle 2^{\omega }}$(véase jerarquía aritmética ) contiene un conjunto de bajo grado (Soare 1987:109). Esto es equivalente, por definición, a la afirmación de que cada subárbol computable infinito del árbol binario${\displaystyle 2^{<\omega }}$tiene un camino infinito de bajo grado.

La demostración utiliza el método de forzar con${\displaystyle \Pi _{1}^{0}}$clases (Cooper 2004:330). Hájek y Kučera (1989) demostraron que la base baja es demostrable en el sistema formal de aritmética conocido como${\displaystyle {\text{I-}}\Sigma _{1}}$.

El argumento de forzamiento también puede formularse explícitamente de la siguiente manera. Para un conjunto X ⊆ω, sea f ( X ) = Σ _{{ i }( X )↓} 2 ^{− i} , donde { i }( X )↓ significa que la máquina de Turing i se detiene en X (con la suma siendo sobre todos tales i ). Entonces, para cada no vacío (cara ligera)${\displaystyle \Pi _{1}^{0}}$S ⊆2 ^ω , el (único) X ∈ S que minimiza f ( X ) tiene un grado de Turing bajo. Esto se debe a que X satisface { i }( X )↓ ⇔ ∀ Y ∈ S ({ i }( Y )↓ ∨ ∃ j < i ({ j }( Y )↓ ∧ ¬{ j }( X )↓)), por lo que la función i ↦ { i }( X )↓ se puede calcular a partir de${\displaystyle \emptyset '}$por inducción sobre i ; tenga en cuenta que ∀ Y ∈ S φ( Y ) es${\displaystyle \Sigma _{1}^{0}}$para cualquier${\displaystyle \Sigma _{1}^{0}}$establecer φ. En otras palabras, si una máquina se detiene en X está determinado por una condición finita, lo que permite X ′ =${\displaystyle \emptyset '}$.

Una aplicación del teorema de la base baja es construir completaciones de teorías efectivas de modo que dichas completaciones tengan un grado de Turing bajo. Por ejemplo, el teorema de la base baja implica la existencia de grados PA estrictamente inferiores a${\displaystyle \emptyset '}$.

• Cenzer, Douglas (1999) .${\displaystyle \Pi _{1}^{0}}$clases en teoría de la computabilidad" . En Griffor, Edward R. (ed.). Manual de teoría de la computabilidad . Stud. Logic Found. Math. Vol.  140. North-Holland. pp. 37–85 . ISBN  0-444-89882-4. SEÑOR 1720779 . Zbl 0939.03047 .  
• Cooper, S. Barry (2004). Teoría de la computabilidad . Chapman and Hall/CRC. ISBN 1-58488-237-9..
• Hájek, Petr; Kučera, Antonín (1989). "Sobre la teoría de la recursividad en IΣ1". Revista de Lógica Simbólica . 54 (2): 576– 589. doi : 10.2307/2274871 . JSTOR 2274871 . S2CID 118808365 .  
• Jockusch, Carl G. Jr.; Soare, Robert I. (1972). " Π (0, 1) Clases y grados de teorías" . Transactions of the American Mathematical Society . 173 : 33–56 . doi : 10.1090/s0002-9947-1972-0316227-0 . ISSN 0002-9947 . JSTOR 1996261. Zbl 0262.02041 .   La publicación original, incluyendo textos aclaratorios adicionales.
• Nies, André (2009). Computabilidad y aleatoriedad . Oxford Logic Guides. Vol.  51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034 . Teorema 1.8.37.
• Soare, Robert I. (1987). Conjuntos y grados recursivamente enumerables. Un estudio de funciones computables y conjuntos generados computacionalmente . Perspectivas en lógica matemática. Berlín: Springer-Verlag . ISBN 3-540-15299-7. Zbl 0667.03030 .