Este artigo carece de reciclagem de acordo com o livro de estilo. Sinta-se livre para editá-lo(a) para que este(a) possa atingir um nível de qualidade superior. (Setembro de 2013)

Este artigo não cita fontes confiáveis. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Setembro de 2013)

Na matemática lógica, o Teorema de Goodstein é um enunciado sobre os números naturais, provado por Reuben Goodstein em 1994, o qual define que toda sequência de Goodstein termina em zero. Kirby & Paris, em 1982, mostraram que isto não é demonstrável na aritmética de Peano (mas isto pode ser provado em sistemas em ordem maior, de acordo com a ordem aritmética). Este foi o terceiro exemplo “natural” de um enunciado verdadeiro que não é demonstrável na aritmética de Peano(depois da prova direta, de Gerhard Gentzen, em 1943,da indemonstrabilidade da indução-ε0 na aritmética de Peano e o Teorema de Paris-Harrington). Anteriormente, enunciados deste tipo tinham sido, exceto para Gentzen, extremamente complicados, construções aleatórias (como os enunciados gerados pela construção dada no Teorema da Incompletude de Gödel) ou interessou metamatemáticos ou resultados combinatoriais (Kirby & Paris 1982).

Laurie Kirby e Jeff Paris deram uma interpretação do Teorema de Goodstein como um jogo de hidras: a “Hidra” é uma árvore enraizada, e um movimento, ou jogada, consiste em cortar uma das suas CABEÇAS (um galho da árvore), a qual a hidra reage com o crescimento de um número finito de novos galhos, de acordo com determinadas regras. A interpretação de Kirby-Paris do teorema diz que a Hidra vai, eventualmente, ser morta, independentemente da estratégia que Hércules usa para cortar fora as cabeças, embora isto possa levar muito, muito tempo.

Sequencias de Goodstein são definidas em termos de uma conceito chamado "notação base-nhereditária". Essa notação é muito similar ao usual base-n notação

posicional, mas a notação usual não é suficiente para os fins do teorema de Goodstein Em notação base-n ordinária, onde n é um numero natural maior que 1, um numero natural arbitrario m é escrito como uma soma dos multiplos das potencias

de n:

${\displaystyle m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},}$

onde cada coeficiente ${\displaystyle a_{i}}$ satisfaz ${\displaystyle 0\leq a_{i}<n}$, e ${\displaystyle a_{k}\not =0}$. Por exemplo, em base 2,

${\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}$

Assim a representação base 2 de 35 é ${\displaystyle 2^{5}+2^{1}+2^{0}}$. (Essa expressão pode ser escrita em notação binaria como 100011.) Similarmente, 100 pode ser

escrito em base 3:

${\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+1.}$

Note que os expoentes por eles mesmos não são escritos na notação base-n. Por exemplos, a expressão acima inclui ${\displaystyle 2^{5}}$ e ${\displaystyle 3^{4}}$. Para converter uma representação base-n para uma notação base n hereditária, primeiro reescreva todos os expoentes em notação base-n. Então reescreva

qualquer expoente dentro dos expoentes, e continue desse forma até todo digito nessa expressão seja n ou menor. Por exemplo, enquanto 35 na notação base-2 é ${\displaystyle 2^{5}+2+1}$, ele é escrito na notação base-2 hereditária como

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

usando o fato que ${\displaystyle 5=2^{2}+1.}$ . Similarmente, 100 na notação base-3 hereditária é

${\displaystyle 100=3^{3+1}+2\cdot 3^{2}+1.}$

A sequencia de Goodstein G(m) de um numero m é uma sequencia de numeros naturais. O primeiro elemento dessa sequencia G(m) é o proprio m. Para pegar

o proximo elemento, escreva m na notação base-2 hereditária, troque todo 2 para 3, e então subtraia 1 do resultado; esse é o segundo elemento de G(m). PAra

conseguir o terceiro elemento de G(m), escreva o segundo elemento na notação base-3 hereditária, troque todo 3 por 4, e subtraia 1 novamente. Continue até que

o resultado seja 0. Anteriormente sequencias de Goodstein terminaram rapidamente. Por exemplo, G(3) termina em seis passos:

Base	Notação hereditária	Valor	Nota
2	${\displaystyle 2^{1}+1}$	3	Escreva 3 na notação base-3
3	${\displaystyle 3^{1}+1-1=3^{1}}$	3	Troque 2 para 3, e subtraia 1
4	${\displaystyle 4^{1}-1=3}$	3	Troque 3 para 4, e subtraia 1. Agora não contem mais 4
5	${\displaystyle 3-1=2}$	2	Nenhum 4 restou para trocar por 5. Apenas subtraia 1
6	${\displaystyle 2-1=1}$	1
7	${\displaystyle 1-1=0}$	0

Depois sequencias de Goodstein aumentaram para um grande numero de passos. Por exemplo, G(4) começa a seguir:

