Sciences · Mathématiques
Les théorèmes d’incomplétude de Gödel
Kurt Gödel a démontré en 1931 que tout système d’axiomes cohérent capable d’exprimer l’arithmétique contient des énoncés vrais qu’il ne peut pas démontrer, et qu’il ne peut pas prouver sa propre cohérence.
Mis à jour le 4 min de lecture
Au début du XXe siècle, les mathématiciens rêvent de fonder toute leur discipline sur un ensemble fini d’axiomes, d’où l’on pourrait déduire mécaniquement toutes les vérités. En 1931, un logicien autrichien de 25 ans, Kurt Gödel, démontre que ce rêve est impossible. Ses deux théorèmes d’incomplétude comptent parmi les résultats les plus profonds du siècle, et parmi les plus souvent mal compris.
Le contexte : le programme de Hilbert
Après les paradoxes de la théorie des ensembles (dont celui de Russell, voir les paradoxes mathématiques), David Hilbert propose dans les années 1920 un programme : formaliser les mathématiques dans un système d’axiomes qui serait
- cohérent (on ne peut pas y démontrer à la fois un énoncé et son contraire) ;
- complet (tout énoncé vrai y serait démontrable) ;
- et dont la cohérence serait prouvée par des moyens élémentaires.
Gödel montre que les deux dernières exigences sont inaccessibles.
Les deux théorèmes
Ces théorèmes s’appliquent à l’arithmétique de Peano comme à la théorie des ensembles de Zermelo-Fraenkel, qui sert de fondement à presque toutes les mathématiques.
L’idée de la démonstration
La preuve est une version rigoureuse du paradoxe du menteur (« cette phrase est fausse »), où « faux » est remplacé par « indémontrable ».
- Coder : Gödel attribue à chaque symbole, formule et démonstration un nombre entier unique (le « nombre de Gödel »). Les énoncés sur les démonstrations deviennent des énoncés sur des nombres, donc des énoncés d’arithmétique.
- Exprimer la démontrabilité : il construit une formule arithmétique qui signifie « la formule de numéro x est démontrable ».
- Construire un énoncé autoréférent G qui affirme, en substance : « G n’est pas démontrable dans ce système ».
- Conclure : si G était démontrable, le système démontrerait un énoncé faux, ce qui contredirait sa cohérence. Donc G n’est pas démontrable. Mais alors ce que dit G est vrai : G est un énoncé vrai et indémontrable dans le système.
Contrairement au paradoxe du menteur, il n’y a pas de contradiction : seulement un écart entre vérité et démontrabilité.
Ce que les théorèmes ne disent pas
| Contre-sens fréquent | Ce qu’il en est |
|---|---|
| « Les mathématiques sont contradictoires » | Non : les théorèmes supposent justement le système cohérent |
| « Rien n’est certain en mathématiques » | Non : ce qui est démontré reste démontré |
| « Il existe des vérités qu’on ne pourra jamais connaître » | Pas exactement : un énoncé indémontrable dans un système peut l’être dans un système plus fort, qui aura à son tour ses propres énoncés indémontrables |
| « Cela s’applique à tous les systèmes logiques » | Non : seulement aux systèmes assez riches pour l’arithmétique. La géométrie euclidienne élémentaire formalisée par Tarski est complète |
| « Cela prouve que l’esprit humain dépasse les machines » | Thèse défendue par certains, mais très contestée par la plupart des logiciens |
Des exemples d’énoncés indécidables
L’énoncé G de Gödel est artificiel. Mais on connaît des énoncés « naturels » indépendants des axiomes usuels :
- l'hypothèse du continu de Cantor (existe-t-il un infini strictement compris entre celui des entiers et celui des réels ?) : Gödel montre en 1938 qu’on ne peut pas la réfuter, Paul Cohen en 1963 qu’on ne peut pas la démontrer, dans la théorie des ensembles usuelle (voir l’infini en mathématiques) ;
- l'axiome du choix, indépendant des autres axiomes de la théorie des ensembles ;
- le théorème de Goodstein, vrai mais indémontrable dans l’arithmétique de Peano (Kirby et Paris, 1982).
Gödel, Turing et les limites du calcul
En 1936, Alan Turing obtient un résultat voisin pour les machines : il n’existe aucun programme capable de décider, pour tout programme et toute donnée, si ce programme finira par s’arrêter (le problème de l’arrêt). Ensemble, les travaux de Gödel, Turing et Alonzo Church montrent qu’il existe des limites intrinsèques à ce que l’on peut démontrer ou calculer mécaniquement. Voir Alan Turing et l'histoire de l’informatique.
Kurt Gödel
Né en 1906 à Brünn (aujourd’hui Brno, en République tchèque), Gödel fait ses études à Vienne, où il fréquente le Cercle de Vienne. Il publie ses théorèmes en 1931. Il émigre aux États-Unis en 1940 et rejoint l’Institute for Advanced Study de Princeton, où il se lie d’amitié avec Albert Einstein. Il y étudie aussi la relativité générale, dont il trouve en 1949 des solutions autorisant, en théorie, des boucles temporelles. Il meurt à Princeton en 1978.
Questions fréquentes
Que dit le théorème de Gödel en termes simples ?
Que dans tout système mathématique cohérent assez puissant pour l’arithmétique, il y a des affirmations vraies qu’on ne peut pas démontrer avec les règles de ce système, et que le système ne peut pas prouver qu’il est sans contradiction.
Les théorèmes de Gödel rendent-ils les mathématiques incertaines ?
Non. Ils montrent les limites de la méthode axiomatique, mais ne remettent en cause aucun théorème démontré. Les mathématiques ont continué à progresser normalement.
Quel est le lien avec le paradoxe du menteur ?
Gödel remplace « cette phrase est fausse » par « cet énoncé n’est pas démontrable ». Le premier mène à une contradiction ; le second à un énoncé vrai mais indémontrable.
Peut-on ajouter l’énoncé indémontrable comme axiome ?
Oui, mais le nouveau système, toujours assez puissant, aura à son tour des énoncés indémontrables. L’incomplétude ne peut pas être éliminée en ajoutant des axiomes.