Les suites de Goodstein ou la puissance du détour par l’infini

Vignette écrite par Michèle Artigue, Ferdinando Arzarello et Susanna Epp.
Etudier l’évolution de phénomènes conduit souvent à étudier des suites numériques, à s’interroger sur leurs types de croissance, et sur leur convergence éventuelle. Les exemples de croissance rencontrés dans l’enseignement secondaire sont en général des croissances polynomiales, exponentielles ou logarithmiques. Mais des suites, même définies de façon très simple, peuvent avoir des comportements complexes comme le montrent les suites chaotiques de la théorie des systèmes dynamiques (Perrin, 2008). Et des suites définies de façon très simples, dont on a calculé des millions de termes, peuvent être source de questions qui défient les mathématiciens depuis plusieurs décennies. Ainsi en est-il par exemple de la question de savoir si les suites connues comme suites « 3n+1 » ou suites de Syracuse introduites par Luther Collatz en 1937, finissent ou non toujours par atteindre la valeur 1 (http://arxiv.org/abs/math/0608208v5).

Les suites que nous considérons dans cette vignette, introduites par le logicien britannique Reuben L. Goodstein en 1944, ont un comportement très différent. Leur croissance initiale, extraordinairement rapide, laisse penser qu’elles vont tendre vers l’infini, mais étonnamment elles finissent toujours par devenir décroissantes et tendre vers 0. La preuve de ce résultat nécessite une généralisation du raisonnement par récurrence à des ordinaux infinis mais sa mécanique en est tout à fait compréhensible. Pour l’expliquer, nous allons introduire, comme le fait Hodgson (2004), un objet plus facile à appréhender : les suites faibles de Goodstein.

1. Les suites faibles de Goodstein

Comme Hodgson, prenons comme point de départ, le nombre 266. Comme tout entier positif, il admet une décomposition additive unique sur la base des puissances de 2 (voir [1]): 266 = 2^8 + 2^3 +2^1. La suite faible de Goodstein dont le premier terme u_0 est 266 est alors définie de la façon suivante. Pour obtenir le terme u_1, on remplace dans l’écriture précédente la base 2 par la base 3, et on soustrait 1 au nombre obtenu. On obtient ainsi u_1 = 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590. En base 3, ce nombre a en fait comme décomposition additive : 3^8 + 3^3 +2. C’est de cette décomposition que l’on repart pour déterminer u_2 en remplaçant la base 3 par la base 4 et en soustrayant 1 au nombre obtenu comme précédemment, et ainsi de suite tant que le terme de la suite est non nul. On obtient ainsi successivement :

u_0 &= 2^8 + 2^3 + 2^1 = 266
u_1 &= 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590
u_2 &= 4^8 + 4^3 + 2 - 1 = 4^8 + 4^3 + 1 = 65,601
u_3 &= 5^8 + 5^3 + 1 - 1 = 5^8 + 5^3 = 390,750
u_4 &= 6^8 + 6^3 - 1 = 6^8 + 5 . 6^2 + 6^2 - 1 = 6^8 + 5 . 6^2 + 5 . 6 + 6 - 1\\ = 6^8 + 5 . 6^2 + 5 . 6^1 + 5 = 1,679,831
u_5 &= 7^8 + 5 . 7^2 + 5 . 7^1 + 5 - 1 = 7^8 + 5 . 7^2 + 5 . 7^1 + 4 = 5,765,085
u_6 &= 8^8 + 5 . 8^2 + 5 . 8^1 + 4 - 1 = 8^8 + 5 . 8^2 + 5 . 8^1 + 3 = 16,777,579
u_7 &= 9^8 + 5 . 9^2 + 5 . 9^1 + 3 - 1 = 9^8 + 5 . 9^2 + 5 . 9^1 + 2 = 43,047,173
u_8 &= 10^8 + 5 . 10^2 + 5 . 10^1 + 2 - 1 = 10^8 + 5 . 10^2 + 5 . 10^1 + 1 = 100,000,551
u_9 &= 11^8 + 5 . 11^2 + 5 . 11^1 + 1 - 1 = 11^8 + 5 . 11^2 + 5 . 11^1 = 214,359,541
u_{10} &= 12^8 + 5 . 12^2 + 5 . 12^1 - 1 = 12^8 + 5 . 12^2 + 4 . 12^1 + 12 - 1\\ = 12^8 + 5 . 12^2 + 4 . 12^1 + 11 = 429,982,475

Table 1: Termes initiaux d’une suite de Goodstein faible.

Les termes de la suite semblent donc croître très vite. Est-ce toujours le cas ? Non, si l’on choisit par exemple : u_0 = 1, alors u_1 = 1 - 1 = 0. Pour u_0 = 2 = 2^1, on a u_1 = 3^1 - 1 = 2, u_2 = 2 - 1 = 1 et u_3 = 1 - 1 = 0. On vérifiera de même que la suite de premier terme 3 ne dépasse jamais 3 et atteint 0 en cinq coups (voir [2]). Mais dès que la décomposition du nombre de départ fait intervenir des puissances élevées de 2, la croissance initiale est très rapide comme celle observée pour 266 et conduit à penser que la suite tend vers l’infini. Comment le fait de retrancher 1 pourrait-il compenser l’impressionnante croissance qui est générée par l’accroissement d’une unité de la base ?

Et pourtant…. Regardons plus soigneusement les expressions écrites ci-dessus. Si les termes successifs de la suite de premier terme 266 croissent rapidement, les exposants intervenant dans les représentations dans les bases successives considérées tendent, eux, cependant à décroître. L’exposant 3 a été remplacé par un exposant 2 dans u_5 . Il finira par être remplacé par un exposant 1 et nécessairement l’exposant 8, à son tour, finira à son tour par être remplacé par un exposant 7

C’est cette caractéristique, commune à toutes les suites de Goodstein, qui va permettre de montrer qu’elles convergent vers 0. Pour cela, il faut faire intervenir, comme annoncé, des ordinaux infinis. Nous faisons donc une digression de ce côté-là.

2. Ordinaux et bon ordre

Ordinaux:
Les ordinaux sont associés à l’idée de rangement. On peut ranger les éléments d’un ensemble fini en les numérotant à l’aide des entiers : premier, deuxième…. La notion d’ordinal transfini, due au mathématicien Georg Cantor qui l’a développée dans une série d’articles parus à la fin du 19ème siècle, prolonge cette idée. Le premier ordinal plus grand que tous les entiers est noté \omega, c’est le premier ordinal infini. Il a un successeur \omega +1, qui a lui-même pour successeur \omega + 2, qui a lui-même pour successeur… Le plus petit ordinal plus grand que tous les \omega + n, est \omega + \omega noté \omega . 2 (voir [3]). Le plus petit ordinal plus grand que tous les \omega . n + m est \omega ^2et, de même, le plus petit ordinal plus grand que tous les \omega ^n est noté \omega^{\omega}.


Rendered by QuickLaTeX.com

On note \varepsilon_0 le premier ordinal limite supérieur à tous les ordinaux qui sont des puissances itérées de \omega Nous nous arrêterons là mais bien sûr \varepsilon_0 a lui aussi un successeur \varepsilon_{0} +1 et la chaîne continue. En fait tous les ordinaux dont il a été question jusqu’ici ne constituent que le début de cette chaîne des ordinaux puisqu’ils sont tous dénombrables : ils peuvent en effet être tous mis en bijection avec l’ensemble des entiers.

Ordinaux et bon ordre:
L’ordre sur les ordinaux, comme celui sur les entiers, est un bon ordre : tout ensemble non vide d’ordinaux a un plus petit élément. De cette propriété, qui pour les entiers est à la base du raisonnement par récurrence, on déduit qu’il ne peut exister de suite infinie strictement décroissante d’ordinaux. En effet supposons qu’une telle suite existe. Notons S l’ensemble de ses termes : S = \{ u_0 , u_1 , ... , u_n , ...\}. S a un plus petit élément, notons le \alpha. C’est un terme de la suite donc il existe un k tel que \alpha = u_k . Mais alors u_{k+1} < u_k et appartient à S, ce qui contredit la définition de \alpha. Une telle suite n’existe donc pas. La propriété de bon ordre permet donc de généraliser aux ordinaux les raisonnements dits « par descente infinie » que l’on peut faire sur les entiers.

Après cette parenthèse, revenons aux suites de Goodstein.

3. La preuve de la convergence vers 0 des suites faibles de Goodstein

A chaque suite faible de Goodstein, on va associer une suite strictement décroissante d’ordinaux. Pour cela, on procède de la façon suivante. A l’étape n, u_n est décomposé sur la base des puissances de (n+2). Dans cette décomposition, remplaçons systématiquement la base par \omega. Pour la suite associée à 266, on obtient ainsi une nouvelle suite ( \alpha_n ) dont les premiers termes sont les suivants :


Rendered by QuickLaTeX.com

Table 2: La suite des ordinaux correspondant à une suite faible de Goodstein.

Vu son mode de construction La suite (\alpha_n) majore la suite (u_n), et elle est de plus décroissante stricte. En effet, le passage d’un terme au suivant se fait forcément de l’une des deux façons suivantes :

  • Soit le reste dans la division par la base est non nul et on le diminue de 1, tout en effectuant le changement de base (c’est le cas pour le passage de u_1 à u_2, de u_2 à u_3 et de u_4 à u_5).
  • Soit ce reste est nul et pour obtenir la décomposition additive du terme suivant, après avoir fait le changement de base, il faut casser le terme de la décomposition ayant le plus faible exposant (c’est le cas pour le passage de u_0 à u_1 , de u_3 à u_4 et de u_9 à u_{10}). Mais dans les deux cas, le nouvel ordinal obtenu est strictement inférieur au précédent.

Nous invitions le lecteur à écrire les deux suites (u_n) et (\alpha_n) lorsque u_0 =5. Pour quelle valeur de n a-t-on \alpha_n = \omega? Que vaut alors u_n et que se passe-t-il pour les termes suivants des deux suites ? (voir 4).

Or, comme les ordinaux sont bien ordonnés, il n’existe pas de suite infinie décroissante stricte d’ordinaux. Il existe donc un m tel que \alpha_m = 0. Et, vu que pour tout n, u_n \leqslant \alpha_n, on en déduit que u_m est aussi égal à 0. La suite (u_n) atteint donc elle aussi 0 en un nombre fini de pas qui peut être bien sûr très grand.

Nous sommes prêts maintenant à aborder les suites de Goodstein proprement dites. Elles sont définies de façon légèrement différente et leur croissance est beaucoup plus spectaculaire ! Mais, curieusement, le principe de la preuve est similaire.

4. Les suites de Goodstein

Revenons au nombre 266 et à sa décomposition sur la base des puissances de 2: 2^8 + 2^3 + 2^1. Dans cette décomposition, les exposants n’ont pas été exprimés en base 2. C’est ce que nous allons faire maintenant : 3 = 2^1 + 1 et 8 = 2^3 = 2^{2^1 +1}. D’où une nouvelle représentation de 266 qui, cette fois, ne fait intervenir que des chiffres inférieurs ou égaux à la base. Pour construire le terme suivant de la suite de Goodstein, on remplace toutes les occurrences de la base 2 par des 3 et on enlève 1 comme on le faisait pour la suite faible. Puis on itère le processus.
Partant de m_0 = 266, on obtient ainsi successivement (voir [5]):

m_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1
m_1 = 3^{3^{3+1}} + 3^{3+1} +3^1 - 1 = 3^{3^{3+1}} + 3^{3+1} + 2\\ = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38}
m_2 = 4^{4^{4+1}} + +4^{4+1} +1 \approx 10^{616}
m_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}
m_4 = 6^{6^{6+1}} + 6^{6+1} -1 = 6^{6^{6+1}} + 5.6^6 + 5.6^5 + 5. 6^4 +5.6^3 + 5.6^2 +5.6^1 + 5\\ \approx10^{217832}
m_5 = 7^{7^{7+1}} + 5.7^7 + 5.7^5 + 5. 7^4 +5.7^3 + 5.7^2 +5.7^1 + 4\\ \approx 10^{4 871 822}

