Teorema de Goodstein

Teorema sobre los números naturales

En lógica matemática , el teorema de Goodstein es un enunciado sobre los números naturales , demostrado por Reuben Goodstein en 1944, que establece que toda secuencia de Goodstein (como se define a continuación) termina eventualmente en 0. Laurence Kirby y Jeff Paris ^[1] demostraron que 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 un enunciado verdadero 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 prueba directa de Gerhard Gentzen de 1943 de la imposibilidad de demostrar la ε 0 -inducción en la aritmética de Peano. El teorema de Paris-Harrington dio otro ejemplo.

Kirby y Paris introdujeron un juego de hidra basado en la teoría de grafos con un comportamiento similar al de las secuencias de Goodstein: la "hidra" (nombrada por la mitológica Hidra de Lerna de múltiples cabezas ) es un árbol con raíces, y un movimiento 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 de acuerdo con ciertas reglas. Kirby y Paris demostraron que la hidra eventualmente será asesinada, independientemente de la estrategia que use Hércules para cortarle las cabezas, aunque esto puede llevar mucho tiempo. Al igual que para las secuencias de Goodstein, Kirby y Paris demostraron que no se puede demostrar solo con la aritmética de Peano. ^[1]

Base hereditaria-nortenotación

Las sucesiones de Goodstein se definen en términos de un concepto llamado "notación hereditaria en base n ". Esta notación es muy similar a la notación posicional en base n habitual , pero la notación habitual no es suficiente para los fines del teorema de Goodstein.

Para lograr la notación base n ordinaria , 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, para lograr la notación de base 2 , se escribe

${\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}$

Por lo tanto, la representación en base 2 de 35 es 100011, lo que significa 2 ⁵ + 2 + 1 . De manera similar, 100 representado en base 3 es 10201:

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

Tenga en cuenta que los exponentes en sí no están escritos en notación de base n . Por ejemplo, las expresiones anteriores incluyen 2 ⁵ y 3 ⁴ , y 5 > 2, 4 > 3.

Para convertir una notación en base n (que es un paso para lograr la representación en base n ) a una notación en base n hereditaria, primero reescribe todos los exponentes como una suma de potencias de n (con la limitación en los coeficientes 0 ≤ a _i < n ). Luego reescribe cualquier exponente dentro de los exponentes en notación en base n (con la misma limitación en los coeficientes), y continúa 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, mientras que 35 en notación base 2 ordinaria es 2 ⁵ + 2 + 1 , se escribe en notación base 2 hereditaria como

${\displaystyle 35=2^{2^{2^{1}}+1}+2^{1}+1,}$

utilizando el hecho de que 5 = 2 ^{2 1} + 1. De manera similar, 100 en notación hereditaria de base 3 es

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

Secuencias de Goodstein

La sucesión de Goodstein G ( m ) de un número m es una sucesión de números naturales. El primer elemento de la sucesión G ( m ) es el propio m . Para obtener el segundo, G ( m )(2), escribe m en notación hereditaria de base 2, cambia todos los 2 por 3 y luego resta 1 al resultado. En general, el ( n  + 1)-ésimo término, G ( m )( n  + 1) , de la sucesión de Goodstein de m es el siguiente:

• Tome la representación hereditaria base n  + 1 de G ( m )( n ).
• Reemplace cada aparición de la base n  + 1 con n  + 2 .
• Restar uno. (Tenga en cuenta que el siguiente término depende tanto del término anterior como del índice n ).
• Continúe hasta que el resultado sea cero, momento en el que la secuencia termina.

Las primeras secuencias de Goodstein terminan rápidamente. Por ejemplo, G (3) termina en el sexto paso:

Las secuencias de Goodstein posteriores aumentan en un número muy grande de pasos. Por ejemplo, G (4) OEIS : A056193 comienza de la siguiente manera:

Los elementos de G (4) continúan aumentando durante un tiempo, pero en la base , alcanzan el máximo de , permanecen allí durante los siguientes pasos y luego comienzan su descenso. ${\displaystyle 3\cdot 2^{402\,653\,209}}$ ${\displaystyle 3\cdot 2^{402\,653\,210}-1}$ ${\displaystyle 3\cdot 2^{402\,653\,209}}$

Sin embargo, incluso G (4) no da una buena idea de cuán rápido pueden aumentar los elementos de una secuencia de Goodstein. 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 eventualmente termina en 0, sin importar cuál sea el valor inicial.

Demostración del teorema de Goodstein

El teorema de Goodstein se puede demostrar (usando técnicas fuera de la aritmética de Peano, ver abajo) de la siguiente manera: Dada una secuencia de Goodstein G ( m ), construimos una secuencia paralela P ( m ) de números ordinales en forma normal de Cantor que es estrictamente decreciente y termina. Un malentendido común de esta prueba es creer que G ( m ) tiende a 0 porque está dominada por P ( m ). En realidad, el hecho de que P ( m ) domine a G ( m ) no juega ningún papel en absoluto. El punto importante es: G ( m )( k ) existe si y solo si P ( m )( k ) existe (paralelismo), y la comparación entre dos miembros de G ( m ) se conserva cuando se comparan las entradas correspondientes de P ( m ). ^[2] Entonces, si P ( m ) termina, también lo hace G ( m ). Por regresión infinita , G ( m ) debe llegar a 0, lo que garantiza la terminación.

Definimos una función que calcula la representación hereditaria de la base k de u y luego reemplaza cada ocurrencia de la base k con el primer número ordinal infinito ω. Por ejemplo, . ${\displaystyle f=f(u,k)}$ ${\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 P ( m )( n ) de la secuencia P ( m ) se define entonces como f ( G ( m )( n ), n+1 ). Por ejemplo, G (3)(1) = 3 = 2 ¹ + 2 ⁰ y P (3)(1) = f (2 ¹ + 2 ⁰ ,2) = ω ¹ + ω ⁰ = ω + 1 . La suma, la multiplicación y la exponenciació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)}$

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

Entonces . Ahora aplicamos la operación menos 1 , y , como . Por ejemplo, y , entonces y , que es estrictamente menor. Nótese que para calcular f(G(m)(n),n+1) , primero necesitamos escribir G ( m )( n ) en notación de base hereditaria n +1 , como por ejemplo la expresión no es un ordinal. ${\displaystyle f(G(m)(n),n+1)=f(G'(m)(n),n+2)}$ ${\displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)}$ ${\displaystyle G'(m)(n)=G(m)(n+1)+1}$ ${\displaystyle G(4)(1)=2^{2}}$ ${\displaystyle G(4)(2)=2\cdot 3^{2}+2\cdot 3+2}$ ${\displaystyle f(2^{2},2)=\omega ^{\omega }}$ ${\displaystyle f(2\cdot 3^{2}+2\cdot 3+2,3)=\omega ^{2}\cdot 2+\omega \cdot 2+2}$ ${\displaystyle \omega ^{\omega }-1}$

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

Si bien esta demostración del teorema de Goodstein es bastante sencilla, el teorema de Kirby-Paris ^[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.

Teorema de Goodstein extendido

La prueba anterior sigue funcionando si se cambia la definición de la sucesión de Goodstein de modo que la operación de cambio de base reemplace cada aparición de la base b por b + 2 en lugar de b + 1. De manera más general, sea b ₁ , b ₂ , b ₃ , ... cualquier sucesión no decreciente de números enteros con b ₁ ≥ 2 . Entonces, sea el ( n + 1)-ésimo término G ( m )( n + 1) de la sucesión extendida de Goodstein de m como sigue:

• Tome la representación de base hereditaria b _n de G ( m )( n ).
• Reemplace cada aparición de la base b _n con b _{n +1} .
• Restar uno.

Una modificación simple de la prueba anterior muestra que esta secuencia todavía termina. Por ejemplo, si b _n = 4 y si b _{n +1} = 9 , entonces , por lo tanto el ordinal es estrictamente mayor que el ordinal ${\displaystyle f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)}$ ${\displaystyle f(3\cdot 4^{4^{4}}+4,4)}$ ${\displaystyle f{\big (}(3\cdot 9^{9^{9}}+9)-1,9{\big )}.}$

La versión extendida es de hecho la considerada en el artículo original de Goodstein, ^[3] donde Goodstein demostró que es equivalente al teorema ordinal restringido (es decir, la afirmación de que la inducción transfinita por debajo de ε 0 es válida), y dio una prueba finitista para el caso donde (equivalente a la inducción transfinita hasta ). ${\displaystyle m\leq b_{1}^{b_{1}^{b_{1}}}}$ ${\displaystyle \omega ^{\omega ^{\omega }}}$

El teorema de Goodstein extendido sin ninguna restricción sobre la secuencia b _n no es formalizable en aritmética de Peano (PA), ya que una secuencia infinita arbitraria de este tipo no puede representarse en PA. Esto parece ser lo que impidió a Goodstein afirmar en 1944 que el teorema de Goodstein extendido es indemostrable en PA debido al segundo teorema de incompletitud de Gödel y la prueba de Gentzen de la consistencia de PA usando ε ₀ -inducción. ^[4] Sin embargo, la inspección de la prueba de Gentzen muestra que solo necesita el hecho de que no existe una secuencia infinita estrictamente decreciente recursiva primitiva de ordinales, por lo que limitar b _n a secuencias recursivas primitivas habría permitido a Goodstein demostrar un resultado de indemostrabilidad. ^[4] Además, con la técnica relativamente elemental de la jerarquía de Grzegorczyk , se puede demostrar que toda secuencia infinita estrictamente decreciente recursiva primitiva de ordinales se puede "ralentizar" de modo que se pueda transformar en una secuencia de Goodstein donde b _n = n + 1 , dando así una prueba alternativa al mismo resultado que Kirby y Paris demostraron. ^[4]

Longitud de la secuencia en función del valor inicial

La función de Goodstein , , se define de modo que sea 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 se puede calibrar relacionándola con varias jerarquías de funciones indexadas ordinalmente estándar, como las funciones en la jerarquía de Hardy y las funciones en la jerarquía de rápido crecimiento de Löb y Wainer: ${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle {\mathcal {G}}(n)}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle H_{\alpha }}$ ${\displaystyle f_{\alpha }}$

• Kirby y Paris (1982) demostraron que

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

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

• Cichon (1983) demostró que

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

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

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

${\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 numéricos de Graham, consulte jerarquía de rápido crecimiento#Funciones en jerarquías de rápido crecimiento ).

Aplicación a funciones computables

El teorema de Goodstein se puede utilizar para 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 se puede enumerar de manera efectiva mediante una máquina de Turing ; por lo tanto, la función que asigna n al número de pasos necesarios para que la secuencia de Goodstein de n termine es computable mediante una máquina de Turing particular. Esta máquina simplemente enumera la secuencia de Goodstein de n y, cuando la secuencia llega a 0 , devuelve la longitud de la secuencia. Debido a que cada secuencia de Goodstein eventualmente termina, esta función es total. Pero debido a que la aritmética de Peano no prueba que cada secuencia de Goodstein termine, la aritmética de Peano no prueba que esta máquina de Turing calcule una función total.

Véase también

• Modelo no estándar de aritmética
• Jerarquía de rápido crecimiento
• Teorema de París-Harrington
• Teorema de Kanamori-McAloon
• Teorema del árbol de Kruskal

Referencias

1. Kirby y París 1982.
2. Rathjen 2014, lema 2.2.
3. García-García 1944.
4. abcRathjen 2014.

Bibliografía

• 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 prueba de dos resultados de independencia recientemente descubiertos utilizando métodos teóricos recursivos", Actas de la American Mathematical Society , 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.

Enlaces externos

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