Aller au contenu

Théorème de Goodstein

Un article de Wikipédia, l'encyclopédie libre.

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'à ), 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

[modifier | modifier le code]

Notation héréditaire en base n

[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 classique de la décomposition en base n :

où chaque 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 : , et en notation héréditaire (on parle aussi de notation itérée) en base 2 : .

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

[modifier | modifier le code]

La suite de Goodstein d'un entier m est notée G(m). Son premier élément est G1(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 est définie en posant et en itérant, pour  :

  • si , n'est pas défini, la suite est finie de longueur n ;
  • sinon :
  1. écrire l'entier en notation héréditaire en base n + 1, et remplacer n + 1 par n + 2 ;
  2. soustraire 1 ; on obtient ainsi .

Énoncé du théorème

[modifier | modifier le code]

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

[modifier | modifier le code]

Les toutes premières suites de Goodstein se terminent rapidement.

  • Ainsi, pour G(1) :
    •  ;
    • .
  • Et pour G(2) :
    •  ;
    •  ;
    •  ;
    • .
  • Pour G(3) :
Base Calcul de (3) Notation héréditaire Notes
2 3 = (21+1) La notation héréditaire est indiquée entre parenthèses
3 3 = (31) On change 2 en 3, puis on soustrait 1
4 3 = (3) On change 3 en 4 puis on soustrait 1
5 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 1 = (1)
7 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×2n : la valeur précédente ne comporte pas de terme unité (terme de (p-1)0), 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×227 – 1 = 402 653 183, le terme de la suite vaut b2 = 162 129 585 780 031 489. 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, 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)2b – 1 = 3×2402 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×2402 653 211 – 1, qui est d'ailleurs un nombre de Woodall (car 3×2402 653 211 = 402 653 184 × 2402653184).

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 10120 000 000[1].

  • 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 :
,
(avec k symboles ),
,
,

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
7 625 597 484 990
environ 1,3 × 10154
environ 1,8 × 102 184
environ 2,6 × 1036 305
environ 3,8 × 10695 974
environ 6 × 1015 151 335

environ 4,3 × 10369 693 099

...

En dépit de cette rapide croissance (de l'ordre de nn7, 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

[modifier | modifier le code]

Théorème de Goodstein

[modifier | modifier le code]

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 de la suite P(m) s'obtient en appliquant une transformation au terme 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 , et on y remplace chaque occurrence de n+1 par le premier ordinal infini, ω ; ainsi, par exemple, et . 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 .

Après soustraction de 1, sera strictement inférieur à  :

  • quand est un ordinal successeur, c'est-à-dire de forme normale de Cantor du type , où est un entier non nul, . Ainsi est strictement supérieur à  ;
  • quand est un ordinal limite, lui est strictement inférieur, ainsi est strictement supérieur à  ;
  • 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 serait toujours défini). Donc P(m) serait également infinie (puisque aussi serait toujours défini). Mais P(m) est décroissante strictement ; or l'ordre standard < sur l'ensemble des ordinaux inférieurs à 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 = 0, et par définition de P(m), on a = 0 aussi).

Indécidabilité dans l'axiomatique de Peano

[modifier | modifier le code]

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, , est définie par «  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 peut être mesurée en la reliant à diverses hiérarchies de fonctions indexées par des ordinaux, telles que les fonctions de la hiérarchie de Hardy (en), ou les fonctions de la hiérarchie de croissance rapide de Löb et Wainer :

  • Kirby et Paris (1982[2]) montrèrent que
croît approximativement aussi vite que (et donc que ) ; plus précisément, domine pour tout , et domine
(pour deux fonctions , on dit que domine si pour tous les assez grands). Plus précisément encore, Cichon (1983) montra que
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 avec alors
.

Voici quelques exemples :

n
1 2
2 4
3 6
4 3·2402 653 211 − 2
5 > A(5,4) (où A est la fonction d'Ackermann)
6 > A(7,6)
7 > A(9,8)
8 > A3(3,3) = A(A(61, 61), A(61, 61))
12 > fω+1(64) > G, le nombre de Graham
16 > , un nombre qui ne peut s'exprimer en notation de Conway qu'avec un nombre de flèches supérieur au nombre de Graham.
19

(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

[modifier | modifier le code]

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

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 à ε0) 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 ε0[2],[3].

  1. (en) James M. Henle, An Outline of Set Theory (lire en ligne), p. 137-138.
  2. a b c et d Laurie Kirby et Jeff Paris, « Accessible independence results for Peano arithmetic. », Bulletin of the London Mathematical Society, vol. 14, no 4,‎ , p. 285-293 (DOI 10.1112/blms/14.4.285, lire en ligne).
  3. David Madore, « J'apprends à compter jusqu'à ψ(εΩ+1) et à dompter les hydres », sur madore.org,‎ (consulté le ).

Bibliographie

[modifier | modifier le code]