Sequências de Goodstein: o poder do desvio via infinito

A autora original é Michèle Artigue, Ferdinando Arzarello and Susanna Epp.

O estudo da evolução de um fenômeno natural leva, com frequência, ao estudo de sequências numéricas, especialmente ao estudo dos seus comportamentos assintóticos (ou de longo prazo) e de suas convergências. No ensino médio encontramos com frequência sequências aritméticas, polinomiais, exponenciais e logarítmicas, mas algumas outras sequências de definição bem simples podem exibir um comportamento mais complexo. Exemplo disso são as sequências caóticas que surgem nos estudo de sistemas dinâmicos (ver [1]) e a sequência Siracusa (ou “3n+1“) , introduzida por Luther Collatz, em 1937. A sequência Siracusa tem desafiado os matemáticos por décadas, e apesar de se já ter calculado uma quantidade imensa de seus valores, até o momento não se sabe se a sequência é infinita ou finita e se sempre termina em 1 (ver [2])

As sequências consideradas neste artigo foram introduzidas pelo lógico britânico R.L. Goodstein, em 1944 (ver [3]), e exibem um tipo diferente de comportamento estranho. Os seus valores iniciais crescem tão rapidamente que somos levados a acreditar que elas tendem a infinito, mas, para a nossa surpresa, eles sempre terminam decrescendo até finalmente alcançarem 0. A prova deste fato requer uma generalização do princípio da boa ordem dos números inteiros (ver [4]) para os números transfinitos, mas a ideia básica não é difícil de entender. Para explicá-la, como Hodgson [5], primeiramente introduzimos um tipo de sequência, chamada Goodstein Fraca, que é mais simples, mas relacionada à sequência de Goodstein.

1. Sequências de Goodstein fracas

Seguindo Hodgson, ilustramos a definição de sequências de Goodstein fraca começando com o número 266. Como qualquer número inteiro positivo, ele possui uma única decomposição como soma de potências de 2 (ver[2]): 266=2^8+2^3+2^1. A sequência de Goodstein fraca com termo inicial u_{0}=266 é definida do seguinte modo: para obter u_1, substituímos a base 2 na expansão acima pela base 3 e, em seguida, subtraímos 1. Reescrevemos o resultado na base 3: u_1=3^8+3^3+3^1-1=3^8+3^3+2.3^0=6 590. Para obter u_2, começamos substituindo a base 3 pela base 4 na decomposição de u_1 e subtraímos 1 do resultado. Assim u_2=4^8+4^3+2-1=65 601. Enquanto não obtivermos 0 podemos proceder do mesmo modo: substituindo a base k da expansão pelo seu sucessor k+1, subtraindo 1 e escrevendo o resultado na nova base, k+1.

u_0 &= 2^8 + 2^3 + 2^1 = 266
u_1 &= 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590
u_2 &= 4^8 + 4^3 + 2 - 1 = 4^8 + 4^3 + 1 = 65,601
u_3 &= 5^8 + 5^3 + 1 - 1 = 5^8 + 5^3 = 390,750
u_4 &= 6^8 + 6^3 - 1 = 6^8 + 5 . 6^2 + 6^2 - 1 = 6^8 + 5 . 6^2 + 5 . 6 + 6 - 1\\ = 6^8 + 5 . 6^2 + 5 . 6^1 + 5 = 1,679,831
u_5 &= 7^8 + 5 . 7^2 + 5 . 7^1 + 5 - 1 = 7^8 + 5 . 7^2 + 5 . 7^1 + 4 = 5,765,085
u_6 &= 8^8 + 5 . 8^2 + 5 . 8^1 + 4 - 1 = 8^8 + 5 . 8^2 + 5 . 8^1 + 3 = 16,777,579
u_7 &= 9^8 + 5 . 9^2 + 5 . 9^1 + 3 - 1 = 9^8 + 5 . 9^2 + 5 . 9^1 + 2 = 43,047,173
u_8 &= 10^8 + 5 . 10^2 + 5 . 10^1 + 2 - 1 = 10^8 + 5 . 10^2 + 5 . 10^1 + 1 = 100,000,551
u_9 &= 11^8 + 5 . 11^2 + 5 . 11^1 + 1 - 1 = 11^8 + 5 . 11^2 + 5 . 11^1 = 214,359,541
u_{10} &= 12^8 + 5 . 12^2 + 5 . 12^1 - 1 = 12^8 + 5 . 12^2 + 4 . 12^1 + 12 - 1\\ = 12^8 + 5 . 12^2 + 4 . 12^1 + 11 = 429,982,475

