Théorème de Goodstein

En mathématiques, et plus précisément en logique mathématique, le théorème de Goodstein est un énoncé arithmétique portant sur des suites, dites suites de Goodstein. Les suites de Goodstein sont des suites d'entiers à la croissance initiale extrêmement rapide, et le théorème établit que (en dépit des apparences) toute suite de Goodstein se termine par 0. Il doit son nom à son auteur, le mathématicien et logicien Reuben Goodstein.

Le théorème de Goodstein peut être énoncé mais ni démontré, ni réfuté dans l'arithmétique de Peano du premier ordre ; il peut néanmoins être démontré dans des théories plus fortes, comme la théorie des ensembles ZF (une démonstration simple utilise les ordinaux jusqu'à ${\displaystyle \varepsilon _{0}}$), ou l'arithmétique du second ordre. Le théorème donne ainsi, dans le cas particulier de l'arithmétique du premier ordre, un exemple d'énoncé indécidable plus naturel que ceux obtenus par les théorèmes d'incomplétude de Gödel.

Définition d'une suite de Goodstein

Notation héréditaire en base n

Avant de définir une suite de Goodstein, définissons d'abord la notation héréditaire en base n. Pour écrire un entier naturel avec une telle notation, on l'écrit d'abord sous la forme classique de la décomposition en base n :

${\displaystyle a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0}}$

où chaque ${\displaystyle a_{i}}$ est un entier compris entre 0 et n-1. Ensuite, on applique le même traitement aux exposants k, k−1, … itérativement, jusqu'à obtenir une expression constituée uniquement d'entiers entre 0 et n−1.

Par exemple, 35 s'écrit en base 2 : ${\displaystyle 2^{5}+2+1}$, et en notation héréditaire (on parle aussi de notation itérée) en base 2 : ${\displaystyle 2^{2^{2}+1}+2^{1}+1}$.

La représentation héréditaire d'un entier en base n est unique, de même que la représentation en base n.

Définition

La suite de Goodstein d'un entier m est notée G(m). Son premier élément est G₁(m) = m. Pour obtenir l'élément suivant, en supposant que m ≠ 0, on écrit m en notation héréditaire en base 2, puis on change chaque 2 en 3, et enfin on soustrait 1 du résultat. On a alors le deuxième élément de la suite. Si cet élément est nul la suite est finie de longueur 2. Sinon, pour obtenir le troisième, on écrit le deuxième élément en notation héréditaire en base 3, on change les 3 en 4, et on retranche 1. Le procédé s'arrête quand on obtient 0 (ce qui est toujours le cas, comme démontré plus bas), et seulement dans ce cas là.

Un peu plus formellement, la suite ${\displaystyle G(m)}$ est définie en posant ${\displaystyle G_{1}(m)=m}$ et en itérant, pour ${\displaystyle n\geq 1}$ :

• si ${\displaystyle G_{n}(m)=0}$, ${\displaystyle G_{n+1}(m)}$ n'est pas défini, la suite ${\displaystyle G(m)}$ est finie de longueur n ;
• sinon :

1. écrire l'entier ${\displaystyle G_{n}(m)}$ en notation héréditaire en base n + 1, et remplacer n + 1 par n + 2 ;
2. soustraire 1 ; on obtient ainsi ${\displaystyle G_{n+1}(m)}$.

Énoncé du théorème

Théorème de Goodstein — Quelle que soit la valeur initiale de m, la suite de Goodstein G(m) se termine par 0.

Exemples de suites de Goodstein

Les toutes premières suites de Goodstein se terminent rapidement.

• Ainsi, pour G(1) :
  • ${\displaystyle G_{1}(1)=1}$ ;
  • ${\displaystyle G_{2}(1)=1-1=0}$.