Table 3.

Comme on le voit, la croissance est cette fois impressionnante et, même avec un ordinateur, vous ne pourrez pas pousser très loin l’exploration ! Et pourtant, cette suite, comme toutes les suites de Goodstein, finit par devenir décroissante et converge vers 0. La preuve est en tout point similaire à celle que nous avons esquissée pour les suites faibles. On associe une suite (\beta_n) à la suite (m_n) en remplaçant chaque occurrence de la base par \omega. Et l’on montre par un raisonnement analogue à celui fait plus haut que la suite d’ordinaux ainsi obtenus est strictement décroissante. Ce raisonnement se généralise à toutes les suites de Goodstein, les ordinaux qui interviennent étant tous dénombrables et inférieurs à \varepsilon_0 (ils étaient tous inférieurs à \omega^{\omega} pour les suites faibles de Goodstein).

Cette démonstration est sans aucun doute élégante mais, pour démontrer un théorème portant sur des suites d’entiers, elle nous a obligés à sortir du cadre de l’arithmétique usuelle, appelée aussi arithmétique de Peano car, le premier, il en a formalisé les axiomes. Il nous a fallu nous situer dans le cadre plus général de la théorie des ensembles pour faire intervenir des ordinaux transfinis. Et pourtant le langage de l’arithmétique de Peano suffit à formuler le théorème de Goodstein qui affirme que toutes les suites de Goodstein convergent vers 0 ! Il est alors normal de se demander s’il est possible de trouver une autre démonstration qui, elle, ne ferait pas sortir du cadre de l’arithmétique usuelle. La réponse est connue, c’est : Non ! Elle a été apportée par Laurie Kirby et Jeff Paris en 1982, soit près de 40 ans après l’introduction des suites de Goodstein. Ils ont en effet montré que le théorème de Goodstein pouvait se ramener à celui de Gentzen (1936) qui prouve la consistance de l’arithmétique de Peano. Or l’on sait, par le théorème d’incomplétude de Gödel, que cette consistance n’est pas démontrable dans l’axiomatique de Peano elle-même. Donc le théorème de Goodstein n’est pas non plus démontrable dans l’arithmétique de Peano. Inutile donc pour les mathématiciens de dépenser leur énergie à chercher une telle preuve !
En revanche, et cela peut paraître étonnant, la convergence vers 0 des suites faibles de Goodstein peut, elle, être démontrée sans sortir du cadre de cette arithmétique car on peut y exprimer des inductions qui ne dépassent pas l’ordinal \omega^{\omega}. Une telle démonstration nous a été proposée par E.A. Cichon qui avait introduit les suites faibles de Goodstein dans (Cichon, 1983). Précisons, pour le lecteur intéressé, que l’on introduit pour cela les m-uplets de coefficients de la décomposition des u_n en base (n+2) et que l’on met sur ces m-uplets l’ordre lexicographique qui est un bon ordre.

