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.
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.
| 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 ômega^ômega. 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.
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.
Perguntas frequentes
- 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.
Coloque em prática
Gostou de pensar sobre isso?
O Math Zen transforma esse tipo de intuição em prática diária, com exercícios adaptativos em 24 temas de matemática.
