Le théorème de Goodstein

Sémantique

Logique

Infini

Mesure

Probas

Nombres

Physique

La notation d'un entier en base 2, par exemple : u₁=23₁₀=10111₂, signifie que 23=2⁴+2²+2¹+2⁰. Pour l'obtenir en superbase 2, nous devons faire disparaître tous les chiffres plus grands que 2, soit : 23=2²²+2²+2¹+2⁰. Gardons cette même définition pour les bases 3, 4, etc.

Appliquons maintenant le processus suivant. Remplaçons tous les 2 par des 3, et soustrayons 1. Nous obtenons u₂=3³³+3³+3¹+3⁰-1=7 625 597 485 017=3²⁷+3³+3¹. Nous le réécrivons en superbase 3 et nous recommençons : u₂=3³³+3³+3¹, donc notre terme suivant est u₃=4⁴⁴+4⁴+4¹−1 qui est déjà un nombre de 155 chiffres. On définit de même u₄, u₅,... u_n,... ; des nombres gigantesques ?

En 1944 R.L. Goodstein a prouvé :

Théorème : (u_n) est stationnaire en 0.

Pour sa démonstration, Goodstein utilise une certaine classe d'ensembles infinis appelés ordinaux. Ceux-ci disposent de règles arithmétiques analogues, mais non identiques, à celles de N. La transformation que nous faisons subir à un entier u_n pour former u_n+1 peut être transposée chez les ordinaux. Goodstein majore chaque terme entier u_n (donc fini) par un ordinal α_n (infini) --- une majoration très large, qui est conservée à chaque étape. Mais la transformation, chez les ordinaux, vérifie :  α_n+1 < α_n. Or il n'existe aucune suite strictement décroissante d'ordinaux : stationner en 0 est inéluctable.

Ce résultat surprenant n'est que le premier étage du paradoxe. La démonstration de Goodstein est un peu gênante : pour justifier une propriété des nombres entiers, formulable dans l'arithmétique de Peano (AP), elle fait intervenir des ensembles infinis. L'existence de ces derniers est assurée par la théorie des ensembles classiques (ZF --- [¹]), mais AP ne suffit pas pour les construire. On a donc cherché (longtemps) une preuve du théorème de Goodstein qui ne ferait appel qu'à des propriétés et des objets de AP. C'était impossible.

En 1981, L. Kirby et J. Paris ont démontré que le recours aux ensembles infinis était effectivement indispensable à la démonstration du théorème de Goodstein. Il n'existe donc aucun espoir de prouver ce dernier en restant strictement dans le cadre de AP. La démonstration est considérablement plus difficile que celle du th. lui-même. Elle utilise la notion de calculabilité : le nombre d'étapes N pour atteindre 0 à partir de la valeur u₁ n'est pas une fonction calculable (cf. les fonctions non calculables) ; grosso modo, elle croît plus vite que toute fonction pouvant s'exprimer à l'aide de formules algébriques contenant des entiers. À titre d'illustration, si l'on part de u₁ = 4 alors N = 3.2^27+3.227−1−2, un nombre de plus de 120 millions de chiffres décimaux.

Plus précisément, Kirby et Paris ont prouvé que le th. de Goodstein impliquait la consistance [¹] de AP. Or il est notoire, depuis Gödel, que cette dernière ne peut être prouvée à l'intérieur de AP. Le th. de Goodstein est ainsi un indécidable [¹] de l'arithmétique de Peano. C'est une propriété profonde, enracinée dans la logique, la théorie des nombres et des ensembles. Il suffirait d'ajouter au principe de récurrence (qui illustre le notion d'infini potentiel) l'existence d'un ensemble infini (infini actuel) pour pouvoir prouver Goodstein, qui est très précisément à la frontière entre ces deux notions.

Note

[¹] cf. les indécidables