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 [1] demostraron que es indemostrable en aritmética de Peano (pero puede demostrarse en sistemas más sólidos, 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 la consistencia de la aritmética de Peano en sí ( el segundo teorema de incompletitud de Gödel ) y el orden de Gerhard Gentzen.Prueba directa de 1943 de la imposibilidad de demostrar [ se necesita una explicación adicional ] de la inducción de ε 0 en la aritmética de Peano. El teorema de París-Harrington fue un ejemplo posterior.
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 use 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. [1]
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 :
donde cada coeficiente a i satisface 0 ≤ a i < n , y a k ≠ 0 . Por ejemplo, en base 2,
Por lo tanto, la representación en base 2 de 35 es 100011, lo que significa 2 5 + 2 + 1 . De manera similar, 100 representado en base 3 es 10201:
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 5 y 3 4 , 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 5 + 2 + 1 , se escribe en la notación de base 2 hereditaria como
usando el hecho de que 5 = 2 2 + 1. De manera similar, 100 en notación hereditaria de base 3 es
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 | 3 | Escribe 3 en notación base 2 | |
3 | 3 | Cambie el 2 a 3, luego reste 1 | |
4 | 3 | Cambie el 3 a un 4, luego reste 1. Ahora no quedan más 4 | |
5 | 2 | No quedan 4 para cambiar a 5. Solo resta 1 | |
6 | 1 | No quedan 5 para cambiar a 6. Solo resta 1 | |
7 | 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 | 4 | |
3 | 26 | |
4 | 41 | |
5 | 60 | |
6 | 83 | |
7 | 109 | |
11 | 253 | |
12 | 299 | |
24 | 1151 | |
Los elementos de G (4) continúan aumentando por un tiempo, pero en la base, alcanzan el máximo de , quédate ahí para el próximo pasos, y luego comenzar su primer descenso.
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 mayores que 4. [ cita requerida ] )
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 |
---|---|
19 | |
7 625 597 484 990 | |
| |
| |
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 en base k de u y luego reemplaza cada aparición de la base k con el primer número ordinal infinito ω. Por ejemplo,.
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 1 + 2 0 y P (3) (1) = f (2 1 + 2 0 , 2) = ω 1 + ω 0 = ω + 1 . La suma, multiplicación y exponenciación de números ordinales están bien definidas.
Afirmamos que :
Dejar 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 menos 1 en esta generación. Observa eso.
Entonces claramente, . Ahora aplicamos la operación menos 1 , y, como . Por ejemplo, y , entonces y , 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 , como por ejemplo la expresión o no tiene sentido o es igual a .
Por tanto, la secuencia P ( m ) es estrictamente decreciente. Como el orden estándar
Si bien esta demostración del teorema de Goodstein es bastante fácil, el teorema de Kirby-Paris , [1] 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 1 , b 2 , b 3 ,… 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, de ahí el ordinal es estrictamente mayor que el ordinal
Longitud de la secuencia en función del valor inicial
La función 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 se puede calibrar relacionándolo con varias jerarquías de funciones indexadas ordinales estándar, como las funciones en la jerarquía de Hardy , y las funcionesen la jerarquía de rápido crecimiento de Löb y Wainer:
- Kirby y Paris (1982) demostraron que
- tiene aproximadamente la misma tasa de crecimiento que (que es el mismo que el de ); más precisamente, domina para cada , y domina
- (Para dos funciones cualesquiera , se dice que domina Si para todo lo suficientemente grande .)
- Cichon (1983) demostró que
- dónde 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) mostró que si con luego
- .
Algunos ejemplos:
norte | |||||
---|---|---|---|---|---|
1 | 2 | ||||
2 | 4 | ||||
3 | 6 | ||||
4 | 3 · 2 402653211 - 2 ≈ 6.895080803 × 10 121210694 | ||||
5 | > A (4,4)> | ||||
6 | > A (6,6) | ||||
7 | > A (8,8) | ||||
8 | > A 3 (3,3) = A ( A (61, 61), A (61, 61)) | ||||
12 | > f ω + 1 (64)> Número de Graham | ||||
19 |
(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
Referencias
- ^ a b c Kirby, L .; París, J. (1982). "Resultados de independencia accesible para la aritmética de Peano" (PDF) . Boletín de la London Mathematical Society . 14 (4): 285. CiteSeerX 10.1.1.107.3303 . doi : 10.1112 / blms / 14.4.285 .
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