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

Énoncés des deux théorèmes

Le premier théorème d'incomplétude peut être énoncé de la façon encore un peu approximative suivante (les termes techniques sont expliqués dans le paragraphe suivant).

Dans n'importe quelle théorie récursivement axiomatisable, cohérente et capable de « formaliser l'arithmétique », on peut construire un énoncé arithmétique qui ne peut être ni prouvé ni réfuté dans cette théorie.

De tels énoncés sont dits indécidables dans cette théorie. On dit également indépendants de la théorie.

Toujours dans l'article de 1931, Gödel en déduit le second théorème d'incomplétude :

Si T est une théorie cohérente qui satisfait des hypothèses analogues, la cohérence de T, qui peut s'exprimer dans la théorie T, n'est pas démontrable dans T.

Ces deux théorèmes ont été prouvés pour l'arithmétique de Peano et donc pour les théories plus fortes que celle-ci, en particulier les théories destinées à fonder les mathématiques, telles que la théorie des ensembles ou les Principia Mathematica.

Les conditions d'application des théorèmes

Pour fixer les idées, on considère dorénavant que les théories en question sont, comme celles que l'on vient de mentionner (arithmétique de Peano, théorie des ensembles), des théories du premier ordre de la logique classique, même si les théorèmes d'incomplétude restent valides, sous les mêmes conditions, par exemple en logique intuitionniste ou en passant à l'ordre supérieur.

