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 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. 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ériditaire d'un entier en base n est unique, de même que la représentation en base n. 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.