Théorème de Goodstein
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 prouvé en utilisant l'axiomatique plus puissante de la théorie des ensembles, et plus particulièrement des ordinaux. Le théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers...) établit que toute suite de Goodstein se termine par 0. Il donne un exemple d'énoncé indécidable particulièrement simple, contrairement aux énoncés considérés dans le théorème d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il faut préciser dans...) de Gödel.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) 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 dans 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 en base 2 : 2^{2^2+1}+2+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 et 4, et on retranche 1. On continue ainsi jusqu'à obtenir 0.

Exemples de suites de Goodstein

Les 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 represente 20.
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 (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie,...), les changements de base ultérieurs sont sans effet.
6 2 − 1 = 1 1
7 1 − 1 = 0 0

Les suites de Goodstein croissent en général pendant un grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'étapes. Par exemple, la suite G(4) commence 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
...

La suite G(4) continue à croître.

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 enfin à décroître, et atteint la valeur nulle pour la base 3 \times 2^{402653211} - 1 qui, curieusement, est un nombre de Woodall, comme toutes les autres bases finales pour des valeurs initiales supérieures à 4. 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.

Cependant, l'exemple de G(4) ne donne pas encore une idée suffisante de la vitesse (On distingue :) à laquelle la suite de Goodstein peut croître. 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 sa rapide croissance, le 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 prouvé en utilisant...) établit que chaque suite de Goodstein se termine par un 0, quelle que soit la valeur initiale de m. A titre d'exemple, le nombre de termes de la suite G(5) se calcule comme suit. Posons :

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 = gM(M),P = gN(N),Q = gP(P)

Le nombre de termes de la suite G(5) est alors Q-1.

Preuve

Le théorème de Goodstein peut être prouvé (en utilisant la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée...) des ordinaux, plus puissante que les axiomes de Peano), comme suit : étant donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...) une suite de Goodstein G(m), on construit une suite parallèle d'ordinaux dont les éléments ne sont pas plus petits que ceux de la suite donnée. Si cette suite parallèle se termine par 0, alors il en sera de même de la suite initiale.

Pour construire la suite parallèle, on prend la représentation héréditaire en base n, du (n-1)-ème élément de la suite de Goodstein, et on remplace chaque instance de n par le premier ordinal infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.) ω. Addition (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les aires, ou les volumes. En...), multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) et exponentiation de nombres ordinaux sont bien définis, et le résultat est un ordinal qui n'est pas plus petit que l'élément original de la suite de Goodstein.

Le changement de base de la suite de Goodstein ne modifie pas l'élément de la suite parallèle ; remplacer tous les 4 dans 4^(4^4) + 4 par ω est identique à remplacer tous les 4 par 5, puis remplacer les 5 par ω. L'opération de soustraction (La soustraction est l'une des opérations basiques de l'arithmétique. La soustraction combine deux ou plusieurs grandeurs du même type, appelées...), cependant, revient à diminuer l'ordinal de la séquence parallèle. Par exemple, ω^(ω^ω) + ω décroît en ω^(ω^ω) + 4 si on est en base 5. 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 doit-elle se terminer par 0 en un nombre fini d'étapes. La suite de Goodstein, majorée par la suite parallèle, devra faire de même.

Tandis que la preuve du théorème de Goodstein est relativement facile, le théorème de Kirby-Paris qui énonce que le théorème de Goodstein ne peut être prouvé à l'aide des seuls axiomes de Peano (Les axiomes de Peano sont, en mathématiques, un ensemble d'axiomes de second ordre proposés par Giuseppe Peano pour définir l'arithmétique [1].), est très technique et considérablement plus difficile. Il utilise des modèles non standard dénombrables de l'arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l'appelle plus généralement la...) de Peano

Bibliographie

  • R. Goodstein, " On the restricted ordinal theorem ", dans Journal of Symbolic Logic, 9 (1944), 33-41
  • L. Kirby et J. Paris (Paris est une ville française, capitale de la France et le chef-lieu de la région d’Île-de-France. Cette ville est construite sur une boucle de la Seine, au centre du bassin parisien,...), " Accessible independence results for Peano arithemtic ", dans Bull. London. Math. Soc., 14 (1982), 285-93
  • Patrick Dehornoy, " L'infini est-il nécessaire ? ", dans Pour la Science, 278 (2000), 102-106
Page générée en 0.220 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique