métamathématique (suite)

Théorèmes de Gödel

Il s’agit de deux théorèmes tout à fait fondamentaux qui portent sur et d’ailleurs sur tous les systèmes formels du même genre, « apparentés » comme le disait Kurt Gödel dans son mémoire de 1931.

Le premier théorème établit que, sous certaines hypothèses de consistance, est un système incomplet. La démonstration rigoureuse et exhaustive est complexe. Mais, comme elle met en jeu des mécanismes de raisonnement essentiels, il est bon d’en présenter le mécanisme.

Convenons d’abord que, si un nombre naturel n est le nombre de Gödel d’une expression bien formée de , nous l’écrirons E_n, et si cette expression contient une variable libre, nous l’écrirons E_n(x). Il est entendu que x prend ses valeurs sur l’ensemble des nombres formels. Dès lors, E_n(O″), par exemple, représente le résultat de la substitution dans E_n(x) de O″ à x. Plus généralement, d’après les notations adoptées, E_n(k) représente le résultat de la substitution dans E_n(x) de l’équivalent formel du nombre intuitif k à la variable x. Ainsi, si l’on substitue à x l’équivalent formel de n, on obtiendra l’expression E_n(n).

Considérons maintenant la relation suivante entre deux nombres naturels n et m : R(n, m) = df n est le nombre de Gödel d’une expression à une variable libre E_n(x) de , et m est le nombre de Gödel d’une démonstration de E_n(n).

La théorie des fonctions récursives permet d’établir le lemme suivant :
Il existe dans une expression formelle A (x, y) et qui est telle que, pour tout n et tout m,
si R (n, m) est vraie, alors ⊢ A (n, m) ;
si R (n, m) est fausse, alors ⊢ ~ A (n, m).

Le signe ⊢ (on écrit aussi parfois le signe ⊩) placé à gauche d’une expression signifie que celle-ci est un théorème de , qu’elle y est démontrable.

Partons de cette expression A (x, y) et considérons la nouvelle expression (∀y) ~ A (x, y). Elle contient la variable libre x et elle appartient encore à . Elle a donc un nombre de Gödel, disons p, et, selon la convention faite, il est possible de l’écrire E_p(x). Il s’ensuit que, en particulier,
(*) (∀y) ~ A (p, y) et E_p(p) désignent la même expression.

• Théorème a. Si est consistant, on ne peut y démontrer E_p(p).

La preuve se conduit par l’absurde. Faisons donc l’hypothèse que E_p(p) est un théorème de , donc que ⊢E_p(p). Cela signifie qu’il en existe une démonstration. La relation R (p, k) est vraie et, par le lemme, on a ⊢A (p, k).

La règle d’introduction de ∃ donne ⊢ (∃y) A (p, y), et l’équivalence entre ∃ et ~ ∀ ~ donne ⊢ ~ (∀y) ~ A (p, y).

Mais par (*), on a ⊢ ~E_p(p), et, comme est supposé consistant, l’hypothèse que E_p(p) est un théorème est fausse.

Dans un système qui formalise l’arithmétique, il est possible de définir une forme forte de consistance, appelée « ω-consistance ». On dira que est ω-consistant s’il ne contient pas à la fois la suite infinie des théorèmes ⊢A (O), ⊢A (O′), ⊢A (O″)... et le théorème ⊢ ~ (∀x) A (x). On démontre que si est ω-consistant, il est consistant.

• Théorème b. Si est ω-consistant, on ne peut y démontrer ~E_p(p).

En effet, comme on sait que E_p(p) n’est pas démontrable, aucun entier n n’est nombre de Gödel d’une preuve de E_P(p). Donc, toutes les relations R(p, 0), R (p, 1), R (p, 2)... sont fausses. Par le lemme ⊢ ~A (p, O), ⊢ ~A (p, O′), ⊢ ~A (p, O″)... et, puisque est supposé ω-consistant, on a que ~ (∀y) A (p, y) n’est pas un théorème. En vertu de (*), cela signifie encore que ~ E_p(p) n’est pas un théorème.

Les théorèmes a et b conduisent au premier théorème de Gödel. Si est ω-consistant, il est incomplet, en ce sens que ni E_p(p) ni ~E_p(p) n’y sont démontrables.

Remarques

1. En 1936 J. B. Rosser (né en 1907) a prouvé le théorème de Kurt Gödel sous l’hypothèse de la consistance simple.
2. Le lemme repose sur la théorie des fonctions récursives, mais il existe des démonstrations qui utilisent le calcul de la λ-conversion ou la théorie des machines de Turing.
3. L’expression qui permet de démontrer l’incomplétude de est donc E_p(p), soit (∀y) ~ A (p, y) ou encore ~ (∃y) A (p, y). Elle exprime formellement qu’il n’existe pas de y qui soit le nombre de Gödel d’une démonstration de l’expression E_p(p). Elle « dit » donc d’elle-même qu’elle n’est pas démontrable. Et comme tel est, en effet, le cas, c’est une expression intuitivement vraie. Le système est ainsi incomplet en ce sens qu’une expression vraie de l’arithmétique élémentaire ne peut y être démontrée.
4. La construction de E_p(p) à partir de E_p(x) utilise le procédé de la diagonale de Cantor. Les expressions bien formées à une variable libre de sont dénombrables. Si on s’en donne une énumération, E_p(p) n’y appartient pas.
5. Enfin, l’interprétation de E_p(p) est du type « paradoxe du menteur ». Les raisonnements restent toutefois corrects grâce à la distinction systématique des niveaux de langue : langue formelle de , et métalangue pour en faire l’analyse.

Le théorème a a donc la forme suivante :
« Si est consistant, E_p(p) n’en est pas un théorème. » Supposons que toute la démonstration de cette proposition puisse se formaliser en et que Cons  soit l’expression formelle de «  est consistant ». On pourra écrire dès lors :

Second théorème de Gödel : si est consistant, il n’est pas possible de démontrer cette consistance en .

En effet, si la chose était possible, on aurait ⊢Cons  et, par détachement, ⊢E_p(p), ce qui est contraire au théorème a.

La preuve de la consistance de , donnée pour la première fois par Gehrard Gentzen (1909-1945) en 1936, a donc dû utiliser des moyens essentiellement plus puissants que ceux dont dispose .