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'à $\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 :

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

où chaque $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 : $2^{5} 2 1$, et en notation héréditaire (on parle aussi de notation itérée) en base 2 : $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 $G(m)$ est définie en posant $G_{1}(m)=m$ et en itérant, pour $n\geq 1$ :

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

1. écrire l'entier $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 $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) :
  • $G_{1}(1)=1$ ;
  • $G_{2}(1)=1-1=0$.

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

• Pour G(3) :

Base	Calcul de $G_{n}$(3)	Notation héréditaire	Notes
2	$G_{1}=3$	3 = (21 1)	La notation héréditaire est indiquée entre parenthèses
3	$G_{2}=(3^{1} 1)-1=3$	3 = (31)	On change 2 en 3, puis on soustrait 1
4	$G_{3}=(4^{1})-1=3$	3 = (3)	On change 3 en 4 puis on soustrait 1
5	$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	$G_{5}=(2)-1=1$	1 = (1)
7	$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 22 26 2·32 2·3 2 41 2·42 2·4 1 60 2·52 2·5 83 2·62 6 5 109 2·72 7 4 ... 253 2·112 11 299 2·122 11 ... 1058 2·232 1151 242 23·24 23 ...

Valeur Notation héréditaire 5 22 1 27 33 255 3·43 3·42 3·4 3 467 3·53 3·52 3·5 2 775 3·63 3·62 3·6 1 1197 3·73 3·72 3·7 1751 3·83 3·82 2·8 7 ... 10830 3·153 3·152 2·15 13087 3·163 3·162 16 15 ... 92287 3·313 3·312 31 101407 3·323 3·322 31 ... 762048 3·633 3·632 798719 3·643 2·642 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}.

• 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 :

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

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

$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)$,

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	$2^{2^{2}} 2 1$
7 625 597 484 990	$3^{3^{3}} 3$
environ 1,3 × 10154	$4^{4^{4}} 3$
environ 1,8 × 102 184	$5^{5^{5}} 2$
environ 2,6 × 1036 305	$6^{6^{6}} 1$
environ 3,8 × 10695 974	$7^{7^{7}}$
environ 6 × 1015 151 335	$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)}$ $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)}$ $...\,\;$ $7\times 8^{(8 2)} 7\times 8^{(8 1)} 7\times 8^{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$
environ 4,3 × 10369 693 099	$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)}$ $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)}$ $...\,\;$ $7\times 9^{(9 2)} 7\times 9^{(9 1)} 7\times 9^{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$
	...

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 $P_{n}(m)$ de la suite P(m) s'obtient en appliquant une transformation $f_{n 1}$ au terme $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 $G_{n}(m)$, et on y remplace chaque occurrence de n 1 par le premier ordinal infini, ω ; ainsi, par exemple, $G_{1}(3)=3=2^{1} 2^{0}$ et $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 $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, $P_{n 1}(m)=f_{n 2}(G_{n 1}(m))$ sera strictement inférieur à $P_{n}(m)$ :

• quand $P_{n}(m)$ est un ordinal successeur, c'est-à-dire de forme normale de Cantor du type $X \alpha$, où $\alpha$ est un entier non nul, $P_{n 1}(m)=X (\alpha -1)$. Ainsi $f_{4}(3\cdot 4^{4^{4}} 3)=3\omega ^{\omega ^{\omega }} 3$ est strictement supérieur à $f_{5}(3\cdot 5^{5^{5}} 3-1)=3\omega ^{\omega ^{\omega }} 2$ ;
• quand $P_{n}(m)$ est un ordinal limite, $P_{n 1}(m)$ lui est strictement inférieur, ainsi $f_{4}(3\cdot 4^{4})=3\omega ^{\omega }$ est strictement supérieur à $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 $G_{k 1}(m)$ serait toujours défini). Donc P(m) serait également infinie (puisque $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 à $\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 $G_{k}(m)$ = 0, et par définition de P(m), on a $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 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, ${\mathcal {G}}:\mathbb {N} \to \mathbb {N} \,\!$, est définie par « ${\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 ${\mathcal {G}}\,\!$ peut être mesurée en la reliant à diverses hiérarchies de fonctions indexées par des ordinaux, telles que les fonctions $H_{\alpha }\,\!$ de la hiérarchie de Hardy (en), ou les fonctions $f_{\alpha }\,\!$ de la hiérarchie de croissance rapide de Löb et Wainer :

• Kirby et Paris (1982) montrèrent que

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

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

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

où $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 $n=2^{m_{1}} 2^{m_{2}} \cdots 2^{m_{k}}$ avec $m_{1}>m_{2}>\cdots >m_{k},$ alors

${\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			${\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·2402 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) (où A est la fonction d'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$	> 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) > G, le nombre de Graham
$\vdots$
16	$2^{2^{2}}$	$2^{2^{2}} 1-1$	$H_{\omega ^{\omega ^{\omega }}}(1)-1$	$f_{\omega ^{\omega }}(3)-2$	> $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.
$\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$

(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 $(b_{n})$ une suite d'entiers (qu'on peut supposer strictement croissante, avec $b_{0}=2$) ; on peut définir une suite de Goodstein généralisée $G(m)(n)$ en posant $G(m)(0)=m$ et en écrivant à chaque étape $G(m)(n)$ en notation héréditaire en base $b_{n}$, en remplaçant tous les $b_{n}$ par $b_{n 1}$, et en soustrayant 1 au résultat pour obtenir $G(m)(n 1)$ ; bien que cette suite puisse croître beaucoup plus vite que la suite de Goodstein usuelle (correspondant à $b_{n}=n 2$), quelle que soit la vitesse de croissance de la suite $(b_{n})$, la démonstration précédente s'applique et la suite finit toujours par atteindre 0.

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

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)