http://cer1se.free.fr/principia/index.php/godel-indemontrable-mais-vrai/

Gödel : indémontrable mais vrai ?

Le 8 décembre 2007 par Sephi, dans Mathématiques

Algèbre

Les théorèmes de Gödel font partie de la culture mathématique la plus répandue. Toutefois, vu leur difficulté technique, il n’est pas évident d’interpréter correctement des énoncés vulgarisés de ces théorèmes. Une des questions essentielles soulevées concerne l’existence théorique d’énoncés vrais et indémontrables. Cet article se propose d’explorer avec un peu plus de détails cette question.


Énoncés des théorèmes d’incomplétude de Gödel

Premier théorème. Si T est une théorie consistante et récursive contenant l’arithmétique, alors il existe des formules indécidables, i.e. T est incomplète.

Second théorème. Si T est une théorie consistante et récursive contenant l’arithmétique, alors on peut écrire dans le langage de T une formule Cons dont la signification intuitive est « T est consistante » et telle que Cons n’est pas démontrable.

Avant toute chose, il faut préciser la signification des termes mentionnés, tels que « consistant » et « récursif ».

Les définitions qui suivent seront pour la plupart informelles, bien que nombreuses (du moins pour un texte de vulgarisation en ligne). Elles seront toutefois nécessaires pour se rapprocher le plus possible de la signification de ces théorèmes.

Définitions préliminaires

Une formule close est une formule logiquement valide sans variables libres (i.e. toute variable est quantifiée).

Exemple. La formule

Px \rightarrow R(x,y)

est logiquement valide mais non close, exprimant que si x possède la propriété P, alors la relation R est vraie entre x et y. Par contre, la formule

\forall x\quad\exists y\quad(Px \rightarrow R(x,y))

est une formule close.

Une théorie est un ensemble (fini ou infini) de formules closes écrites avec des symboles puisés dans un ensemble de symboles appelé langage. Les éléments d’une théorie sont appelés axiomes. Voici des exemples importants :

Exemple. L’arithmétique élémentaire est la théorie écrite dans le langage \{0,S,+,\times\} formée des sept axiomes suivants :

\forall x\quad(Sx\neq 0)
\forall x\quad(x=0\quad\vee\quad\exists y\quad(x=Sy))
\forall x,y\quad(Sx=Sy\rightarrow x=y)
\forall x\quad(x+0=x)
\forall x,y\quad(x+Sy=S(x+y))
\forall x\quad(x\times 0 = 0)
\forall x,y\quad(x\times Sy = x\times y + x)

Ces axiomes permettent de formaliser l’ensemble des nombres naturels. La fonction S est le « successeur » qui, en pratique, associe à un naturel x le naturel x+1.

Exemple. L’arithmétique de Peano, que l’on notera PA, est obtenue à partir de l’arithmétique élémentaire en ajoutant l’axiome de récurrence1 qui affirme que pour vérifier qu’une propriété F est vraie pour tous les naturels, il suffit de montrer qu’elle est vraie pour 0, et que si elle est vraie pour un naturel x, alors elle est vraie pour son successeur Sx.

Exemple. La théorie des ensembles de Zermelo-Fraenkel (notée ZF) est l’ensemble formé des axiomes d’extensionnalité, de la paire, de la réunion, des parties, de l’infini et du schéma de remplacement. Le lecteur intéressé trouvera sans mal les définitions de ces axiomes. On retiendra que ZF permet de formaliser la totalité des mathématiques actuelles.

Une théorie est consistante si et seulement si elle est non-contradictoire, i.e. s’il est impossible de démontrer à la fois une formule et sa négation.

Une théorie est récursive s’il est possible de déterminer (en un nombre fini d’étapes) si une formule F donnée fait partie des axiomes de la théorie.

Exemple. Toute théorie formée d’un nombre infini d’axiomes est non récursive.

Une formule F est décidable dans une théorie T si cette dernière démontre F ou sa négation, i.e. si on peut déterminer à partir des axiomes de T, et avec les règles d’inférence de la logique classique, si F est vraie ou fausse.

Une théorie est complète si et seulement si elle est consistante et si toute formule F est décidable.

Nous avons maintenant en main tous les outils pour comprendre les énoncés des théorèmes de Gödel.

Première lecture des théorèmes d’incomplétude

Premier théorème. Si T est une théorie consistante et récursive contenant l’arithmétique, alors il existe des formules indécidables, i.e. T est incomplète.

Toute théorie construite par une activité humaine est récursive. En effet, pouvoir repérer les axiomes de la théorie est la moindre des choses ! De plus, toute théorie digne de ce nom doit être consistante (on adopte donc le principe de non-contradiction). Rappelons-nous qu’en logique classique, si une théorie est inconsistante, i.e. contradictoire, alors toute formule, sans exception, est démontrable. Dans une telle théorie, il ne serait plus possible de distinguer les vérités des faussetés. Cette situation inacceptable est illustrée par l’anecdote (à l’authenticité incertaine) sur Bertrand Russell.

Anecdote. Lors d’un cours de logique, Bertrand Russell était en train d’expliquer le fait que tout est démontrable à partir d’une contradiction lorsqu’un étudiant l’interrompit :
– Dans ce cas, en supposant que 2+2=5, pourriez-vous démontrer que vous êtes le Pape ?
– Rien de plus simple, répondit Russell. Soustrayez 2 des membres de l’égalité, vous obtenez 2=3. Permutez les membres et soustrayez encore 1, vous obtenez 2=1. Le Pape et moi sommes deux, or deux est égal à un. Par conséquent, je suis le Pape.

Les hypothèses de consistance et de récursivité sont donc naturelles et très générales. Enfin, l’hypothèse que la théorie doit contenir l’arithmétique signifie seulement que l’on souhaite avoir une théorie capable de produire au moins des résultats mathématiques simples, tels que les opérations élémentaires entre les nombres naturels. Une théorie satisfaisant ces hypothèses sera dite « convenable ».

La conclusion est d’autant plus surprenante : aucune théorie « convenable » n’est capable de démontrer l’entièreté des formules écrites dans son propre langage.

Il y a cependant des conclusions hâtives à ne pas tirer de ce premier théorème. Cette question sera abordée dans la prochaine section.

Second théorème. Si T est une théorie consistante et récursive contenant l’arithmétique, alors on peut écrire dans le langage de T une formule Cons dont la signification intuitive est « T est consistante » et telle que Cons n’est pas démontrable.

Non content de nous avoir secoués avec son premier théorème, Gödel revient à la charge en disant, cette fois, qu’aucune théorie consistante « convenable » n’est capable de démontrer sa propre consistance ! Ce théorème peut se reformuler par sa contraposée :

Si T est une théorie récursive, contenant l’arithmétique et capable de démontrer au sein d’elle-même sa propre consistance, alors T est inconsistante.

Cette formulation est certainement troublante. En effet, elle s’applique à la théorie des ensembles ZF qui, rappelons-le, formalise la totalité des mathématiques. On ignore actuellement si ZF est consistante mais on sait que si, un jour, on pouvait démontrer sa consistance par ses propres outils, c’est qu’elle est inconsistante. On en vient presque à exprimer le désir de ne jamais être sûr de la consistance de ZF si on veut préserver une chance qu’elle soit consistante !

Seconde lecture des théorèmes : les conséquences

Bien que les théorèmes soient profondément novateurs (qui pourrait le nier !), on trouve toutefois un certain nombre de conséquences erronées issues d’une interprétation pas assez rigoureuse de ces théorèmes. Dans cette section, je tenterai de nuancer certaines conséquences, en les présentant sous la forme de questions.

1. L’arithmétique de Peano PA et la théorie des ensembles ZF sont-elles consistantes ?

On l’ignore actuellement. Il est clair que PA et ZF sont récursives. Il reste à savoir si elles sont consistantes pour pouvoir appliquer les résultats de Gödel. Or on ne peut pas démontrer qu’elles sont consistantes avec leurs propres outils, car cela reviendrait à montrer qu’elles sont inconsistantes (en vertu du second théorème) !

De plus, pour éviter d’entrer dans un cercle vicieux, on ne peut pas se contenter de démontrer la consistance d’une théorie à partir d’une théorie qui l’englobe, car il faudrait alors démontrer la consistance de la grande théorie et ainsi de suite. C’est d’ailleurs le cas de PA : une preuve de sa consistance est possible au sein de ZF. Une telle preuve de consistance est dite relative.

2. Existe-t-il une preuve absolue (i.e. non relative) de la consistance de PA et de ZF ?

Certaines personnes ont proposé des preuves absolues, mais aucune n’a encore fait l’unanimité. L’existence même d’une preuve absolue est incertaine. Toutefois, les théorèmes de Gödel n’impliquent pas l’inexistence de telles preuves.

Signalons aussi qu’avec la théorie des modèles, on peut définir la consistance d’une autre façon : une théorie est consistante si et seulement si elle admet un modèle2. Dans ce cas, on pourrait dire, de façon absolue, que l’arithmétique PA est consistante : en effet, l’ensemble des nombres naturels en est un modèle. Mais cette vision est problématique : PA permet de formaliser les naturels, or on utilise justement les naturels pour montrer sa consistance…

3. Parmi les formules indécidables d’une théorie « convenable », y en a-t-il certaines qui sont vraies ?

Si la théorie est consistante, alors la réponse est oui. Ceci découle de la preuve du premier théorème, dans laquelle on construit une formule G exprimant, dans le langage de la théorie T, le fait que « G n’est pas démontrable ». On montre ensuite que cette formule (appelée la « phrase de Gödel ») est indécidable dans T et est vraie à la condition que T soit consistante.

