Enoncé

Le premier théorème d’incomplétude de Kurt Gödel démontre que tout système logique suffisamment puissant pour démontrer les théorèmes de base de l’arithmétique admet nécessairement des énoncés qu’il ne peut ni démontrer ni réfuter. Pourtant ces énoncés ont un sens en termes d’arithmétique élémentaire et l’on pourrait s’attendre à ce qu’un système logique permette de déduire à partir de ses axiomes une réponse Vrai ou Faux à tous ces énoncés.  En fait pour certains d’entre eux ce n’est pas le cas, de tels énoncés sont dits indécidables dans le système logique considéré. Cette situation est intrinsèque à tout système suffisamment puissant, un système logique augmenté de nouveaux axiomes pourrait apporter une preuve à ces énoncés, mais de nouveau, dans ce système logique augmenté il y aura forcément encore des énoncés indécidables.

En résumé, ce théorème montre qu’un système logique doté d’une certaine complexité, comme c’est le cas de l’arithmétique usuelle, est alors suffisamment puissant pour démontrer qu’il y a des énoncés vrais ou faux qu’il ne peut pas démontrer ni réfuter.

A l’inverse, le second théorème d’incomplétude de Gödel démontre qu’un système logique n’est jamais assez puissant pour démontrer sa propre cohérence.

De façon plus rigoureuse le théorème s’énonce comme suit :

Soit Λ un système formel cohérent qui représente l’arithmétique. Alors Λ  est incomplet.

Les termes de système formel, de cohérence, et d’incomplétude qui apparaissent dans le théorème ont un sens précis qui est présenté dans le paragraphe Boîte à outils.

Histoire du théorème

Le premier théorème d’incomplétude a été présenté par Kurt Gödel alors qu’il avait 25 ans dans un article publié en 1931 dans les annales du Monatschefte für Mathematik. Il eut un très fort retentissement car il mettait un terme au projet conduit depuis le milieu du XIXe siècle par les logiciens pour établir un fondement sur la base duquel toutes les vérités mathématiques pourraient être construites.

Le second théorème, publié avec le premier, affirme que si un système logique est cohérent, alors sa propre cohérence ne peut pas en être déduite, autrement dit : une théorie cohérente ne peut pas démontrer sa propre cohérence.

Boîte à outils

Avant d’entrer dans le vif de la démonstration, nous devons clarifier plusieurs notions qui jouent un rôle fondamental dans la démonstration : il s’agit des notions de calcul, de fonctions calculables, d’ensembles énumérables, quelques notions sur les systèmes logiques, et sur ce que l’on appelle la cohérence et la complétude d’un système logique.

1) Notion de calcul : 

Sans beaucoup nuire au fond de la démonstration, on peut résumer la notion de calcul à ce qui peut être programmé dans un ordinateur avec un langage informatique qui permet de travailler avec les structures de données suivantes : l’ensemble N des entiers naturels, le type booléen Bool = {Vrai, Faux} et les chaînes de caractères (sur un alphabet fini donné).

Le calcul, à proprement parler, est exécuté par un ordinateur, qui suit simplement les instructions pour lesquelles il a été programmé, sans pouvoir prendre de décisions arbitraires. Il s’agit donc d’un procédé déterministe.

Pour se rapprocher de la notion théorique de ce qu’est un calcul, il faut faire abstraction des contraintes physiques et imaginer que les programmes sont exécutés par un ordinateur idéal, qui n’aurait aucune limitation en quantité de mémoire ou de temps pour mener son calcul à terme.

Il y a, bien sûr, la possibilité qu’un calcul donné ne se termine jamais, par exemple, si le programme conduit à une boucle infinie, mais ce genre de non terminaison reste une conséquence déterministe du programme codé par le programmeur. Un programme P est dit total si son exécution (sur un ordinateur idéal) se termine en un temps fini, peu importe la valeur d’entrée qu’on donne au programme.

2) Fonctions calculables :

Intuitivement, une fonction est calculable s’il existe une procédure effective, un algorithme, pouvant la calculer. Les fonctions calculables furent d’abord modélisées par le calcul, mais d’autres formalismes comme les fonctions récursives ou les machines de Turing ont été proposés par la suite. Il a ensuite été prouvé que toutes ces définitions, bien que fondées sur des idées assez différentes, décrivent exactement le même ensemble de fonctions.

