vignette|Kurt Gödel en 1925 Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »). Ils ont marqué un tournant dans l'histoire de la logique en apportant une réponse négative à la question de la démonstration de la cohérence des mathématiques posée plus de vingt ans auparavant par le programme de Hilbert.
Les deux théorèmes Le premier théorème d'incomplétude établit qu'une théorie cohérente suffisante pour y démontrer les théorèmes de base de l'arithmétique est nécessairement incomplète, au sens où il existe des énoncés qui n'y sont ni démontrables, ni réfutables (un énoncé est démontrable si on peut le déduire des axiomes de la théorie, il est réfutable si on peut déduire sa négation). On parle alors d'énoncés indécidables dans la théorie. Le second théorème d'incomplétude est à la fois un corollaire et une formalisation d'une partie de la preuve du premier. Il traite le problème des preuves de cohérence d'une théorie : une théorie est cohérente s'il existe des énoncés qui n'y sont pas démontrables (ou, ce qui revient au même, si on ne peut y démontrer A et non A) ; par exemple, on exprime souvent la cohérence de l'arithmétique par le fait que l'énoncé 0 = 1 n'y est pas démontrable (sachant que bien entendu 0 ≠ 1 l'est). Sous des hypothèses à peine plus fortes que celles du premier théorème, on peut construire un énoncé exprimant la cohérence d'une théorie dans le langage de celle-ci. Le second théorème affirme alors que si la théorie est cohérente cet énoncé ne peut pas en être conséquence, ce que l'on peut résumer par : « une théorie cohérente ne démontre pas sa propre cohérence. »
Énoncés 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) :
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 :
Ces deux théorèmes sont valides par exemple 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.
Conditions d'application 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 intuitionnisteLa prouvabilité intuitionniste étant plus faible que la prouvabilité classique, l'énoncé que Gödel fournit pour le premier théorème d'incomplétude, indécidable en logique classique, le reste en logique intuitionniste. Par ailleurs, la preuve de Gödel est constructive : l'énoncé indécidable peut être donné explicitement pour une théorie donnée. Elle peut se formaliser en logique intuitionniste, même si le présent article ne s'en soucie pas. 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 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 des théories utilisées pour formaliser tout ou partie des mathématiques usuelles. Une théorie est cohérente s'il existe des énoncés qui ne sont pas conséquence de ses axiomes ; ou autrement dit si elle ne démontre pas tous les énoncés. Une théorie incohérente permet de tout démontrer et est donc vide de sens. La cohérence est souvent exprimée sous la forme équivalente : aucune contradiction ne peut être prouvée à partir des axiomes. On dit aussi qu'elle est consistante ou non contradictoire. Pour pouvoir démontrer son premier théorème d'incomplétude sous sa forme la plus générale — il existe un énoncé qui n'est ni démontrable, ni réfutable dans la théorie — Gödel faisait une hypothèse de cohérence un peu plus forte. Cette hypothèse n'est toutefois pas nécessaire pour le second théorème, qui n'énonce que la non-démontrabilité de l'énoncé de cohérence. De plus, John Barkley 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é ci-dessus n'est donc pas exactement celui de Gödel ; pour cette raison on nomme celui-ci « 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, les preuves usuelles utilisent 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 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 contraposée).
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 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édiat.
Il peut être utile pour comprendre l'énoncé du second théorème d'incomplétude, de le reformuler par contraposée :
On peut remarquer que ce théorème ne dit rien dans le cas où T démontre un énoncé exprimant qu'elle n'est pas cohérente. De fait, on peut déduire du second théorème cette conséquence, apparemment paradoxale, qu'il existe des théories non contradictoires démontrant leur propre incohérence.
Pour voir cela, appelons cohT 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 cohT est encore cohérente. R« 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 cohT a pour conséquence non cohT' (n'oublions pas cependant que cohT et cohT' 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 – par exemple l'arithmétique de Peano – l'existence d'une théorie T' cohérente qui démontre non cohT', par exemple l'arithmétique de Peano augmentée d'un axiome exprimant l'incohérence de celle-ci. De telles théories sont pathologiquesDit de façon plus mathématique, ces théories ne sont pas ω-cohérentes. : on n'en rencontre pas parmi les théories mathématiques usuelles.
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.
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.