Teorema de Goodstein

Em matemática , e mais precisamente em lógica matemática , o teorema de Goodstein é uma declaração aritmética relacionada a sequências , chamadas sequências de Goodstein . As sequências de Goodstein são sequências de inteiros de crescimento inicial extremamente rápido, e o teorema afirma que (apesar das aparências) toda sequência de Goodstein termina em 0. Ela deve seu nome ao seu autor, o matemático e lógico Reuben Goodstein .

O teorema de Goodstein não é demonstrável na aritmética de Peano de primeira ordem, mas pode ser demonstrado em teorias mais fortes, como a teoria dos conjuntos ZF (uma prova simples usa ordinais até ), ou a aritmética de segunda ordem . O teorema, portanto, dá, no caso particular da aritmética de primeira ordem, um exemplo de uma afirmação indecidível mais natural do que aquelas obtidas pelos teoremas da incompletude de Gödel . $\ varejpsilon _ {0}$

Definição de uma sequência de Goodstein

Antes de definir uma sequência de Goodstein, vamos primeiro definir a notação hereditária na base n . Para escrever um número inteiro natural com tal notação, primeiro o escrevemos na forma clássica da decomposição de base n :

a_ {k} n ^ {k} + a _ {{k-1}} n ^ {{k-1}} + \ cdots + a_ {0}

onde cada um é um número inteiro entre 0 e n-1 . Em seguida, aplicamos o mesmo tratamento aos expoentes k , k-1 , ... iterativamente, até obtermos uma expressão que consiste apenas em inteiros entre 0 e n-1 . $ter}$

Por exemplo, 35 é escrito na base 2 e a notação hereditária (também conhecida como pontuação iterada ) na base 2 . $2 ^ {5} + 2 + 1$ ${\ displaystyle 2 ^ {2 ^ {2} +1} + 2 ^ {1} +1}$

A sequência de Goodstein de um inteiro m , denotada por G ( m ), é definida como segue: o primeiro elemento da sequência é m . Para obter o seguinte elemento, escrevemos m em notação hereditária na base 2, depois transformamos cada 2 em 3 e, finalmente, subtraímos 1 do resultado. Temos então o segundo elemento da sequência. Para obter o terceiro, escrevemos o elemento previamente calculado em notação hereditária na base 3, mudamos os 3s para 4 e subtraímos 1. Continuamos assim até chegarmos a 0 (o que sempre acontece, como mostrado abaixo).

Mais formalmente, a sequência é definida pela iteração das duas operações a seguir: na etapa n (colocando ): ${\ displaystyle G (m)}$ ${\ displaystyle G_ {1} (m) = m}$

Escreva o número inteiro em notação hereditária na base n + 1 e substitua n + 1 por n + 2; ${\ displaystyle G_ {n} (m)}$
Subtraia 1; é assim que conseguimos . ${\ displaystyle G_ {n + 1} (m)}$

Declaração do teorema

Teorema de Goodstein - qualquer que seja o valor inicial de m , a sequência de Goodstein G ( m ) termina com 0.

Exemplos de suítes Goodstein

As primeiras sequências de Goodstein terminam rapidamente.

Assim, para G (1):
- $G_1$ (1) = 1,
- $G_2$ (1) = 1 - 1 = 0

E para G (2):
- $G_1$ (2) = 2 = 2 1
- $G_2$ (2) = 3 1 - 1 = 2
- $G_ {3}$ (2) = 2 - 1 = 1
- ${\ displaystyle G_ {4}}$ (2) = 1 - 1 = 0

Para G (3):

Sediada	Cálculo de (3) $G_ {n}$	Notação hereditária	Notas
2	$G_1$ = 3	3 = (2 1 +1)	A notação hereditária é mostrada entre parênteses
3	$G_2$ = (3 1 +1) −1 = 3	3 = (3 1 )	Mudamos 2 para 3, então subtraímos 1
4	$G_ {3}$ = (4 1 ) −1 = 3	3 = (3)	Mudamos 3 para 4 e então subtraímos 1
5	${\ displaystyle G_ {4}}$ = (3) -1 = 2	2 = (2)	Uma vez que a base usada é maior do que os dígitos da decomposição, as alterações de base subsequentes não têm efeito.
6	${\ displaystyle G_ {5}}$ = (2) -1 = 1	1 = (1)
7	${\ displaystyle G_ {6}}$ = (1) -1 = 0	0

Mas as sequências de Goodstein geralmente crescem durante um grande número de estágios, como veremos mais precisamente na última seção . Por exemplo, as sequências G (4) e G (5) começam da seguinte forma:

Valor	Notação hereditária
4	2 2
26	2 3 2 + 2 3 + 2
41	2 4 2 + 2 4 + 1
60	2 5 2 + 2 5
83	2 6 2 + 6 + 5
109	2 7 2 + 7 + 4
	...
253	2 11 2 + 11
299	2 12 2 + 11
	...
1058	2 23 2
1151	24 2 + 23 24 + 23
	...

Valor	Notação hereditária
5	2 2 +1
27	3 3
255	3 4 3 + 3 4 2 + 3 4 + 3
467	3 5 3 + 3 5 2 + 3 5 + 2
775	3 6 3 + 3 6 2 + 3 6 + 1
1197	3 7 3 + 3 7 2 + 3 7
1751	3 8 3 + 3 8 2 + 2 8 + 7
	...
10830	3 15 3 + 3 15 2 + 2 15
13087	3 16 3 + 3 16 2 + 16 + 15
	...
92287	3 31 3 + 3 31 2 + 31
101407	3 32 3 + 3 32 2 + 31
	...
762048	3 63 3 + 3 63 2
798719	3 64 3 + 2 64 2 + 63 64 + 63
	...

No que diz respeito à sequência G (4), o fenômeno observado para as bases 6, 12 e 24 é reproduzido para todas as bases da forma p = 3 × 2 n : o valor anterior não inclui um termo unitário (termo de (p- 1) 0 ) e, portanto, aparece na base p o termo de potência 0 igual a (p-1), com redução simultânea em uma unidade do termo de potência 1 ou 2.

Assim, quando alcançamos a base b = 3 × 2 27 - 1 = 402 653 183, o termo da sequência é igual a b 2 = 162 129 585 780 031 489. O próximo termo é ( b + 1) 2 - 1 , isto é, na base ( b + 1): b ( b + 1) + b , e o termo seguinte será, portanto, b ( b + 2) + b - 1, etc., de modo que não há mais nenhum termo de potência 2 ou maior na notação hereditária.

Quando alcançamos a base B = ( b + 1) 2 b - 1 = 3 × 2 402 653 210 - 1, o termo da sequência é igual a B (a sequência também foi constante da base ( B + 1) / 2). O próximo valor é, portanto, B-1, ou seja, a sequência finalmente começa a diminuir e atinge o valor zero para a base 2 B + 1 = 3 × 2 402 653 211 - 1 , que é d 'em outro lugar a Woodall número (porque 3 × 2 402 653 211 = 402 653 184 × 2 402653184 ). .

A base sobre a qual G (4) posterior termina com mais de 120 milhões de números, o que significa que o número de termos da seqüência G (4) é da ordem de 10 120 milhões .

Embora a sequência G (5) não cresça muito mais rápido, ela cresce muito mais, e as notações exponenciais usuais não nos permitem mais expressar a maior base alcançada. Posando:

g (n) = n2 ^ {n}

g ^ {k} = g \ circ g \ circ \ cdots \ circ g

k vezes

M = g ^ {3} (64) = 2 ^ {{70 + 2 ^ {{70}} + 2 ^ {{70}} 2 ^ {{2 ^ {{70}}}}}}

N = g ^ {M} (M), \ P = g ^ {N} (N), \ Q = g ^ {P} (P),