• Et pour G(2) :
  • ${\displaystyle G_{1}(2)=2=2^{1}}$ ;
  • ${\displaystyle G_{2}(2)=3^{1}-1=2}$ ;
  • ${\displaystyle G_{3}(2)=2-1=1}$ ;
  • ${\displaystyle G_{4}(2)=1-1=0}$.

• Pour G(3) :

Base	Calcul de ${\displaystyle G_{n}}$(3)	Notation héréditaire	Notes
2	${\displaystyle G_{1}=3}$	3 = (2^1+1)	La notation héréditaire est indiquée entre parenthèses
3	${\displaystyle G_{2}=(3^{1}+1)-1=3}$	3 = (3^1)	On change 2 en 3, puis on soustrait 1
4	${\displaystyle G_{3}=(4^{1})-1=3}$	3 = (3)	On change 3 en 4 puis on soustrait 1
5	${\displaystyle G_{4}=(3)-1=2}$	2 = (2)	Puisque la base utilisée est supérieure aux chiffres de la décomposition, les changements de base ultérieurs sont sans effet.
6	${\displaystyle G_{5}=(2)-1=1}$	1 = (1)
7	${\displaystyle G_{6}=(1)-1=0}$	0

Mais les suites de Goodstein croissent en général pendant un grand nombre d'étapes, comme on le verra plus précisément dans la dernière section. Par exemple, les suites G(4) et G(5) commencent comme suit :

Valeur Notation héréditaire 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 ...

Valeur Notation héréditaire 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 ...

• Concernant la suite G(4), le phénomène observé pour les bases 6,12 et 24 se reproduit pour toutes les bases de la forme p=3×2ⁿ : la valeur précédente ne comporte pas de terme unité (terme de (p-1)⁰), et apparaît donc en base p le terme de puissance 0 égal à (p-1), avec réduction simultanée d'une unité du terme de puissance 1 ou 2.

Ainsi, lorsqu'on atteint la base b = 3×2²⁷ – 1 = 402 653 183, le terme de la suite vaut b² = 162 129 585 780 031 489. Le terme suivant est (b + 1)² – 1, soit, en base (b + 1) : b(b + 1) + b, et le terme suivant sera donc b(b + 2) + b – 1, etc, de sorte qu'il n'y a plus ensuite de terme de puissance 2 ou supérieure dans la notation héréditaire.

Lorsqu'on atteint la base B = (b + 1)2^b – 1 = 3×2^{402 653 210} – 1, le terme de la suite vaut B (la suite était d'ailleurs constante depuis la base (B + 1)/2). La valeur suivante est donc B-1, c'est-à-dire que la suite se met enfin à décroître, et atteint la valeur nulle pour la base 2B + 1 = 3×2^{402 653 211} – 1, qui est d'ailleurs un nombre de Woodall (car 3×2^{402 653 211} = 402 653 184 × 2^402653184).

La base à laquelle la suite G(4) se termine possède plus de 120 millions de chiffres, ce qui signifie que le nombre de termes de la suite G(4) est de l'ordre de 10^{120 000 000[1]}.

• Bien que la suite G(5) ne croisse pas beaucoup plus vite, elle le fait bien plus longuement, et les notations exponentielles usuelles ne permettent plus d'exprimer la plus grande base atteinte. Posant :

${\displaystyle g(n)=n2^{n}}$,

${\displaystyle g^{k}=g\circ g\circ \cdots \circ g}$ (avec k symboles ${\displaystyle g}$),

${\displaystyle M=g^{3}(64)=2^{70+2^{70}+2^{70}2^{2^{70}}}}$,

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

le nombre de termes de la suite G(5) est alors Q – 2 (voir la dernière section pour une justification de ce calcul). Ce nombre ne peut s'exprimer exactement à l'aide de la notation des flèches de Knuth, mais est (dans cette notation) de l'ordre de 2↑↑↑6, ou encore, en utilisant la fonction d'Ackermann, de l'ordre de A(5, 4).

