Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Goodstein
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.