Pour comprendre ce théorème, il faut considérer un système formel (comme l’arithmétique de Peano ou la théorie des ensembles ZFC) qui est :
- Suffisamment puissant pour exprimer au minimum l’arithmétique de base (addition, multiplication sur les entiers naturels).
- Consistant (ou cohérent) : Il est impossible de démontrer une contradiction à l’intérieur du système (on ne peut pas prouver à la fois un énoncé $P$ et sa négation $\neg P$).
- Récursivement axiomatisable : Il existe un algorithme qui peut décider si une formule donnée est un axiome ou non. C’est le cas de tous les systèmes mathématiques usuels.
Tout système formel consistant et récursivement axiomatisable, suffisamment puissant pour formaliser l’arithmétique des entiers, est nécessairement incomplet.
Autrement dit, il existe au moins un énoncé (une formule $\varphi$) formulé dans le langage de ce système, tel que ni l’énoncé $\varphi$, ni sa négation $\neg\varphi$, ne sont démontrables à l’intérieur du système. Un tel énoncé est dit indécidable.
Dans un tel système, il existe des énoncés qui sont vrais mais indémontrables.
Esquisse de la Démonstration
La démonstration de Gödel est une construction extraordinairement ingénieuse qui permet à un système formel de « parler de lui-même ». Voici les grandes étapes :
Étape 1 : La Numérotation de Gödel (Gödelisation)
L’idée de génie de Gödel est d’associer un numéro de Gödel, un entier naturel unique, à chaque symbole, formule, et suite de formules (démonstration) du système formel. Par exemple :
- « $\forall$ » → 1, « $x$ » → 2, « $=$ » → 3, etc.
- Une formule comme « $\forall x, x=x$ » devient une suite de nombres (1, 2, 3, 2), qui peut elle-même être encodée en un unique grand entier.
Cette astuce transforme les énoncés sur les propriétés des formules (comme « cette formule est un axiome » ou « cette suite de formules est une démonstration ») en énoncés sur les propriétés arithmétiques de certains nombres entiers. La méta-mathématique devient une branche de l’arithmétique.
Étape 2 : Le Prédicat de Démontrabilité
Grâce à la numérotation, on peut construire une formule arithmétique, notons-la $Dem(y, x)$, avec deux variables libres $y$ et $x$. Cette formule exprime la relation :
« L’entier $y$ est le numéro de Gödel d’une démonstration de la formule dont le numéro de Gödel est $x$. »
Le système peut donc désormais exprimer sa propre notion de démontrabilité. L’énoncé « la formule $\varphi$ est démontrable » se traduit par la formule arithmétique « $\exists y, Dem(y, g_\varphi)$ », où $g_\varphi$ est le numéro de Gödel de $\varphi$.
Étape 3 : La Construction de l’Énoncé de Gödel
C’est le cœur de la preuve. En utilisant une technique appelée le lemme de diagonalisation, Gödel construit une formule spécifique, notée $G$, qui est auto-référentielle et qui affirme sa propre non-démontrabilité. La formule $G$ est équivalente à l’énoncé :
« La formule $G$ n’est pas démontrable dans le système. »
Formellement, le système prouve l’équivalence $G \iff \neg(\exists y, Dem(y, g_G))$, où $g_G$ est le numéro de Gödel de $G$ elle-même.
Étape 4 : L’Argument Final
On analyse alors la situation de cet énoncé $G$ en supposant que le système est consistant.
-
Cas 1 : Supposons que $G$ est démontrable.
Si le système peut prouver $G$, alors l’énoncé « $G$ est démontrable » est vrai. Mais $G$ affirme exactement le contraire (« $G$ n’est pas démontrable »). Le système prouverait donc un énoncé qui est faux. Un système consistant ne peut pas faire cela. Plus formellement, s’il prouve $G$, il prouve aussi $\neg(\exists y, Dem(y, g_G))$. Mais le fait même qu’il existe une preuve de $G$ rend $\exists y, Dem(y, g_G)$ vrai. Le système prouverait donc une fausseté, ce qui le rendrait incohérent. Donc, si le système est consistant, $G$ ne peut pas être démontrée. -
Cas 2 : Supposons que $\neg G$ est démontrable.
Si le système peut prouver $\neg G$, alors par l’équivalence, il peut aussi prouver que « $G$ est démontrable ». Mais nous venons de voir à l’étape 1 que si le système est consistant, $G$ n’est PAS démontrable. Le système prouverait donc à nouveau une fausseté. Donc, si le système est consistant, $\neg G$ ne peut pas non plus être démontrée.
Conclusion : Si le système formel est consistant, alors l’énoncé de Gödel $G$ est tel que ni $G$, ni sa négation $\neg G$, ne peuvent être démontrés à l’intérieur du système. Le système est donc incomplet. De plus, comme nous avons montré que $G$ n’est pas démontrable, l’énoncé $G$ (qui dit « je ne suis pas démontrable ») est de fait vrai. Nous avons donc trouvé un énoncé vrai mais indémontrable.