Définition 1 : Une fonction f : d’un ensemble A sur un ensemble B (A -> B) est dite calculable si on peut écrire un programme qui lorsqu’il est exécuté sur un ordinateur idéal, renvoie la valeur f(x) en temps fini, pour toute valeur d’entrée x appartenant à l’ensemble A.

Exemple d’une fonction calculable : la fonction f : de N (ensemble des entiers) vers l’ensemble Booléen (Vrai, Faux) définie comme suit :

f(n) = Vrai, si n est premier,

f(n) = Faux, sinon.

De façon contrintuitive il y a bien peu de fonctions calculables car le code source du programme qui les calcule est une chaîne de caractères et les chaînes de caractères sont dénombrables. Le cardinal des fonctions non calculables est largement supérieur à celui des fonctions calculables. Paradoxalement il n’est pas simple de trouver une fonction particulière qui ne soit pas calculable. Alan Turing en a fourni une qui est célèbre : 

soit h :  fonction de l’ensemble des Programmes programmables sur ordinateur (ensemble noté Prog) vers Bool, définie pour chaque programme P de Prog par :

h(P) = Vrai, si P est total,

h(P) = Faux, sinon.

3) Ensembles énumérables :

Un programme P énumère un ensemble A s’il produit, avec le temps, une liste (a_n) avec n entier (une énumération) d’éléments de A, dans laquelle chaque élément apparaît au moins une fois. La liste peut être infinie, elle ne sera alors jamais achevée, mais on exige seulement que le temps de production d’un nouvel élément soit toujours fini. Un ensemble A est énumérable s’il existe un programme P qui l’énumère.

L’exemple le plus commun d’un ensemble infini énumérable est l’ensemble N des entiers naturels. L’énumération c’est ce que l’on fait lorsque l’on compte : Chaque entier n de N sera, en principe, éventuellement nommé si on est disposé à compter assez longtemps. De façon similaire, l’ensemble des chaînes de caractères sur un alphabet fini donné est énumérable : on peut faire la liste de toutes les chaînes de longueur 1, puis de toutes les chaînes de longueur 2 (en ordre alphabétique) et ainsi de suite.

La notion d’ensemble énumérable semble proche de celle d’ensemble dénombrable, elle est cependant différente. La notion d’ensemble énumérable est plus restrictive que la notion d’ensemble dénombrable : Un ensemble A est dénombrable s’il existe une bijection f : de l’ensemble N des entiers vers A, et la suite des f(n) avec n entier pourrait alors faire penser à une possible énumération de A. En fait chaque ensemble énumérable est dénombrable, mais la réciproque est fausse : la propriété que l’on exige en plus d’être dénombrable pour qu’un ensemble soit énumérable, c’est que la bijection f soit calculable.

L’ensemble des fonctions calculables est dénombrable, et on en déduit alors qu’il y a seulement une quantité dénombrable d’ensembles énumérables. Il y a toutefois beaucoup plus d’ensembles dénombrables que d’ensembles énumérables (on verra au chapitre Démonstration un exemple d’ensemble dénombrable qui n’est pas énumérable).

Le lemme suivant permet de construire à partir d’un ensemble énumérable, de nouveaux ensembles énumérables.

Lemme 1 : Soit A un ensemble énumérable et P un programme total, qui à chaque élément de A associe un booléen. Alors l’ensemble B = {a ∈  A tel que  P(a) = Vrai} est énumérable.

Démonstration : 

Soit P un programme qui dresse la liste de tous les éléments de A. On va décrire un programme, disons P_B, qui dresse la liste de tous les éléments de B. On initialise le programme P_B avec une liste vide.

Pour chaque élément a de A, on lance le programme P. Si P(a) = Vrai, le programme P_B rajoute l’élément a à sa liste. Sinon, il ne fait rien et passe à l’élément suivant. On énumère ainsi tous les éléments de A qui satisfont le prédicat encodé par le programme P, c’est-à-dire, tous les éléments de l’ensemble B.

4) Syntaxe des fonctions calculables :

Pour simplifier l’exposé on se restreint ici aux fonctions calculables d’une seule variable, de N vers N.