Tabela 1: Termos iniciais de uma sequência fraca de Goodstein

Como você pode ver, os termos da sequência rapidamente tornam-se muito grandes, portanto, é natural perguntar se todas as sequências construídas dessa maneira crescem da mesma forma. Mas, de fato, isso não acontece. Por exemplo, se u_0=1, então u_1=1-1=0. Se tomarmos u_0=2=2^1, então, u_1=3^1-1=2, u_2=2-1=1 e u_3=1-1=0 (pois a base para u_2 é 4 e a base para u_3 é 5). Você pode verificar que se u_0=3, então os termos da sequência nunca são maiores do que 3 e atingem o valor 0 em cinco passos (ver [7]). Entretanto, desde que a decomposição para os valores iniciais u_0 incluam potências de 2 maiores do que 2^1, o crescimento inicial da sequência é muito rápido (como no caso u_0=266). Isso leva-nos a crer que a sequência cresce arbitrariamente ( isto é, tende a infinito). Como o fato de subtrair meramente 1 em cada passo pode contrabalançar o enorme crescimento dos termos que são obtidos pela substituição do inteiro da base pelo seu sucessor?

Ainda assim, vamos olhar com mais cuidado para as espressões na tabela 1 acima. Apesar de os primeiros termos da sequência de valor inicial 266 crescerem rapidamente, os expoentes das representações em bases sucessivas tendem a diminuir. Por exemplo, o expoente 1 de 2 no termo u_0 já não existe na expansão de u_1. Analogamente, o expoente 3 em u_3 é substituído por 2 em u_4 e ao chegarmos a u_9 torna-se igual a 1. O expoente 8 em u_{10} irá reduzir-se a 7 e continuará a reduzir-se mais adiante.

Esta é a característica comum a todas as sequências de Goodstein que permitirá provar que todas convergem a 0. Para ver isso, precisamos lançar mão, como prometido, dos números ordinais.

2. Números ordinais transfinitos e boa ordenação

Em linguagem comum, números ordinais são usados para indicar posição em uma lista: primeiro, segundo, terceiro, etc. De fato, os números inteiros positivos podem ser usados para posicionar dessa maneira os elementos de um conjunto finito qualquer.A ideia de número ordinal transfinito estende a noção de número ordinal. Ela foi desenvolvida por Georg Cantor em uma série de artigos publicados no final do Século XIX. Como o conjunto dos números inteiros é infinito, se imaginarmos começando com 0 e contando sucessivamente os inteiros, nunca terminaremos. Porém, podemos imaginar que existe um “número” \omega que é o primeiro número maior do que qualquer número inteiro positivo. \omega é chamado um número ordinal “transfinito”, porque existem infinitos números inteiros positivos menores do que \omega. O sucessor de \omega, denotamos por \omega +1, que é seguido de \omega + 2 e assim por diante. O menor ordinal que é maior do que qualquer ordinal da forma \omega +n é denotado por \omega + \omega ou \omega.2 (ver [8]) e o menor ordinal que é maior do que qualquer ordinal da forma \omega.n+m (com m um ordinal menor do que \omega.n) é denotado por {\omega}^2. O menor ordinal maior do que qualquer ordinal da forma {\omega}^n+m (com m um ordinal menor do que {\omega}^n) é denotado por {\omega}^{\omega}.


Rendered by QuickLaTeX.com

