O que o teorema de Goodstein realmente diz?

Ele diz que toda sequência de Goodstein, por maiores que fiquem seus números pelo caminho, acaba chegando a zero. O crescimento pode ser astronômico e durar um número inimaginável de passos, mas o término é garantido para qualquer valor inicial.

Por que a sequência volta a descer se ela não para de crescer?

Cada termo tem um parceiro ordinal escondido que decresce estritamente a cada passo. Os números inteiros visíveis podem inchar, mas o ordinal por trás deles só pode descer, e uma sequência decrescente de ordinais não cai para sempre, então o processo precisa terminar em zero.

O que é a notação hereditária de base n?

Significa escrever um número na base n e depois escrever também todos os seus expoentes na base n, descendo até o fim. Por exemplo, 4 na base 2 hereditária é escrito como dois elevado a dois, com o expoente também expresso na base 2.

Por que o teorema de Goodstein é famoso na lógica?

Porque ele é verdadeiro, mas não pode ser demonstrado usando apenas a aritmética de Peano. Foi uma das primeiras afirmações naturais, não fabricadas, sobre números comuns a se mostrar indemonstrável nesse sistema, e é por isso que ele fica na fronteira entre a matemática e a lógica.

O jogo da hidra é a mesma ideia?

Sim, a hidra de Kirby e Paris é a mesma matemática contada de outro jeito. Cortar uma cabeça pode fazer muitas outras nascerem, mas a hidra sempre é derrotada no fim, exatamente pelo mesmo motivo que faz uma sequência de Goodstein sempre chegar a zero.

Teorema de Goodstein: a sequência que explode e depois sempre volta a zero

Escolha um número inteiro. Qualquer um. Agora aplique uma regra de dois passos, repetidamente, e observe o resultado. Para quase todo valor inicial que você escolher, a sequência dispara para cima, ultrapassa um googol, passa por números que fazem a contagem de átomos do universo observável parecer minúscula, passa por qualquer coisa que você conseguiria escrever em uma vida inteira. E, ainda assim, está provado: ela sempre volta a zero.

Esse é o teorema de Goodstein e, na primeira vez que você ouve falar dele, parece pegadinha. A regra não é complicada, os números são comuns e o enunciado é limpo. Mesmo assim, durante décadas, a razão de ele ser verdadeiro não tinha lugar dentro da aritmética comum. Este artigo não pede que você acompanhe uma demonstração de lógica. Em vez disso, ele mostra a imagem que está por baixo e, quando você a enxerga, o teorema deixa de ser um mistério.

A regra é quase infantilmente simples

Você começa com um número inteiro e uma base, a partir da base 2. Em cada passo você faz duas coisas: primeiro, reescreve o número atual em algo chamado notação hereditária de base n; segundo, troca toda ocorrência da base n por n+1 e então subtrai 1. Depois passa para a próxima base e repete.

Notação hereditária de base n significa escrever seu número na base n e depois escrever todo expoente também na base n, descendo até que apareça apenas o dígito 1 nos expoentes. Nada fica na forma abreviada. Por exemplo, a expansão comum de 26 na base 2 é 11010 em binário, o que significa $2^{4}$ + $2^{3}$ + $2^{1}$ . Mas 4 é $2^{2}$ e 3 é... bem, 3 não é potência de 2, então na base 2 comum você já terminou. Na base 2 hereditária, você desce mais um nível: $2^{2^{2}}$ + $2^{2+1}$ + $2^{1}$ . Todo expoente precisa ser expresso usando apenas a base, empilhado o quanto for necessário. Esse empilhamento é exatamente o que dá à notação sua estranha resistência, e ele se conecta diretamente a como os expoentes crescem muito mais rápido do que você imagina.

Aumentar a base e subtrair parece coisa branda. Passar uma base de 2 para 3 soa como uma mudança pequena. Subtrair 1 soa como algo que deveria segurar o número. Você vai ver em seguida por que nenhuma das duas intuições sobrevive ao contato com a notação hereditária.

Veja a explosão