• Par théorie récursivement axiomatisable, on entend que la théorie peut être axiomatisée de façon à ce qu'il soit possible de reconnaître purement mécaniquement les axiomes parmi les énoncés du langage de la théorie. C'est le cas évidemment des théories utilisées pour formaliser tout ou partie des mathématiques usuelles.
• Une théorie est cohérente si aucune contradiction ne peut être prouvée à partir de ses axiomes. On dit aussi qu'elle est consistante ou non-contradictoire. Dans une théorie qui n'est pas cohérente on peut tout démontrer, et donc la théorie est vide de sens. Pour le premier théorème d'incomplétude, Gödel faisait une hypothèse de cohérence un peu plus forte. L'hypothèse de cohérence la plus simple suffit de toute façon pour le second théorème, qui n'énonce que la non-démontrabilité de l'énoncé de cohérence. De plus, J. B. Rosser a donné en 1936 une démonstration du premier théorème d'incomplétude sous cette simple hypothèse de cohérence. À proprement parler, l'énoncé du premier théorème d'incomplétude donné au début de cet article n'est donc pas exactement celui de Gödel. On le nomme souvent théorème de Gödel-Rosser.
• Une théorie permet de formaliser l'arithmétique si, d'une part il est possible de définir (en un sens qu'il faudrait préciser) les entiers (donnés par zéro et la fonction successeur), avec les opérations usuelles, au moins l'addition et la multiplication, et si d'autre part un certain nombre d'énoncés sur les entiers sont prouvables dans la théorie. L'arithmétique de Peano est une telle théorie, et satisfait les hypothèses des deux théorèmes d'incomplétude. En fait une théorie arithmétique beaucoup plus faible suffit pour le premier (la récurrence n'est essentiellement pas utile). Pour le second, il faut un minimum de récurrence.
  Il est remarquable que pour formaliser l'arithmétique, l'addition et la multiplication suffisent (en plus de zéro et du successeur). C'est le tout premier pas vers la solution du dixième problème de Hilbert (voir théorème de Matiyasevich). L'addition seule ne suffit pas : l'arithmétique de Presburger, qui est la théorie obtenue en restreignant l'arithmétique de Peano au langage de l'addition (en plus de zéro et du successeur), est complète.

Conséquences immédiates du premier théorème d'incomplétude

On peut reformuler le premier théorème d'incomplétude en disant que si une théorie T satisfait les hypothèses utiles, il existe un énoncé tel que chacune des deux théories obtenues l'une en ajoutant à T cet énoncé comme axiome, l'autre en ajoutant la négation de cet énoncé, sont cohérentes. Donnons-en la démonstration.

Étant donné un énoncé G, notons non G sa négation. On montre facilement qu'un énoncé G n'est pas démontrable dans T si et seulement si la théorie T + non G (la théorie T à laquelle on ajoute l'axiome non G) est cohérente. En effet, si G est démontrable dans T, T + non G est évidemment contradictoire. Réciproquement, supposons T + non G contradictoire. Cela signifie que, dans la théorie T, on peut déduire de non G une contradiction. On en déduit que G est conséquence de T (c'est un raisonnement par l'absurde).

Il est donc équivalent de dire qu'un énoncé G est indécidable dans une théorie cohérente T, et de dire que les deux théories T + non G et T + G sont cohérentes. L'énoncé G n'étant évidemment pas indécidable dans chacune de ces deux théories, on voit que la notion d'énoncé indécidable est par nature relative à une théorie donnée.

Ainsi, si G est un énoncé indécidable donné pour T par le premier théorème d'incomplétude, on aura, en appliquant à nouveau ce théorème, un nouvel énoncé indécidable dans la théorie T + G (et donc d'ailleurs indécidable aussi dans la théorie T). De fait, quand le théorème d'incomplétude s'applique à une théorie T, il s'applique à toutes les extensions cohérentes de cette théorie, tant qu'elles restent récursivement axiomatisables : il n'y a aucun moyen effectif de compléter une telle théorie.

On peut également noter que, quelle que soit la théorie en jeu, Gödel a montré que l'énoncé indécidable qu'il construit pour démontrer son théorème est arithmétique, c’est-à-dire qu'on peut l'exprimer dans le langage de l'arithmétique, même si la théorie est plus expressive. Il s'agit même d'un énoncé de l'arithmétique qui, bien que fastidieux à écrire explicitement, est logiquement assez simple (en un sens qui sera précisé en fin d'article). Par exemple, on obtiendra par le théorème de Gödel appliqué à la théorie des ensembles de Zermelo-Fraenkel un énoncé arithmétique, qui sera pourtant indécidable dans cette même théorie des ensembles.

Conséquences immédiates du second théorème d'incomplétude

L'énoncé du second théorème d'incomplétude a ceci de particulier, qu'il utilise la formalisation de la théorie dans elle-même, puisqu'il parle de la cohérence de la théorie comme d'un énoncé de celle-ci. C'est assez inhabituel en mathématiques, et cela entraîne facilement des confusions. Les conséquences qui suivent sont immédiates, au sens où elles se déduisent « simplement » du second théorème d'incomplétude, mais cette simplicité elle-même peut n'avoir rien d'immédiate.

Il peut être utile pour comprendre l'énoncé du second théorème d'incomplétude, de le reformuler par contraposée :

Si T est une théorie récursivement axiomatisable qui permet de formaliser « suffisamment d'arithmétique », et si T prouve un énoncé exprimant qu'elle est cohérente, alors T est contradictoire.

En revanche, une théorie qui démontre un énoncé exprimant qu'elle n'est pas cohérente, peut très bien ne pas être contradictoire, comme on le déduit du second théorème d'incomplétude lui-même !

Donnons en une preuve. Appelons coh_T un énoncé qui exprime la cohérence de T dans la théorie T. De la même façon qu'au paragraphe précédent pour le premier théorème, on reformule le second théorème d'incomplétude en disant que, sous les hypothèses utiles sur T, si la théorie T est cohérente, la théorie T'=T + non coh_T est encore cohérente. Rappelons que « T n'est pas cohérente », signifie qu'il existe une preuve d'une contradiction dans T. Une preuve dans T est aussi une preuve dans T' , qui a juste un axiome supplémentaire. Il est donc simple de montrer dans une théorie telle que T, qui satisfait les hypothèses du théorème de Gödel, que non coh_T a pour conséquence non coh_T' (n'oublions pas cependant que coh_T et coh_T' sont des énoncés exprimés dans le langage de ces théories, il faudrait, pour que la preuve soit vraiment complète, rentrer dans le détail de cette représentation pour montrer cette implication). On a donc déduit du second théorème d'incomplétude, et de l'existence d'une théorie cohérente T qui satisfait les hypothèses de ce théorème -- prenons par exemple l'arithmétique de Peano -- l'existence d'une théorie T' cohérente qui démontre non coh_T', à savoir un énoncé exprimant qu'elle n'est pas cohérente. De telles théories sont fort heureusement pathologiques : on n'en a jamais rencontré parmi les théories mathématiques usuelles. Ce résultat peut choquer l'intuition, mais il faut bien voir que l'on peut reformuler le second théorème d'incomplétude en disant que toute théorie cohérente qui satisfait les hypothèses utiles a une extension qui démontre la négation de sa cohérence.

A contrario une théorie incohérente, dans laquelle tous les énoncés sont prouvables, démontrera évidemment un énoncé exprimant qu'elle est cohérente.

On voit par ces diverses remarques que le second théorème d'incomplétude ne dit rien en défaveur de la cohérence d'une théorie à laquelle il s'applique, par exemple la cohérence de l'arithmétique de Peano. Tout ce qu'il dit de cette dernière, c'est qu'elle ne peut se prouver que dans une théorie logiquement plus forte.

Un autre exemple d'application simple, mais assez surprenante, du second théorème d'incomplétude est le théorème de Löb, qui affirme que, dans une théorie T qui satisfait les hypothèses utiles, prouver dans T un énoncé sous l'hypothèse que cet énoncé est prouvable dans la théorie, revient à prouver l'énoncé. Autrement dit cette hypothèse est inutile.