Continuando, {\omega}^{\omega} é seguido por {\omega}^{\omega}+1, {\omega}^{\omega} +2, …,{\omega}^{2\omega}+1,…,{\omega}^{2\omega}+\omega, …, {\omega}^{{\omega}^{\omega}},… e definimos \epsilon_0 como o menor número ordinal maior do que todas as somas de potências iteradas de \omega e continuamos com o processo indefinidamente. De fato, todos os ordinais considerados até aqui constituem apenas o início de uma cadeia de ordinais, pois formam um conjunto enumerável, isto é, podem ser colocados em correspondência 1 a 1 com os números inteiros positivos.

Ordinais e boa ordenação:

Uma diferença significativa entre ordinais transfinitos e inteiros não negativos é que cada inteiro maior do que 0 possui um antecessor imediato, enquanto ordinais do tipo \omega, \omega.2 e {\omega}^{\omega}, não. Entretanto, assim como os números inteiros, o conjunto de números ordinais estendido é “bem ordenado” no sentido de que todo subconjunto não vazio de ordinais possui um menor elemento. Esta propriedade implica na não existência de uma sequência infinita estritamente decrescente de números ordinais. Suponha o contrário, e seja u_0,u_1,u_2,... uma tal sequência. Denote por S o conjunto dos seus elementos. Como S é não vazio, existe o menor elemento, digamos \alpha=u_k, para algum índice k. Mas como a sequência é estritamente decrescente, u_{k+1}<u_k=\alpha, ou seja, \alpha não é o menor elemento de S. Obtivemos assim uma contradição.

Mostraremos agora como usar os números ordinais para provar o resultado sobre sequências de Goodstein fracas.

3. Provando que uma sequência de Goodstein fraca converge a zero

A cada sequência de Goodstein fraca (u_n) associamos uma sequência estritamente
decrescente de ordinais (\alpha_n) substituindo a base da expansão de u_n pelo ordinal \omega. Observe que a decomposição de u_n possui base n+2, pois, como vimos, a base inicial de u_0 é 2, a de u_1 é 3 e em cada passo, a base é acrescida de 1. Por exemplo, na sequência associada a 266, os termos iniciais da sequência \alpha_n são exibidos na Tabela 2;


Rendered by QuickLaTeX.com

Tabela 2: A sequência de ordinais correpondentes a uma sequência Goodstein fraca

Por construção, cada termo \alpha_n é maior do que o termo correspondente u_n, mas enquanto (u_n) é uma sequência crescente, a sequência (\alpha_n) é decrescente. A razão disso é que na decomposição de u_n na base n+2, o termo unitário ( ou o resto da divisão de u_n pela base) pode ser nulo ou não e a passagem de um termo para o termo seguinte pode ocorrer de duas maneiras:

  • Se o termo unitário é não nulo, então como em cada passo subtraímos 1, o termo unitário diminui de 1. (Na Tabela 2, isso ocorre na passagem de u_1 para u_2, de u_2 para u_3, de u_4 para u_5 e de u_5 para u_6).
  • Se o termo unitário de u_n é nulo, quando escrevemos u_n na nova base, o termo do menor expoente é particionado em duas parcelas.(Na Tabela 2, isso ocorre quando vamos de u_0 para u_1, de u_3 para u_{4} e de u_9 para u_{10}. Veja a Tabela 1 para o caminho detalhado.

Observe que em ambos os casos, o novo termo \alpha_n correspondente é estritamente menor do que o termo que o precede.

Como os ordinais são bem ordenados, não existe uma sequência estritamente decrescente infinita de ordinais, portanto, deve existir o menor elemento do conjunto \{ \alpha_n \}. Isto é, existe um índice m tal que \alpha_m=0. Além disso, como 0\leq u_n \leq \alpha_n, para todo n, então u_m=0. Em outras palavras, a sequência (u_n) atinge 0 em um número finito de passos, apesar de o número de passos ser em geral, extremamente grande.

Convidamos o leitor a escrever os termos das sequências (u_n) e (\alpha_n) para a condição inicial u_0=5. Para qual valor de n teremos \alpha_n=\omega?
Qual é o valor correspondente de u_n ? Quais são os termos seguintes das duas sequências? (ver[10]).

Estamos agora preparados para examinar as sequências de Goodstein, cuja definição difere um pouco das sequências de Goodstein fracas e o modo que crescem é ainda mais espetacular. Entretanto, surpreendentemente, a estratégia para provar o seu decrescimento a zero é semelhante ao que acabamos de fazer.

4. Sequências de Goodstein

Considere novamente a representação na base 2 de 266: 2^8+2^3+2^1. Agora, escreva os expoentes na base 2: 3=2^{1}+1, 8=2^3=2^{2^1+1}. Como resultado, obtemos a expressão de 266 escrita inteiramente sem usar números maiores do que a base 2. Iniciamos a sequência de Goodstein (m_n) com m_0=266. Para construir m_1, substituímos todas as ocorrências de 2 na expansvo acima por 3 e subtraímos 1. Reescreva o resultado sem usar números maiores do que 3. Continue esse processo iterativamente para obter os termos sucessivos de m_n como é mostrado na Tabela 3 (ver[11]).

m_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1
m_1 = 3^{3^{3+1}} + 3^{3+1} +3^1 - 1 = 3^{3^{3+1}} + 3^{3+1} + 2\\ = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38}
m_2 = 4^{4^{4+1}} + +4^{4+1} +1 \approx 10^{616}
m_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}
m_4 = 6^{6^{6+1}} + 6^{6+1} -1 = 6^{6^{6+1}} + 5.6^6 + 5.6^5 + 5. 6^4 +5.6^3 + 5.6^2 +5.6^1 + 5\\ \approx10^{217832}
m_5 = 7^{7^{7+1}} + 5.7^7 + 5.7^5 + 5. 7^4 +5.7^3 + 5.7^2 +5.7^1 + 4\\ \approx 10^{4 871 822}

