Teorema de Goodstein

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.​