Teorema de Goodstein

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde setembro de 2013).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Question book.svg
Esta página ou se(c)ção não cita fontes fiáveis e independentes (desde setembro de 2013). Por favor, adicione referências e insira-as no texto ou no rodapé, conforme o livro de estilo. Conteúdo sem fontes poderá ser removido.

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.

Notação base-n hereditária[editar | editar código-fonte]

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 = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_0,

onde cada coeficiente a_i satisfaz  0 \le a_i < n , e a_k\not=0. Por exemplo, em base 2,

35 = 32 + 2 + 1 = 2^5 + 2^1 + 2^0.

Assim a representação base 2 de 35 é  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:

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 2^5 e 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 é 2^5 + 2 + 1, ele é escrito na notação base-2 hereditária como

35 = 2^{2^2+1}+2+1,

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

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

Sequencias de Goodstein[editar | editar código-fonte]

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  2^1 + 1 3 Escreva 3 na notação base-3
3  3^1 + 1 - 1 = 3^1 3 Troque 2 para 3, e subtraia 1
4  4^1 - 1 = 3 3 Troque 3 para 4, e subtraia 1. Agora não contem mais 4
5  3 - 1 = 2 2 Nenhum 4 restou para trocar por 5. Apenas subtraia 1
6  2 - 1 = 1 1
7  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
 2^2 4
 3^3 - 1 = 2 \cdot 3^2 + 2 \cdot 3 + 2 26
 2 \cdot 4^2 + 2 \cdot 4 + 1 41
 2 \cdot 5^2 + 2 \cdot 5 60
 2 \cdot 6^2 + 2 \cdot 6 - 1 = 2 \cdot 6^2 + 6 + 5 83
 2 \cdot 7^2 + 7 + 4 109
 \vdots  \vdots
 2 \cdot 11^2 + 11 253
 2 \cdot 12^2 + 12 - 1 = 2 \cdot 12^2 + 11 299
 \vdots  \vdots

Elementos de G(4) continuam a acrescentar por um tempo, mas a base 3 \cdot 2^{402653209}, eles chegam no maximo de 3 \cdot 2^

{402653210} - 1 passos, e então começa seu primeiro e ultimo descida. O valor 0 é encontrado na base 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
 2^{2^2} + 2 + 1 19
 3^{3^3} + 3 7,625,597,484,990
 4^{4^4} + 3  \approx 1.3 \times 10^{154}
 5^{5^5} + 2  \approx 1.8 \times 10^{2184}
 6^{6^6} + 1  \approx 2.6 \times 10^{36,305}
 7^{7^7}  \approx 3.8 \times 10^{695,974}

 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)} + 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 + 7 \cdot 8^{(8+2)} + 7 \cdot 8^{(8+1)} + 7 \cdot 8^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

 \approx 6 \times 10^{15,151,335}

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)} + 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 + 7 \cdot 9^{(9+2)} + 7 \cdot 9^{(9+1)}+ 7 \cdot 9^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

 \approx 4.3 \times 10^{369,693,099}
 \vdots  \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[editar | editar código-fonte]

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 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, \omega^{\omega^\omega} + \omega é reduzido para \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.

Tamanho da sequencia como um função de valor inicial[editar | editar código-fonte]

A função de Goodstein, \mathcal{G}: \mathbb{N} \to \mathbb{N} \,\!, é definida tal que \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 \mathcal{G}\,\!

pode ser calibrada por relaciona-lo com varios hierarquias ordinal-indexadas padroes de funções, tal que as funções H_\alpha\,\! em uma

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

  • Kirby and Paris (1982) provou que
\mathcal{G}\,\! contem aproximadamente a mesma taxa de crescimento como H_{\epsilon_0}\,\! (que é a mesma de f_

{\epsilon_0}\,\!); mais precisamente, \mathcal{G}\,\! domina H_\alpha\,\! para todo \alpha < \epsilon_0\,\!, e

H_{\epsilon_0}\,\! domina \mathcal{G}\,\!.

(Para qualquer qualquer 2 funções f, g: \mathbb{N} \to \mathbb{N} \,\!, f\,\! é dita dominada g\,\! se f(n) > 

g(n)\,\! para todo suficientemente grande n\,\!.)
  • Cichon (1983) mostrou que
 \mathcal{G}(n) = H_{R_2^\omega(n+1)}(1) - 1,
ondeR_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 = 2^{m_1} + 2^{m_2} + \cdots + 2^{m_k} with  m_1 > m_2 > \cdots > m_k, então
 \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 \mathcal{G}(n)
1 2^0 2 - 1 H_\omega(1) - 1 f_0(3) - 2 2
2 2^1 2^1 + 1 - 1 H_{\omega + 1}(1) - 1 f_1(3) - 2 4
3 2^1 + 2^0 2^2 - 1 H_{\omega^\omega}(1) - 1 f_1(f_0(3)) - 2 6
4 2^2 2^2 + 1 - 1 H_{\omega^\omega + 1}(1) - 1 f_\omega(3) - 2 3·2402653211 − 2
5 2^2 + 2^0 2^2 + 2 - 1 H_{\omega^\omega + \omega}(1) - 1 f_\omega(f_0(3)) - 2 > A(4,4)
6 2^2 + 2^1 2^2 + 2 + 1 - 1 H_{\omega^\omega + \omega + 1}(1) - 1 f_\omega(f_1(3)) - 2 > A(6,6)
7 2^2 + 2^1 + 2^0 2^{2 + 1} - 1 H_{\omega^{\omega + 1}}(1) - 1 f_\omega(f_1(f_0(3))) - 2 > A(8,8)
8 2^{2 + 1} 2^{2 + 1} + 1 - 1 H_{\omega^{\omega + 1} + 1}(1) - 1 f_{\omega + 1}(3) - 2 > A3(3,3) = A(A(61, 61), A(61, 61))
\vdots
12 2^{2 + 1} + 2^2 2^{2 + 1} + 2^2 + 1 - 1 H_{\omega^{\omega + 1} + \omega^\omega + 1}(1) - 1 f_{\omega + 1}(f_\omega(3)) - 2 > fω+1(64) > Número de Graham
\vdots
19 2^{2^2} + 2^1 + 2^0 2^{2^2} + 2^2 - 1 H_{\omega^{\omega^\omega} + \omega^\omega}(1) - 1 f_{\omega^\omega}(f_1(f_0(3))) - 2

Aplicação para funções computáveis[editar | editar código-fonte]

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.