Tabela 3.

Como você pode ver, o crescimento dos termos é espetacular e, mesmo assim, essa sequência, como todas as sequências de Goodstein, após um certo tempo começa a decrescer para finalmente convergir para 0 (atingir 0) . A prova disso é muito similar à prova usada para as sequências de Goodstein fracas. Como naquele caso, associamos a uma sequência (u_n) uma sequência \beta_n substituindo cada ocorrência da base de u_n por \omega.

Os primeiros termos da sequência (\beta_n) correspondentes à Tabela 3 são os seguintes:

\beta_0 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + \omega^1
\beta_1 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + 2
\beta_2 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + 1
\beta_3 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1}
\beta_4 = \omega^{\omega^{\omega +1}} + 5. \omega^{\omega} + 5 . \omega^{5} + 5 . \omega^{4} + 5 . \omega^{3} + 5 . \omega^{2} + 5 . \omega^{1} + 5
\beta_5 = \omega^{\omega^{\omega +1}} + 5. \omega^{\omega} + 5 . \omega^{5} + 5 . \omega^{4} + 5 . \omega^{3} + 5 . \omega^{2} + 5 . \omega^{1} + 4

A sequência de Goodstein (\beta_n) de números ordinais é estritamente decrescente, o que implica que possui menor elemento. Mas, como toda vez que computamos um termo não nulo da sequência, podemos computar o termo seguinte (que é ainda menor), então, podemos concluir que o menor elemento é 0. Um procedimento semelhante pode ser usado para qualquer sequência de Goodstein.

A aritmética dos números inteiros é chamada aritmética de Peano porque foi o matemático Giuseppe Peano quem primeiro formulou os seus axiomas. O que é notável na prova acima é que as ferramentas que usamos estão além da axiomática de Peano para provar um resultado totalmente formulado dentro dessa axiomática. Em outras palavras, a prova usa uma teoria geral de conjuntos que inclui os ordinais transfinitos para provar um teorema sobre números inteiros não negativos, isto é, toda sequência de Goodstein converge a 0. É natural perguntar se a convergência da sequência de Goodstein pode ser provada sem a utilização dos ordinais transfinitos. A resposta é não! Isso foi provado em 1982, por Lauri Kirby e Jeff Paris (ver [12]), aproximadamente 40 anos depois que as sequências foram introduzidas. Eles mostraram que se a convergência pudesse ser provada usando apenas o princípio da boa ordenação dos inteiros (isto é, dentro da aritmética de Peano) então o teorema sobre sequências Goodstein poderia ser reduzido a um teorema de Geutzen (1936), a partir do qual a consistência da aritmética de Peano poderia ser deduzida. Mas sabemos, pelo Teorema da Incompletude de Gödel (1931), que a consistência da aritmética não pode ser provada usando apenas axiomas desta aritmética. Portanto, é inútil os matemáticos gastarem energia para encontrar tal prova!