• Cependant, ces deux exemples ne donnent pas encore une idée suffisante de la vitesse à laquelle la suite de Goodstein peut croître. Ainsi, G(19) croît beaucoup plus rapidement et commence comme suit :

Valeur	Notation héréditaire
19	${\displaystyle 2^{2^{2}}+2+1}$
7 625 597 484 990	${\displaystyle 3^{3^{3}}+3}$
environ 1,3 × 10^154	${\displaystyle 4^{4^{4}}+3}$
environ 1,8 × 10^2 184	${\displaystyle 5^{5^{5}}+2}$
environ 2,6 × 10^36 305	${\displaystyle 6^{6^{6}}+1}$
environ 3,8 × 10^695 974	${\displaystyle 7^{7^{7}}}$
environ 6 × 10^15 151 335	${\displaystyle 7\times 8^{(7\times 8^{7}+7\times 8^{6}+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+7)}}$ ${\displaystyle +7\times 8^{(7\times 8^{7}+7\times 8^{6}+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+6)}}$ ${\displaystyle +...\,\;}$ ${\displaystyle +7\times 8^{(8+2)}+7\times 8^{(8+1)}+7\times 8^{8}+7\times 8^{7}+7\times 8^{6}}$ ${\displaystyle +7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+7}$
environ 4,3 × 10^369 693 099	${\displaystyle 7\times 9^{(7\times 9^{7}+7\times 9^{6}+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+7)}}$ ${\displaystyle +7\times 9^{(7\times 9^{7}+7\times 9^{6}+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+6)}}$ ${\displaystyle +...\,\;}$ ${\displaystyle +7\times 9^{(9+2)}+7\times 9^{(9+1)}+7\times 9^{9}+7\times 9^{7}+7\times 9^{6}}$ ${\displaystyle +7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+6}$
	...

En dépit de cette rapide croissance (de l'ordre de nⁿ⁷, et ce pendant un nombre d'étapes bien supérieur au nombre de Graham), la suite finit par décroître, jusqu'à zéro.

Démonstrations

Théorème de Goodstein