Sous cette condition, et par un raisonnement méta-mathématique, on peut voir que cette formule est effectivement vraie. Si G est démontrable, alors il y aurait contradiction car G affirme justement le contraire. Comme on a supposé la théorie consistante, il faut en conclure que G n’est pas démontrable. Or, c’est exactement ce qu’affirme G, ce qui nous permet de dire que G est vraie (et indémontrable).

4. La phrase de Gödel est-elle une formule méta-mathématique, ou une formule mathématique ?

Les deux. La preuve du premier théorème repose sur une traduction des énoncés méta-mathématiques portant sur la théorie T en des formules au sein de T elle-même.

Dans le cas de l’arithmétique PA, un nombre naturel unique est associé à chaque symbole pouvant servir à formuler des énoncés méta-mathématiques. Une bijection est alors construite entre les propriétés des nombres naturels, et les relations entre énoncés méta-mathématiques. Ainsi, la phrase de Gödel après traduction est bel et bien une formule de l’arithmétique, qui exprime une certaine relation entre les nombres naturels.

5. Y a-t-il des propriétés mathématiques vraies et indémontrables ?

Si l’arithmétique est consistante, alors la réponse est oui. En effet, dans la suite de la preuve de Gödel, l’assertion méta-mathématique suivante est démontrée :

Si T est consistante, alors G est vraie.

(Rappel : la consistance de T n’est pas démontrable). On a vu dans la question 4 que G correspond, après traduction, à une propriété précise sur les nombres naturels, i.e. une propriété arithmétique. Cette propriété-là est vraie et indémontrable si l’arithmétique est consistante. Ceci reste vrai pour toute théorie consistante et récursive qui contient l’arithmétique. En conclusion, la vérité de la phrase de Gödel (et de sa traduction dans la théorie T) est implicitement contenue dans l’hypothèse que T est consistante.

En pratique, comme on ignore la plupart du temps si T est consistante, on a finalement autant de raison de croire en la vérité de G, qu’on en a de croire en la consistance de T. Dès lors, on ne peut pas affirmer, dans l’absolu, qu’il existe des vérités indémontrables dans les mathématiques actuelles.

En outre, le théorème de Gödel ne fournit aucun autre exemple de formule vraie et indémontrable.

6. L’esprit humain surpasse-t-il toute machine ?

Un argument souvent rencontré est qu’en vertu des théorèmes, une machine capable d’appliquer des règles d’inférence sur un nombre fini d’axiomes (comme un ordinateur) ne peut se prononcer sur la vérité de certains énoncés (qui sont les phrases de Gödel G) alors que l’être humain est capable de voir qu’ils sont vrais.

Cette conclusion passe sous silence le fait que les théorèmes ont la forme conditionnelle : si la théorie (et son implémentation dans la machine) est consistante, alors l’humain peut affirmer la vérité de G. Or, il est extrêmement difficile pour l’être humain de déterminer si une théorie est consistante (le second théorème n’aidant pas…) et il n’y a actuellement pas de méthode miracle pour y arriver.

L’argument ci-dessus suppose implicitement une capacité humaine à déterminer la consistance de toute théorie, ce qui est hautement spéculatif.

Toutefois, pour terminer, on peut mentionner un dernier résultat intéressant. On dit qu’une théorie T est décidable si on peut toujours déterminer, en un nombre fini d’étapes, si une formule donnée F est démontrable dans T (sans nécessairement avoir la preuve de F). On peut alors démontrer que :

L’arithmétique est indécidable.

Autrement dit : il n’existe pas de moyen automatique de savoir si une formule donnée est vraie ou pas pour les nombres naturels. Peut-être ce résultat illustre-t-il le fait qu’il faille une part de génie et d’intuition pour pouvoir deviner la vérité de certains énoncés mathématiques ? Ceci, pour l’instant, reste effectivement hors de portée des machines.

 
 
 

Références :

  • David R., Nour K., Raffalli C., Introduction à la logique, 2e éd., Paris : Dunod, (2001) 2003.
  • Nagel E., Newman J. R., Gödel K., Girard J.-Y., Le théorème de Gödel, Paris : Éditions du Seuil, 1989. Points Sciences.
  • Raatikainen P., On the philosophical relevance of Gödel’s incompleteness theorems, Revue Internationale de Philosophie 59 (2005), 513–534.

  1. En fait, ce n’est pas l’axiome de récurrence mais le schéma de récurrence qui est ajouté. Je me suis permis cet abus pour ne pas alourdir le texte. []
  2. La définition d’un modèle sort du cadre de cet article. On peut toutefois la comprendre intuitivement : un modèle pour une théorie T est un ensemble d’objets qui reflètent (ou satisfont) les axiomes de T. Un exemple très simple est donné par la théorie des groupes dont les axiomes sont ceux qui définissent la structure de groupe. L’ensemble des entiers muni de l’addition usuelle en est un modèle, de même que l’ensemble des rotations de l’espace muni de la composition. []

Cliquez ici pour imprimer.