Les théoremes d'incomplétude de Gödel

Wikipedia : Théorie des ensembles, Kurt Gödel, Théorème d'incomplétude de Gödel, Programme de Hilbert, La liste des 23 problèmes de Hilbert

Pages personnelles : Le théorème de Gödel, la vérité n'est pas toujours prouvable par Eric Andres et Laurent Signac, What is Mathematics: Gödel's Theorem and Around par Karlis Podnieks (Université de Latvia), Kurt Gödel's ontological argument par Christopher Small (Université de Waterloo, Ontario)

Qu'est-ce qu'une théorie ?

Définition

De manière générale, une théorie mathématique est constituée

  • d'un langage dans lequel elle s'exprime. Il s'agit d'une liste de symboles et de règles de grammaire, qui permettent d'écrire des phrases, que l'on appelera assertions. Pour fixer les idées, dans le cadre de la théorie de l'arithmétique par exemple :
$1+1=2$ est une assertion (vraie)
$1+1=3$ est une assertion (fausse)
$1+1=$ n'est pas une assertion (car pas grammaticalement correcte).
  • d'une liste d'axiomes, ou postulats, qui sont le point de départ, les "vérités" de base de la théorie. Il s'agit simplement d’assertions supposées vraies.
  • de règles de déduction qui permettent de déduire une assertion à partir d'une autre. Ces règles permettent de dire que si une assertion A est vraie, alors telle assertion B (construite à partir de A) est vraie aussi1.

On appellera proposition, ou théorème une assertion vraie et prouvée, c'est à dire déduite des axiomes en appliquant les régles de déduction.

Cohérence et complétude

La première chose qu'on demande à une théorie est d'être cohérente (ou consistante). Cela veut simplement dire que si on peut prouver qu'une proposition est vraie, alors on ne peut pas prouver qu'elle est fausse. Et inversement s'il existe un contre-exemple montrant qu'une proposition est fausse, alors il n'existe pas de démonstration de cette proposition.
Cette propriété concerne les axiomes : c'est les axiomes qui ne doivent pas contenir de contradiction entre eux.

C'est un minimum… et pourtant, rien ne nous dit qu'il n'y a pas de contradiction dans les axiomes de la géométrie, de l'arithmétique, etc. On ne sait pas si ces théories sont cohérentes. En 1900, David Hilbert rêvait d'une preuve de la cohérence des mathématiques2.

A ce stade, on comprend que certains - avant la découverte de Gödel - croyaient que tout ce qu'il y aurait à faire pour les mathématiciens dans les siècles à venir, une fois la cohérence des mathématiques prouvées, serait simplement de lister tout ce qui est vrai et tout ce qui est faux (en donnant démonstrations et contre-exemples) dans le cadre de chaque théorie mathématique.

C'est l'idée de complétude : une théorie est complète si, pour toute proposition que l'on peut écrire dans le langage de la théorie, il existe une démonstration montrant qu'elle est vraie ou un contre-exemple montrant qu'elle est fausse. On dit alors que toutes les propositions sont décidables.

La vérité est higher

Aujourd’hui en mathématiques, on ne prétend plus que la vérité absolue existe, tout ce qu'une théorie affirme est relatif, rien d’autre que "si les axiomes sont vrais, alors les théorèmes le sont aussi". A mon avis, la découverte du théorème de Gödel est au moins en partie responsable de cette compréhension, cela nous apparait maintenant comme une évidence. Il faut bien un point de départ dans un raisonnement.

Cela n’a pas toujours été le cas. On peut penser à Aristote [1] :

Pour être acceptable en tant que connaissance scientifique, une vérité doit être déduite d’autres vérités.

Euclide [2] fut certainement un des grands pionniers de cette approche axiomatique avec la géométrie. Pour donner un exemple, les premiers axiomes de sa théorie sont

1. Etant donné deux points, on peut tracer un segment de droite reliant ces deux points.

2. Etant donné un segment de droite, on peut le prolonger indéfiniment de chaque coté.

(liste complète sur Wikipedia)

Pour certains, ces phrases semblaient des vérités absolues, ou des évidences intuitives dictées par un bon sens universel commun. Personne n’a jamais eu d’objection, pendant des siècles. Ca "marche" toujours avec une règle et un crayon, quelque soit notre précision, c'est une observation systématique lors d'une expérience facile à refaire.

Avec un petit nombre de telles phrases, et un petit nombre de règles de déduction tout aussi « évidentes » (par exemple, « deux quantités égales à une troisième sont égales entre elles »), Euclide obtint un système d’une grande efficacité. On peut démontrer le théorème de Pythagore et bien d’autres.

Une efficacité peut-être déraisonnable, aux conséquences démesurées. Pendant des siècles, ces phrases furent enseignées sans modification, comme des commandements religieux ; l’enseignement de cette « science » fut paradoxalement un frein considérable au développement de l’esprit scientifique, qui a besoin d’esprit critique.

Les géométries non-euclidiennes

On prend dans cette section le temps de développer un exemple historique assez simple qui est de nature à éclairer grandement la compréhension du lecteur.
Les mathématiciens du XIXème siècle se sont rendu compte qu’en un sens, plusieurs vérités étaient possibles.

Le postulat des parallèles

Le 5ème axiome, ou 5ème postulat d’Euclide, a joué un rôle particulier dans cette histoire et nous en rappelons une forme classique.

5. Etant donné une droite, et un point en dehors de cette droite, il existe une et une seule droite parallèle à cette droite et passant par ce point.

5emeEuclide.jpg

En fait, dans le texte d’Euclide, cet axiome introduit le concept nouveau de droite parallèle, une droite qui ne rencontre jamais l’autre. Certains avaient des objections : comment savoir si les droites ne se rencontrent vraiment jamais ? on ne peut pas le vérifier en pratique… Cet axiome était gênant, il était moins « évident » que les autres. On a rêvé le déduire des autres axiomes, en faire un théorème qu’on ne pourrait plus contester (on a fini par prouver que c’est impossible, cet axiome est indépendant des autres).

Les géométries de Riemann et Lobatchevski

Dans cette quête pour la solidité des fondements des mathématiques, on découvrit autre chose. Riemann et Lobatchevski avaient choisi de raisonner par contradiction. Pour prouver que le 5ème postulat était vrai, ils supposaient son contraire, et essayaient d’aboutir à une contradiction.

Riemann est parti de l’hypothèse :

5 bis. Etant donné une droite D et un point P n’appartenant pas à D, il n’existe aucune droite parallèle à D passant par P.

5emeRiemann.jpg

C’est comme supposer que toutes les droites passant par P coupent D, autrement dit que les parallèles n’existent pas. Comme supposer que si l’on regarde suffisamment loin, on verra que toutes les droites finissent par se croiser. On ne peut pas vérifier cette hypothèse en pratique car elle implique l’infini (comme celle d’Euclide).

Et à l’inverse, Lobatchevski est parti de :

5 ter. Etant donné une droite D et un point P n’appartenant pas à D, il existe plusieurs droites parallèles à D passant par P.

5emeLobatchevski.jpg

De la même façon, on suppose ici quelque chose sur ce qui se passe à l’infini, qu’on ne peut pas infirmer en pratique.

Prendre une de ces deux phrases 5 bis ou 5 ter comme hypothèse de départ, au lieu de l’axiome original d’Euclide, donne de nouvelles géométries. Les règles sont différentes, le théorème de Pythagore n’est plus vrai, la somme des angles d’un triangle ne fait plus 180°, mais il y a d’autres formules, et ces géométries sont cohérentes.

Dans ces deux cas, Riemann et Lobatchevski réussirent à montrer qu’il n’existait pas plus de contradiction dans leurs nouveaux systèmes (ou le 5ème axiome d’Euclide est remplacé par son contraire) que dans le système classique d’Euclide.

A noter qu’on ne sait pas si la géométrie d’Euclide est elle-même cohérente. Il s’agit d’un résultat relatif.

Incomplétude et indécidabilité

Les théorèmes de Gödel

Résumons-nous : il y a plusieurs théories possibles, toutes aussi logiques, mais réellement différentes, par leurs principes de base notamment. Dans ces conditions, quel sens donner à la vérité du 5ème axiome d’Euclide ?

Ici clairement, vrai ou faux dépend d’un point de vue, et un vrai choix est possible.

Le 5ème axiome est dit indécidable à partir des autres axiomes, on ne peut ni le montrer, ni montrer son contraire. On peut le supposer vrai ou faux, et obtenir, choisir ainsi deux mondes différents, tout aussi réels mathématiquement. Selon Albert Jacquard [4], "le concept d'indécidabilité est scandaleusement ignoré de la quasi-totalité des étudiants".

Et si l’on refuse de trancher, la géométrie est incomplète : on ne peut plus démontrer le théorème de Pythagore ou son équivalent non-euclidien.

La section précédente nous a montré au moins un exemple de théorie incomplète, à cause d’une phrase indécidable. Le théorème de Gödel montre que c’est la situation générale, toutes les théories sont dans ce cas.

A la fin du XIXème siècle, David Hilbert espérait qu’on sortirait de la célèbre et historique « crise des fondements des mathématiques » en prouvant définitivement la cohérence des mathématiques.

Kurt Gödel réduisit cet espoir à néant en 1932.

Premier théorème d'incomplétude de Gödel

Une théorie mathématique suffisamment riche4 est nécessairement

  • soit incohérente, ce qui signifie qu'il existe des propositions à la fois vraies et fausses (prouvables et réfutables)
  • soit incomplète, ce qui signifie qu'il existe des propositions indécidables, qu'on ne peut ni prouver, ni réfuter.

Notre foi en la cohérence des mathématiques est telle qu'on l'exprime souvent sous la forme :

Une théorie mathématique cohérente et suffisamment riche est nécessairement incomplète.

ou bien

Dans toute théorie mathématique cohérente et suffisamment riche, il existe des propositions indécidables, qu'on ne peut ni prouver ni réfuter.

En termes de complexité [3], une conséquence importante est la suivante. Lorsqu’on identifie une assertion indécidable, on peut toujours l’ajouter aux axiomes de la théorie (ou ajouter son contraire), mais le premier théorème de Gödel dit qu’il n’y a aucun espoir d’obtenir une théorie complète. Il restera toujours d’autres assertions indécidables.

Une théorie cohérente et suffisamment riche a donc une base infinie d’axiomes.

Il est par exemple impossible, à partir d’un nombre fini d’axiomes, de décrire tout ce qui est vrai sur les nombres entiers. Il faudrait une infinité d’axiomes, chacun indépendant des autres.

En termes de vérité, on énonce parfois le premier théorème de Gödel sous la forme :

L'ensemble des assertions vraies est strictement plus grand que l'ensemble des assertions démontrables.

En fait, il existe des assertions vraies, pour lesquelles il n’y a pas de démonstration (on ne peut arriver à la solution en un nombre fini d’étapes). Autrement dit, la démonstration des assertions indécidables demanderait une infinité d’étapes. Et sans même aller jusqu’à l’indécidable, on peut imaginer facilement des problèmes dont la complexité dépasse l’échelle humaine. Le premier théorème de Gödel dit qu’il n’y a pas de limite à cette complexité, elle peut croître au-delà de toute borne.

Second théorème d'incomplétude de Gödel

La cohérence d'une théorie mathématique suffisamment riche est indécidable (à l'intérieur de cette théorie).

C'est à dire, à partir d'une théorie T (de son langage, ses axiomes et ses règles), on ne peut ni prouver ni réfuter la proposition "La théorie T est cohérente".

La prouesse de Gödel est d'arriver à exprimer la cohérence d'une théorie à partir du langage de cette même théorie.

Le second théorème est plus fort que le premier : parmi les phrases indécidables dont le premier théorème énonce seulement l’existence, le second théorème exhibe une phrase indécidable très particulière (le second implique le premier).

En quelque sorte, ce second théorème dit qu’une théorie ne peut pas se prouver elle-même. On sent bien que c’est une histoire de serpent-qui-se-mord-la-queue. Il faut toujours un point de départ extérieur, la vérité mathématique ne peut qu’être relative.

C’est ce résultat qui a ruiné l’espoir de David Hilbert. Les mathématiciens, comme les autres scientifiques, sont condamnés à remettre sans cesse en cause les fondements de leur édifice intellectuel. Dans le même ordre idée, Bertrand Russell disait que ce qui fait le caractère scientifique d’une théorie n’est pas sa prouvabilité, mais sa réfutabilité. Le mieux que l’on puisse espérer est de constater qu’une théorie n’est pas réfutée par de nombreuses expériences.

Mais il n’y a pas lieu d’être triste, car ce théorème montre aussi que la création d’une théorie complète est toujours une quête sans fin. Le monde serait beaucoup plus ennuyeux si ce n’était pas le cas.

Références
1. Ethique à Nicomaque, Aristote (vers 340 avant J.-C.)
2. Les éléments, Euclide (vers 300 avant J.-C.)
3. Hasard et chaos, David Ruelle (1991), Odile Jacob
4. L'équation du nénuphar, Albert Jacquard (1998), Calmann-Lévy
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License