Le théorème de Goodstein peut être démontré (par une méthode qui ne se formalise pas dans l'arithmétique de Peano) en utilisant des ordinaux : étant donnés un entier m et sa suite de Goodstein G(m), on construit une suite parallèle P(m) d'ordinaux telle que P(m) décroisse strictement et se termine. Il en sera alors de même de la suite de Goodstein G(m) qui ne peut se terminer que lorsqu'elle s'annule.

Plus précisément, pour chaque entier n, le terme ${\displaystyle P_{n}(m)}$ de la suite P(m) s'obtient en appliquant une transformation ${\displaystyle f_{n+1}}$ au terme ${\displaystyle G_{n}(m)}$ de la suite de Goodstein de m de la manière suivante : on prend la représentation héréditaire en base n+1 du terme ${\displaystyle G_{n}(m)}$, et on y remplace chaque occurrence de n+1 par le premier ordinal infini, ω ; ainsi, par exemple, ${\displaystyle G_{1}(3)=3=2^{1}+2^{0}}$ et ${\displaystyle P_{1}(3)=f_{2}(G_{1}(3))=\omega ^{1}+\omega ^{0}=\omega +1}$. Addition, multiplication et exponentiation de nombres ordinaux sont bien définies, et le résultat est un ordinal représenté en forme normale de Cantor. L'étape intermédiaire de changement de base dans la définition d'une suite de Goodstein ne modifie pas l'ordinal associé : par exemple ${\displaystyle f_{4}(3\cdot 4^{4^{4}}+3)=3\omega ^{\omega ^{\omega }}+3=f_{5}(3\cdot 5^{5^{5}}+3)}$.

Après soustraction de 1, ${\displaystyle P_{n+1}(m)=f_{n+2}(G_{n+1}(m))}$ sera strictement inférieur à ${\displaystyle P_{n}(m)}$ :

• quand ${\displaystyle P_{n}(m)}$ est un ordinal successeur, c'est-à-dire de forme normale de Cantor du type ${\displaystyle X+\alpha }$, où ${\displaystyle \alpha }$ est un entier non nul, ${\displaystyle P_{n+1}(m)=X+(\alpha -1)}$. Ainsi ${\displaystyle f_{4}(3\cdot 4^{4^{4}}+3)=3\omega ^{\omega ^{\omega }}+3}$ est strictement supérieur à ${\displaystyle f_{5}(3\cdot 5^{5^{5}}+3-1)=3\omega ^{\omega ^{\omega }}+2}$ ;
• quand ${\displaystyle P_{n}(m)}$ est un ordinal limite, ${\displaystyle P_{n+1}(m)}$ lui est strictement inférieur, ainsi ${\displaystyle f_{4}(3\cdot 4^{4})=3\omega ^{\omega }}$ est strictement supérieur à ${\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}$ ;
• dans les deux cas, on conclut que la suite parallèle P(m) décroît strictement.

Une fois établie la décroissance stricte de la suite P(m), l'argument se poursuit ainsi : si la suite G(m) n'atteignait pas 0, elle serait infinie (car ${\displaystyle G_{k+1}(m)}$ serait toujours défini). Donc P(m) serait également infinie (puisque ${\displaystyle P_{k+1}(m)}$ aussi serait toujours défini). Mais P(m) est décroissante strictement ; or l'ordre standard < sur l'ensemble des ordinaux inférieurs à ${\displaystyle \varepsilon _{0}}$ est un bon ordre, il n'existe donc pas de suite infinie strictement décroissante d'ordinaux, ou, dit autrement, toute suite strictement décroissante d'ordinaux termine et ne peut donc être infinie. Cette contradiction montre que la suite G(m) termine et donc atteint 0 (au passage, puisqu'il existe un entier naturel k tel que ${\displaystyle G_{k}(m)}$ = 0, et par définition de P(m), on a ${\displaystyle P_{k}(m)}$ = 0 aussi).

Indécidabilité dans l'axiomatique de Peano

Tandis que la preuve du théorème de Goodstein est relativement facile, le théorème^[2] de Laurence Kirby et Jeff Paris qui énonce que le théorème de Goodstein ne peut être prouvé dans l'arithmétique de Peano, est technique et considérablement plus difficile. La démonstration de Kirby et Paris utilise des modèles non standards dénombrables de l'arithmétique de Peano pour ramener le théorème de Goodstein au théorème de Gentzen, qui donne la cohérence de l'arithmétique par récurrence jusqu'à l'ordinal ε₀ (la borne supérieure des ordinaux utilisés pour la démonstration du théorème de Goodstein).

La longueur de la suite en fonction de la valeur initiale

La fonction de Goodstein, ${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} \,\!}$, est définie par « ${\displaystyle {\mathcal {G}}(n)}$ est la longueur de la suite de Goodstein G(n) » (c'est une application, puisque toutes les suites de Goodstein se terminent). L'extrême rapidité de croissance de ${\displaystyle {\mathcal {G}}\,\!}$ peut être mesurée en la reliant à diverses hiérarchies de fonctions indexées par des ordinaux, telles que les fonctions ${\displaystyle H_{\alpha }\,\!}$ de la hiérarchie de Hardy (en), ou les fonctions ${\displaystyle f_{\alpha }\,\!}$ de la hiérarchie de croissance rapide de Löb et Wainer :

• Kirby et Paris (1982^[2]) montrèrent que

${\displaystyle {\mathcal {G}}\,\!}$ croît approximativement aussi vite que ${\displaystyle H_{\varepsilon _{0}}\,\!}$ (et donc que ${\displaystyle f_{\varepsilon _{0}}\,\!}$) ; plus précisément, ${\displaystyle {\mathcal {G}}\,\!}$ domine ${\displaystyle H_{\alpha }\,\!}$ pour tout ${\displaystyle \alpha <\varepsilon _{0}\,\!}$, et ${\displaystyle H_{\varepsilon _{0}}\,\!}$ domine ${\displaystyle {\mathcal {G}}\,\!.}$

(pour deux fonctions ${\displaystyle f,g:\mathbb {N} \to \mathbb {N} \,\!}$, on dit que ${\displaystyle f\,\!}$ domine ${\displaystyle g\,\!}$ si ${\displaystyle f(n)>g(n)\,\!}$ pour tous les ${\displaystyle n\,\!}$ assez grands). Plus précisément encore, Cichon (1983) montra que

${\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}$

où ${\displaystyle R_{2}^{\omega }(n)}$ est le résultat de l'écriture de n en notation héréditaire de base 2, puis en remplaçant tous les 2 par ω (comme dans la démonstration du théorème de Goodstein).

• Caicedo (2007) montra que si ${\displaystyle n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}}$ avec ${\displaystyle m_{1}>m_{2}>\cdots >m_{k},}$ alors