Une fonction calculable de f de N dans N est définie par une formule qui décrit le processus de calcul à effectuer sur l’entrée x, pour obtenir l’image de x notée f(x). Cette formule peut être vue comme un programme P, qui pour une valeur n d’entier donne en sortie la valeur f(n) issue du processus de calcul. Elle peut aussi être vue comme une chaîne de caractères qui décrit dans le langage de l’arithmétique et en respectant les règles de syntaxes du langage de l’arithmétique, le processus de calcul à effectuer. 

Par exemple la succession des caractères ‘(5 x + 2 )*(x + 2)’respecte les règles de la syntaxe de l’arithmétique, par contre ‘5x +/ ‘ou ‘(5 x + 2’ ne les respectent pas.

On exige donc d’un système formel que l’ensemble de ses formules soient exprimées en respectant les règles définies. C’est dire à que l’on doit avoir défini un processus algorithmique (un programme) qui prend en entrée une chaîne de caractères et qui détermine, en un temps fini, si cette chaîne est une formule conforme à la syntaxe ou pas. Ce programme de contrôle de la syntaxe est très comparable à ce que fait en informatique un compilateur.

Pour les systèmes logiques auxquels on s’intéresse, comme typiquement celui de l’arithmétique que l’on connait avec ses opérations addition et multiplication, les formules sont définies par récurrence, avec un alphabet symbolique assez restreint. Il en résulte un programme très simple pour déterminer si une chaîne donnée de caractères est une formule syntaxiquement correcte pour décrire le calcul sur un entier n de N.

5) Codage :

On considère f fonction de N dans N exprimée de façon syntaxiquement correcte. Comme on vient de le voir, elle s’écrit sous la forme f(x) = ‘une succession de caractères ou symboles’, cette succession respectant certaines règles de rédaction qui assurent que la formule exprimée par cette succession de caractères a un sens mathématique : c’est l’écriture symbolique de la formule. A chacun des caractères ou symboles de l’expression de la fonction on peut associer un entier n_i  (par exemple le code ASCII du caractère en question). A partir de la succession des entiers n_i on peut construire un entier E (n₁,n₂,…n_k) tel que connaissant E appartenant à l’ensemble des entiers correspondant à un code on en déduit la suite des n_i, et tel que connaissant les n_i on en déduit le nombre E.

Exemple : chaque caractère sera codé par un nombre exprimé sur 8 bits (cela donne 256 caractères possibles). L’ensemble des codes des caractères mis bout à bout donne une chaîne de k fois 8 bits, où k est le nombre de caractères, ce qui correspond à un entier exprimé en base 2, que l’on peut aussi exprimer en base 10. Réciproquement, en partant d’un nombre qui en base 2 s’exprime par un nombre s’étalant sur k fois 8 bits, on peut lui faire correspondre une succession de caractère en associant à chaque groupe de 8 bits le caractère correspondant.

Remarque : En limitant le nombre de caractère à 255, on pourra toujours s’arranger pour que le code 0 ne soit pas utilisé pour un caractère de l’alphabet, et puisse avoir une autre signification.

Le processus de décodage DECOD de N dans Booléen, définit par :

DECOD(k) = Vrai, si k est le code d’une fonction calculable exprimée de façon syntaxiquement correcte,

DECOD(k) = Faux, sinon.

est calculable, car il est exécuté par une succession finie d’opérations d’examen du respect de la syntaxe.

On note pour la suite Γ l’ensemble des entiers qui sont le code d’une fonction calculable qui respecte les règles de syntaxe imposées par le système logique, et sont produits par le processus de codage décrit précédemment. Γ ne contient que des entiers, mais Γ n’est qu’un sous ensemble de N car tout entier, après décodage, ne produit pas forcément une écriture symbolique valide / applicable.

6) Cohérence et complétude

Définition 3 : Un système Λ est incohérent s’il existe un énoncé St qui est à la fois démontré et réfuté par Λ. Si Λ n’est pas incohérent, on dit qu’il est cohérent.

Il va de soi que la cohérence est une propriété souhaitable en vertu du principe « ex falso sequitur quodlibet » (d’une contradiction découle n’importe quoi). Dans un tel système, l’incohérence entraîne que tout, et son contraire, se démontre trivialement, ce qui en détruit l’intérêt.

Définition 4 : Un système formel Λ est complet si pour tout énoncé St, ou bien Λ démontre St, ou alors Λ réfute St. Si Λ n’est pas complet, on dit qu’il est incomplet.