o número de termos da sequência G (5) é então Q - 2 (consulte a última seção para uma justificativa desse cálculo). Este número não pode ser expresso exatamente usando a notação de seta de Knuth , mas é (nesta notação) da ordem de 2 ↑↑↑ 6, ou novamente, usando a função de Ackermann , da ordem de A (5, 4).

No entanto, esses dois exemplos ainda não dão uma ideia suficiente de quão rápido a sequência de Goodstein pode crescer. Assim, G (19) cresce muito mais rápido e começa da seguinte forma:

Valor	Notação hereditária
19	$2 ^ {{2 ^ {2}}} + 2 + 1$
7 625 597 484 990	$3 ^ {{3 ^ {3}}} + 3$
cerca de 1,3 × 10 154	$4 ^ {{4 ^ {4}}} + 3$
cerca de 1,8 × 10 2 184	$5 ^ {{5 ^ {5}}} + 2$
cerca de 2,6 × 10 36 305	$6 ^ {{6 ^ {6}}} + 1$
cerca de 3,8 × 10.695.974	$7 ^ {{7 ^ {7}}}$
aprox. 6 × 10 15 151 335	$7 \ vezes 8 ^ {{(7 \ vezes 8 ^ {7} +7 \ vezes 8 ^ {6} +7 \ vezes 8 ^ {5} +7 \ vezes 8 ^ {4} +7 \ vezes 8 ^ { 3} +7 \ vezes 8 ^ {2} +7 \ vezes 8 + 7)}}$ $+7 \ vezes 8 ^ {{(7 \ vezes 8 ^ {7} +7 \ vezes 8 ^ {6} +7 \ vezes 8 ^ {5} +7 \ vezes 8 ^ {4} +7 \ vezes 8 ^ {3} +7 \ vezes 8 ^ {2} +7 \ vezes 8 + 6)}}$ $+ ... \, \;$ $+7 \ vezes 8 ^ {{(8 + 2)}} + 7 \ vezes 8 ^ {{(8 + 1)}} + 7 \ vezes 8 ^ {8} +7 \ vezes 8 ^ {7} +7 \ vezes 8 ^ {6}$ $+7 \ vezes 8 ^ {5} +7 \ vezes 8 ^ {4} +7 \ vezes 8 ^ {3} +7 \ vezes 8 ^ {2} +7 \ vezes 8 + 7$
aproximadamente 4,3 × 10.369.693.099	$7 \ vezes 9 ^ {{(7 \ vezes 9 ^ {7} +7 \ vezes 9 ^ {6} +7 \ vezes 9 ^ {5} +7 \ vezes 9 ^ {4} +7 \ vezes 9 ^ { 3} +7 \ vezes 9 ^ {2} +7 \ vezes 9 + 7)}}$ $+7 \ vezes 9 ^ {{(7 \ vezes 9 ^ {7} +7 \ vezes 9 ^ {6} +7 \ vezes 9 ^ {5} +7 \ vezes 9 ^ {4} +7 \ vezes 9 ^ {3} +7 \ vezes 9 ^ {2} +7 \ vezes 9 + 6)}}$ $+ ... \, \;$ $+7 \ vezes 9 ^ {{(9 + 2)}} + 7 \ vezes 9 ^ {{(9 + 1)}} + 7 \ vezes 9 ^ {9} +7 \ vezes 9 ^ {7} +7 \ vezes 9 ^ {6}$ $+7 \ vezes 9 ^ {5} +7 \ vezes 9 ^ {4} +7 \ vezes 9 ^ {3} +7 \ vezes 9 ^ {2} +7 \ vezes 9 + 6$
	...

Apesar desse rápido crescimento (da ordem de n n 7 , e isso por um número de etapas muito maior do que o número de Graham ), a sequência finalmente diminui, para zero.

Prova

O teorema de Goodstein pode ser demonstrado (por um método que está fora da aritmética de Peano) usando ordinais : dado um inteiro m e sua sequência de Goodstein G ( m ), construímos uma sequência paralela P ( m ) de ordinais tais que P ( m ) estritamente diminui e termina. Será então o mesmo para a continuação de Goodstein G ( m ), que só pode terminar quando for cancelada.