${\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}$.

Voici quelques exemples :

n			${\displaystyle {\mathcal {G}}(n)}$
1	${\displaystyle 2^{0}}$	${\displaystyle 2-1}$	${\displaystyle H_{\omega }(1)-1}$	${\displaystyle f_{0}(3)-2}$	2
2	${\displaystyle 2^{1}}$	${\displaystyle 2^{1}+1-1}$	${\displaystyle H_{\omega +1}(1)-1}$	${\displaystyle f_{1}(3)-2}$	4
3	${\displaystyle 2^{1}+2^{0}}$	${\displaystyle 2^{2}-1}$	${\displaystyle H_{\omega ^{\omega }}(1)-1}$	${\displaystyle f_{1}(f_{0}(3))-2}$	6
4	${\displaystyle 2^{2}}$	${\displaystyle 2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega }(3)-2}$	3·2^402 653 211 − 2
5	${\displaystyle 2^{2}+2^{0}}$	${\displaystyle 2^{2}+2-1}$	${\displaystyle H_{\omega ^{\omega }+\omega }(1)-1}$	${\displaystyle f_{\omega }(f_{0}(3))-2}$	> A(5,4) (où A est la fonction d'Ackermann)
6	${\displaystyle 2^{2}+2^{1}}$	${\displaystyle 2^{2}+2+1-1}$	${\displaystyle H_{\omega ^{\omega }+\omega +1}(1)-1}$	${\displaystyle f_{\omega }(f_{1}(3))-2}$	> A(7,6)
7	${\displaystyle 2^{2}+2^{1}+2^{0}}$	${\displaystyle 2^{2+1}-1}$	${\displaystyle H_{\omega ^{\omega +1}}(1)-1}$	${\displaystyle f_{\omega }(f_{1}(f_{0}(3)))-2}$	> A(9,8)
8	${\displaystyle 2^{2+1}}$	${\displaystyle 2^{2+1}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+1}(1)-1}$	${\displaystyle f_{\omega +1}(3)-2}$	> A^3(3,3) = A(A(61, 61), A(61, 61))
${\displaystyle \vdots }$
12	${\displaystyle 2^{2+1}+2^{2}}$	${\displaystyle 2^{2+1}+2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega +1}(f_{\omega }(3))-2}$	> fω+1(64) > G, le nombre de Graham
${\displaystyle \vdots }$
16	${\displaystyle 2^{2^{2}}}$	${\displaystyle 2^{2^{2}}+1-1}$	${\displaystyle H_{\omega ^{\omega ^{\omega }}}(1)-1}$	${\displaystyle f_{\omega ^{\omega }}(3)-2}$	> ${\displaystyle f_{\omega ^{2}}(G)}$ , un nombre qui ne peut s'exprimer en notation de Conway qu'avec un nombre de flèches supérieur au nombre de Graham.
${\displaystyle \vdots }$
19	${\displaystyle 2^{2^{2}}+2^{1}+2^{0}}$	${\displaystyle 2^{2^{2}}+2^{2}-1}$	${\displaystyle H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1}$	${\displaystyle f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2}$