Démonstration du 1er théorème d’incomplétude de Gödel

La démonstration présentée dans cet article est une reformulation simplifiée construite à partir des articles listés dans la bibliographie. Elle perd en rigueur et en généralité ce qu’elle gagne en accessibilité pour un public de lecteurs élargi.

Avant d’entrer dans le vif de la démonstration, nous faisons une première approche du raisonnement en se concentrant sur la démonstration d’un premier théorème qui est facilement accessible. Cela permettra de mieux comprendre le mécanisme utilisé par la suite.

Théorème :  Il existe des sous-ensemble de N qui sont dénombrables, mais non énumérables. 

Démonstrations :

On considère que l’on dispose d’une fonction de codage telle que pour chaque k, on sait dire si k est valide pour une fonction, et on en déduit la formule de la fonction.

Pour la suite, une fonction f de N dans N correspondant au code k sera notée : f_k. Et l’on sait donc, à partir de k appartenant à Γ l’ensemble des entiers qui correspondent à un code, exprimer la fonction f_k, et réciproquement connaissant f_k exprimer k.

On considère le sous-ensemble de N, noté L défini par :

L = { n de Γ; n ∉ Image de f_n }

Cet ensemble est mathématiquement défini : pour tout n de Γ on peut construire la fonction f_n et lancer l’opération de calcul des f_n(x).

Cet ensemble n’est pas vide : Par exemple le code des fonctions du type f(x) = x Mod 2, f(x) = x Mod 3 etc aura forcément un numéro de code très supérieur à 1 respectivement 2, car ces codes auront été déjà pris par des fonctions d’un seul caractère => les numéros de code de ces fonctions seront dans L.

Cet ensemble n’est pas non plus N : soit k₁ le code de la fonction f(x) = x, k₂ celui de la fonction f(x) = x + 1, k₁ et k₂ seront dans l’image de f, et donc les entiers k₁ et k₂ ne sont pas dans L.

L est un sous-ensemble de N, il est donc dénombrable, mais L n’est pas énumérable , en effet :

Si L est énumérable, alors il existe une succession finie d’opérations logiques qui pour chaque élément i de Γ est capable de dire en temps fini que cet élément n’est pas dans l’image de f_i c’est à dire que la fonction g de N dans N définie par :

g(i) = ( i ∈ Γ = Vrai )_*( i ∉ Image de f_i = Vrai )_*i 

produira tous les éléments de L et eux seulement ∪ {0} (∪ symbole de Union). Cette fonction fait partie des fonctions calculables de N dans N, elle a donc un code dans Γ, disons que c’est le numéro k, il n’est pas nul. La fonction f_k a pour image tous les éléments de L ∪ {0}, c’est à dire qu’elle liste tous les éléments de L ∪ {0}

Dans l’hypothèse où L est énumérable, l’énoncé ‘k ∈ L’ pour k de N non nul est-il vrai ?

• Hypothèse 1 : k ∈ L

On en déduit, par définition de L que k n’est pas dans l’image de f_k, donc f_k ne produit jamais le numéro k, donc on n’a jamais f_k(x) = k, or comme f_k liste tous les éléments de L lorsque k est non nul, cela signifie que k ∉ L, en contradiction avec l’hypothèse.

• Hypothèse 2 : k ∉ L

k étant un élément de Γ, on en déduit, par définition de L que k est produit par f_k, c’est-à-dire qu’il existe x tel que f_k(x) = k, et par définition de f_k on en déduit que k est un élément de L, ce qui est en contradiction avec l’hypothèse.

En conclusion, si L est énumérable alors cela induit des conséquences contradictoires, donc, pour rester dans une théorie cohérente, on en déduit que L est un ensemble précisément défini, qui n’est pas vide, qui est dénombrable, mais qui n’est pas énumérable. Le théorème est démontré.

Appliquons maintenant le même type de raisonnement, mais en travaillant non plus seulement sur les fonctions arithmétiques et leurs opérations sur des entiers, mais aussi sur des propositions logiques et sur leurs démonstrations.

Notions complémentaires sur les systèmes logiques :

Outre les opérations de calcul sur les entiers ou booléens, le langage d’un système logique tel que l’arithmétique doit aussi être doté de la capacité :