Mais precisamente, para cada inteiro n , o termo da sequência P ( m ) é obtido aplicando uma transformação ao final da sequência de Goodstein de m da seguinte forma: tomamos a representação hereditária na base n +1 do termo , e substituímos cada ocorrência de n +1 pelo primeiro ordinal infinito, ω; então, por exemplo, e . A adição, multiplicação e exponenciação de números ordinais são bem definidas e o resultado é um ordinal representado na forma normal de Cantor . Além disso, quando realizamos uma mudança de base na sequência de Goodstein para ir de para , temos : é o ponto central dessa construção (por exemplo, ). ${\ displaystyle P_ {n} (m)}$ ${\ displaystyle f_ {n + 1}}$ ${\ displaystyle G_ {n} (m)}$ ${\ displaystyle G_ {n} (m)}$ ${\ displaystyle G_ {1} (3) = 3 = 2 ^ {1} + 2 ^ {0}}$ ${\ displaystyle P_ {1} (3) = f_ {2} (G_ {1} (3)) = \ omega ^ {1} + \ omega ^ {0} = \ omega +1}$ ${\ displaystyle G_ {n} (m)}$ ${\ displaystyle G_ {n + 1} (m)}$ ${\ displaystyle P_ {n} (m) = f_ {n + 1} (G_ {n} (m)) = f_ {n + 2} (G_ {n} (m))}$ ${\ displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3,4 ^ {0}) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3 = f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3)}$

Depois de subtrair 1, será estritamente menor que : ${\ displaystyle P_ {n + 1} (m) = f_ {n + 2} (G_ {n} (m)) - 1 = f_ {n + 2} (G_ {n + 1} (m))}$ ${\ displaystyle P_ {n} (m)}$

quando a forma normal de Cantor de é a forma com , = . Portanto, é estritamente maior do que ; ${\ displaystyle P_ {n} (m)}$ $X + \ alpha. \ Omega ^ {0}$ $\ alpha \ neq 0$ ${\ displaystyle P_ {n + 1} (m)}$ ${\ displaystyle P_ {n} (m)}$ ${\ displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3}$ ${\ displaystyle f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3) -1) = 3 \ omega ^ {\ omega ^ {\ omega}} + 2}$
da mesma forma, quando é um limite ordinal, é estritamente inferior, portanto, estritamente superior ; ${\ displaystyle P_ {n} (m)}$ ${\ displaystyle P_ {n + 1} (m)}$ ${\ displaystyle f_ {4} (3 \ cdot 4 ^ {4}) = 3 \ omega ^ {\ omega}}$ ${\ displaystyle f_ {5} (3 \ cdot 5 ^ {5} -1) = f_ {5} (2 \ cdot 5 ^ {4} +4 \ cdot 5 ^ {3} +4 \ cdot 5 ^ {2 } +4 \ cdot 5 ^ {1} +4 \ cdot 5 ^ {0}) = 2 \ cdot \ omega ^ {4} +4 \ cdot \ omega ^ {3} +4 \ cdot \ omega ^ {2} +4 \ cdot \ omega +4}$
em ambos os casos, concluímos que a sequência paralela P ( m ) diminui estritamente.

Uma vez estabelecida a redução estrita da sequência P ( m ), o argumento continua da seguinte forma: se a sequência G ( m ) não chegasse a 0, seria infinita (porque estaria sempre definida). Então P ( m ) também seria infinito (já que também sempre seria definido). Mas P ( m ) é estritamente decrescente; agora que a ordem padrão < no conjunto de ordinais é menor do que uma boa ordem , não há, portanto, nenhuma sequência infinita estritamente decrescente de ordinais ou, em outras palavras, qualquer sequência estritamente decrescente de ordinais termina e não pode, portanto, ser infinita. Essa contradição mostra que a sequência G ( m ) termina e, portanto, chega a 0 (aliás, já que existe um inteiro natural k tal que = 0, e por definição de P ( m ), também temos = 0). ${\ displaystyle G_ {k + 1} (m)}$ ${\ displaystyle P_ {k + 1} (m)}$ $\ varejpsilon _ {0}$ ${\ displaystyle G_ {k} (m)}$ ${\ displaystyle P_ {k} (m)}$

