Théorème d'incomplétude de Gödel - Définition

Des exemples de systèmes incomplets et d'énoncés indécidables

L'existence de théories incomplètes est banale. Beaucoup de théories, comme la théorie des groupes, des anneaux, des corps, ne sont pas complètes : par exemple on peut dire au premier ordre qu'un groupe ou un corps a 2 éléments, ou 3 éléments. C'est différent pour l'arithmétique, on aurait souhaité capturer par une axiomatique toutes les propriétés des entiers naturels. Pour les théories destinées à fonder les mathématiques, Principia Mathematica ou théorie des ensembles, on peut s'attendre à ne pas avoir encore découvert tous les axiomes. Mais le théorème de Gödel affirme qu'il restera toujours des énoncés indécidables (tant que la théorie reste récursivement axiomatisable).

Il existe également des théories complètes intéressantes, comme l'arithmétique de Presburger déjà évoquée, la théorie des corps algébriquement clos d'une caractéristique donnée, la théorie des corps réels clos, et la géométrie élémentaire qui lui est associée.

Énoncés indécidables dans l'arithmétique de Peano

Appliqués à l'arithmétique, les théorèmes de Gödel fournissent des énoncés dont la signification est tout à fait intéressante, puisqu'il s'agit de la cohérence de la théorie. Cependant ces énoncés dépendent du codage choisi. Ils sont pénibles à écrire explicitement.

Paris et Harrington ont montré en 1977 qu'un renforcement du théorème de Ramsey fini, vrai dans N, n'est pas démontrable dans l'arithmétique de Peano. Il s'agit du premier exemple d'énoncé indécidable dans l'arithmétique qui n'utilise pas de codage du langage. Depuis, on en a découvert d'autres. Le théorème de Goodstein est un tel énoncé ; sa preuve est particulièrement simple (quand on connaît les ordinaux), mais utilise une induction jusqu’à l'ordinal dénombrable ε₀. Kirby et Paris ont démontré en 1982 que l'on ne peut pas prouver ce théorème dans l'arithmétique de Peano.

Les énoncés de ce genre qui ont été découverts sont des résultats de combinatoire. Leur preuve n'est pas nécessairement très compliquée, et en fait il n'y a aucune raison de penser qu'il y a un lien entre complexité technique d'une preuve et possibilité de formaliser celle-ci dans l'arithmétique de Peano.

Énoncés indécidables en théorie des ensembles

En théorie des ensembles, on a d'autres énoncés indécidables que ceux fournis par le théorème de Gödel qui peuvent être de nature différente. Ainsi, d'après des travaux de Gödel, puis de Paul Cohen, l'axiome du choix et l'hypothèse du continu sont des énoncés indécidables dans ZF la théorie des ensemble de Zermelo et Fraenkel, le second étant d'ailleurs indécidable dans ZFC (ZF plus l'axiome du choix). Mais d'une part, ce ne sont pas des énoncés arithmétiques. D'autre part, la théorie obtenue en ajoutant à ZF l'axiome du choix ou sa négation est équi-cohérente à ZF : la cohérence de l'une entraîne la cohérence de l'autre et réciproquement. De même pour l'hypothèse du continu. Ce n'est pas le cas pour un énoncé exprimant la cohérence de ZF, d'après justement le second théorème d'incomplétude. De même pour l'un des deux énoncés obtenus par les preuves usuelles du premier théorème d'incomplétude (il est équivalent à un énoncé de cohérence).

Considérons une théorie des ensembles T+A. Démontrer qu'un ensemble (un objet de la théorie) est modèle de la théorie des ensembles T, c’est démontrer la cohérence de T. Si l'on suppose que l'on peut faire une telle démonstration, on peut donc déduire par le second théorème d'incomplétude que, si T est cohérente, A n'est pas démontrable dans T. On montre ainsi que certains axiomes qui affirment l'existence de « grands » cardinaux, ne sont pas démontrables dans ZFC.