Accueil » Publications » Le Bulletin Vert » Les dossiers » Les suites de Goodstein ou la (...)
  APMEP   Les suites de Goodstein ou la puissance du détour par l’infini

Article du bulletin 498

Adhérer ou faire un don

- 19 septembre 2014 -

Michèle Artigue et Ferdinando Arzarello

Étudier l’évolution de phénomènes conduit souvent dans l’enseignement secondaire à étudier des suites numériques, à s’interroger sur leurs types de croissance, et sur leur convergence éventuelle. Les exemples de croissance rencontrés 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). 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

Prenons comme point de départ, le nombre 266 utilisé par Kirby et Paris qui, on le verra, jouent un rôle important dans cette histoire. Comme tout entier positif, il admet une décomposition additive unique sur la base des puissances de 2 [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 pour $u_1=3^8 + 3^3 + 3^1-1$ , soit 6 590. En base 3, ce nombre a en fait comme décomposition additive : $3^8 + 3^3 + 3^1+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 + 3^1+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 \cdot 6^2+6^2-1$$

$$\text{donc } u_4= 6^8 +5 \cdot 6^2+ 5 \cdot 6^1 +6-1= 6^8 +5 \cdot 6^2+ 5 \cdot 6^1 +5=1\ 679\ 831$$

$$u_5=7^8 +5 \cdot 7^2 +5 \cdot 7^1 +5-1=7^8 +5 \cdot 7^2 +5 \cdot 7^1 +4=5\ 765\ 085$$

$$u_6=8^8+5\cdot8^2+5\cdot8^1+3=16\ 777\ 579$$

$$u_7=9^8+5\cdot9^2+5\cdot9^1+2=43\ 047\ 173$$

....

$$u_{10}=12^8+5\cdot12^2+5\cdot12^1-1=12^8+5\cdot12^2+4\cdot12^1+12-1$$

$$\text{donc } u_{10}=12^8+5\cdot12^2+4\cdot12^1+11=429\ 928\ 475$$

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, u_1= 1 - 1 = 0$. Pour $u_0= 2 = 2^1 , u_1= 3^1 - 1 = 2, u_2= 1 \text{ et } u_3= 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 [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 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 19e 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$, et ainsi de suite… Le plus petit ordinal plus grand que tous les $\omega+n$ est $\omega+\omega$ noté $\omega\cdot2$(on prolonge en effet aux ordinaux les opérations sur les entiers mais la commutativité de l’addition et de la multiplication ne sont pas conservées). Le plus petit ordinal plus grand que tous les $\omega\cdotn$est $\omega^2$ et, de même, le plus petit ordinal plus grand que tous les $\omega^n$ est $\omega^\omega$. 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$. La propriété de bon ordre permet donc de généraliser aux ordinaux les raisonnements par descente infinie que l’on fait au lycée 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

À 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. À 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 : 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$, 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 invitons 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 ? [3]

Or, comme les ordinaux sont bien ordonnés, il n’existe pas de suite infinie décroissante stricte d’ordinaux. Il existe donc un n tel que $\alpha_n = 0$. Et, vu que pour tout n, $u_n<\alpha_n$ , on en déduit que la suite ($u_n$) atteint 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 [4] : 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 Laurent 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. 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 (ici des suites). 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 :

Cichon, E. A. (1983). A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods, Proceedings of the American Mathematical Society, 87, 704-706.

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

Dehornoy, P. (2009). Cantor et les infinis. http://www.math.unicaen.fr/ dehorno...

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

Hodgson B. (2004). Herculean of Sisyphean tasks ? EMS Newsletter, March 2004, p. 11-16.

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

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

Perrin, D. (2008). La suite logistique et le chaos. http://www.math.upsud.fr/ perrin/Co...

(Article mis en ligne par Armelle BOURGAIN)

[1] Un entier b > 0 appelé la base étant choisi, tout entier n peut s’écrire de façon unique sous la forme suivante, dénommée sa décomposition en base b : $n = d_m\cdot b^m+d_{m-1}\cdot b^{m-1}+ ... + d_1\cdot 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), u_3= 2, u_4= 1, u_5= 0$.

[3] 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$. On a alors $\alpha_{30} = 31$. À 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$.

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


 Accueil   Plan du site   Haut de la page   Page précédente