Comece com 4. Na base 2 hereditária, isso é $2^{2}$ . Aumente todo 2 para 3 e subtraia 1: você obtém $3^{3}$ menos 1, que é 26. Agora escreva 26 na base 3 hereditária, aumente para a base 4, subtraia 1, e você chega a 41. Continue.

The Goodstein sequence starting at 4: each step bumps the base then subtracts one.
Step	Base	Written in that base	Value
1	2	2²	4
2	3	2·3² + 2·3 + 2	26
3	4	2·4² + 2·4 + 1	41
4	5	2·5² + 2·5	60
5	6	2·6² + 6 + 5	83
6	7	2·7² + 7 + 4	109

A sequência que começa em 4 segue assim: 4, 26, 41, 60, 83, 109, e continua subindo a partir daí. Mesmo esse início modesto segue crescendo por um trecho notavelmente longo antes de finalmente descer. Comece em 19 e os números alcançam alturas fisicamente impossíveis de escrever. A quantidade de passos antes de a sequência sequer começar a virar é maior que o número de átomos do universo observável. Se você tivesse iniciado o cálculo no Big Bang, no computador mais rápido concebível, não veria o pico hoje.

Todo instinto diz: isso diverge. Não tem volta de números tão grandes. Aqui a intuição está simplesmente errada, e é esse o ponto. Algo invisível está acontecendo, e os números crus não mostram.

O número escondido que só desce

Troque cada termo por sua sombra ordinal

Aqui está o movimento central. Pegue qualquer termo da sequência de Goodstein e leia sua expressão na base n hereditária. Agora, onde quer que apareça a base n, escreva no lugar o símbolo ômega (o primeiro ordinal infinito). Você não mudou nada da estrutura da expressão. Só trocou um rótulo. O resultado é um número ordinal, um tipo de contagem que se estende para além dos inteiros, entrando no infinito.

Por exemplo, 4 na base 2 hereditária é $2^{2}$ . Substitua 2 por ômega e você obtém $\omega^\omega$ . A sombra ordinal de 26 na base 3 hereditária é dois vezes ômega ao quadrado, mais dois vezes ômega, mais dois: um polinômio de altura finita em ômega, muito menor que ômega elevado a ômega. Os expoentes 2, 1 e 0 da expressão na base 3 hereditária já são menores que 3, então não há novo empilhamento. Esses ordinais são objetos matemáticos perfeitamente bem definidos.

Aumentar a base não faz nada com a sombra

Quando você aumenta a base de n para n+1, a expressão hereditária troca o rótulo n por n+1, mas o formato da expressão continua idêntico. Então a sombra ordinal não muda com o aumento. A sombra do termo antes do aumento e a sombra do termo depois do aumento são o mesmo ordinal.

Mas então você subtrai 1 do número inteiro. Subtrair 1, em notação hereditária, exige descascar o termo mais baixo da expressão. Isso muda o formato da expressão hereditária de um jeito que, quando você troca a base por ômega, resulta em um ordinal estritamente menor. Não por uma quantidade minúscula, não por coincidência: toda subtração de 1 na sequência de números inteiros empurra a sombra ordinal estritamente para baixo.

Então o padrão é: aumenta a base (a sombra fica parada), subtrai 1 (a sombra cai). Efeito líquido por passo: a sombra ordinal desce pelo menos um degrau, todas as vezes.

Ordinais não podem decrescer para sempre

Uma sequência estritamente decrescente de ordinais não pode continuar para sempre. Esse é um dos fatos mais fundamentais sobre ordinais: diferente do que ocorre com os inteiros, você não consegue descer indefinidamente. Existe um fundo. A sequência de sombras ordinais precisa chegar a zero em algum momento e, quando a sombra ordinal é zero, o único número inteiro cuja expressão hereditária corresponde ao ordinal zero é o próprio zero. Logo, a sequência de Goodstein também precisa chegar a zero.