1. à exprimer des ‘propositions logiques’ ou des énoncés que nous appellerons pour la suite des formules,
2. à démontrer certaines formules, c’est à dire fournir une suite valide de déductions logiques qui aboutit à la conclusion ‘La formule = Vrai’. Les règles de déductions à respecter sont définies par le système logique.

Les formules : 

Les formules d’un système formel Λ peuvent être vues comme des chaînes de caractères conçues pour exprimer les propriétés de certains objets mathématiques ; elles peuvent donc être ou bien vraies, ou bien fausses. Les formules sont les phrases syntaxiquement correctes, ou expressions bien formées, d’un langage symbolique, telles que celle-ci :

f(n) = « ∀ d, (d | n) ⟹ (d = 1) ou (d = n) »

qui exprime la propriété mathématique ‘n est un nombre premier’ (cela peut être vrai ou faux selon la valeur de n). En revanche, des certaines chaînes de caractères telles que « ^9∃9n = U+ » ne sont pas des formules, même si elles utilisent le même alphabet, car elles ne sont pas construites en suivant les règles syntaxiques.

On exige donc d’un système formel Λ que l’ensemble F de ses formules soit exprimées en respectant des règles bien définies. C’est dire à que, là encore, comme pour l’écriture des fonctions arithmétiques avec leurs opérations et leurs variables, on doit avoir défini un processus algorithmique (un programme) qui prend en entrée une chaîne de caractères et qui détermine, en un temps fini, si cette chaîne respecte la syntaxe et est une formule ou pas. 

Comme pour les fonctions de N dans N, il est possible de définir un code , nombre entier qui sera associé à chaque formule en suivant la même démarche que celle utilisée pour les formules. 

Notons que puisque l’ensemble des chaînes de caractères est énumérable, alors par le Lemme 1, cette exigence entraîne que l’ensemble F des formules est énumérable à son tour.

Les démonstrations :

Les démonstrations, ou preuves, d’un système Λ sont constituées d’une succession logique de formules qui respectent les règles de déduction du système en question. Sans perte de généralité́, les preuves peuvent être amalgamées en une chaîne de caractères, comme un texte est un amalgame de phrases. Comme pour les formules, on exige donc que L soit accompagné d’un programme qui vérifie, étant donné une chaîne de caractères, s’il s’agit bien d’une preuve valide, auquel cas ce programme doit aussi pouvoir déterminer quelle est la conclusion (un énoncé, c’est-à-dire une formule qui n’a plus de variable libre) que cette preuve démontre. Si un énoncé́ φ s’avère être la conclusion d’une preuve valide, on dit qu’il s’agit d’un théorème du système Λ, ou encore, que Λ démontre φ. 

Proposition 1 : Soit Λ un système formel. Alors l’ensemble des théorèmes de Λ est énumérable.

Démonstration : On procède de façon similaire au Lemme 1 pour décrire un programme, Thm, qui construit progressivement la liste de tous les théorèmes de Λ. On initialise le programme avec une liste vide. 

On a déjà̀ vu que l’ensemble de toutes les chaînes de caractères étaient énumérables. Sur chaque élément de la liste des chaînes de caractères, on peut donc lancer le programme qui détermine si cette chaîne représente une preuve et qui, le cas échéant, trouve sa conclusion. Chaque fois que ce programme trouve une conclusion, qui est donc un théorème de Λ, le programme Thm rajoute celle-ci à sa liste. Sinon, il ne fait rien et passe à la chaîne suivante. 

Puisque chaque théorème de Λ doit être la conclusion d’au moins une preuve, on obtient ainsi chaque théorème au moins une fois dans la liste de théorèmes produite par Thm.

Supposons donc que Λ soit un système formel cohérent. Alors on peut définir un programme Dem de l’ensemble des énoncés (c’est-à-dire des formules fermées) vers les booléens Vrai/ Faux, avec le résultat suivant :
Dem(φ) = Vrai, si Λ démontre φ,

Dem(φ) = Faux, si Λ réfute φ. 

