El teorema de base baja es uno de varios teoremas de base en la teoría de computabilidad, cada uno de los cuales muestra que, dado un subárbol infinito del árbol binario, es posible encontrar una ruta infinita a través del árbol con propiedades de computabilidad particulares. El teorema de base baja, en particular, muestra que debe haber un camino que sea bajo ; es decir, el salto de Turing del camino es Turing equivalente al problema de detención .
Declaración y prueba
El teorema de base baja establece que todo no vacío clase en(ver 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 tiene un camino infinito de bajo grado.
La prueba usa el método de forzar con 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.
Solicitud
Una aplicación del teorema de base baja es construir terminaciones de teorías efectivas de modo que las terminaciones tengan un grado de Turing bajo. Por ejemplo, el teorema de base baja implica la existencia de grados de PA estrictamente por debajo de.
Referencias
- Cenzer, Douglas (1999). "clases de teoría de la computabilidad " . En Griffor, Edward R. (ed.). Manual de teoría de la computabilidad . Stud. Logic Found. Math. 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 y 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 .
- Jockusch, Carl G., Jr .; Soare, Robert I. (1972). "Π (0, 1) Clases y grados de teorías" . Transacciones de la 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, incluida la prosa aclaratoria adicional.
- Nies, André (2009). Computabilidad y aleatoriedad . Guías lógicas de Oxford. 51 . Oxford: Prensa de la Universidad de Oxford. 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 computablemente . Perspectivas en lógica matemática. Berlín: Springer-Verlag . ISBN 3-540-15299-7. Zbl 0667.03030 .