Teorema de Goodstein
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 eventualmente 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.
Índice
1 Notação base-n hereditária
2 Sequencias de Goodstein
3 Prova do Teorema de Goodstein
4 Tamanho da sequencia como um função de valor inicial
5 Aplicação para funções computáveis
Notação base-n hereditária |
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:
- m=aknk+ak−1nk−1+⋯+a0,{displaystyle m=a_{k}n^{k}+a_{k-1}n^{k-1}+cdots +a_{0},}
onde cada coeficiente ai{displaystyle a_{i}}
- 35=32+2+1=25+21+20.{displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}
Assim a representação base 2 de 35 é 25+21+20{displaystyle 2^{5}+2^{1}+2^{0}}
escrito em base 3:
- 100=81+18+1=34+2⋅32+1.{displaystyle 100=81+18+1=3^{4}+2cdot 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 25{displaystyle 2^{5}}
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 é 25+2+1{displaystyle 2^{5}+2+1}
- 35=222+1+2+1,{displaystyle 35=2^{2^{2}+1}+2+1,}
usando o fato que 5=22+1.{displaystyle 5=2^{2}+1.}
- 100=33+1+2⋅32+1.{displaystyle 100=3^{3+1}+2cdot 3^{2}+1.}
Sequencias de Goodstein |
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 | 21+1{displaystyle 2^{1}+1} | 3 | Escreva 3 na notação base-3 |
| 3 | 31+1−1=31{displaystyle 3^{1}+1-1=3^{1}} | 3 | Troque 2 para 3, e subtraia 1 |
| 4 | 41−1=3{displaystyle 4^{1}-1=3} | 3 | Troque 3 para 4, e subtraia 1. Agora não contem mais 4 |
| 5 | 3−1=2{displaystyle 3-1=2} | 2 | Nenhum 4 restou para trocar por 5. Apenas subtraia 1 |
| 6 | 2−1=1{displaystyle 2-1=1} | 1 | |
| 7 | 1−1=0{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 |
|---|---|
22{displaystyle 2^{2}} | 4 |
33−1=2⋅32+2⋅3+2{displaystyle 3^{3}-1=2cdot 3^{2}+2cdot 3+2} | 26 |
2⋅42+2⋅4+1{displaystyle 2cdot 4^{2}+2cdot 4+1} | 41 |
2⋅52+2⋅5{displaystyle 2cdot 5^{2}+2cdot 5} | 60 |
2⋅62+2⋅6−1=2⋅62+6+5{displaystyle 2cdot 6^{2}+2cdot 6-1=2cdot 6^{2}+6+5} | 83 |
2⋅72+7+4{displaystyle 2cdot 7^{2}+7+4} | 109 |
⋮{displaystyle vdots } | ⋮{displaystyle vdots } |
2⋅112+11{displaystyle 2cdot 11^{2}+11} | 253 |
2⋅122+12−1=2⋅122+11{displaystyle 2cdot 12^{2}+12-1=2cdot 12^{2}+11} | 299 |
| ⋮{displaystyle vdots } | ⋮{displaystyle vdots } |
Elementos de G(4) continuam a acrescentar por um tempo, mas a base 3⋅2402653209{displaystyle 3cdot 2^{402653209}}
O valor 0 é encontrado na base 3⋅2402653211−1{displaystyle 3cdot 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 |
|---|---|
222+2+1{displaystyle 2^{2^{2}}+2+1} | 19 |
333+3{displaystyle 3^{3^{3}}+3} | 7,625,597,484,990 |
444+3{displaystyle 4^{4^{4}}+3} | ≈1.3×10154{displaystyle approx 1.3times 10^{154}}  |
555+2{displaystyle 5^{5^{5}}+2} | ≈1.8×102184{displaystyle approx 1.8times 10^{2184}}  |
666+1{displaystyle 6^{6^{6}}+1} | ≈2.6×1036,305{displaystyle approx 2.6times 10^{36,305}}  |
777{displaystyle 7^{7^{7}}} | ≈3.8×10695,974{displaystyle approx 3.8times 10^{695,974}}  |
888−1=7⋅8(7⋅87+7⋅86+7⋅85+7⋅84+7⋅83+7⋅82+7⋅8+7){displaystyle 8^{8^{8}}-1=7cdot 8^{(7cdot 8^{7}+7cdot 8^{6}+7cdot 8^{5}+7cdot 8^{4}+7cdot 8^{3}+7cdot 8^{2}+7cdot 8+7)}} | ≈6×1015,151,335{displaystyle approx 6times 10^{15,151,335}}  |
7⋅9(7⋅97+7⋅96+7⋅95+7⋅94+7⋅93+7⋅92+7⋅9+7){displaystyle 7cdot 9^{(7cdot 9^{7}+7cdot 9^{6}+7cdot 9^{5}+7cdot 9^{4}+7cdot 9^{3}+7cdot 9^{2}+7cdot 9+7)}} | ≈4.3×10369,693,099{displaystyle approx 4.3times 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.
Prova do Teorema de Goodstein |
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 444+4{displaystyle 4^{4^{4}}+4}
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.
Tamanho da sequencia como um função de valor inicial |
A função de Goodstein, G:N→N{displaystyle {mathcal {G}}:mathbb {N} to mathbb {N} ,!}
de Goodstein que começa com n. (Essa é uma função total até toda sequencia de Goodstein termine.) A taxa de crescimento extrema de G{displaystyle {mathcal {G}},!}
hierarquia de Hardy e as funções fα{displaystyle f_{alpha },!}
- Kirby and Paris (1982) provou que
G{displaystyle {mathcal {G}},!}(que é a mesma de fϵ0{displaystyle f_{epsilon _{0}},!}
); mais precisamente, G{displaystyle {mathcal {G}},!}
, e
Hϵ0{displaystyle H_{epsilon _{0}},!}
- (Para qualquer qualquer 2 funções f,g:N→N{displaystyle f,g:mathbb {N} to mathbb {N} ,!}
, f{displaystyle f,!}
é dita dominada g{displaystyle g,!}
se f(n)>g(n){displaystyle f(n)>g(n),!}
para todo suficientemente grande n{displaystyle n,!}
.)
- Cichon (1983) mostrou que
- G(n)=HR2ω(n+1)(1)−1,{displaystyle {mathcal {G}}(n)=H_{R_{2}^{omega }(n+1)}(1)-1,}
- ondeR2ω(n){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 n=2m1+2m2+⋯+2mk{displaystyle n=2^{m_{1}}+2^{m_{2}}+cdots +2^{m_{k}}}
with m1>m2>⋯>mk,{displaystyle m_{1}>m_{2}>cdots >m_{k},}
então
G(n)=fR2ω(m1)(fR2ω(m2)(⋯(fR2ω(mk)(3))⋯))−2{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 | G(n){displaystyle {mathcal {G}}(n)} | ||||
|---|---|---|---|---|---|
| 1 | 20{displaystyle 2^{0}}  | 2−1{displaystyle 2-1}  | Hω(1)−1{displaystyle H_{omega }(1)-1}  | f0(3)−2{displaystyle f_{0}(3)-2}  | 2 |
| 2 | 21{displaystyle 2^{1}}  | 21+1−1{displaystyle 2^{1}+1-1}  | Hω+1(1)−1{displaystyle H_{omega +1}(1)-1}  | f1(3)−2{displaystyle f_{1}(3)-2}  | 4 |
| 3 | 21+20{displaystyle 2^{1}+2^{0}}  | 22−1{displaystyle 2^{2}-1}  | Hωω(1)−1{displaystyle H_{omega ^{omega }}(1)-1}  | f1(f0(3))−2{displaystyle f_{1}(f_{0}(3))-2}  | 6 |
| 4 | 22{displaystyle 2^{2}} | 22+1−1{displaystyle 2^{2}+1-1}  | Hωω+1(1)−1{displaystyle H_{omega ^{omega }+1}(1)-1}  | fω(3)−2{displaystyle f_{omega }(3)-2}  | 3·2402653211 − 2 |
| 5 | 22+20{displaystyle 2^{2}+2^{0}}  | 22+2−1{displaystyle 2^{2}+2-1}  | Hωω+ω(1)−1{displaystyle H_{omega ^{omega }+omega }(1)-1}  | fω(f0(3))−2{displaystyle f_{omega }(f_{0}(3))-2}  | > A(4,4) |
| 6 | 22+21{displaystyle 2^{2}+2^{1}}  | 22+2+1−1{displaystyle 2^{2}+2+1-1}  | Hωω+ω+1(1)−1{displaystyle H_{omega ^{omega }+omega +1}(1)-1}  | fω(f1(3))−2{displaystyle f_{omega }(f_{1}(3))-2}  | > A(6,6) |
| 7 | 22+21+20{displaystyle 2^{2}+2^{1}+2^{0}}  | 22+1−1{displaystyle 2^{2+1}-1}  | Hωω+1(1)−1{displaystyle H_{omega ^{omega +1}}(1)-1}  | fω(f1(f0(3)))−2{displaystyle f_{omega }(f_{1}(f_{0}(3)))-2}  | > A(8,8) |
| 8 | 22+1{displaystyle 2^{2+1}}  | 22+1+1−1{displaystyle 2^{2+1}+1-1}  | Hωω+1+1(1)−1{displaystyle H_{omega ^{omega +1}+1}(1)-1}  | fω+1(3)−2{displaystyle f_{omega +1}(3)-2}  | > A3(3,3) = A(A(61, 61), A(61, 61)) |
⋮{displaystyle vdots } | |||||
| 12 | 22+1+22{displaystyle 2^{2+1}+2^{2}}  | 22+1+22+1−1{displaystyle 2^{2+1}+2^{2}+1-1}  | Hωω+1+ωω+1(1)−1{displaystyle H_{omega ^{omega +1}+omega ^{omega }+1}(1)-1}  | fω+1(fω(3))−2{displaystyle f_{omega +1}(f_{omega }(3))-2}  | > fω+1(64) > Número de Graham |
⋮{displaystyle vdots } | |||||
| 19 | 222+21+20{displaystyle 2^{2^{2}}+2^{1}+2^{0}}  | 222+22−1{displaystyle 2^{2^{2}}+2^{2}-1}  | Hωωω+ωω(1)−1{displaystyle H_{omega ^{omega ^{omega }}+omega ^{omega }}(1)-1}  | fωω(f1(f0(3)))−2{displaystyle f_{omega ^{omega }}(f_{1}(f_{0}(3)))-2}  | |
Aplicação para funções computáveis |
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.