Enquanto a prova do teorema de Goodstein é relativamente fácil, o teorema de Laurence Kirby e Jeff Paris, que afirma que o teorema de Goodstein não pode ser provado na aritmética de Peano, é técnico e consideravelmente mais difícil. A prova de Kirby e Paris usa modelos não padronizados contáveis da aritmética de Peano para reduzir o teorema de Goodstein ao teorema de Gentzen , que dá a consistência da aritmética por indução até o ordinal ε 0 (o limite superior dos ordinais usados para a prova de Goodstein teorema).

O comprimento da sequência em função do valor inicial

A função Goodstein , é definida por " é o comprimento da sequência de Goodstein G ( n )" (isto é , se aplica , como todas as suítes do final de Goodstein). O crescimento extremamente rápido pode ser medido conectando-se a várias hierarquias de funções indexadas por ordinais, como as funções da hierarquia Hardy (in) ou as funções da hierarquia de crescimento rápido de Löb e Wainer: ${\ mathcal {G}}: {\ mathbb {N}} \ to {\ mathbb {N}} \, \!$ ${\ mathcal {G}} (n)$ ${\ mathcal {G}} \, \!$ $H _ {\ alpha} \, \!$ $f _ {\ alpha} \, \!$

Kirby e Paris (1982) mostraram que

{\ mathcal {G}} \, \!

cresce aproximadamente tão rápido quanto (e, portanto, quanto ); mais precisamente, domina por tudo e domina

H _ {{\ varepsilon _ {0}}} \, \!

f _ {{\ varepsilon _ {0}}} \, \!

{\ mathcal {G}} \, \!

H _ {\ alpha} \, \!

\ alpha <\ varepsilon _ {0} \, \!

H _ {{\ varepsilon _ {0}}} \, \!

{\ mathcal {G}} \, \!.

(para duas funções , dizemos que domina se for grande o suficiente). Mais precisamente ainda, Cichon (1983) mostrou que

f, g: {\ mathbb {N}} \ to {\ mathbb {N}} \, \!

f \, \!

g \, \!

f (n)> g (n) \, \!

não\,\!

{\ mathcal {G}} (n) = H _ {{R_ {2} ^ {\ omega} (n + 1)}} (1) -1,

onde é o resultado de escrever n na notação hereditária de base 2, substituindo então todos os 2 por ω (como na demonstração do teorema de Goodstein).

R_ {2} ^ {\ omega} (n)

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

