teorema de goodstein

Teorema sobre los números naturales

En lógica matemática , el teorema de Goodstein es una afirmación sobre los números naturales , probada por Reuben Goodstein en 1944, que establece que toda secuencia de Goodstein (como se define a continuación) eventualmente termina en 0. Laurence Kirby y Jeff Paris ^[1] demostraron que es indemostrable. en aritmética de Peano (pero se puede demostrar en sistemas más fuertes, como la aritmética de segundo orden ). Este fue el tercer ejemplo de una afirmación verdadera sobre números naturales que no es demostrable 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 ε 0 en la aritmética de Peano. El teorema de Paris-Harrington dio otro ejemplo.

Kirby y Paris introdujeron un juego de hidra de teoría de grafos con un comportamiento similar al de las secuencias de Goodstein: la "Hydra" (llamada así por la mitológica Hidra de múltiples cabezas de Lerna ) 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 morirá, independientemente de la estrategia que utilice Hércules para cortarle la cabeza, aunque esto puede llevar mucho tiempo. Al igual que con las secuencias de Goodstein, Kirby y Paris demostraron que esto no se puede demostrar únicamente con la aritmética de Peano. ^[1]

Base hereditaria- notación n

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

Para lograr la notación ordinaria de 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, 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 base n . Por ejemplo, las expresiones anteriores incluyen 2 ⁵ y 3 ⁴ , y 5 > 2, 4 > 3.

Para convertir una notación de base n (que es un paso para lograr la representación de base n ) a una notación de base n hereditaria , primero reescribe todos los exponentes como una suma de potencias de n (con la limitación de los coeficientes 0 ≤ a _yo < norte ). Luego, reescribe cualquier exponente dentro de los exponentes en notación de base n (con la misma limitación en los coeficientes) y continúa de esta manera hasta que cada número que aparece en la expresión (excepto las propias bases) esté escrito en notación de base n .

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

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

usando 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 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 ( n  + 1) -st término, G ( m )( n  + 1) , de la secuencia de Goodstein de m es el siguiente:

• Tome la representación de base hereditaria 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:

Posteriormente, las secuencias de Goodstein aumentan en una gran cantidad de pasos. Por ejemplo, G (4) OEIS : A056193 comienza de la siguiente manera:

Los elementos de G (4) continúan aumentando por 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, ni siquiera G (4) 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:

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.

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 en forma normal de Cantor que es estrictamente decreciente y termina. Un malentendido común de esta prueba es creer que G ( m ) llega 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. El punto importante es: G ( m )( k ) existe si y sólo si P ( m )( k ) existe (paralelismo), y la comparación entre dos miembros de G ( m ) se conserva al comparar 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 en 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}+\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, 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)}$

Sea 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 menos 1 en esta generación. Observa eso . ${\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 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 hereditaria de base n +1 , ya que, 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 tanto, la secuencia P ( m ) es estrictamente decreciente. Como el orden estándar < en ordinales está bien fundamentado , 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 sencilla, 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. Hace uso de modelos contables no estándar de aritmética de Peano.

Teorema de Goodstein extendido

Supongamos que se cambia la definición de la secuencia de Goodstein de modo que en lugar de reemplazar cada aparición de la base b con b + 1 , la reemplaza con b + 2 . ¿Aún terminaría la secuencia? De manera más general, sean b ₁ , b ₂ , b ₃ , ... cualquier secuencia de números enteros. Entonces, sea el ( n + 1) -st término G ( m )( n + 1) de la secuencia extendida de Goodstein de m el siguiente: tome la representación de base hereditaria b _n de G ( m )( n ) y reemplace cada aparición 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 representación base hereditaria b _n de G ( m )( n ) y reemplace cada aparición 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 , 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 )}.}$

Longitud de la secuencia en función del valor inicial.

La función de Goodstein , , se define de manera 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 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 . -Jerarquía creciente 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 lo 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 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 conocer 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 puede enumerarse 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 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. Como toda secuencia de Goodstein termina finalmente, esta función es total. Pero como la aritmética de Peano no prueba que toda secuencia de Goodstein termine, 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 en rápido crecimiento
• Teorema de París-Harrington
• Teorema de Kanamori-McAloon
• Teorema del árbol de Kruskal

Referencias

1. Kirby, L .; París, 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.
2. M. Rathjen, revisión del teorema de Goodstein (lema 2.2). Consultado el 14 de agosto de 2022.

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 breve prueba de dos resultados de independencia recientemente descubiertos utilizando métodos teóricos recursivos", Actas de la Sociedad Matemática Estadounidense , 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 universitaria de Justin T Miller
• Una clasificación de modelos no estándar de aritmética de Peano según 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 subprograma de Java
• Implementación de Javascript de una variante del juego Hydra.
• Secuencias Goodstein: El poder de un desvío a través del infinito: buena exposición con ilustraciones de Secuencias Goodstein y el juego de la hidra.
• Calculadora Goodstein