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.

Le théorème de Goodstein n'est pas démontrable dans l'arithmétique de Peano du premier ordre, mais peut ê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 de 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

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 :

$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 suite de Goodstein d'un entier m, notée G(m), est définie comme suit : le premier élément de la suite est m. Pour obtenir l'élément suivant, 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. Pour obtenir le troisième, on écrit l'élément précédemment calculé en notation héréditaire en base 3, on change les 3 en 4, et on retranche 1. On continue ainsi jusqu'à obtenir 0 (ce qui se produit toujours, comme démontré plus bas).

Plus formellement, la suite G(m)(n) est définie par l'itération des deux opérations suivantes : à l'étape n (en posant G(m)(1) = m) :

1. Écrire l'entier G(m)(n) en notation héréditaire en base n + 1, et remplacer n + 1 par n + 2 ;
2. Soustraire 1 ; on obtient ainsi G(m)(n+1).

Exemples de suites de Goodstein ; énoncé du théorème

Les toutes premières suites de Goodstein se terminent rapidement. Par exemple G(3) :

Base	Notation héréditaire	Valeur	Notes
2	21 + 1	3	Le 1 représente 20 (dans les étapes suivantes, il reste inchangé, puisque b0 = 1 pour tout b).
3	31 + 1 − 1 = 3	3	On change 2 en 3, puis on soustrait 1
4	41 − 1 = 3	3	On change 3 en 4 puis on soustrait 1
5	3 − 1 = 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	2 − 1 = 1	1
7	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 :

Notation héréditaire Valeur 22 4 2·32 + 2·3 + 2 26 2·42 + 2·4 + 1 41 2·52 + 2·5 60 2·62 + 6 + 5 83 2·72 + 7 + 4 109 ... 2·112 + 11 253 2·122 + 11 299 ... 2·232 1058 242+23·24+23 1151 ...

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

La suite G(4) continue à croître, le phénomène observé pour les bases 6,12 et 24 se reproduisant pour toutes les bases de la forme 3×2Modèle:Exp. Lorsqu'on atteint la base Modèle:Nobr le terme de la suite vaut bModèle:2 = Modèle:Nombre. À partir de ce terme, il n'apparait plus de carrés dans la notation héréditaire : le terme suivant est (b + 1)Modèle:2 – 1, soit, en base (b + 1) : b(b + 1) + b, et le terme suivant sera donc b(b + 2) + b – 1, etc.

Lorsqu'on atteint la base Modèle:Nobr le terme de la suite vaut B (la suite était d'ailleurs constante depuis la base (B + 1)/2).

La suite se met alors enfin à décroître, et atteint la valeur nulle pour la base Modèle:Nobr, qui est d'ailleurs un nombre de Woodall (car Modèle:Nobr 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 Modèle:Nobr.

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$ k fois

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

Notation héréditaire	Valeur
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	Modèle:Nombre
$4^{4^{4}}+3$	environ Modèle:Nobr
$5^{5^{5}}+2$	environ Modèle:Nobr
$6^{6^{6}}+1$	environ Modèle:Nobr
$7^{7^{7}}$	environ Modèle:Nobr
$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 Modèle:Nobr
$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$	environ Modèle:Nobr
...

En dépit de cette rapide croissance (de l'ordre de nModèle:Exp, et ce pendant un nombre d'étapes bien supérieur au nombre de Graham), on a le Modèle:Théorème

Preuve

Le théorème de Goodstein peut être démontré (par une méthode qui est en dehors de 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(m)(n) de la suite P(m) s'obtient en appliquant une transformation $f_{n+1}$ au terme G(m)(n) 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(m)(n), et on y remplace chaque occurrence de n+1 par le premier ordinal infini, ω ; ainsi, par exemple, $G(3)(1)=3=2^{1}+2^{0}$ et $P(3)(1)=f_{2}(G(3)(1))=\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. De plus, lorsqu'on effectue un changement de base dans la suite de Goodstein pour passer de G(m)(n) à G(m)(n+1), on a $P(m)(n)=f_{n+1}(G(m)(n))=f_{n+2}(G(m)(n))$ (c'est le point central de cette construction). Par exemple, $f_{4}(3\cdot 4^{4^{4}}+3.4^{0})=3\omega ^{\omega ^{\omega }}+3=f_{5}(3\cdot 5^{5^{5}}+3)$. Et après soustraction de 1, $P(m)(n+1)=f_{n+2}(G(m)(n))-1=f_{n+2}(G(m)(n+1))$ sera strictement inférieur à P(m)(n) :

• quand la forme normale de Cantor de P(m)(n) est de la forme $X+\alpha .\omega ^{0}$ avec $\alpha \neq 0$, P(m)(n+1) = P(m)(n)-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$ ;
• de même, lorsque P(m)(n) est un ordinal limite, P(m)(n+1) 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(m)(k+1) serait toujours défini). Donc P(m) serait également infinie (puisque P(m)(k+1) 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(m)(k) = 0, et par définition de P(m), on a P(m)(k) = 0 aussi).

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 Modèle:Lien, 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

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 Kirsby 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 ε₀Modèle:,.

Voir aussi

• Modèle:Lien
• Hiérarchie de croissance rapide

Bibliographie

• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article