En effet, puisque l’ensemble des théorèmes de Λ est énumérable (Proposition 1), il suffit donc de faire fonctionner le programme Thm jusqu’à voir passer la formule φ ou bien la formule qui exprime le contraire de φ (notée ¬φ) Le programme Dem surveille cette énumération et renvoie Vrai dès qu’il voit passer φ et Faux dès qu’il voit passer ¬φ. Ces deux situations ne peuvent pas toutes deux se produire pour une même instance, puisque Λ est cohérent. De plus l’une 2 sorties (Vrai ou Faux) va forcément se produire si le système est complet puisque dans un système complet toute formule Vrai peut être démontrée comme étant vraie et toute formule Faux peut être démontrée comme étant fausse. Dans un système cohérent et complet, le programme Dem est donc total, il ne peut y avoir de boucle infinie.

Nous voilà armés pour démontrer le théorème.

Démonstration du Théorème :

Nous nous plaçons dans le cas le cas où le système logique Λ est celui de l’arithmétique, ou un équivalent. Supposons que le système Λ soit cohérent et complet. Considérons les 2 ensembles G et E suivants :

• G = { (n,m) de N² ; ∃ ϕ formule d’1 variable, telle que ( m = code(ϕ) ) & ( Dem(ϕ(n)) = Vrai) }

En claire, G est l’ensemble des couples d’entiers (n,m) tels que m est le code d’une formule ϕ d’1 variable et cette formule ϕ qui a pour code m est démontrée = Vrai lorsque la variable prend la valeur n, c’est-à-dire ϕ(n) est Vrai, c’est-à-dire ϕ(n) est prouvable dans le système logique Λ. Si le système logique est cohérent et complet Les processus de vérification que m est le code d’une formule et (Dem(ϕ(n)) = Vrai) sont calculable et l’ensemble G est énumérable.

• E = { n ∈ N; ∃ ϕ formule d’1 variable telle que (n = code(ϕ) ) & (Dem(ϕ(n)) = Faux) }.

Ce qui signifie que E est l’ensemble des entiers n tels que n est le code d’une formule ϕ d’1 variable, et ϕ est démontrée Faux lorsque la variable prend la valeur n, c’est-à-dire ϕ(n) est Faux, c’est-à-dire ϕ(n) n’est pas prouvable dans le système logique. Là encore l’ensemble E est énumérable dans l’hypothèse où le système logique est cohérent et complet.

Soit maintenant la formule Ψ(x) de la variable x définit par : ‘x ∈ E’. On note n_x le code de cette formule.

Dans l’hypothèse où Λ est cohérent et complet, nous allons voir que la formule Ψ(x) appliquée à n_x c’est-à-dire l’énoncé ‘n_x ∈ E’ , n’est pas démontrable, c’est-à-dire que l’énoncé Ψ(n_x) n’est pas prouvable dans le système logique.

• Hypothèse 1 : Dem (Ψ (n_x) ) = Vrai. 

