Théorème 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 théorie des ensembles, et plus particulièrement des ordinaux. Le théorème é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 de Gödel.

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 $a i$ 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+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 en 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	2¹ + 1	3	Le 1 représente 2⁰.
3	3¹ + 1 − 1 = 3	3	On change 2 en 3, puis on soustrait 1
4	4¹ − 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

Les suites de Goodstein croissent en général pendant un grand nombre d'étapes. Par exemple, la suite G(4) commence comme suit :

Notation héréditaire	Valeur
2²	4
2·3² + 2·3 + 2	26
2·4² + 2·4 + 1	41
2·5² + 2·5	60
2·6² + 6 + 5	83
2·7² + 7 + 4	109
...
2·11² + 11	253
2·12² + 11	299
...
2·23²	1058
24²+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 b² = 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 à 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 × 10¹⁵⁴
$5^{5^5}+2$	environ 1.8 × 10²¹⁸⁴
$6^{6^6}+1$	environ 2.6 × 10³⁶³⁰⁵
$7^{7^7}$	environ 3.8 × 10⁶⁹⁵⁹⁷⁴
$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 × 10^15151335
$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 × 10^369693099
...

En dépit de sa rapide croissance, le théorème de Goodstein établit que chaque suite de Goodstein se termine par 0, quelle que soit la valeur initiale de m. À titre d'exemple, le nombre de termes de la suite G(5) se calcule comme suit. Posons :

g (n) = n 2 n

$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-1.

Preuve

Le théorème de Goodstein peut être démontré (en utilisant la théorie des ordinaux, plus puissante que les axiomes de Peano), comme suit : é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 premier terme de la suite P, on prend la représentation héréditaire en base 2 du premier terme de la suite de Goodstein G, et on y remplace chaque instance de 2 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.

On construit les termes suivants de P, en parallèle aux opérations de construction de G de la manière suivante :

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, on peut imposer à l'élément parallèle que l'on construit d'être strictement inférieur au terme qui le précède : si un entier $a$ est inférieur ou égal à un ordinal non nul $b$ , alors il existe un ordinal $b'$ tel que $a-1 \leq b' < b$ .

Ainsi, la suite parallèle majore la suite de Goodstein, et décroît strictement tant qu'elle ne s'annule pas. 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 stationner sur 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 Kirby-Paris qui énonce que le théorème de Goodstein ne peut être prouvé à l'aide des seuls axiomes de Peano, est très technique et considérablement plus difficile. Il utilise des modèles non standards dénombrables de l'arithmétique de Peano.

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

Patrick Dehornoy, « L'infini est-il nécessaire ? », dans Pour la Science, 278 (2000), 102-106

Liens externes

Quelques éléments de la preuve que le théorème de Goodstein n'est pas un théorème de l'arithmétique de Peano peuvent être trouvées ici : http://www.u.arizona.edu/~miller/thesis/node11.html

Portail des mathématiques

Ce document provient de « Th%C3%A9or%C3%A8me de Goodstein ».

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 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… … 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

Dictionnaires et Encyclopédies sur 'Academic'

Théorème de goodstein