Teorema de Goodstein

En lógica matemática , el teorema de Goodstein es una afirmación sobre los números naturales , demostrada por Reuben Goodstein en 1944, que establece que toda secuencia de Goodstein (como se define más adelante) termina finalmente en 0. Laurence Kirby y Jeff Paris ^{[ 1 ]} demostraron en 1982 que el teorema de Goodstein es indemostrable en la aritmética de Peano (pero puede demostrarse en sistemas más fuertes, como la aritmética de segundo orden o la teoría de conjuntos de Zermelo-Fraenkel ). Este fue el tercer ejemplo de una afirmación verdadera sobre los números naturales que es indemostrable en la aritmética de Peano, después de los ejemplos proporcionados por el teorema de incompletitud de Gödel y la demostración directa de Gerhard Gentzen de 1943 de la indemostrabilidad de la inducción ε ₀ en la aritmética de Peano. El teorema de Paris-Harrington dio otro ejemplo.

Kirby y Paris también introdujeron un juego de hidra basado en la teoría de grafos con un comportamiento similar al de las secuencias de Goodstein: la "Hidra" (llamada así por la Hidra mitológica de múltiples cabezas de Lerna ) es un árbol con raíz , y un movimiento de " Hércules " consiste en cortar una de sus "cabezas" (una rama del árbol), a lo que la Hidra responde haciendo crecer un número finito de nuevas cabezas según ciertas reglas. Kirby y Paris demostraron que la Hidra acabará siendo destruida, independientemente de la estrategia que Hércules utilice para cortar sus cabezas, aunque esto puede llevar mucho tiempo. Al igual que con las secuencias de Goodstein, Kirby y Paris demostraron que no se puede probar solo con la aritmética de Peano. ^{[ 1 ]}

Las secuencias de Goodstein se definen mediante un concepto llamado "notación hereditaria en base n ". Esta notación es muy similar a la notación posicional usual en base n para números naturales, pero la notación usual no es suficiente para los propósitos del teorema de Goodstein.

Para lograr la notación ordinaria en base n , donde n es un número natural mayor que 1, un número natural arbitrario m se escribe como una suma de múltiplos de potencias de n :

${\displaystyle m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},}$

donde cada coeficiente a _i satisface 0 ≤ a _i < n , y a _k ≠ 0 .

Por ejemplo, la notación en base 3 de 100:

${\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.}$

Aquí, los exponentes de n en sí mismos no están escritos en notación de base n , como se ve en el caso 3 ⁴ , arriba.

Para convertir una notación en base n a una notación hereditaria en base n , primero reescriba todos los exponentes como una suma de potencias de n (con la limitación en los coeficientes 0 ≤ a _i < n ). Luego, reescriba cualquier exponente dentro de los exponentes nuevamente en notación en base n (con la misma limitación en los coeficientes) y continúe de esta manera hasta que cada número que aparezca en la expresión (excepto las bases mismas) esté escrito en notación en base n .

Por ejemplo, 100 en notación hereditaria de base 3 es

${\displaystyle 100=3^{3^{1}+1}+2\cdot 3^{2}+1.}$

La secuencia de Goodstein${\displaystyle G_{m}}$de un número m es una secuencia de números naturales. El primer elemento de la secuencia, escrito como${\displaystyle G_{m}(1)}$, es m mismo. El segundo elemento,${\displaystyle G_{m}(2)}$, se obtiene escribiendo m en notación hereditaria de base 2, cambiando todos los 2 por 3 y luego restando 1 al resultado. En general, el término${\displaystyle G_{m}(n+1)}$de la secuencia de Goodstein de m se calcula mediante:

• tomando la representación de base hereditaria ( n + 1 ) de${\displaystyle G_{m}(n)}$,
• reemplazando cada ocurrencia de la base ( n + 1 ) con n + 2 , entonces
• restando uno.

${\displaystyle G_{m}(n+1)}$depende tanto de${\displaystyle G_{m}(n)}$y en el índice n . A veces${\displaystyle G_{m}(n)}$se escribe como${\displaystyle G_{n-1}(m)}$. ^{[ 2 ]}

Una secuencia de Goodstein termina cuando su elemento llega a 0. Las secuencias de Goodstein tempranas terminan rápidamente. Por ejemplo,${\displaystyle G_{3}}$finaliza en el sexto paso (la columna etiquetada como "Notación hereditaria" muestra cómo se calcula el valor):

Las secuencias de Goodstein posteriores aumentan durante un número muy grande de pasos. Por ejemplo,${\displaystyle G_{4}}$comienza de la siguiente manera ( OEIS : A056193  ):

Elementos de${\displaystyle G_{4}}$continuarán aumentando durante un tiempo, pero en base${\displaystyle 3\cdot 2^{402\,653\,209}}$, alcanzan el máximo de${\displaystyle 3\cdot 2^{402\,653\,210}-1}$, quédese allí para el próximo${\displaystyle 3\cdot 2^{402\,653\,209}}$escalones, y luego comienza a descender de 1 en 1, llegando a 0 cuando la base llega${\displaystyle 3\cdot 2^{402\,653\,211}-1.}$El exponente aquí es igual a${\displaystyle 3\cdot 2^{27}+27,}$^{[ 3 ]} por lo tanto la base es igual a${\displaystyle n\cdot 2^{n}-1,}$un número de Woodall con${\displaystyle n=3\cdot 2^{27}.}$

Por otro ejemplo,${\displaystyle G_{19}}$aumenta mucho más rápidamente y comienza de la siguiente manera:

A pesar de este rápido crecimiento, el teorema de Goodstein establece que toda secuencia de Goodstein termina finalmente en 0, independientemente del valor inicial.

El teorema de Goodstein se puede demostrar (utilizando técnicas ajenas a la aritmética de Peano, véase más abajo) de la siguiente manera: Dada una secuencia de Goodstein${\displaystyle G_{m}}$, construimos una secuencia paralela${\displaystyle P_{m}}$de números ordinales en forma normal de Cantor que es estrictamente decreciente y termina. Un error común de interpretación de esta demostración es creer que${\displaystyle G_{m}}$va a${\displaystyle 0}$porque está dominado por${\displaystyle P_{m}}$. En realidad, el hecho de que${\displaystyle P_{m}}$domina${\displaystyle G_{m}}$No desempeña ningún papel. Lo importante es:${\displaystyle G_{m}(k)}$existe si y solo si${\displaystyle P_{m}(k)}$existe (paralelismo) y comparación entre dos miembros de${\displaystyle G_{m}}$se conserva al comparar las entradas correspondientes de${\displaystyle P_{m}}$. ^{[ 4 ]} Entonces si${\displaystyle P_{m}}$termina, también lo hace${\displaystyle G_{m}}$. Por regresión infinita ,${\displaystyle G_{m}}$debe llegar${\displaystyle 0}$, lo que garantiza la rescisión.

Definimos una función${\displaystyle f=f(u,k)}$que calcula la base hereditaria${\displaystyle k}$representación de${\displaystyle u}$y luego reemplaza cada aparición de la base${\displaystyle k}$con el primer número ordinal infinito${\displaystyle \omega }$. Por ejemplo,${\displaystyle f(100,3)=f(3^{3^{1}+1}+2\cdot 3^{2}+1,3)=\omega ^{\omega ^{1}+1}+\omega ^{2}\cdot 2+1=\omega ^{\omega +1}+\omega ^{2}\cdot 2+1}$.

Cada término${\displaystyle P_{m}(n)}$de la secuencia${\displaystyle P_{m}}$entonces se define como${\displaystyle f(G_{m}(n),n+1)}$. Por ejemplo,${\displaystyle G_{3}(1)=3=2^{1}+2^{0}}$y${\displaystyle P_{3}(1)=f(2^{1}+2^{0},2)=\omega ^{1}+\omega ^{0}=\omega +1}$La suma, la multiplicación y la potenciación de números ordinales están bien definidas.

Afirmamos que${\displaystyle f(G_{m}(n),n+1)>f(G_{m}(n+1),n+2)}$:

Dejar${\displaystyle G'_{m}(n)}$ser${\displaystyle G_{m}(n)}$después de aplicar la primera operación de cambio de base para generar el siguiente elemento de la secuencia de Goodstein, pero antes de la segunda operación de resta 1 en esta generación. Observe que${\displaystyle G_{m}(n+1)=G'_{m}(n)-1}$.

Entonces${\displaystyle f(G_{m}(n),n+1)=f(G'_{m}(n),n+2)}$. ^{[ Nota 1 ]} Ahora aplicamos la operación de resta 1 , y${\displaystyle f(G'_{m}(n),n+2)>f(G_{m}(n+1),n+2)}$, como${\displaystyle G'_{m}(n)=G_{m}(n+1)+1}$. ^{[ Nota 2 ]}

Por ejemplo,${\displaystyle G_{4}(1)=2^{2}}$y${\displaystyle G_{4}(2)=2\cdot 3^{2}+2\cdot 3+2}$, entonces${\displaystyle f(2^{2},2)=\omega ^{\omega }}$y${\displaystyle f(2\cdot 3^{2}+2\cdot 3+2,3)=\omega ^{2}\cdot 2+\omega \cdot 2+2}$, que es estrictamente menor. Tenga en cuenta que para calcular${\displaystyle f(G_{m}(n),n+1)}$, primero necesitamos escribir ${\displaystyle G_{m}(n)}$de base hereditaria${\displaystyle n+1}$notación, como por ejemplo la expresión${\displaystyle \omega ^{\omega }-1}$no es un ordinal.

Por lo tanto, la secuencia${\displaystyle P_{m}}$es estrictamente decreciente. Como el orden estándar < en los ordinales está bien fundamentado , no puede existir una secuencia estrictamente decreciente infinita, o equivalentemente, toda secuencia estrictamente decreciente de ordinales termina (y no puede ser infinita). Pero${\displaystyle P_{m}(n)}$se calcula directamente a partir de${\displaystyle G_{m}(n)}$. Por lo tanto, la secuencia${\displaystyle G_{m}}$debe terminar también, lo que significa que debe llegar${\displaystyle 0}$.

Si bien esta demostración del teorema de Goodstein es bastante sencilla, el teorema de Kirby-París ^{[ 1 ]} , que demuestra que el teorema de Goodstein no es un teorema de la aritmética de Peano, es técnico y considerablemente más difícil. Utiliza modelos no estándar numerables de la aritmética de Peano.

La función Goodstein ,${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} }$, se define de tal manera que${\displaystyle {\mathcal {G}}(n)}$es la longitud de la secuencia de Goodstein que comienza con n . (Esta es una función total ya que cada secuencia de Goodstein termina). La tasa de crecimiento extremadamente alta de${\displaystyle {\mathcal {G}}}$puede calibrarse relacionándolo con varias jerarquías estándar indexadas ordinalmente de funciones, como las funciones${\displaystyle H_{\alpha }}$en la jerarquía de Hardy y las funciones${\displaystyle f_{\alpha }}$en la jerarquía en rápido crecimiento de Löb y Wainer:

• Kirby y Paris (1982) demostraron que

${\displaystyle {\mathcal {G}}}$tiene aproximadamente la misma tasa de crecimiento que${\displaystyle H_{\epsilon _{0}}}$(que es lo mismo que el de${\displaystyle f_{\epsilon _{0}}}$); más precisamente,${\displaystyle {\mathcal {G}}}$domina${\displaystyle H_{\alpha }}$por cada${\displaystyle \alpha <\epsilon _{0}}$, y${\displaystyle H_{\epsilon _{0}}}$domina${\displaystyle {\mathcal {G}}\,\!.}$

(Para cualesquiera dos funciones${\displaystyle f,g:\mathbb {N} \to \mathbb {N} }$,${\displaystyle f}$Se dice que domina${\displaystyle g}$si${\displaystyle f(n)>g(n)}$para todos suficientemente grandes${\displaystyle n}$.)

• Cichon (1983) demostró que

${\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}$

dónde${\displaystyle R_{2}^{\omega }(n)}$es el resultado de poner n en notación hereditaria de base 2 y luego reemplazar todos los 2 con ω (como se hizo en la demostración del teorema de Goodstein).

• Caicedo (2007) demostró que si${\displaystyle n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}}$con${\displaystyle m_{1}>m_{2}>\cdots >m_{k},}$entonces

${\displaystyle {\mathcal {G}}(n)=f_{R_{2}^{\omega }(m_{1})}(f_{R_{2}^{\omega }(m_{2})}(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2}$.

Algunos ejemplos:

(Para la función de Ackermann y los límites del número de Graham, véase jerarquía de rápido crecimiento §  Funciones en jerarquías de rápido crecimiento ).

El teorema de Goodstein permite construir una función computable total que la aritmética de Peano no puede demostrar que sea total. La secuencia de Goodstein de un número puede ser enumerada eficazmente por una máquina de Turing ; por lo tanto, la función que asigna a n el número de pasos necesarios para que la secuencia de Goodstein de n termine es computable por una máquina de Turing específica. Esta máquina simplemente enumera la secuencia de Goodstein de n y, cuando la secuencia llega a 0, devuelve su longitud. Dado que toda secuencia de Goodstein termina eventualmente, esta función es total. Sin embargo, como la aritmética de Peano no demuestra que toda secuencia de Goodstein termine, tampoco demuestra que esta máquina de Turing calcule una función total.

• Modelo aritmético no estándar
• Jerarquía de rápido crecimiento
• Teorema de Paris-Harrington
• Teorema de Kanamori-McAloon
• Teorema del árbol de Kruskal
• Rompecabezas de cuerdas que queman

• Kirby, L.; Paris, J. (1982). "Resultados de independencia accesibles para la aritmética de Peano" (PDF) . Boletín de la Sociedad Matemática de Londres . 14 (4): 285. CiteSeerX 10.1.1.107.3303 . doi : 10.1112/blms/14.4.285 . 
• Rathjen, Michael (2014). "Goodstein revisitado". arXiv : 1405.4484 [ matemáticas.LO ].
• Goodstein, R. (1944). "Sobre el teorema ordinal restringido". Journal of Symbolic Logic . 9 (2): 33– 41. doi : 10.2307/2268019 . JSTOR 2268019. S2CID 235597 .  
• Cichon, E. (1983). "Una breve demostración de dos resultados de independencia descubiertos recientemente utilizando métodos teóricos recursivos" . Actas de la Sociedad Matemática Americana . 87 (4): 704– 706. doi : 10.2307/2043364 . JSTOR 2043364 . 
• Caicedo, A. (2007). "Función de Goodstein" (PDF) . Revista Colombiana de Matemáticas . 41 (2): 381– 391.

• Weisstein, Eric W. "Secuencia de Goodstein" . MundoMatemático .
• Algunos elementos de una demostración de que el teorema de Goodstein no es un teorema de PA, de una tesis de pregrado de Justin T Miller.
• Clasificación de modelos no estándar de la aritmética de Peano mediante el teorema de Goodstein - Tesis de Dan Kaplan, Biblioteca del Franklan and Marshall College
• Definición de secuencias de Goodstein en Haskell y el cálculo lambda
• Secuencias de Goodstein: El poder de un desvío a través del infinito : una buena exposición con ilustraciones de las secuencias de Goodstein y el juego de la hidra.
• Calculadora Goodstein archivada el 4 de febrero de 2017 en Wayback Machine.