Por outro lado, o que pode ser considerado surpreendente é que a convergência das sequências de Goodstein fracas pode ser provada dentro da aritmética de Peano. A razão essencialmente é que os termos da sequência de ordinais correspondentes são menores do que {\omega}^{\omega}. Uma prova disso foi dada por E.Cichon, que introduziu as sequências de Goodstein fracas, em 1983,(ver [13)]. A cada termo u_n de uma seqência de Goodstein fraca, podemos associar uma m-upla de coeficientes da decomposição na base n+2 e mostrar que essas m-uplas satisfazem uma boa ordem lexicográfica estritamente decrescente.

5. Sequências de Goodstein e o jogo Hidra

Kirby e Paris mencionam em seu artigo (ver [14]) um outro processo, o jogo Hidra, que possui muitas semelhanças com as sequências de Goodstein. O nome do jogo vem da mitologia grega, de um combate entre Hércules e um animal de muitas cabeças: a Hidra (Hidra de Lerna). Cada vez que uma cabeça da Hidra é cortada, duas outras surgem em seu lugar. No jogo, a Hidra é modelada por uma árvore e as cabeças são vértices terminais ou folhas das árvores. Se Hércules corta uma cabeça que não está diretamente conectada à raiz da árvore, a aresta que chega à cabeça é eliminada, mas duas novas cabeças crescem a partir do nó localizado dois níveis abaixo da cabeça cortada. Isso pode ser feito de diversas maneiras. No exemplo de Kyrby e Paris, usado também por Hodgson ( ver [4]), se uma cabeça é cortada no passo n do jogo a Hidra gera n cópias da parte da árvore acima do nó do qual o ramo foi removido. No diagrama abaixo, a parte cortada é mostrada em linha tracejada, a parte que é regenerada é mostrada em vermelho e a parte nova da árvore está em azul.

é possível provar que qualquer que seja a configuração das cabeças da Hidra e qualquer que seja a estratégia empregada por Hércules, ele conseguirá cortar todas as cabeças, apesar de isso acontecer após um tempo extraordinariamente longo.

Como no caso da convergência da sequência de Goodstein, a prova é baseada na relação entre árvores sucessivas e uma sequência decrescente de ordinais. Como você poderia imaginar pelos diagramas acima, as árvores tornam-se cada vez mais abertas, mas as alturas decrescem no longo prazo. Por fim, Hércules pode eliminar todas as cabeças que encontram-se em mais de um nível acima da raiz e neste momento (como ilustrado no passo 3) ele pode cortar as cabeças restantes sem gerar novas cabeças.

6. O que nos ensinam esses exemplos?

Os exemplos deste artigo são interessantes por várias razões. Eles mostram que a lógica matemática é relevante para além da metamatemática, que teoremas do tipo Teorema da Incompletude de Gödel, e objetos tais como os números transfinitos são necessários para o estudo de objetos comuns da matemática como sequências de inteiros e árvores matemáticas (grafos). Ao mostrar que uma propriedade dos números inteiros pode ser provada usando-se a teoria geral dos conjuntos mas não com a aritmética de Peano, os exemplos também chamam a nossa atenção para o cenário teórico e linguístico no qual a prova se desenvolve. Neste caso, eles mostram que a aritmética de Peano é mais fraca do que a teoria geral dos conjuntos.