(les inégalités mettant en jeu la fonction d'Ackermann A et le nombre de Graham G sont détaillées dans l'article hiérarchie de croissance rapide).

Généralisations et théorèmes analogues

Les suites de Goodstein sont constituées à partir de bases s'incrémentant d'une unité à chaque itération (2, puis 3, 4, etc...). On peut remplacer cette suite de bases par une quelconque suite d'entiers, commençant par 2 : soit ${\displaystyle (b_{n})}$ une suite d'entiers (qu'on peut supposer strictement croissante, avec ${\displaystyle b_{0}=2}$) ; on peut définir une suite de Goodstein généralisée ${\displaystyle G(m)(n)}$ en posant ${\displaystyle G(m)(0)=m}$ et en écrivant à chaque étape ${\displaystyle G(m)(n)}$ en notation héréditaire en base ${\displaystyle b_{n}}$, en remplaçant tous les ${\displaystyle b_{n}}$ par ${\displaystyle b_{n+1}}$, et en soustrayant 1 au résultat pour obtenir ${\displaystyle G(m)(n+1)}$ ; bien que cette suite puisse croître beaucoup plus vite que la suite de Goodstein usuelle (correspondant à ${\displaystyle b_{n}=n+2}$), quelle que soit la vitesse de croissance de la suite ${\displaystyle (b_{n})}$, la démonstration précédente s'applique et la suite finit toujours par atteindre 0^[2].

Paris et Kirby ont construit des suites analogues en utilisant un modèle d'hydre s'inspirant de la légende du combat d'Hercule contre l'Hydre de Lerne. Il s'agit d'arbres dont Hercule peut trancher à chaque coup un sommet (une tête), ce qui fait repousser un nombre arbitraire de sous-arbres, mais à un niveau inférieur ; on démontre en remplaçant chaque arbre par un ordinal (inférieur à ε₀) que les ordinaux obtenus forment une suite décroissante, d'où le résultat : si mauvaise que soit la stratégie d'Hercule, et si nombreuses que soient les têtes qui repoussent, l'hydre finit toujours par être vaincue ; avec des règles de repousse de têtes plus complexes, des raisonnements analogues peuvent demander d'ailleurs d'utiliser des ordinaux beaucoup plus grands que ε₀^[2],[3].

Notes

1. (en) James M. Henle, An Outline of Set Theory (lire en ligne), p. 137-138.
2. Laurie Kirby et Jeff Paris, « Accessible independence results for Peano arithmetic. », Bulletin of the London Mathematical Society, vol. 14, n^o 4,‎ 1982, p. 285-293 (DOI 10.1112/blms/14.4.285, lire en ligne).
3. David Madore, « J'apprends à compter jusqu'à ψ(ε_Ω+1) et à dompter les hydres », sur madore.org,‎ 16 mars 2008 (consulté le 29 avril 2019).

Voir aussi

• Théorème de Paris-Harrington
• Hiérarchie de croissance rapide

Bibliographie

• (en) A. Caicedo, « Goodstein's function », Revista Colombiana de Matemáticas, vol. 41, n^o 2,‎ 2007, p. 381-391 (lire en ligne)
• (en) E. A. Cichon, « A short proof of two recently discovered independence results using recursive theoretic methods », Proc. Amer. Math. Soc., vol. 87,‎ 1983, p. 704-706 (lire en ligne)
• Patrick Dehornoy, « L'infini est-il nécessaire ? », Pour la science, n^o 278 « Les infinis »,‎ 2000, p. 102-106 (lire en ligne)
• (en) R. Goodstein, « On the restricted ordinal theorem », J. Symb. Logic, vol. 9,‎ 1944, p. 33-41 (DOI 10.2307/2268019)