En lógica matemática, el teorema de Goodstein es una proposición sobre los números naturales, demostrada por Reuben Goodstein en 1944, que establece que toda sucesión de Goodstein (tal como se define más adelante) termina en 0. Laurence Kirby y Jeff Paris demostraron en 1982 que el teorema de Goodstein es indemostrable a partir de la aritmética de Peano (pero puede demostrarse en sistemas más fuertes, como la aritmética de segundo orden o los axiomas de Zermelo-Fraenkel). Este fue el tercer ejemplo de una afirmación verdadera sobre los números naturales que resulta indemostrable en la aritmética de Peano, después de los ejemplos proporcionados por los teoremas de incompletitud de Gödel y la demostración directa de Gerhard Gentzen en 1943 sobre la indemostrabilidad de la inducción de ε0 en la aritmética de Peano. El principio de Paris-Harrington proporcionó otro ejemplo.
Kirby y Paris también introdujeron en teoría de grafos el juego de la hidra con un comportamiento similar al de las sucesiones de Goodstein: la Hidra (llamada así por la criatura mitológica de múltiples cabezas, la Hidra de Lerna) es un árbol, 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 derrotada, independientemente de la estrategia que Hércules utilice para cortarle las cabezas, aunque esto puede llevar mucho tiempo. Al igual que con las sucesiones de Goodstein, Kirby y Paris demostraron que no se puede probar solo con la aritmética de Peano.
Notación hereditaria en base n Las sucesiones de Goodstein se definen mediante un concepto llamado "notación hereditaria en base n". Esta notación es muy similar a la notación usual en la notación posicional de base n para los números naturales, pero la notación usual no es suficiente para los propósitos del teorema de Goodstein.
Para obtener 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:
donde cada coeficiente ai satisface y .
Por ejemplo, la notación base-3 de 100 es:
Aquí, los exponentes de n no se escriben en la notación de base n , como se ve en el caso 34, arriba.
Para convertir una notación en base n a una notación hereditaria en base n, primero deben reescribirse todos los exponentes como una suma de potencias de n (con la limitación en los coeficientes ). Luego, hay que reescribir cualquier exponente dentro de los exponentes nuevamente en notación en base n (con la misma limitación en los coeficientes), y continuar 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 en base 3 es:
Sucesiones de Goodstein La sucesión de Goodstein de un número es una sucesión de números naturales. El primer elemento de la sucesión, escrito como , es mismo. El segundo elemento, se obtiene escribiendo en notación hereditaria de base 2, cambiando todos los 2 por 3 y restando 1 al resultado. En general, el término de la sucesión de Goodstein se calcula de la siguiente manera:
Tomando la representación hereditaria de base () de Reemplazando cada ocurrencia de la base () por , y luego Restando uno.
depende tanto de como del índice . A veces, se escribe como .
Una sucesión de Goodstein termina cuando su elemento llega a 0. Las primeras sucesiones de Goodstein terminan rápidamente. Por ejemplo, termina en el sexto paso (la columna etiquetada como "Notación hereditaria" muestra cómo se calcula el valor):
Base Notación hereditarria Valor Cálculo2333Se obtiene escribiendo el último elemento (3) en notación hereditaria de base 2, reemplazando todos los 2 por 3 y luego restando 1.43Se obtiene escribiendo el último elemento (3) en notación hereditaria de base 3, reemplazando todos los 3 por 4 y luego restando 1.52Se obtiene restando 1 al último elemento (3), ya que no hay 4 que reemplazar.61Se obtiene restando 1 al último elemento (2), ya que no hay 5 que reemplazar.70Se obtiene restando 1 al último elemento (1), ya que no hay 6 que reemplazar.
Las sucesiones de Goodstein posteriores aumentan durante un gran número de pasos. Por ejemplo, comienza de la siguiente manera :
Base Notación hereditarria Valor2432644156068371091125312299241151
Los elementos de continúan aumentando durante un tiempo, pero en la base , alcanzan el máximo de , se mantienen allí durante los siguientes pasos y luego comienzan a descender de uno en uno, llegando a 0 cuando la base alcanza . El exponente aquí es igual a , por lo que la base es igual a el número de Woodall con
Por otro lado, aumenta mucho más rápidamente y comienza como a continuación:
Notación hereditarria Valor19
A pesar de este rápido crecimiento, el teorema de Goodstein establece que toda sucesión de Goodstein termina en 0, independientemente del valor inicial.
Demostración del teorema de Goodstein El teorema de Goodstein se puede demostrar (utilizando técnicas ajenas a la aritmética de Peano, véase más adelante) de la siguiente manera: dada una sucesión de Goodstein , se construye una sucesión paralela de números ordinales en la forma normal de Cantor que es estrictamente decreciente y termina. Un error común en esta demostración es creer que tiende a porque está dominada por . En realidad, el hecho de que domine a no influye en absoluto. Lo importante es que existe si y solo si existe (paralelismo), y la comparación entre dos miembros de se conserva al comparar las entradas correspondientes de . Entonces, si termina, también lo hace . Por regresión infinita, debe llegar a , lo que garantiza la terminación.
Se define una función que calcula la representación de base hereditaria de y luego reemplaza cada aparición de la base con el primer número ordinal infinito . Por ejemplo, .
Cada término de la sucesión se define entonces como . Por ejemplo, y . La suma, la multiplicación y la exponenciación de números ordinales están bien definidas.
Afirmando que :
Sea después de aplicar la primera operación de cambio de base al generar el siguiente elemento de la sucesión de Goodstein, pero antes de la segunda operación de resta de 1 en esta generación. Obsérvese que .
Luego . Ahora, se aplica la operación de menos 1, y , como ..
Por ejemplo, y , por lo que y , que es estrictamente menor. Nótese que para calcular , primero se debe escribir en notación de base hereditaria , ya que, por ejemplo, la expresión no es un ordinal.
Por lo tanto, la sucesión es estrictamente decreciente. Como el orden estándar < en ordinales es una relación bien fundada, no puede existir una sucesión estrictamente decreciente infinita, o equivalentemente, toda sucesión estrictamente decreciente de ordinales termina (y no puede ser infinita). Pero se calcula directamente a partir de . Por lo tanto, la sucesión también debe terminar, lo que significa que debe alcanzar .
Si bien esta demostración del teorema de Goodstein es bastante sencilla, el teorema de Kirby-París, 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 contables de la aritmética de Peano.
Teorema extendido de Goodstein La demostración anterior sigue siendo válida si se modifica 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 por en lugar de .
De forma más general, sean , y cualquier sucesión no decreciente de enteros con .
Entonces, sea el -ésimo término de la sucesión extendida de Goodstein de la siguiente manera:
Se toma la representación de base hereditaria de . Se reemplaza cada aparición de la base por . Se resta uno.
Una simple modificación de la demostración anterior permite comprobar que esta sucesión sigue teniendo terminación. Por ejemplo, si y , entonces , por lo tanto, el ordinal es estrictamente mayor que el ordinal .
La versión extendida es, de hecho, la considerada en el artículo original de Goodstein, donde demostró que es equivalente al teorema ordinal restringido (es decir, la afirmación de que la inducción transfinita es menor que ε0 es válida), y proporcionó una demostración finitista para el caso en que (equivalente a la inducción transfinita hasta ).
El teorema extendido de Goodstein sin ninguna restricción en la sucesión bn no es formalizable en la aritmética de Peano (AP), ya que una sucesión infinita arbitraria de este tipo no puede representarse en la AP. Esto parece ser lo que impidió que Goodstein afirmara en 1944 que el teorema extendido de Goodstein es indemostrable en la AP debido a los teoremas de incompletitud de Gödel y a la prueba de Gentzen de la consistencia de la AP usando la inducción ε0. Sin embargo, la inspección de la demostración de Gentzen muestra que solo necesita el hecho de que no existe una sucesión de ordinales de recursión primitiva infinita estrictamente decreciente, por lo que limitar bn a sucesiones recursivas primitivas habría permitido a Goodstein probar un resultado de indemostrabilidad. Además, con la técnica relativamente elemental de la jerarquía de Grzegorczyk, se puede demostrar que toda sucesión infinita recursiva estrictamente decreciente de ordinales primitiva puede ralentizarse de manera que se transforme en una sucesión de Goodstein donde , lo que proporciona una demostración alternativa al mismo resultado que demostraron Kirby y Paris.
Longitud de la sucesión en función del valor inicial La función de Goodstein, , se define de tal manera que es la longitud de la sucesión de Goodstein que comienza con n (es una función parcial, ya que toda sucesión de Goodstein tiene terminación). La altísima tasa de crecimiento de puede calibrarse relacionándola con diversas jerarquías de funciones estándar indexadas por orden, 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:
Kirby y Paris (1982) demostraron que:
tiene aproximadamente la misma tasa de crecimiento que (que es la misma que la de ). Más precisamente, domina a para todo , y domina a (para cualesquiera dos funciones , se dice que domina a si para todo suficientemente grande).
Cichon (1983) demostró que:
donde es el resultado de poner n en notación hereditaria de base 2 y luego reemplazar todos los 2 por ? (como se hizo en la demostración del teorema de Goodstein).
Caicedo (2007) demostró que si con entonces: .
Algunos ejemplos:
n 12243643·2402653211 − 2 ≈ 6.895080803×101212106945> A(4,4) > 101010197276> A(6,6)7> A(8,8)8> A3(3,3)= A(A(61, 61), A(61, 61))12> fω+1(64) > Número de Graham19
(Para los límites de la función de Ackermann y el número de Graham, véase .)
Aplicación a funciones computables El teorema de Goodstein puede utilizarse para construir una función computable total que la aritmética de Peano no puede demostrar que sea total. La sucesión de Goodstein de un número puede enumerarse eficazmente mediante una máquina de Turing. Por lo tanto, la función que asigna a n el número de pasos necesarios para que la sucesión de Goodstein de n termine es computable por una máquina de Turing particular. Esta máquina simplemente enumera la sucesión de Goodstein de n y, cuando la sucesión llega a 0, devuelve su longitud. Dado que toda sucesión de Goodstein termina finalmente, esta función es total. Pero como la aritmética de Peano no demuestra que toda sucesión de Goodstein termine, tampoco demuestra que esta máquina de Turing calcule una función total.
Véase también Aritmética no estándar Jerarquía de rápido crecimiento Principio de París-Harrington Teorema de Kanamori-McAloon Teorema de los árboles de Kruskal Rompecabezas de cuerdas quemadas
Notas
Referencias
Bibliografía
Enlaces externos