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

Notação base-n hereditária editar

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:

 

onde cada coeficiente   satisfaz  , e  . Por exemplo, em base 2,

 

Assim a representação base 2 de 35 é  . (Essa expressão pode ser escrita em notação binaria como 100011.) Similarmente, 100 pode ser

escrito em base 3:

 

Note que os expoentes por eles mesmos não são escritos na notação base-n. Por exemplos, a expressão acima inclui   e  . 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 é  , ele é escrito na notação base-2 hereditária como

 

usando o fato que   . Similarmente, 100 na notação base-3 hereditária é

 

Sequencias de Goodstein editar

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   3 Escreva 3 na notação base-3
3   3 Troque 2 para 3, e subtraia 1
4   3 Troque 3 para 4, e subtraia 1. Agora não contem mais 4
5   2 Nenhum 4 restou para trocar por 5. Apenas subtraia 1
6   1
7   0

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

Hereditary notation Value
  4
  26
  41
  60
  83
  109
   
  253
  299
   

Elementos de G(4) continuam a acrescentar por um tempo, mas a base  , eles chegam no maximo de   passos, e então começa seu primeiro e ultimo descida. O valor 0 é encontrado na base  . 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
  19
  7,625,597,484,990
   
   
   
   

         

 

         

 
   

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 editar

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   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,   é reduzido para   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.

Tamanho da sequencia como um função de valor inicial editar

A função de Goodstein,  , é definida tal que   é 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   pode ser calibrada por relaciona-lo com varios hierarquias ordinal-indexadas padroes de funções, tal que as funções   em uma

hierarquia de Hardy e as funções   na hierarquia de crescimento rapido de Löb e Wainer:

  • Kirby and Paris (1982) provou que
  contem aproximadamente a mesma taxa de crescimento como   (que é a mesma de  ); mais precisamente,   domina   para todo  , e

  domina  

(Para qualquer qualquer 2 funções  ,   é dita dominada   se   para todo suficientemente grande  .)
  • Cichon (1983) mostrou que
 
onde  é 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   with   então
 .

Alguns exemplos:

n  
1         2
2         4
3         6
4         3·2402653211 − 2
5         > A(4,4)
6         > A(6,6)
7         > A(8,8)
8         > A3(3,3) = A(A(61, 61), A(61, 61))
 
12         > fω+1(64) > Número de Graham
 
19        

Aplicação para funções computáveis editar

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.