5. Suites de Goodstein et jeu de l’hydre

Dans leur article, Kirby et Paris, mentionnent un autre processus qui présente des similarités profondes avec les suites de Goodstein : le jeu de l’hydre (voir aussi (Dehornoy, 2001)). Il tient son nom de la référence mythologique au combat d’Hercule contre l’hydre de Lerne dont les têtes coupées repoussaient sans cesse. C’est un jeu dans lequel l’hydre est modélisée par un arbre. Les têtes de l’hydre sont, à tout instant, les sommets terminaux de l’arbre. Si Hercule coupe une tête qui n’est pas directement reliée à la racine de l’arbre en supprimant l’arête associée, l’hydre se régénère à partir des sommets situés à deux niveaux sous la tête coupée. Elle peut le faire de différentes façons. Par exemple, dans l’exemple ci-dessous utilisé par Kirby et Paris et repris par Hodgson, si la tête est coupée à l’étape n du jeu, l’hydre génère n copies de la partie de l’arbre située au-dessus de ce nœud. A chaque étape, la partie coupée est indiquée en pointillés, la partie qui se régénère en rouge et la partie qui a repoussé en bleu.

On peut montrer que, quelle que soit la configuration de l’hydre, la stratégie d’Hercule et celle de l’hydre, Hercule finit toujours par couper toutes les têtes, même si cela peut nécessiter un temps très très long. La démonstration, comme dans le cas de la convergence des suites de Goodstein, est basée sur l’association aux arbres successifs d’une suite strictement décroissante d’ordinaux. Comme on peut le conjecturer à partir des représentations ci-dessus, l’arbre peut s’étendre en largeur mais sa hauteur, elle, finit nécessairement par diminuer. On pourra trouver une simulation du jeu de l’hydre sur le site : http://math.andrej.com/wp-content/uploads/2008/02/Hydra/hydraApplet.html