Uma outra lição a partir desses exemplos é a abordagem de um problema mais difícil (convergência das sequências de Goodstein) por meio de um problema mais acessível (convergência das sequências de Goodstein fracas). Além disso, os exemplos mostram como um exemplo genérico- a sequência cujo valor inicial é 266- pode ilustrar todas as propriedades do caso geral. Os exemplos são ilustrativos também porque mostram as limitações da nossa intuição. Sequências que aparentemente tendem a infinito, convergem, pois após um número finito de etapas atingem 0. Finalmente, os exemplos permitem-nos ver tanto o poder quanto as limitações da tecnologia pois esta nos dá a sensação concreta de crescimento rápido dos termos da sequência, mas sua utilidade é limitada quando lidamos com a explosão numérica gerada pela definição da sequência.

Referências

[1] Elert, Glenn (1995-2007). The Chaos HypertextbookTM, Bodnar, M. & Ramsden P. Discrete Logistic Equation, Wolfram Demonstrations Project. Perrin, D. (2008). La suite logistique et le chaos.

[2] Lagarias, J. C. (2001) The Syracuse Problem. In Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer.

[3] Goodstein,R.L. (1944) On the Restricted Ordinal Theorem, Journal of Symbolic Logic, 9,33-41.

[4] O princípio da boa ordenação para números inteiros diz que se todo elemento em um conjunto S de inteiros é maior do que um inteiro m, então S possui o menor elemento.

[5] Hodgson B. (2004). Herculean of Sisyphean tasks? EMS Newsletter, March 2004, pp. 11-16.

[6] Dado um inteiro positivo b>1, todo número inteiro positivo n possui uma única decomposição na base b: n=d_m.b^m+d_{m-1}.b^{m-1}+...+d_1.b^1+d_0, com todos os coeficientes d_i números inteiros entre 0 e b-1 e d_m \neq 0. Note que b^m < n <b^{m+1}. Esta é uma generalização do modo de decompor um número na base dez.

[7] Se u_0=3= 2^1+1, então u_1=3^1+1-1=3,u_2=4^1-1=3, u_3=3-1=2, u_4=2-1 e u_5=1-1=0. A partir de u_3, cada termo sucessivo é igual a 1 a menos do que o anterior porque em cada caso a base é maior do que o termo precedente.

[8] Estendemos as operações de soma e o produto de inteiros para os números ordinais transfinitos, observando, entretanto que a comutatividade da soma e do produto não é preservada.

[9] Em geral, quando o termo unitário de u_n é zero, então o menor termo de u_n tem a forma a.{(b-1)}^k, com k um inteiro positivo e a<b-1. Portanto, como a base é aumentada de 1 e subtraímos 1 do resultado, a decomposição para u_{n+1} termina em a.b^k-1=(a-1)b^k+b^k-1=(a-1)b^k+(b-1)b^{k-1}+(b-1)b^{k-2}+(b-1)b^{k-3}+...+(b-1)b^1+(b-1). Logo, o coeficiente da menor potência da base é diminuído de 1 e o termo unitário torna-se 1 a menos que a nova base.

[10] As soluções são as seguintes: \alpha_n=\omega quando u_{29}={31}^1. Para obter u_{30}, substituímos a base 31 pela base 32 e subtraímos 1. Logo u_{30}={32}^1-1=31. Como a base do termo u_{30} é 32 e 31<32, começando com o índice 30 as sequências (u_n) e (\alpha_n) possuem exatamente os mesmos termos. Eles formam um progressão aritmética decrescente com diferença constante igual a -1, e segue-se que u_{61}=\alpha_{61}=0.

[11] The terms of {mn} shown in Table 3 were computed using http://www.wolframalpha.com.

[12] Kirby,L. e Paris, J. (1982) Accessible Independence Results for Peano Arithmetic, Bulletin of the London Mathematical Society, 14, 285-293.

[13] Cichon,E.A. (1983). A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretical Methods, Proceedings of the AMS,87,704-706.

[14] Bauer,A. Java applet for the Hydra Game ( Se o applet não funcionar em um brouser, tente em outro.)

Este post está disponível em: Inglês, Francês, Alemão, Italiano, Espanhol, Árabe, Khmer

This entry was posted in Vignettes. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *