Théorème de Goodstein

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 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'à epsilon_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.

Sommaire

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 ai 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 : 25 + 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 commençant à n= 2, et en posant G(m)(2) = m)

(1) Écrire l'entier G(m)(n) en notation héréditaire en base n, et remplacer n par n+1;
(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 \times 2^{n} . Lorsqu'on atteint la base b = 3 \times 2^{27} -1 = 402653183, le terme de la suite vaut b2 = 162129585780031489.

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 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 10120000000.

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) = n2n
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

Le théorème de Goodstein peut être démontré (par une méthode qui n'est pas accessible dans l'arithmétique de Peano) en utilisant des ordinaux : étant donnée une suite de Goodstein G, on construit une suite parallèle P d'ordinaux telle que P majore G, décroisse et s'annule à partir d'un certain rang. Il en sera alors de même de la suite de Goodstein G.

Pour construire le terme d'ordre n de la suite P, on prend la représentation héréditaire en base n du terme d'ordre n de la suite de Goodstein G, et on y remplace chaque instance de n par le premier ordinal infini, ω. Addition, multiplication et exponentiation de nombres ordinaux sont bien définies, et le résultat est un ordinal supérieur ou égal à l'élément original de G.

  • Lorsqu'on effectue un changement de base dans la suite de Goodstein, on ne modifie pas l'élément de la suite parallèle, qui reste supérieur ou égal au résultat obtenu. Par exemple, l'inégalité 3 \cdot 4^{4^4} + 4 \leq 3 \omega^{\omega^\omega} + \omega reste valable lorsqu'on remplace tous les 4 par des 5.
  • Lorsqu'on retranche ensuite une unité à l'élément de la suite de Goodstein, l'élément parallèle que l'on construit est strictement inférieur au terme qui le précède.

Ainsi, la suite parallèle majore la suite de Goodstein, et décroît strictement. Or, du fait que les ordinaux sont bien ordonnés, il n'existe pas de suite infinie strictement décroissante d'ordinaux. Aussi la suite parallèle P doit-elle en fait atteindre 0 au bout d'un nombre fini d'étapes. La suite de Goodstein G, majorée par P, devra faire de même.

Tandis que la preuve du théorème de Goodstein est relativement facile, le théorème de Laurence Kirby (de) 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

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) dont le premier terme est 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,
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 20 2 − 1 Hω(1) − 1 f0(3) − 2 2
2 21 21 + 1 − 1 Hω + 1(1) − 1 f1(3) − 2 4
3 21 + 20 22 − 1 H_{\omega^\omega}(1) - 1 f1(f0(3)) − 2 6
4 22 22 + 1 − 1 H_{\omega^\omega + 1}(1) - 1 fω(3) − 2 3·2402653211 − 2
5 22 + 20 22 + 2 − 1 H_{\omega^\omega + \omega}(1) - 1 fω(f0(3)) − 2 > A(5,4) (où A est la fonction d'Ackermann)
6 22 + 21 22 + 2 + 1 − 1 H_{\omega^\omega + \omega + 1}(1) - 1 fω(f1(3)) − 2 > A(7,6)
7 22 + 21 + 20 22 + 1 − 1 H_{\omega^{\omega + 1}}(1) - 1 fω(f1(f0(3))) − 2 > A(9,8)
8 22 + 1 22 + 1 + 1 − 1 H_{\omega^{\omega + 1} + 1}(1) - 1 fω + 1(3) − 2 > A3(3,3) = A(A(61, 61), A(61, 61))
\vdots
12 22 + 1 + 22 22 + 1 + 22 + 1 − 1 H_{\omega^{\omega + 1} + \omega^\omega + 1}(1) - 1 fω + 1(fω(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 et le nombre de Graham sont détaillées dans l'article hiérarchie de croissance rapide).

Voir aussi

Bibliographie

  • R. Goodstein, « On the restricted ordinal theorem », dans Journal of Symbolic Logic, 9 (1944), 33-41
  • L. Kirby et J. Paris, Accessible independence results for Peano arithmetic, dans Bull. London. Math. Soc., 14 (1982), 285-93
  • E. Cichon, « A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods », dans Proceedings of the American Mathematical Society, vol. 87, 1983, p. 704–706 [texte intégral] .
  • A. Caicedo, « Goodstein's function », dans Revista Colombiana de Matemáticas, vol. 41, no 2, 2007, p. 381–391 [texte intégral] .
  • Patrick Dehornoy, « L'infini est-il nécessaire ? », dans Pour la Science, 278 (2000), 102-106

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de Goodstein de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Theoreme de Goodstein — Théorème de Goodstein En logique mathématique, le théorème de Goodstein est un énoncé arithmétique qui est indécidable dans l axiomatique des entiers naturels de Peano, mais peut être démontré en utilisant l axiomatique plus puissante de la… …   Wikipédia en Français

  • Théorème de goodstein — En logique mathématique, le théorème de Goodstein est un énoncé arithmétique qui est indécidable dans l axiomatique des entiers naturels de Peano, mais peut être démontré en utilisant l axiomatique plus puissante de la théorie des ensembles, et… …   Wikipédia en Français

  • Theoreme d'incompletude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude — de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les… …   Wikipédia en Français

  • Théorème d'incomplétude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude de Gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'incomplétude de gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'indécidabilité — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème de Gödel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème de Kruskal — En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski[1], affirmant que l ensemble des arbres… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”