6. Quelques leçons à tirer de cet exemple

Cet exemple nous semble intéressant à plus d’un titre. Il montre tout d’abord que la logique n’est pas qu’affaire métamathématique. Des théorèmes comme le théorème d’incomplétude de Gödel qui peuvent paraître justement de nature exclusivement métamathématique, des objets qui peuvent paraître très éloignés des mathématiques élémentaires comme les ordinaux transfinis, s’incarnent dans des théorèmes qui portent sur des propriétés d’objets mathématiques ordinaires (suites, arbres). Il attire aussi notre attention sur le fait que démontrer un résultat fait uniquement sens dans le cadre d’un langage et d’une théorie qui s’exprime dans ce langage, même si ceci reste souvent pour nous implicite. Une propriété concernant des entiers peut ainsi pouvoir être démontrée dans la théorie des ensembles et non dans la théorie de Peano qui est donc strictement plus faible.
Mais cet exemple nous semble aussi instructif au-delà de la seule logique. Il nous montre d’abord les limites de l’intuition : des suites dont tout nous porte a priori à croire qu’elles vont tendre vers l’infini vont finalement devenir décroissantes et atteindre 0 en un nombre fini de pas. Il nous montre l’intérêt qu’il peut y avoir pour comprendre un phénomène à modifier le problème initial en un problème plus accessible : ici c’est celui des suites faibles de Goodstein pour lequel l’exploration est davantage possible. Il nous montre comment l’étude d’exemples génériques, dans ce cas simplifié, permet de comprendre la raison d’être du phénomène avant même que l’on introduise, pour formaliser le raisonnement dans le cas général, des ordinaux transfinis. Il nous donne enfin à voir à la fois la puissance et les limites de la technologie, sa capacité à nous faire ressentir la croissance rapide de la suite, mais aussi ses limites aussi face à l’explosion numérique que génère ce processus.