Hereditary notation	Value
${\displaystyle 2^{2}}$	4
${\displaystyle 3^{3}-1=2\cdot 3^{2}+2\cdot 3+2}$	26
${\displaystyle 2\cdot 4^{2}+2\cdot 4+1}$	41
${\displaystyle 2\cdot 5^{2}+2\cdot 5}$	60
${\displaystyle 2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5}$	83
${\displaystyle 2\cdot 7^{2}+7+4}$	109
${\displaystyle \vdots }$	${\displaystyle \vdots }$
${\displaystyle 2\cdot 11^{2}+11}$	253
${\displaystyle 2\cdot 12^{2}+12-1=2\cdot 12^{2}+11}$	299
${\displaystyle \vdots }$	${\displaystyle \vdots }$

Elementos de G(4) continuam a acrescentar por um tempo, mas a base ${\displaystyle 3\cdot 2^{402653209}}$, eles chegam no maximo de ${\displaystyle 3\cdot 2^{402653210}-1}$ passos, e então começa seu primeiro e ultimo descida. O valor 0 é encontrado na base ${\displaystyle 3\cdot 2^{402653211}-1}$. Entretanto, mesmo G(4) não dão uma boa de o quão rapido os elementos da sequencia de Goodstein pode aumentar. G(19) aumenta muito mais rapidamente, a

assim como mostrado a seguir:

Hereditary notation	Value
${\displaystyle 2^{2^{2}}+2+1}$	19
${\displaystyle 3^{3^{3}}+3}$	7,625,597,484,990
${\displaystyle 4^{4^{4}}+3}$	${\displaystyle \approx 1.3\times 10^{154}}$
${\displaystyle 5^{5^{5}}+2}$	${\displaystyle \approx 1.8\times 10^{2184}}$
${\displaystyle 6^{6^{6}}+1}$	${\displaystyle \approx 2.6\times 10^{36,305}}$
${\displaystyle 7^{7^{7}}}$	${\displaystyle \approx 3.8\times 10^{695,974}}$
${\displaystyle 8^{8^{8}}-1=7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7)}}$ ${\displaystyle +7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+6)}+\cdots }$ ${\displaystyle +7\cdot 8^{(8+2)}+7\cdot 8^{(8+1)}+7\cdot 8^{8}}$ ${\displaystyle +7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}}$ ${\displaystyle +7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7}$	${\displaystyle \approx 6\times 10^{15,151,335}}$
${\displaystyle 7\cdot 9^{(7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+7)}}$ ${\displaystyle +7\cdot 9^{(7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6)}+\cdots }$ ${\displaystyle +7\cdot 9^{(9+2)}+7\cdot 9^{(9+1)}+7\cdot 9^{9}}$ ${\displaystyle +7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}}$ ${\displaystyle +7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6}$	${\displaystyle \approx 4.3\times 10^{369,693,099}}$
${\displaystyle \vdots }$	${\displaystyle \vdots }$

Devido a este grande crescimento, o Teorema de Goodstein declara que toda sequência de Goodstein eventualmente termina em zero, não importando qual o valor inicial.

O Teorema de Goodstein pode ser provado (usando técnicas fora da aritmética de Peano, veja abaixo) como segue: Dada uma sequência de Goodstein G(m), vamos construir uma sequência paralela de números ordinais, cujos elementos não são menores que os que da sequência original. Se os elementos da sequência paralela tendem a zero, os elementos da sequência de Goodstein devem também tender a zero.

Para construir a sequência paralela, pegue a representação da base hereditária n do elemento (n-1) da sequência de Goodstein, e substitua cada instância de n com primeiro número ordinal infinito ω. Adição, multiplicação e exponenciação de números ordinais são bem definidas, e o número ordinal resultante claramente não pode ser menor que o elemento original.

A operação de mudança de base da sequência de Goodstein não muda o elemento da sequência paralela: realocando the os 4s em ${\displaystyle 4^{4^{4}}+4}$ com ω é o mesmo que realocar todos os 4s com 5s e então todos os 5s com ω. A operação de subtrair 1, no entanto, corresponde ao decrescimento do número ordinal infinito numa sequência paralela; por exemplo, ${\displaystyle \omega ^{\omega ^{\omega }}+\omega }$ é reduzido para ${\displaystyle \omega ^{\omega ^{\omega }}+4}$ se o passo acima é executado. Pelo fato dos ordinais serem bem-ordenados, não há uma sequência infinita estritamente definida de ordinais. Assim, a sequência paralela deve terminar em zero após um número finito de passos. A sequência de Goodstein, a qual é limitada superiormente pela sequência paralela, deve terminar em zero também.

Enquanto esta prova do Teorema de Goodstein é relativamente fácil, o Teorema de Kirby-Paris diz que o Teorema de Goodstein não é um Teorema da Aritmética de Peano, é técnico e consideravelmente mais difícil. Ele faz uso de modelos contáveis despadronizados da Aritmética de Peano. O que Kirby mostrou é que o Teorema de Goodstein leva ao Teorema de Gentzen, isto é, ele pode substituir para a indução até ε0.

A função de Goodstein, ${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} \,\!}$, é definida tal que ${\displaystyle {\mathcal {G}}(n)}$ é o tamanho da sequancia