{\ 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

Aqui estão alguns exemplos :

não			${\ 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 2 402 653 211 - 2
5	$2 ^ {2} + 2 ^ {0}$	$2 ^ {2} + 2-1$	$H _ {{\ omega ^ {\ omega} + \ omega}} (1) -1$	$f _ {\ omega} (f_ {0} (3)) - 2$	> A (5,4) (onde A é a função de Ackermann )
6	$2 ^ {2} + 2 ^ {1}$	$2 ^ {2} + 2 + 1-1$	$H _ {{\ omega ^ {\ omega} + \ omega +1}} (1) -1$	$f _ {\ omega} (f_ {1} (3)) - 2$	> A (7,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 (9,8)
8	$2 ^ {{2 + 1}}$	$2 ^ {{2 + 1}} + 1-1$	$H _ {{\ omega ^ {{\ omega +1}} + 1}} (1) -1$	$f _ {{\ omega +1}} (3) -2$	> A 3 (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)> G, o número de Graham
$\ vdots$
16	$2 ^ {{2 ^ {2}}}$	$2 ^ {{2 ^ {2}}} + 1-1$	$H _ {{\ omega ^ {{\ omega ^ {{\ omega}}}}}} (1) -1$	$f _ {{\ omega ^ {{\ omega}}}} (3) -2$	> , um número que só pode ser expresso em notação de Conway com um número de setas maior que o número de Graham . $f _ {{\ omega ^ {{2}}}} (G)$
$\ 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$

(as desigualdades envolvendo a função de Ackermann A e o número de Graham G são detalhadas no artigo sobre hierarquia de crescimento rápido ).

Generalizações e teoremas análogos

Let Ser uma seqüência de inteiros (que podemos supor ser estritamente crescente, com ); podemos definir uma sequência de Goodstein generalizada definindo e escrevendo em cada etapa da notação de base hereditária , substituindo todos os by e subtraindo 1 do resultado a ser obtido ; embora essa sequência possa crescer muito mais rápido do que a sequência normal de Goodstein (correspondendo a ), qualquer que seja a velocidade de crescimento da sequência , a prova anterior se aplica e a sequência sempre termina chegando a 0. $(b_n)$ ${\ displaystyle b_ {0} = 2}$ ${\ displaystyle G (m) (n)}$ ${\ displaystyle G (m) (0) = m}$ ${\ displaystyle G (m) (n)}$ $b_n$ $b_n$ ${\ displaystyle b_ {n + 1}}$ ${\ displaystyle G (m) (n + 1)}$ ${\ displaystyle b_ {n} = n + 2}$ $(b_n)$

Paris e Kirby construíram suítes semelhantes usando um modelo de hidra inspirado na lenda da batalha de Hércules com a Hidra de Lerna . São árvores das quais Hércules pode cortar um vértice (uma cabeça) a cada golpe, o que faz com que um número arbitrário de subárvores cresça de volta, mas em um nível inferior; demonstramos substituindo cada árvore por um ordinal (menor que ε 0 ) que os ordinais obtidos formam uma sequência decrescente, daí o resultado: por pior que seja a estratégia de Hércules, e por mais numerosas que sejam as cabeças que voltam a crescer, a hidra acaba sempre sendo derrotado; com regras de crescimento de cabeça mais complexas, o raciocínio análogo também pode exigir o uso de ordinais muito maiores do que ε 0 .

Notas

(em) James M. Henle, An Outline of Set Theory ( leia online ) , p. 137-138.
Um erro comum é pensar que G ( m ) chega a 0 porque é dominado por P ( m ); de fato, que P ( m ) domina G ( m ) não desempenha nenhum papel: o ponto central é que existe se e somente se existe (paralelismo de sequências). Então, se P ( m ) termina, necessariamente G ( m ) também. E G ( m ) só pode terminar atingindo 0. ${\ displaystyle G_ {k} (m)}$ ${\ displaystyle P_ {k} (m)}$
(en) L. Kirby e J. Paris , “ Resultados da independência acessíveis para a aritmética de Peano ” , Bull. Londres. Matemática. Soc. , vol. 14,1982, p. 285-293 ( ler online ).
David Madore, " Estou aprendendo a contar até ψ (εΩ + 1) e domar hidras " , em http://www.madore.org ,16 de março de 2008(acessado em 29 de abril de 2019 ) .

Veja também

Teorema Paris e Harrington (en)
Hierarquia de rápido crescimento

Bibliografia

(en) R. Goodstein , “ On the restricted ordinal teemem ” , J. Symb. Logic , vol. 9,1944, p. 33-41 ( DOI 10.2307 / 2268019 )
(pt) EA Cichon , " Uma Prova Curta de Dois Resultados de Independência Recentemente Descobertos Usando Métodos Teóricos Recursivos " , Proc. Amargo. Matemática. Soc. , vol. 87,1983, p. 704-706 ( ler online , acessado em 23 de junho de 2013 ).
(en) A. Caicedo , “ A função de Goodstein ” , Revista Colombiana de Matemáticas , vol. 41, n o 22007, p. 381-391 ( ler online , acessado em 23 de junho de 2013 ).
Patrick Dehornoy , “ Is Infinity Necessary? ", Pour la science , n o 278" The infinites ",2000, p. 102-106 ( ler online )