Références :

[1] Un entier b >0 appelé la base étant choisi, tout entier naturel n peut s’écrire de façon unique sous la forme suivante, dénommée sa décomposition en base b : n=d_m . b^m +d_{m-1} .b^{m-1} + ... + d_1 b^1 + d_0, tous les d_i étant des entiers compris entre 0 et b-1, et d_m étant non nul (n est alors supérieur ou égal à b^m et inférieur strict à b_{m+1}). L’écriture usuelle des nombres correspond à leur décomposition dans la base dix.

[2] La suite de valeur initiale u_0 = 3 (=2^1 +1) a pour termes successifs : u_1= 3^1 (=3^1 + 1 - 1), u_2 = 3 (= 4^1 - 1) qui est plus petit que la base, et donc u_3= 2 ( = 3 - 1), u_4=1 et u_5=0.

[3] On prolonge en effet aux ordinaux les opérations sur les entiers mais, attention, la commutativité de l’addition et de la multiplication ne sont pas conservées.

[4] Les réponses sont les suivantes : \alpha_n = \omega pour n = 29, et alors u_{29} = 31^1. Pour obtenir u_{30}, on remplace la base 31 par la base 32 et on soustrait 1, donc u_{30} = 32^1 - 1 = 31 qui est plus petit que la base.On a alors \alpha_{30} = 31. A partir de l’indice 30, les suites (u_n) et (\alpha_n) sont égales et forment une suite arithmétique décroissante de raison -1. Il s’ensuit que u_{61} = \alpha_{61} = 0.

[5] On pourra pour cela utiliser le site http://www.wolframalpha.com.

[6] Cichon, E. A. (1983). A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods, Proc. Amer. Math. Soc., 87, 704-706.

[7] Dehornoy, P. (2001). L’infini est-il nécessaire ? Pour la Science, Dossier.

[8] Dehornoy, P. (2009). Cantor et les infinis.

[9] Hodgson B. (2007). Envolées intersidérales… à destination terrestre !. Accromath. Hiver-printemps 2007, www.accromath.ca

[10] Hodgson B. (2004). Herculean of Sisyphean tasks? EMS Newsletter, March 2004, pp. 11-16.

[11] Goodstein, R. L. (1944). On the Restricted Ordinal Theorem, Journal of Symbolic Logic, 9, 33-41,

[12] Kirby, L. and Paris, J. (1982). Accessible Independence Results for Peano Arithmetic, Bulletin of the London Mathematical Society, 14, 285-293.

[13] Perrin, D. (2008). La suite logistique et le chaos.

Ce post est disponible en: Anglais, Allemand, Italien, Espagnol, Arabe, Khmère, Portugais - du Brésil

This entry was posted in Vignettes. Bookmark the permalink.

  1. Nicolas says:

    Très bonne vignette, bravo ! Très clair et interessant.

    Il me reste cependant une question, après lecture de l’article: en quoi sort-on de l’arithmétique de Peano en faisant intervenir des ordinaux supérieurs à omega^omega, et pourquoi n’en sort-on pas quand on reste en dessous de omega^omega ?

    Merci,

    Nicolas

    • Antoine Nectoux says:

      L’arithmetique de Peano ne concerne que les nombre entiers, c’est a dire l’arithmetique classique. Les ordinaux infinis comme omega n’en font pas partie.

    • Gasole says:

      Parce que quand on reste “sous” ω^ω, en fait, les ordinaux ne sont pas nécessaires pour établir une preuve, ils sont juste une façon élégante d’emboîter un nombre fini mais quelconque de récurrences

Leave a Reply

Your email address will not be published. Required fields are marked *