Théorème de Goodstein

En logique mathématique , le théorème de Goodstein est un énoncé sur les nombres naturels , prouvé par Reuben Goodstein en 1944, qui stipule que toute suite de Goodstein (telle que définie ci-dessous) se termine finalement à 0. Laurence Kirby et Jeff Paris ont montré qu'il est indémontrable en arithmétique de Peano (mais il peut être prouvé dans des systèmes plus forts, tels que l'arithmétique du second ordre ou la théorie des ensembles de Zermelo-Fraenkel ). Il s'agit du troisième exemple d'un énoncé vrai sur les nombres naturels qui est indémontrable en arithmétique de Peano, après les exemples fournis par le théorème d'incomplétude de Gödel et la preuve directe de Gerhard Gentzen en 1943 de l'improuvabilité de l' ε ₀ -induction en arithmétique de Peano. Le théorème de Paris-Harrington en a donné un autre exemple.

Kirby et Paris ont introduit un jeu d'hydre basé sur la théorie des graphes, dont le comportement est similaire à celui des suites de Goodstein : l'« hydre » (du nom de l'hydre mythologique à plusieurs têtes de Lerne ) est un arbre enraciné, et un mouvement consiste à couper l'une de ses « têtes » (une branche de l'arbre), ce à quoi l'hydre répond en faisant pousser un nombre fini de nouvelles têtes selon certaines règles. Kirby et Paris ont prouvé que l'hydre finira par être tuée, quelle que soit la stratégie utilisée par Hercule pour lui couper la tête, même si cela peut prendre beaucoup de temps. Tout comme pour les suites de Goodstein, Kirby et Paris ont montré que cela ne peut pas être prouvé en arithmétique de Peano seule.

Les suites de Goodstein sont définies selon un concept appelé « notation héréditaire en base n ». Cette notation est très similaire à la notation positionnelle en base n habituelle , mais elle ne suffit pas pour les besoins du théorème de Goodstein.

Pour obtenir la notation ordinaire en base n , où n est un nombre naturel supérieur à 1, un nombre naturel arbitraire m est écrit comme une somme de multiples de puissances de n :

où chaque coefficient a _i satisfait 0 ≤ a _i < n et a _k ≠ 0 . Par exemple, pour obtenir la notation en base 2 , on écrit

Ainsi, la représentation en base 2 de 35 est 100011, ce qui signifie 2 ⁵ + 2 + 1. De même, 100 représenté en base 3 est 10201 :

Notez que les exposants eux-mêmes ne sont pas écrits en notation de base n . Par exemple, les expressions ci-dessus incluent 2 ⁵ et 3 ⁴ , et 5 > 2, 4 > 3.

Pour convertir une notation en base n (qui est une étape dans la réalisation d'une représentation en base n ) en une notation héréditaire en base n , réécrivez d'abord tous les exposants comme une somme de puissances de n (avec la limitation sur les coefficients 0 ≤ a _i < n ). Réécrivez ensuite tout exposant à l'intérieur des exposants en notation en base n (avec la même limitation sur les coefficients), et continuez de cette manière jusqu'à ce que chaque nombre apparaissant dans l'expression (à l'exception des bases elles-mêmes) soit écrit en notation en base n .

Par exemple, alors que 35 en notation ordinaire en base 2 est 2 ⁵ + 2 + 1 , il s'écrit en notation héréditaire en base 2 comme

en utilisant le fait que 5 = 2 ^{2 1} + 1. De même, 100 dans la notation héréditaire en base 3 est

La suite de Goodstein d'un nombre m est une suite de nombres naturels. Le premier élément de la suite est m lui-même. Pour obtenir le second, , écrivez m en notation héréditaire en base 2, remplacez tous les 2 par des 3, puis soustrayez 1 du résultat. En général, le terme 1 + n , , de la suite de Goodstein de m est le suivant :

• Prenons la représentation héréditaire en base n  + 1 de .
• Remplacez chaque occurrence de la base n  + 1 par n  + 2 .
• Soustraire un. (Notez que le terme suivant dépend à la fois du terme précédent et de l'indice n .)
• Continuez jusqu’à ce que le résultat soit zéro, auquel cas la séquence se termine.

Les premières séquences de Goodstein se terminent rapidement. Par exemple, elles se terminent à la 6e étape :

Les séquences de Goodstein ultérieures augmentent pour un très grand nombre d'étapes. Par exemple, OEIS : A056193 commence comme suit :

Les éléments de continuent d'augmenter pendant un certain temps, mais à la base , ils atteignent le maximum de , y restent pour les étapes suivantes, puis commencent leur descente.

Cependant, même cela ne donne pas une bonne idée de la rapidité avec laquelle les éléments d'une séquence de Goodstein peuvent augmenter. augmente beaucoup plus rapidement et commence comme suit :

Malgré cette croissance rapide, le théorème de Goodstein stipule que chaque séquence de Goodstein se termine finalement à 0, quelle que soit la valeur de départ.

Le théorème de Goodstein peut être démontré (en utilisant des techniques en dehors de l'arithmétique de Peano, voir ci-dessous) comme suit : Étant donnée une suite de Goodstein G ( m ), nous construisons une suite parallèle P ( m ) de nombres ordinaux sous forme normale de Cantor qui est strictement décroissante et se termine. Une mauvaise compréhension courante de cette preuve est de croire que G ( m ) tend vers 0 parce qu'elle est dominée par P ( m ). En fait, le fait que P ( m ) domine G ( m ) ne joue aucun rôle. Le point important est que G ( m )( k ) existe si et seulement si P ( m )( k ) existe (parallélisme), et la comparaison entre deux membres de G ( m ) est préservée lors de la comparaison des entrées correspondantes de P ( m ). Alors si P ( m ) se termine, G ( m ) se termine aussi . Par régression infinie , G ( m ) doit atteindre 0, ce qui garantit la terminaison.

Nous définissons une fonction qui calcule la représentation héréditaire de base k de u , puis remplace chaque occurrence de la base k par le premier nombre ordinal infini ω. Par exemple, .

Chaque terme P ( m )( n ) de la suite P ( m ) est alors défini comme f ( G ( m )( n ), n+1 ). Par exemple, G (3)(1) = 3 = 2 ¹ + 2 ⁰ et P (3)(1) = f (2 ¹ + 2 ⁰ ,2) = ω ¹ + ω ⁰ = ω + 1 . L'addition, la multiplication et l'exponentiation des nombres ordinaux sont bien définies.

Nous affirmons que : $f(G(m)(n+1),n+2)f\left(G\right(m\left)\right(n),n+1)>f\left(G\right(m\left)\right(n+1),n+2)$f(G(m)(n+1),n+2)}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ec796c9e26e97dafdd6f97a301ec7acb894585e">

Soit G ( m )( n ) après avoir appliqué la première opération de changement de base lors de la génération de l'élément suivant de la séquence de Goodstein, mais avant la deuxième opération moins 1 de cette génération. Observez que .

Ensuite . Appliquons maintenant l' opération moins 1 , et , comme . Par exemple, et , donc et , qui est strictement plus petit. Notez que pour calculer f(G(m)(n),n+1) , nous devons d'abord écrire G ( m )( n ) en notation héréditaire de base n +1 , car par exemple l'expression n'est pas un ordinal. $f(G(m)(n+1),n+2)f\left(G^{\prime }\right(m\left)\right(n),n+2)>f\left(G\right(m\left)\right(n+1),n+2)$f(G(m)(n+1),n+2)}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ae9713d26e221daa81d56f4dd97d925b0b423216">

Ainsi, la suite P ( m ) est strictement décroissante. Comme l'ordre standard < sur les ordinaux est bien fondé , une suite strictement décroissante infinie ne peut exister, ou de manière équivalente, toute suite strictement décroissante d'ordinaux se termine (et ne peut être infinie). Mais P ( m )( n ) est calculée directement à partir de G ( m )( n ). Par conséquent, la suite G ( m ) doit également se terminer, ce qui signifie qu'elle doit atteindre 0.

Bien que cette démonstration du théorème de Goodstein soit assez simple, le théorème de Kirby-Paris , qui montre que le théorème de Goodstein n'est pas un théorème de l'arithmétique de Peano, est technique et considérablement plus difficile. Il utilise des modèles non standard dénombrables de l'arithmétique de Peano.

La preuve ci-dessus fonctionne toujours si la définition de la suite de Goodstein est modifiée de sorte que l'opération de changement de base remplace chaque occurrence de la base b par b + 2 au lieu de b + 1. Plus généralement, soit b ₁ , b ₂ , b ₃ , ... une séquence non décroissante d'entiers avec b ₁ ≥ 2. Alors soit le ( n + 1)-er terme G ( m )( n + 1) de la suite de Goodstein étendue de m comme suit :

• Prenons la représentation de base héréditaire b _n de G ( m )( n ).
• Remplacez chaque occurrence de la base b _n par b _{n +1} .
• Soustraire un.

Une simple modification de la preuve ci-dessus montre que cette séquence se termine toujours. Par exemple, si b _n = 4 et si b _{n +1} = 9 , alors , donc l'ordinal est strictement supérieur à l'ordinal

La version étendue est en fait celle considérée dans l'article original de Goodstein, où Goodstein a prouvé qu'elle est équivalente au théorème ordinal restreint (c'est-à-dire l'affirmation selon laquelle l'induction transfinie en dessous de ε ₀ est valide), et a donné une preuve finitiste pour le cas où (équivalent à l'induction transfinie jusqu'à ).

Le théorème de Goodstein étendu sans aucune restriction sur la séquence b _n n'est pas formalisable en arithmétique de Peano (PA), car une telle séquence infinie arbitraire ne peut pas être représentée en PA. C'est ce qui semble avoir empêché Goodstein de prétendre en 1944 que le théorème de Goodstein étendu est indémontrable en PA en raison du deuxième théorème d'incomplétude de Gödel et de la preuve de cohérence de PA par Gentzen en utilisant l'induction ε ₀ . Cependant, l'inspection de la preuve de Gentzen montre qu'elle n'a besoin que du fait qu'il n'existe pas de séquence infinie strictement décroissante récursive primitive d'ordinaux, donc limiter b _n aux séquences récursives primitives aurait permis à Goodstein de prouver un résultat d'indémontrable. De plus, avec la technique relativement élémentaire de la hiérarchie de Grzegorczyk , il peut être démontré que toute séquence infinie primitive récursive strictement décroissante d'ordinaux peut être « ralentie » de sorte qu'elle puisse être transformée en une séquence de Goodstein où b _n = n + 1 , donnant ainsi une preuve alternative au même résultat que Kirby et Paris ont prouvé.

La fonction de Goodstein , , est définie de telle sorte que est la longueur de la séquence de Goodstein qui commence par n . (Il s'agit d'une fonction totale puisque chaque séquence de Goodstein se termine.) Le taux de croissance extrêmement élevé de peut être étalonné en le reliant à diverses hiérarchies de fonctions standard indexées par ordre ordinal, telles que les fonctions de la hiérarchie de Hardy et les fonctions de la hiérarchie à croissance rapide de Löb et Wainer :

• Kirby et Paris (1982) ont prouvé que

(Pour deux fonctions quelconques , est dit dominant si pour tout suffisamment grand .)$g(n)f\left(n\right)>g\left(n\right)$g(n)}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/675ebf1382ef91952c46c2669d87a86b139b8225">

• Cichon (1983) a montré que

où est le résultat de la mise en notation héréditaire de base 2 de n , puis du remplacement de tous les 2 par ω (comme cela a été fait dans la preuve du théorème de Goodstein).

• Caicedo (2007) a montré que si avec alors$m\_\{2\}>\backslash cdots\; >m\_\{k\},m_1>m_2>\cdots >m_k,$m_{2}>\cdots >m_{k},}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/771baf4748b87d17597a7c690c7bf2793b7fab79">

Quelques exemples :

(Pour la fonction d'Ackermann et les limites du nombre de Graham, voir Hiérarchie à croissance rapide#Fonctions dans les hiérarchies à croissance rapide .)

Le théorème de Goodstein peut être utilisé pour construire une fonction calculable totale dont l'arithmétique de Peano ne peut pas prouver qu'elle est totale. La suite de Goodstein d'un nombre peut être effectivement énumérée par une machine de Turing ; ainsi, la fonction qui associe n au nombre d'étapes nécessaires à la fin de la suite de Goodstein de n est calculable par une machine de Turing particulière. Cette machine énumère simplement la suite de Goodstein de n et, lorsque la séquence atteint 0 , renvoie la longueur de la séquence. Étant donné que chaque séquence de Goodstein se termine éventuellement, cette fonction est totale. Mais comme l'arithmétique de Peano ne prouve pas que chaque séquence de Goodstein se termine, l'arithmétique de Peano ne prouve pas que cette machine de Turing calcule une fonction totale.