Théorème de Goodstein

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 les suites de Goodstein, des suites d'entiers à la croissance initiale extrêmement rapide, et il établit (en dépit des apparences) que 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 même l'arithmétique du second ordre (en). 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 le théorème d'incomplétude de Gödel.

Définition d'une suite de Goodstein[modifier | modifier le code]

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 + 2^0} + 2^{2^0} + 2^0.

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[modifier | modifier le code]

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 \times 2^{n} . Lorsqu'on atteint la base b = 3 \times 2^{27} -1 = 402653183, le terme de la suite vaut b2 = 162129585780031489. À partir de ce terme, il n'apparait plus de carrés dans la notation héréditaire : le terme suivant est (b+1)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 B = (b+1)2^b -1 = 3 \times 2^{402653210} - 1, 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 2B+1=3 \times 2^{402653211} - 1 qui, curieusement, est un nombre de Woodall (car \scriptstyle 3 \cdot 2^{402653211} - 1 = 402653184 \cdot 2^{402653184} - 1), comme toutes les bases finales pour des valeurs initiales supérieures ou égales à 3. 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^{120000000}.

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 7625597484990
4^{4^4}+3 environ 1.3 × 10154
5^{5^5}+2 environ 1.8 × 102184
6^{6^6}+1 environ 2.6 × 1036305
7^{7^7} environ 3.8 × 10695974

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 6 × 1015151335

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 4.3 × 10369693099
...

En dépit de cette rapide croissance (de l'ordre de \scriptstyle n^{{n^7}}, et ce pendant un nombre d'étapes bien supérieur au nombre de Graham), on a le

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

Preuve[modifier | modifier le code]

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ée 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[1].

Plus précisément, chaque terme P(m)(n) de la suite P(m) s'obtient en appliquant une fonction f 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 du terme G(m)(n), et on y remplace chaque occurrence de n par le premier ordinal infini, ω. par exemple G(3)(1)=3=2^1+2^0 et P(3)(1) = f(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, pour chaque base n, la fonction x\mapsto f(x) est strictement croissante, d'après les propriétés de la représentation héréditaire en base n (et celles de la forme normale de Cantor). Ainsi, lorsqu'on effectue un changement de base dans la suite de Goodstein pour passer de G(m)(n) à G(m)(n+1), f ne change pas de valeur (c'est le point central de cette construction), par exemple f(3 \cdot 4^{4^4} + 3.4^0) = 3 \omega^{\omega^\omega} + 3= f(3 \cdot 5^{5^5} + 3). Et après soustraction de 1, P(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(3 \cdot 4^{4^4} + 3)=3\omega^{\omega^\omega} + 3 est strictement supérieur à f((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(3 \cdot 4^{4})=3\omega^{\omega} est strictement supérieur à f((3 \cdot 5^{5}-1)= f(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, puisque 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[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 ε0 (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[modifier | modifier le code]

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,
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·2402653211 − 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).

Notes[modifier | modifier le code]

  1. Une erreur commune est de penser que G(m) atteint 0 parce qu'elle est dominée par P(m). En fait, que P(m) domine G(m) ne joue aucun rôle. Le point central est que G(m)(k) existe si et seulement si P(m)(k) existe (parallélisme des suites). Alors si P(m) termine, nécessairement G(m) aussi. Et G(m) ne peut terminer qu'en atteignant 0.
  2. Paris et Kirby

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • R. Goodstein, « On the restricted ordinal theorem », Journal of Symbolic Logic, vol. 9,‎ 1944, p. 33-41 (lire en ligne)
  • L. Kirby et J. Paris, « Accessible independence results for Peano arithmetic », Bull. London. Math. Soc., vol. 14,‎ 1982, p. 285-293 (lire en ligne)
  • E. Cichon, « A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods », Proceedings of the American Mathematical Society, vol. 87,‎ 1983, p. 704-706 (lire en ligne).
  • A. Caicedo, « Goodstein's function », Revista Colombiana de Matemáticas, vol. 41, no 2,‎ 2007, p. 381-391 (lire en ligne).