Logique et ensemblesNotion · Glossaire
théorèmes d'incomplétude de Gödel
Les théorèmes d’incomplétude de Gödel affirment que toute théorie formelle cohérente, récursivement axiomatisable et assez expressive pour formaliser l’arithmétique élémentaire est incomplète : il existe un énoncé arithmétique qu’elle ne peut ni démontrer ni réfuter. Le second ajoute que, sous ces mêmes hypothèses, une telle théorie ne peut démontrer en son sein sa propre cohérence ; ils révèlent ainsi des limites intrinsèques de la démonstration formelle.
Sommaire
Ce que vous allez apprendre
- Distinguer les conclusions du premier et du second théorème.
- Vérifier les trois hypothèses avant d'appliquer les résultats.
- Comprendre le sens précis d'un énoncé indécidable dans une théorie.
- Séparer incomplétude, incohérence et absence momentanée de preuve.
- Relier la portée des théorèmes au programme de Hilbert sans la généraliser abusivement.
En clair
Imaginez un livre de règles capable d'écrire l'arithmétique et de vérifier des démonstrations. Même si ses règles ne se contredisent pas, elles ne répondent pas à toutes les questions arithmétiques que ce livre peut formuler : au moins un énoncé ne peut être ni prouvé ni réfuté avec elles.
Gödel montre aussi une seconde limite : ce même système cohérent ne peut pas démontrer, par ses seules règles, qu'il ne produira jamais de contradiction. Ces limites concernent des théories formelles assez puissantes, pas n'importe quel ensemble de règles.
Définition
Les théorèmes d'incomplétude sont deux résultats de logique mathématique publiés en 1931 par Kurt Gödel. Ils s'appliquent à une théorie formelle T lorsque trois conditions sont réunies : ses axiomes sont énumérables par une procédure effective, elle est cohérente, et elle est assez expressive pour formaliser l'arithmétique élémentaire. Une théorie cohérente ne démontre pas à la fois un énoncé et sa négation.
Le premier théorème affirme qu'il existe alors un énoncé arithmétique indécidable dans T : ni cet énoncé ni sa négation ne sont démontrables à partir des axiomes de T. La théorie est donc incomplète. Si G désigne un tel énoncé et si le signe ⊬ signifie « ne démontre pas », cette double impossibilité s'écrit : .
Le second théorème porte sur l'énoncé qui formule la cohérence de T, noté Con(T). Sous les mêmes hypothèses, T ne peut pas démontrer cet énoncé : . Le schéma associé sépare les hypothèses communes des deux conclusions. Ces résultats établissent ainsi deux limites précises : T est incomplète et, sous les hypothèses considérées, elle ne peut pas démontrer sa propre cohérence.
Un exemple, pas à pas
Considérons une théorie formelle T. Les données du cas sont les suivantes : ses axiomes peuvent être énumérés par une procédure effective ; T est supposée cohérente ; T formalise l'arithmétique élémentaire. Il ne s'agit pas de calculer un énoncé particulier, mais d'appliquer exactement les hypothèses des deux théorèmes.
1. Vérifions le domaine : T est une théorie formelle et porte assez d'arithmétique pour exprimer les énoncés concernés.
2. Vérifions les deux autres hypothèses : l'axiomatisation est effective et aucune contradiction n'est supposée démontrable dans T.
3. Le premier théorème garantit alors l'existence d'au moins un énoncé arithmétique que T ne démontre ni ne réfute. Le contrôle consiste à constater que les trois hypothèses ont été utilisées avant de conclure à l'incomplétude.
4. Le second théorème s'applique au même cas : si la cohérence de T est formulée dans T, elle n'y est pas démontrable. Le résultat porte sur les capacités de T elle-même ; il ne constitue pas une preuve que T est cohérente.
En pratique
Face à l'affirmation qu'une théorie formelle décide toute question arithmétique, examinez d'abord son domaine. Si elle est effectivement axiomatisable, cohérente et assez puissante pour l'arithmétique élémentaire, le premier théorème écarte cette prétention de complétude. Si une hypothèse manque, ce théorème ne suffit pas pour trancher.
Face à une preuve de cohérence présentée dans la théorie même qu'elle étudie, repérez précisément le cadre utilisé. Sous les hypothèses de Gödel, le second théorème interdit à T de démontrer sa propre cohérence ; une justification ne peut donc pas être attribuée à T sans vérifier ce point.
Dans l'histoire des fondements, ces résultats servent à situer la limite du programme de Hilbert. Ils ne suppriment pas l'étude formelle de l'arithmétique : ils montrent que l'objectif conjoint de complétude et de preuve interne de cohérence ne peut pas être atteint sous les hypothèses indiquées.
À ne pas confondre
Incomplétude et incohérence. Une théorie incomplète laisse au moins un énoncé sans preuve ni réfutation ; une théorie incohérente démontre une contradiction. Le premier théorème conclut à l'incomplétude précisément sous l'hypothèse de cohérence : les deux propriétés ne sont donc pas synonymes.
Indécidable dans T et simplement non démontré. Un énoncé indécidable dans T résiste dans les deux sens : T ne démontre ni l'énoncé ni sa négation. Constater seulement l'absence d'une preuve de l'énoncé ne suffit donc pas à établir son indécidabilité.
Limites et pièges
Théorie trop faible. Les conclusions ne visent pas tout système de règles. Si une théorie ne formalise pas suffisamment l'arithmétique élémentaire, une hypothèse essentielle manque ; il faut étudier ce système avec un résultat adapté au lieu d'invoquer automatiquement Gödel.
Axiomes non effectivement énumérables. Le premier théorème exige une théorie récursivement axiomatisable. Si aucune procédure effective n'énumère les axiomes, son domaine d'application n'est pas établi ; la seule richesse du langage ne permet pas de conclure.
Cohérence supposée, non obtenue gratuitement. Les deux théorèmes sont conditionnels. Ils ne prouvent pas qu'une théorie donnée est cohérente ; si une contradiction y est démontrable, l'hypothèse annoncée échoue et la conclusion ne peut pas être citée sous cette forme.
Portée du second théorème. L'impossibilité concerne une preuve de la cohérence de T dans T elle-même, sous les mêmes hypothèses. Elle ne dit pas que l'énoncé de cohérence ne peut pas être formulé : la source précise au contraire qu'il peut l'être.
Pour aller plus loin
Un prolongement naturel consiste à étudier séparément les trois hypothèses : cohérence, axiomatisation effective et capacité à formaliser l'arithmétique élémentaire. Cette lecture montre exactement où s'appliquent les deux conclusions et empêche de transformer une limite conditionnelle en affirmation sur tout système formel.
L'autre piste est historique : confronter les objectifs du programme de Hilbert aux deux résultats publiés par Gödel en 1931. Pour toute théorie T qui satisfait les hypothèses considérées, ils établissent son incomplétude et l'impossibilité pour T de démontrer sa propre cohérence, et non un abandon de l'arithmétique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres