Teorema de Goodstein - Goodstein's theorem

En lógica matemática , el teorema de Goodstein es un enunciado sobre los números naturales , probado por Reuben Goodstein en 1944, que establece que cada secuencia de Goodstein eventualmente termina en 0. Kirby y Paris demostraron que es indemostrable en aritmética de Peano (pero se puede probar en sistemas más fuertes, como la aritmética de segundo orden ). Este fue el tercer ejemplo de un enunciado verdadero que no se puede demostrar 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 inducción ε ₀ en la aritmética de Peano. El teorema de París-Harrington dio otro ejemplo.

Laurence Kirby y Jeff Paris introdujeron un juego de hidra de teoría gráfica con un comportamiento similar al de las secuencias de Goodstein: la "Hydra" (llamada así por la mitológica Hydra de Lerna con múltiples cabezas ) es un árbol enraizado, y un movimiento consiste en cortar uno de sus "cabezas" (una rama del árbol), a las 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 utilice Hércules para cortarle la cabeza, aunque esto puede llevar mucho tiempo. Al igual que para las secuencias de Goodstein, Kirby y Paris demostraron que no se puede probar solo con la aritmética de Peano.

Notación base- n hereditaria

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

En notación de 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} norte ^ {k} + a_ {k-1} norte ^ {k-1} + \ cdots + a_ {0},}$

donde cada coeficiente a _i satisface 0 ≤ a _i < n , y a _k ≠ 0 . Por ejemplo, en base 2,

${\ 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í mismos 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 base- n representación a hereditaria base- n notación, primero reescribir todos los exponentes en base- n notación. Luego reescriba cualquier exponente dentro de los exponentes y continúe de esta manera hasta que todos los números que aparecen en la expresión (excepto las bases mismas) se hayan convertido a la notación de base n .

Por ejemplo, mientras que 35 en la notación de base 2 ordinaria es 2 ⁵ + 2 + 1 , se escribe en la notación de base 2 hereditaria como

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

usando el hecho de que 5 = 2 ² + 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 secuencia de Goodstein G ( m ) de un número m es una secuencia de números naturales. El primer elemento de la secuencia G ( m ) es el propio m . Para obtener el segundo, G ( m ) (2), escriba m en notación hereditaria de base 2, cambie todos los 2 a 3 y luego reste 1 del resultado. En general, el término ( n  + 1) -st , G ( m ) ( n  + 1) , de la secuencia de Goodstein de m es el siguiente:

• Tome la representación hereditaria en base- n  + 1 de G ( m ) ( n ).
• Reemplace cada aparición de la base- n  + 1 con n  + 2 .
• Resta 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 termina la secuencia.

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

Base	Notación hereditaria	Valor	Notas
2	${\ Displaystyle 2 ^ {1} +1}$	3	Escribe 3 en notación base 2
3	${\ Displaystyle 3 ^ {1} + 1-1 = 3 ^ {1}}$	3	Cambie el 2 a 3, luego reste 1
4	${\ Displaystyle 4 ^ {1} -1 = 3}$	3	Cambie el 3 a un 4, luego reste 1. Ahora no quedan más 4
5	${\ Displaystyle 3-1 = 2}$	2	No quedan 4 para cambiar a 5. Solo resta 1
6	${\ Displaystyle 2-1 = 1}$	1	No quedan 5 para cambiar a 6. Solo resta 1
7	${\ Displaystyle 1-1 = 0}$	0	No quedan 6 para cambiar a 7. Solo resta 1

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

Base	Notación hereditaria	Valor
2	${\ Displaystyle 2 ^ {2 ^ {1}}}$	4
3	${\ Displaystyle 3 ^ {3 ^ {1}} - 1 = 2 \ cdot 3 ^ {2} +2 \ cdot 3 + 2}$	26
4	${\ Displaystyle 2 \ cdot 4 ^ {2} +2 \ cdot 4 + 1}$	41
5	${\ Displaystyle 2 \ cdot 5 ^ {2} +2 \ cdot 5}$	60
6	${\ Displaystyle 2 \ cdot 6 ^ {2} +2 \ cdot 6-1 = 2 \ cdot 6 ^ {2} + 6 + 5}$	83
7	${\ Displaystyle 2 \ cdot 7 ^ {2} + 7 + 4}$	109
${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$
11	${\ Displaystyle 2 \ cdot 11 ^ {2} +11}$	253
12	${\ Displaystyle 2 \ cdot 12 ^ {2} + 12-1 = 2 \ cdot 12 ^ {2} +11}$	299
${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$
24	${\ Displaystyle 2 \ cdot 24 ^ {2} -1 = 24 ^ {2} +23 \ cdot 24 + 23}$	1151
${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$
${\ Displaystyle B = 3 \ cdot 2 ^ {402 \, 653 \, 209} -1}$	${\ Displaystyle 2 \ cdot B ^ {1}}$	${\ Displaystyle 3 \ cdot 2 ^ {402 \, 653 \, 210} -2}$
${\ Displaystyle B = 3 \ cdot 2 ^ {402 \, 653 \, 209}}$	${\ Displaystyle 2 \ cdot B ^ {1} -1 = B ^ {1} + (B-1)}$	${\ Displaystyle 3 \ cdot 2 ^ {402 \, 653 \, 210} -1}$
${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$

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

El valor 0 se alcanza en la base . (Curiosamente, este es un número de Woodall :. Este también es el caso con todas las demás bases finales para valores iniciales superiores a 4). ${\ Displaystyle 3 \ cdot 2 ^ {402 \, 653 \, 211} -1}$${\ Displaystyle 3 \ cdot 2 ^ {402 \, 653 \, 211} -1 = 402 \, 653 \, 184 \ cdot 2 ^ {402 \, 653 \, 184} -1}$

Sin embargo, incluso G (4) no da una buena idea de qué tan 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:

Notación hereditaria	Valor
${\ Displaystyle 2 ^ {2 ^ {2}} + 2 + 1}$	19
${\ Displaystyle 3 ^ {3 ^ {3}} + 3}$	7 625 597 484 990
${\ Displaystyle 4 ^ {4 ^ {4}} + 3}$	${\ Displaystyle \ aproximadamente 1,3 \ veces 10 ^ {154}}$
${\ Displaystyle 5 ^ {5 ^ {5}} + 2}$	${\ Displaystyle \ approx 1.8 \ times 10 ^ {2 \, 184}}$
${\ Displaystyle 6 ^ {6 ^ {6}} + 1}$	${\ Displaystyle \ approx 2.6 \ times 10 ^ {36 \, 305}}$
${\ Displaystyle 7 ^ {7 ^ {7}}}$	${\ Displaystyle \ approx 3.8 \ times 10 ^ {695 \, 974}}$
${\ Displaystyle 8 ^ {8 ^ {8}} - 1 = 7 \ cdot 8 ^ {7 \ cdot 8 ^ {7} +7 \ cdot 8 ^ {6} +7 \ cdot 8 ^ {5} +7 \ cdot 8 ^ {4} +7 \ cdot 8 ^ {3} +7 \ cdot 8 ^ {2} +7 \ cdot 8 + 7}}$ ${\ displaystyle +7 \ cdot 8 ^ {7 \ cdot 8 ^ {7} +7 \ cdot 8 ^ {6} +7 \ cdot 8 ^ {5} +7 \ cdot 8 ^ {4} +7 \ cdot 8 ^ {3} +7 \ cdot 8 ^ {2} +7 \ cdot 8 + 6} + \ cdots}$ ${\ Displaystyle +7 \ cdot 8 ^ {8 + 2} +7 \ cdot 8 ^ {8 + 1} +7 \ cdot 8 ^ {8}}$ ${\ Displaystyle +7 \ cdot 8 ^ {7} +7 \ cdot 8 ^ {6} +7 \ cdot 8 ^ {5} +7 \ cdot 8 ^ {4}}$ ${\ Displaystyle +7 \ cdot 8 ^ {3} +7 \ cdot 8 ^ {2} +7 \ cdot 8 + 7}$	${\ Displaystyle \ aproximadamente 6 \ times 10 ^ {15 \, 151 \, 335}}$
${\ Displaystyle 7 \ cdot 9 ^ {7 \ cdot 9 ^ {7} +7 \ cdot 9 ^ {6} +7 \ cdot 9 ^ {5} +7 \ cdot 9 ^ {4} +7 \ cdot 9 ^ {3} +7 \ cdot 9 ^ {2} +7 \ cdot 9 + 7}}$ ${\ displaystyle +7 \ cdot 9 ^ {7 \ cdot 9 ^ {7} +7 \ cdot 9 ^ {6} +7 \ cdot 9 ^ {5} +7 \ cdot 9 ^ {4} +7 \ cdot 9 ^ {3} +7 \ cdot 9 ^ {2} +7 \ cdot 9 + 6} + \ cdots}$ ${\ Displaystyle +7 \ cdot 9 ^ {9 + 2} +7 \ cdot 9 ^ {9 + 1} +7 \ cdot 9 ^ {9}}$ ${\ Displaystyle +7 \ cdot 9 ^ {7} +7 \ cdot 9 ^ {6} +7 \ cdot 9 ^ {5} +7 \ cdot 9 ^ {4}}$ ${\ Displaystyle +7 \ cdot 9 ^ {3} +7 \ cdot 9 ^ {2} +7 \ cdot 9 + 6}$	${\ Displaystyle \ approx 5.6 \ times 10 ^ {35 \, 942 \, 384}}$
${\ Displaystyle \ vdots}$	${\ Displaystyle \ vdots}$

A pesar de este rápido crecimiento, el teorema de Goodstein establece que cada secuencia de Goodstein eventualmente termina en 0 , sin importar cuál sea el valor inicial.

Prueba del teorema de Goodstein

El teorema de Goodstein se puede demostrar (usando técnicas fuera de la aritmética de Peano, ver más abajo) de la siguiente manera: Dada una secuencia de Goodstein G ( m ), construimos una secuencia paralela P ( m ) de números ordinales que es estrictamente decreciente y termina. Entonces G ( m ) debe terminar también, y puede terminar sólo cuando va a 0. Un malentendido común de esta prueba es creer que G ( m ) va a 0 porque está dominado 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). Entonces, si P ( m ) termina, también lo hace G ( m ). Y G ( m ) puede terminar solo cuando se trata de 0.

Definimos una función que calcula la representación hereditaria de base k de u y luego reemplaza cada aparición 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 } +2 \ omega ^ {2} + 1 = \ omega ^ {\ omega +1} +2 \ omega ^ {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, multiplicación y 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)}$

Dejado ser G ( m ) ( n ) después de aplicar la primera, la base de cambio de operación en la generación de la siguiente elemento de la secuencia Goodstein, pero antes de la segunda menos 1 operación en esta generación. Observa eso . ${\ Displaystyle G '(m) (n)}$${\ Displaystyle G (m) (n + 1) = G '(m) (n) -1}$

Entonces es claro, . Ahora aplicamos la operación menos 1 y , como . Por ejemplo, and , so and , que es estrictamente más pequeño. Tenga en cuenta que para calcular f (G (m) (n), n + 1) , primero debemos escribir G ( m ) ( n ) en notación de base hereditaria n +1 , ya que, por ejemplo, la expresión no tiene sentido o es igual a . ${\ Displaystyle f (G (m) (n), norte + 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) = 2 \ omega ^ {2} +2 \ omega +2}$${\ Displaystyle \ omega ^ {\ omega} -1}$${\ Displaystyle \ omega ^ {\ omega}}$

Por 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 de manera equivalente, 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 fácil, el teorema de Kirby-Paris , que muestra 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 contables no estándar de aritmética de Peano.

Teorema de Goodstein extendido

Suponga que la definición de la secuencia de Goodstein se cambia de modo que en lugar de reemplazar cada aparición de la base b con b +1 , la reemplaza con b +2 . ¿Terminaría aún la secuencia? De manera más general, sean b ₁ , b ₂ , b ₃ ,… cualquier secuencia de números enteros. Entonces, deje que el n + 1er término G ( m ) ( n +1) de la secuencia de Goodstein extendida de m sea ​​como sigue: tome la base hereditaria b _n representación de G ( m ) ( n ), y reemplace cada ocurrencia de la base b _n con b _{n +1} y luego restar uno. La afirmación es que esta secuencia aún termina. La prueba extendida define P ( m ) ( n ) = f ( G ( m ) ( n ), n ) de la siguiente manera: tome la base hereditaria b _n representación de G ( m ) ( n ), y reemplace cada ocurrencia de la base b _n con el primer número ordinal infinito ω. La operación de cambio de base de la secuencia de Goodstein al pasar de G ( m ) ( n ) a G ( m ) ( n +1) todavía no cambia el valor de f . Por ejemplo, si b _n = 4 y si b _{n +1} = 9 , entonces , 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 ((3 \ cdot 9 ^ {9 ^ {9}} + 9) -1,9).}$

Longitud de la secuencia en función del valor inicial

La función de Goodstein , , se define de tal manera que 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 extrema de puede calibrarse relacionándola con varias jerarquías de funciones indexadas ordinales estándar, como las funciones en la jerarquía de Hardy y las funciones en la jerarquía rápida. -creciente jerarquía 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 todos 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 es suficientemente grande ).${\ 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 hereditaria de base 2 y luego reemplazar todos los 2 con ω (como se hizo en la demostración 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:

norte			${\ Displaystyle {\ mathcal {G}} (n)}$
1	${\ Displaystyle 2 ^ {0}}$	${\ Displaystyle 2-1}$	${\ Displaystyle H _ {\ omega} (1) -1}$	${\ Displaystyle f_ {0} (3) -2}$	2
2	${\ Displaystyle 2 ^ {1}}$	${\ Displaystyle 2 ^ {1} + 1-1}$	${\ Displaystyle H _ {\ omega +1} (1) -1}$	${\ Displaystyle f_ {1} (3) -2}$	4
3	${\ Displaystyle 2 ^ {1} + 2 ^ {0}}$	${\ Displaystyle 2 ^ {2} -1}$	${\ Displaystyle H _ {\ omega ^ {\ omega}} (1) -1}$	${\ Displaystyle f_ {1} (f_ {0} (3)) - 2}$	6
4	${\ Displaystyle 2 ^ {2}}$	${\ Displaystyle 2 ^ {2} + 1-1}$	${\ Displaystyle H _ {\ omega ^ {\ omega} +1} (1) -1}$	${\ displaystyle f _ {\ omega} (3) -2}$	3 · 2 402653211 - 2 ≈ 6.895080803 × 10 121210694
5	${\ Displaystyle 2 ^ {2} + 2 ^ {0}}$	${\ Displaystyle 2 ^ {2} + 2-1}$	${\ Displaystyle H _ {\ omega ^ {\ omega} + \ omega} (1) -1}$	${\ Displaystyle f _ {\ omega} (f_ {0} (3)) - 2}$	> A (4,4)> 10 10 10 19728
6	${\ Displaystyle 2 ^ {2} + 2 ^ {1}}$	${\ Displaystyle 2 ^ {2} + 2 + 1-1}$	${\ Displaystyle H _ {\ omega ^ {\ omega} + \ omega +1} (1) -1}$	${\ Displaystyle f _ {\ omega} (f_ {1} (3)) - 2}$	> A (6,6)
7	${\ Displaystyle 2 ^ {2} + 2 ^ {1} + 2 ^ {0}}$	${\ Displaystyle 2 ^ {2 + 1} -1}$	${\ Displaystyle H _ {\ omega ^ {\ omega +1}} (1) -1}$	${\ Displaystyle f _ {\ omega} (f_ {1} (f_ {0} (3))) - 2}$	> A (8,8)
8	${\ Displaystyle 2 ^ {2 + 1}}$	${\ Displaystyle 2 ^ {2 + 1} + 1-1}$	${\ Displaystyle H _ {\ omega ^ {\ omega +1} +1} (1) -1}$	${\ displaystyle f _ {\ omega +1} (3) -2}$	> A 3 (3,3) = A ( A (61, 61), A (61, 61))
${\ Displaystyle \ vdots}$
12	${\ Displaystyle 2 ^ {2 + 1} + 2 ^ {2}}$	${\ Displaystyle 2 ^ {2 + 1} + 2 ^ {2} + 1-1}$	${\ Displaystyle H _ {\ omega ^ {\ omega +1} + \ omega ^ {\ omega} +1} (1) -1}$	${\ Displaystyle f _ {\ omega +1} (f _ {\ omega} (3)) - 2}$	> f ω + 1 (64)> Número de Graham
${\ Displaystyle \ vdots}$
19	${\ Displaystyle 2 ^ {2 ^ {2}} + 2 ^ {1} + 2 ^ {0}}$	${\ Displaystyle 2 ^ {2 ^ {2}} + 2 ^ {2} -1}$	${\ Displaystyle H _ {\ omega ^ {\ omega ^ {\ omega}} + \ omega ^ {\ omega}} (1) -1}$	${\ Displaystyle f _ {\ omega ^ {\ omega}} (f_ {1} (f_ {0} (3))) - 2}$

(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 eficazmente mediante una máquina de Turing ; por tanto, la función que asigna n al número de pasos necesarios para que termine la secuencia de Goodstein de n es calculable por una máquina de Turing particular. Esta máquina simplemente enumera la secuencia de Goodstein de ny , 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 todas las secuencias de Goodstein terminen, la aritmética de Peano no prueba que esta máquina de Turing calcule una función total.

Ver 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

Bibliografía

• 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 prueba breve 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), "La función de Goodstein" (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381–391.

enlaces externos

• Weisstein, Eric W. "Secuencia de Goodstein" . MathWorld .
• 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 por el teorema de Goodstein - Tesis de Dan Kaplan, Franklan and Marshall College Library
• Definición de secuencias de Goodstein en Haskell y el cálculo lambda
• El juego Hydra implementado como un applet de Java
• Implementación de Javascript de una variante del juego Hydra
• Goodstein Sequences: The Power of a Detour via Infinity : buena exposición con ilustraciones de Goodstein Sequences y el juego de hidra.
• Calculadora Goodstein