En matemáticas, el teorema de la aceleración de Gödel , probado por Gödel ( 1936 ), muestra que hay teoremas cuyas demostraciones se pueden acortar drásticamente trabajando en sistemas axiomáticos más poderosos.
Kurt Gödel mostró cómo encontrar ejemplos explícitos de enunciados en sistemas formales que son probables en ese sistema pero cuya prueba más corta es inimaginablemente larga. Por ejemplo, la declaración:
- "Esta afirmación no se puede probar en aritmética de Peano en menos de un googolplex símbolos"
es demostrable en la aritmética de Peano (PA) pero la prueba más corta tiene al menos un símbolo de googolplex, mediante un argumento similar a la prueba del primer teorema de incompletitud de Gödel : si PA es consistente, entonces no puede probar el enunciado en menos de un símbolo de googolplex, porque la existencia de tal demostración sería en sí misma un teorema de PA, una contradicción. Pero simplemente enumerando todas las cadenas de longitud hasta un googolplex y verificando que cada una de esas cadenas no sea una prueba (en PA) de la declaración, se obtiene una prueba de la declaración (que es necesariamente más larga que los símbolos de un googolplex).
El enunciado tiene una prueba corta en un sistema más poderoso: de hecho, la prueba dada en el párrafo anterior es una prueba en el sistema de la aritmética de Peano más el enunciado "La aritmética de Peano es consistente" (que, según el teorema de incompletitud, no se puede probar en aritmética de Peano).
En este argumento, la aritmética de Peano puede ser reemplazada por cualquier sistema consistente más poderoso, y un googolplex puede ser reemplazado por cualquier número que pueda describirse de manera concisa en el sistema.
Harvey Friedman encontró algunos ejemplos naturales explícitos de este fenómeno, dando algunos enunciados explícitos en la aritmética de Peano y otros sistemas formales cuyas demostraciones más cortas son ridículamente largas ( Smoryński 1982 ). Por ejemplo, la declaración
- "hay un número entero n tal que si hay una secuencia de árboles con raíces T 1 , T 2 , ..., T n tal que T k tiene como máximo k +10 vértices, entonces algún árbol se puede incrustar homeomórficamente en un uno"
es demostrable en aritmética de Peano, pero la prueba más corta tiene una longitud de al menos A (1000), donde A (0) = 1 y A ( n +1) = 2 A ( n ) . El enunciado es un caso especial del teorema de Kruskal y tiene una breve demostración en aritmética de segundo orden .
Si se toma la aritmética de Peano junto con la negación del enunciado anterior, se obtiene una teoría inconsistente cuya contradicción más corta es inimaginablemente larga.
Ver también
Referencias
- Buss, Samuel R. (1994), "Sobre los teoremas de Gödel sobre la longitud de las demostraciones. I. Número de líneas y aceleración para la aritmética", The Journal of Symbolic Logic , 59 (3): 737–756, doi : 10.2307 / 2275906 , ISSN 0022-4812 , JSTOR 2275906 , MR 1295967
- Buss, Samuel R. (1995), "Sobre los teoremas de Gödel sobre la longitud de las demostraciones. II. Límites inferiores para reconocer k demostrabilidad de símbolos", en Clote, Peter; Remmel, Jeffrey (eds.), Matemáticas factibles, II (Ithaca, NY, 1992) , Progr. Computación. Sci. Apl. Logic, 13 , Boston, MA: Birkhäuser Boston, págs. 57–90, ISBN 978-0-8176-3675-3, MR 1322274
- Gödel, Kurt (1936), "Über die Länge von Beweisen" , Ergebnisse eines Mathematischen Kolloquiums (en alemán), 7 : 23-24, ISBN 9780195039641, Reimpreso con traducción al inglés en el volumen 1 de sus obras completas.
- Smoryński, C. (1982), "Las variedades de la experiencia arbórea", Math. Intelligencer , 4 (4): 182–189, doi : 10.1007 / bf03023553 , MR 0685558