de Goodstein que começa com n. (Essa é uma função total até toda sequencia de Goodstein termine.) A taxa de crescimento extrema de ${\displaystyle {\mathcal {G}}\,\!}$ pode ser calibrada por relaciona-lo com varios hierarquias ordinal-indexadas padroes de funções, tal que as funções ${\displaystyle H_{\alpha }\,\!}$ em uma

hierarquia de Hardy e as funções ${\displaystyle f_{\alpha }\,\!}$ na hierarquia de crescimento rapido de Löb e Wainer:

• Kirby and Paris (1982) provou que

${\displaystyle {\mathcal {G}}\,\!}$ contem aproximadamente a mesma taxa de crescimento como ${\displaystyle H_{\epsilon _{0}}\,\!}$ (que é a mesma de ${\displaystyle f_{\epsilon _{0}}\,\!}$); mais precisamente, ${\displaystyle {\mathcal {G}}\,\!}$ domina ${\displaystyle H_{\alpha }\,\!}$ para todo ${\displaystyle \alpha <\epsilon _{0}\,\!}$, e

${\displaystyle H_{\epsilon _{0}}\,\!}$ domina ${\displaystyle {\mathcal {G}}\,\!.}$

(Para qualquer qualquer 2 funções ${\displaystyle f,g:\mathbb {N} \to \mathbb {N} \,\!}$, ${\displaystyle f\,\!}$ é dita dominada ${\displaystyle g\,\!}$ se ${\displaystyle f(n)>g(n)\,\!}$ para todo suficientemente grande ${\displaystyle n\,\!}$.)

• Cichon (1983) mostrou que

${\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}$

onde${\displaystyle R_{2}^{\omega }(n)}$ é resultado do inclusão de n na notação base-2 hereditáriae então substituindo todo 2 com ω (como foi feito na prova do

teorema de Goodstein).

• Caicedo (2007) mostrou que se ${\displaystyle n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}}$ with ${\displaystyle m_{1}>m_{2}>\cdots >m_{k},}$ então

${\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}$.

Alguns exemplos:

n			${\displaystyle {\mathcal {G}}(n)}$
1	${\displaystyle 2^{0}}$	${\displaystyle 2-1}$	${\displaystyle H_{\omega }(1)-1}$	${\displaystyle f_{0}(3)-2}$	2
2	${\displaystyle 2^{1}}$	${\displaystyle 2^{1}+1-1}$	${\displaystyle H_{\omega +1}(1)-1}$	${\displaystyle f_{1}(3)-2}$	4
3	${\displaystyle 2^{1}+2^{0}}$	${\displaystyle 2^{2}-1}$	${\displaystyle H_{\omega ^{\omega }}(1)-1}$	${\displaystyle f_{1}(f_{0}(3))-2}$	6
4	${\displaystyle 2^{2}}$	${\displaystyle 2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega }(3)-2}$	3·2402653211 − 2
5	${\displaystyle 2^{2}+2^{0}}$	${\displaystyle 2^{2}+2-1}$	${\displaystyle H_{\omega ^{\omega }+\omega }(1)-1}$	${\displaystyle f_{\omega }(f_{0}(3))-2}$	> A(4,4)
6	${\displaystyle 2^{2}+2^{1}}$	${\displaystyle 2^{2}+2+1-1}$	${\displaystyle H_{\omega ^{\omega }+\omega +1}(1)-1}$	${\displaystyle f_{\omega }(f_{1}(3))-2}$	> A(6,6)
7	${\displaystyle 2^{2}+2^{1}+2^{0}}$	${\displaystyle 2^{2+1}-1}$	${\displaystyle H_{\omega ^{\omega +1}}(1)-1}$	${\displaystyle f_{\omega }(f_{1}(f_{0}(3)))-2}$	> A(8,8)
8	${\displaystyle 2^{2+1}}$	${\displaystyle 2^{2+1}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+1}(1)-1}$	${\displaystyle f_{\omega +1}(3)-2}$	> A3(3,3) = A(A(61, 61), A(61, 61))
${\displaystyle \vdots }$
12	${\displaystyle 2^{2+1}+2^{2}}$	${\displaystyle 2^{2+1}+2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega +1}(f_{\omega }(3))-2}$	> fω+1(64) > Número de Graham
${\displaystyle \vdots }$
19	${\displaystyle 2^{2^{2}}+2^{1}+2^{0}}$	${\displaystyle 2^{2^{2}}+2^{2}-1}$	${\displaystyle H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1}$	${\displaystyle f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2}$

O Teorema de Goodstein pode ser usado para construir uma função computável total, que a Aritmética de Peano não pode provar a completude. A sequência de Goodstein de um número pode ser efetivamente enumerada por uma Máquina de Turing; assim, a função que mapeia "n" para o número de passos requeridos para a sequência de Goodstein de "n" para terminar é computável por uma Máquina de Turing em particular. Esta máquina meramente enumera a Sequência de Goodstein de n e, quando a sequência chega a 0, retorna o comprimento da sequência. Pois, toda sequência de Goodstein eventualmente termina, esta função é total. Porém, devido a Aritmética de Peano não provar que toda sequência de Goodstein termina, ela não prova que esta máquina de Turing computa a função total.