Os números inteiros podem inchar até tamanhos inimagináveis. Mas os ordinais por trás deles seguem, silenciosa e inevitavelmente, marcando a contagem regressiva a cada passo. O barulho está nos números visíveis. A verdade está na sombra.

A hidra conta a mesma coisa

Você pode contar a mesma história como um jogo. Imagine um monstro em forma de árvore, uma hidra, com cabeças nas pontas dos galhos. Você corta uma cabeça. Dependendo de qual cabeça você corta e de quando, várias cabeças novas podem brotar do toco, às vezes muitas. Você continua cortando. Parece que a hidra está ganhando.

Corte uma cabeça e outras nascem, mas toda hidra acaba sendo derrotada: o corpo encolhe como uma sequência de Goodstein.

O jogo da hidra de Kirby e Paris, apresentado pelos matemáticos Jeff Paris e Laurie Kirby em 1982, é exatamente essa situação e codifica a mesma matemática da sequência de Goodstein. A regra de brotar cabeças corresponde à explosão do aumento de base. A estrutura de árvore corresponde à notação hereditária. E o ordinal escondido por trás da árvore decresce estritamente a cada corte, como no argumento de Goodstein.

Não importa a estratégia que você use, não importa o descuido com que escolha qual cabeça cortar, você sempre vence. A hidra sempre morre. A explosão de cabeças novas é real e pode ser espetacular, mas por baixo dos fogos de artifício uma contagem regressiva está rodando. O jogo da hidra é o teorema de Goodstein fantasiado.

Por que os matemáticos se importam

É aqui que a história vira. O teorema de Goodstein é verdadeiro. É comprovadamente verdadeiro, como mostra o argumento ordinal acima. Mas, em 1982, Kirby e Paris provaram outra coisa: o teorema não pode ser demonstrado dentro da aritmética de Peano.

A aritmética de Peano é o sistema formal padrão para raciocinar sobre números inteiros. Ela captura quase tudo o que você chamaria de aritmética comum: adição, multiplicação, indução sobre os números naturais. É a arena onde vive a maior parte dos resultados de sala de aula. E ela simplesmente não é forte o bastante para provar que as sequências de Goodstein terminam.

Isso não significa que o teorema seja indemonstrável em todos os sentidos. O argumento ordinal funciona e é completamente rigoroso. Mas o argumento ordinal exige raciocinar sobre o infinito de um jeito que a aritmética de Peano não alcança. O sistema consegue descrever as sequências de Goodstein com precisão. Consegue rodá-las, termo a termo. Consegue até reconhecer que cada termo é um número inteiro específico. O que ele não consegue é enxergar a sombra, a estrutura ordinal que garante a descida.

O teorema de Goodstein foi um dos primeiros exemplos de uma afirmação natural, de aparência comum, sobre números comuns, que acabou ficando logo além do alcance da aritmética padrão. Não é um quebra-cabeça lógico artificial construído para ser indemonstrável. É uma afirmação que você poderia explicar para um estudante do ensino médio, sobre uma sequência que caberia em um guardanapo, e a aritmética padrão não consegue fechar o caso.

O zen da coisa

Há algo aqui que vale a pena deixar assentar. A sequência que parece explodir sem limite está, a cada passo, participando de uma descida que os números crus escondem de você. As duas coisas acontecem ao mesmo tempo: crescimento enorme e retorno silencioso e inevitável.

Isso não é uma contradição. É um lembrete de que o tamanho de um número não é o mesmo que o destino dele. O que importa é a estrutura por baixo, e aqui a estrutura sempre aponta para o zero.

A matemática está cheia de momentos assim: uma quantidade que parece que deveria divergir e não diverge, uma demonstração que parece que deveria falhar e se sustenta, uma sequência que parece infinita e termina. A habilidade não está em calcular termos na força bruta. Está em achar a sombra certa para acompanhar, aquela que conta o que realmente está acontecendo. Quando você vê o ordinal descendo por trás da pirotecnia, o teorema não é apenas verdadeiro. Ele parece inevitável.

Tamanho é ruído. Estrutura é sinal. A sequência sempre esteve voltando para casa.