Donc la formule ‘n_x ∈ E’ est démontrée Vrai pour n_x, c’est-à-dire (Ψ(n_x) est prouvable dans le système logique de l’arithmétique de Peano.

⟹ n_x ∈ E

⟹ ∃ ϕ formule d’1 variable telle que (n_x = code(ϕ) ) & (Dem(ϕ(n_x)) = Faux)

⟹ (n_x, n_x) ∉ G, par définition de G,

⟹ ¬(∃ ϕ formule d’1 variable telle que ( n_x = code(ϕ) ) & (Dem(ϕ(n_x)) = Vrai) ) par définition de G

⟹ ∀ ϕ formule d’1 variable : ¬ ( ( n_x = code(ϕ) ) & (Dem(ϕ(n_x)) = Faux)

⟹ ∀ ϕ formule d’1 variable : (n_x n’est pas le code de ϕ) ou (Dem(ϕ(n_x)) = Faux)

Ce résultat est donc applicable à  Ψ : ⟹ (n_x n’est pas le code de Ψ) ou (Dem(Ψ(n_x)) = Faux )

Or par définition de n_x, n_x est le code de Ψ, cela implique Dem(Ψ(n_x)) = Faux

En synthèse : Dem (Ψ(n_x) ) = Vrai ⟹ Dem (Ψ(n_x) ) = Faux

• Hypothèse 2 : Dem (Ψ(n_x) ) = Faux

Donc la formule ‘n_x ∈ Q’ est démontrée Faux pour n_x

⟹ n_x ∉ E

⟹ ¬(∃ ϕ formule d’1 variable telle que (n_x = code(ϕ) ) & (Dem(ϕ(n_x))  = Faux) )

⟹ ∀ ϕ formule d’1 variable : ¬ ( ( n_x = code(ϕ) ) & (Dem(ϕ(n_x)) = Faux) par définition de E

⟹ ∀ ϕ formule d’1 variable :  ( n_x n’est pas le code de (ϕ) ) ou (Dem(ϕ(n_x)) = Vrai) par définition de E

On applique cette formule à Ψ : (n_x n’est pas le code de Ψ) ou (Dem(Ψ(n_x)) = Vrai)

Or par définition de n_x, n_x est le code de Ψ, cela implique Dem(Ψ(n_x)) = Vrai

En synthèse : Dem (Ψ(n_x) ) = Faux ⟹ Dem (Ψ(n_x) ) = Vrai

Ainsi à partir de l’hypothèse que le système est cohérent et complet on obtient que le système devient incohérent. Si l’on fait l’hypothèse (souhaitable) que le système est cohérent, alors on est obligé d’admettre qu’il est incomplet et donc qu’il y a des formules indémontrables. Ces formules peuvent être vraies ou fausses, mais on ne peut démontrer ni l’un ni l’autre.

Exemple de problème non résoluble

Lors de la publication des théorèmes d’incomplétude de Gödel, la majorité des mathématiciens ont pensé que ces théorèmes indémontrables consistaient en des constructions abstraites auto-référentes formant une zone à part, sans signification mathématiquement réellement intéressante. Cette zone serait totalement invisible et on ne la rencontrerait jamais dans les mathématiques usuelles.

Le cas du théorème de Goodstein montre qu’il n’en est rien. Ce théorème que l’on va présenter et dont l’énoncé est naturel a été démontré en 1944 par Reuben Goodstein. Sa démonstration est construite dans le système logique de la théorie des ensembles qui est un système logique plus puissant que l’arithmétique ordinaire, dite de Peano.

En 1982, les mathématiciens Laurence Kirby et Jeffrey Paris démontrèrent que le théorème de Goodstein était indémontrable dans l’arithmétique de Peano.

Définition d’une suite de Goodstein :

Avant de définir une suite de Goodstein, définissons d’abord ce que l’on appelle la notation héréditaire en base b.

Pour écrire un entier naturel n avec une telle notation, on l’écrit d’abord sous sa forme classique de décomposition en base b :

n = a_kb^k + a_k-1b^k-1 + … + a₁ b + a₀,

où chaque a_i  est un entier compris entre 0 et b-1, mais où les exposants k sont en général exprimés en base 10.

Par exemple 1027 = 2¹⁰ + 2¹ + 1

La notation héréditaire en base b exige que les exposants k soient eux aussi exprimés par une décomposition héréditaire en base b. Cela conduit à un traitement itératif des exposants k jusqu’à ce qu’ils soient tous exprimés en notation héréditaire en base b. On obtient à la fin une expression constituée uniquement d’entiers entre 0 et b-1.

Reprenons l’exemple de 1027, et donnons sa notation héréditaire en base 2 : 

Première itération      1027 = 2¹⁰ + 2¹ + 1

Deuxième itération    1027 = 2^{2^3 + 2} + 2¹ + 1 (on a exprimé l’exposant 10 en base 2)

Troisième itération    1027 = 2^{2^(2^1+1) + 2} + 2¹ + 1 (on a exprimé l’exposant 3 en base 2 et il ne reste plus que des exposants exprimés en notation héréditaire de base 2).

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. G₁(m) = m. On écrit G₁(m) en notation héréditaire en base 2.
• Pour obtenir le deuxième élément de la suite, G₂(m), on remplace dans l’expression de G₁(m) tous les 2 par des 3 et on soustrait 1 au résultat. On exprime le résultat de la soustraction en notation héréditaire de base 3.
• Pour obtenir le troisième élément de la suite, G₃(m), on remplace dans l’expression de G₂(m) tous les 3 par des 4 et on soustrait 1 au résultat. On exprime le résultat de la soustraction en notation héréditaire de base 4.
• Et ainsi de suite…

Plus formellement, la suite G(m) est définie par :

            G₁(m) = m, écrire G1(m) en base 2,

Les G_n(m) suivant sont donnés par l’itération à chaque étape n des 2 opérations suivantes :

1. Prendre l’entier G_n-1(m) écrit en notation héréditaire de base (n). Remplacer tous les n par (n+1) 
2. Soustraire 1 et exprimer le résultat avec la notation héréditaire de base (n+1). Cela donne G_n+1(m)

La suite s’arrête dès que l’on arrive à une étape qui donne G_i(m) = 0.

Les toutes premières suites de Goodstein par exemple les suites G(1), G(2), ou G(3) se terminent rapidement.

Ainsi la suite G(1) donne :

Etape 1 :          G₁(1) = 1                     qui en notation héréditaire en base 2 = 1

Etape 2 :          G₂(1) = 1 – 1 = 0       la suite s’arrête

La suite G(2) donne :

Etape 1 :          G₁(2) = 2                      qui en notation héréditaire en base 2 = 2¹

Etape 2 :          G₂(2) = 3¹ – 1 = 2        qui en notation héréditaire en base 3 = 2

Etape 3 :          G₃(2) = 2¹ – 1 = 1        qui en notation héréditaire en base 4 = 1

Etape 4 :          G₄(2) = 1 – 1 = 0          La suite s’arrête

La suite G(3) donne :

Etape 1 :          G₁(3) = 3                       qui en notation héréditaire en base 2 = 2¹ + 1

Etape 2 :          G₂(3) = 3¹ + 1 – 1 = 3  qui en notation héréditaire en base 3 = 3¹

Etape 3 :          G₃(3) = 4¹ – 1 = 3        qui en notation héréditaire en base 4 = 3

Etape 4 :          G₄(3) = 3 – 1 = 2          qui en notation héréditaire en base 5 = 2

Etape 5 :          G₅(3) = 2 – 1 = 1           qui en notation héréditaire en base 6 = 1

Etape 6 :          G₆(3) = 1 – 1 = 0           La suite s’arrête

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

N° de l’étape	Valeur de G(4) à l’étape
1	4 = 22
2	26 =2·32 + 2·3 + 2
3	41 =2·42 + 2·4 + 1
4	60 =2·52 + 2·5
5	83= 2·62 + 6 + 5
6	109 = 2·72 + 7 + 4
…	…
10	253 =2·112 + 11
11	299 =2·122 + 11
…	…
22	1058 = 2·232
23	1151 = 242+23·24+23
…	…

Le numéro de l’étape pour lequel 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 10^{120 000 000}.

De son côté la suite G(5) ne croît pas beaucoup plus vite, mais elle le fait bien plus longuement, au point que les notations usuelles ne permettent même plus d’exprimer le numéro de l’étape à pour laquelle la valeur de la suite G(5) est maximale. Elle finit néanmoins aussi par atterrir sur 0.

Cependant, ces deux exemples ne sont rien par rapport à G(19) dont la croissance est faramineuse : elle est en n à la puissance n à la puissance 7. Ce qui donne :

G₁(19) = 19

G₂(19) = 7 625 597 484 990

G₃(19) = environ 1,3 × 10¹⁵⁴

…

G₈(19) = environ 4,3 × 10^{369 693 099}

Et cette croissance se poursuit ainsi pendant un nombre d’étapes lui-même faramineux. Néanmoins elle finit par revenir à 0.

Théorème de Goodstein :

Quelle que soit la valeur initiale de m, la suite de Goodstein G(m) se termine par 0.

Compte tenu de ce que l’on vient de voir sur les exemples de suite G(4), G(5), G19, on comprend que ce théorème n’avait rien d’évident. Il y a pourtant une démonstration qui prouve qu’il est vraie en utilisant la théorie des ensembles. En revanche ce résultat est indémontrable avec l’arithmétique usuelle.

Bibliographie

Cet article a été construit principalement à partir des 2 premières références listées dans cette bibliographie.

1. J. Fortier, Une preuve moderne du théorème d’incomplétude de Gödel. Bulletin AMQ, Vol. LVI, n° 3, octobre 2016.
2. R. Hoyoux, Les théorèmes d’incomplétude, Mémoire en vue de l’obtention du diplôme de Master en sciences mathématiques , septembre 2011.
3. Yanofsky, N. S. (2003), A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points. The Bulletin of Symbolic Logic, 9 (3), 362–386. 
4. Gödel, K. (1931). Über Formal Unentscheidbare Sätze der Principia Mathematica Und Verwandter Systeme I. Monatshefte für Mathematik und Physik, 38 (1), 173–198.