Le théorème de Gödel


Biographie de K. Gödel

Énoncé simplifié du théorème d'incomplétude :
Dans toute branche des mathématiques suffisamment complexe (par exemple l'arithmétique), il existe une infinité de faits vrais qu'il est impossible de prouver en utilisant la branche des mathématiques en question. Bien évidement le théorème tel qu'il a été écrit par Gödel est plus précis, de même que la preuve qu'il en a donné. L'idée de cette preuve est néanmoins accessible, et nous en donnons plus loin une esquisse.

Qu'a fait Gödel avec son théorème ?
Jusqu'au début du siècle les mathématiciens étaient persuadés qu'on pouvait, un peu à la manière des écoliers en géométrie, démontrer toutes les vérités mathématiques par déduction.

Gödel a démontré en 1931 deux résultats mathématiques :
=> Il se peut que dans certains cas, on puisse démontrer une chose et son contraire (inconsistance).
=> Il existe des vérités mathématiques qu'il est impossible de démontrer (incomplétude)
Le plus célèbre de ces résultats est le second, qu'on appelle théorème d'incomplétude de Gödel.

Quelques définitions
Système formel
Preuve
Machine de Turing
Programme informatique
(voir le glossaire en bas de la page)

Une preuve simplifiée du théorème
Malgré les performances et la diversité des ordinateurs actuels, tous ont un modèle théorique commun appelé machine de Turing. On peut donner à une machine de Turing un programme arbitrairement long, mais évidemment de taille finie, qui répond VRAI ou FAUX à une affirmation qu'on lui donne, sans jamais se tromper.
La question est:
Si un humain est capable de savoir si la phrase qu'il donne à la machine est vraie ou fausse, la machine est-elle aussi capable de découvrir la vérité ?

Gödel donne alors la phrase suivante à la machine:
"La machine ne répondra jamais VRAI à cette phrase"

Que fait la machine ?

Si elle répond VRAI, elle affirme que "La machine ne répondra jamais VRAI à cette phrase" est une affirmation vraie. Or ce n'est pas le cas, puisqu'elle vient justement de répondre VRAI à la phrase. Si la machine ne se trompe pas, elle ne peut donc pas répondre VRAI.

Si elle répond FAUX, elle affirme que "La machine ne répondra jamais VRAI à cette phrase" est une affirmation fausse. Or l'affirmation n'est pas fausse puisque la machine vient justement de répondre FAUX. Si la machine ne se trompe pas, elle ne peut donc pas répondre FAUX.

Et nous, pouvons nous répondre à la question ?...
La phrase dit : "La machine ne répondra jamais VRAI à cette phrase". Nous venons de voir qu'en effet, la machine ne peut pas répondre VRAI. Nous savons donc que cette phrase est une vérité. Pourtant la machine ne pourra pas la découvrir...

Voyons le théorème d'un peu plus près :

La géométrie d'Euclide
Tous les écoliers le savent, la géométrie est une discipline déductive. Elle se différencie en cela des sciences physiques, par exemple, qui sont une science en partie expérimentale car on peut vérifier la véracité de ce que l'on affirme par l'expérience.

D'aucun répondront qu'on peut faire de même en géométrie : mesurer un angle, les côtés d'un triangle...Eh bien, oui et non... Ce qui a fait le succès de la géométrie et le malheur de nombreux écoliers depuis les Grecs c'est la méthode axiomatique utilisée par Euclide, qui permet de démontrer en géométrie des théorèmes en utilisant uniquement la logique de l'esprit et des axiomes de base (axiomes d'Euclide par exemple) comme le fameux :

"Par deux points, on ne mène qu'une droite"

Ce type de démonstration se passe de vérification par l'expérience. Le côté évidement vrai des axiomes et la logique normalement implacable de la déduction font que le résultat obtenu ne peut être que vrai, ce qui a fait de la géométrie Euclidienne un modèle de connaissance scientifique pendant 2000 ans.

On pensait encore, il y a 200 ans, que toutes les branches des mathématiques, à l'instar de la géométrie, pouvaient être axiomatisées et qu'on pouvait déduire logiquement de ces axiomes toutes les vérités concernant la discipline en question.

Mais au 19ème siècle, certains scientifiques ont remplacé un des axiomes d'Euclide :

"par un point donné, on fait passer exactement une parallèle à une droite donnée"

par un autre énoncé, comme par exemple celui de Riemann :

"par un point hors d'une droite, on ne peut faire passer aucune parallèle à cette droite"

En utilisant le nouveau jeu d'axiomes comme vérités de base, on peut déduire, comme en géométrie Euclidienne, des théorèmes, dont certains seront faux dans notre monde, puisqu'ils sont déduis d'un axiome faux dans notre monde (ce qui n'exclu pas qu'ils soient justes dans un monde imaginaire dans lequel les axiomes seraient vrais).

Ce phénomène a fait prendre conscience aux mathématiciens que la géométrie était une chose "palpable", dont les affirmations, énoncés et théorèmes n'étaient pas vides de sens, et que ce sens "intuitif" pouvait les gêner dans leur tâche qui consiste à déduire une chose de certaines autres, sans forcément se soucier de la véracité des faits démontrés.
Or on sait qu'il faut se méfier de l'intuition et du « C'est clair ! » des profs de maths, comme le montre l'exemple suivant dû à Russel :

Il y a deux sortes d'ensembles, les ensembles normaux, qui ne se contiennent pas eux même, comme l'ensemble des mots de ce texte, et les ensembles non-normaux, qui se contiennent eux même, comme l'ensemble des choses dont on parle dans ce texte (en effet, je viens d'en parler). Considérons à présent N, l'ensemble des ensembles normaux. La question est : N est-il normal ?
=> Si N est normal, alors, il est dans N puisque N est l'ensemble des ensembles normaux. N se contient donc lui-même et par conséquent N est non-normal.
=> Au contraire, si N est non-normal, alors il se contient lui-même, or les éléments de N sont les ensembles normaux, donc N est normal.

Où est passée l'intuition...?

La tentative de Hilbert
Afin de trouver une solution à un certain nombre de ces problèmes, Hilbert a proposé au début du siècle un programme de recherche visant entre autres à formaliser les mathématiques, c'est à dire à définir les termes utilisés de façon non ambigu et sans faire appel à l'intuition.

Un des buts de Hilbert était d'obtenir des théories formelles en mathématiques, c'est à dire :

=> un ensemble de règles pour écrire les formules
=> un ensemble d'axiomes (formules de base qui représentent ce qu'on juge vrai) écrits dans le système formel
=> un ensemble de règles de transformation qui permettent de passer d'une formule à une autre, c'est à dire de déduire d'un axiome ou d'un théorème, un nouveau théorème

Les règles doivent être suffisamment précises pour être applicables mécaniquement, par une machine par exemple, sans faire appel à l'intelligence.
On pourrait ainsi programmer un ordinateur en lui donnant les règles et les axiomes, puis en lui demandant d'appliquer successivement toutes les règles à tous les axiomes, dans un processus éventuellement infini. L'ordinateur serait alors capable de lister tout ce qu'on peut déduire des axiomes, c'est à dire tous les théorèmes possibles de la théorie formelle.
Imaginons à présent que nous voulions savoir si une certaine formule F est un théorème, c'est à dire si elle peut être déduite des axiomes en utilisant une suite de déductions. Quatre cas peuvent se présenter si nous utilisons l'ordinateur en question :

1. Il listera la formule F , et pas la formule non F
2. Il listera la formule non F , et pas la formule F
3. Il listera la formule F et la formule non F
4. Il ne listera ni la formule F , ni la formule non F

Dans le cas 1, cela signifie que la formule F est un théorème. Dans le cas 2, que la formule non F est un théorème. Que dire des autres cas ? Dans le cas 3, on dit que la théorie est inconsistante, c'est à dire qu'on peut à la fois prouver une chose et son contraire. Dans le quatrième cas, on dit que la théorie est incomplète, c'est à dire qu'il existe des choses dont on ne peut savoir si elles sont vraies ou non.

Un exemple concret de système formel, avec redéfinition des termes consistance et complétude est accessible ici.

La deuxième partie du programme de Hilbert consistait justement à démontrer que les théories formelles des mathématiques étaient consistantes.

Si beaucoup de travail a été réalisé en ce qui concerne la formalisation des mathématiques (des théories formelles pour de nombreuses branches des mathématiques ont été développées à partir du 19ème siècle, avant même le programme de Hilbert), il a fallu attendre les résultats de Gödel, assez inattendus, pour répondre entre autres à la deuxième partie du programme.

La réponse de Gödel
En 1931, dans un article intitulé "Über formal unentscheidbare Sâtze der Principia Mathematica und verwandter Systeme" (Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés) Gödel a démontré qu'il était impossible de prouver la consistance d'un certain nombre de théories formelles (dont l'arithmétique) en utilisant ces théories, contrairement à ce que semblait croire Hilbert. Ce premier résultat, très inattendu pour l'époque s'est accompagné d'un deuxième, plus célèbre, le théorème d'incomplétude qui énonce que la plupart des théories formelles (dont l'arithmétique), si elles sont consistantes, sont incomplètes, c'est à dire qu'il existe des résultats effectivement vrais qui ne peuvent pas être prouvés dans cette théorie.

Pour en revenir à notre ordinateur qui déduit des théorèmes, les résultats de Gödel prouvent que pour la plupart des théories formelles, il existe des formules F pour lesquelles l'ordinateur sera confronté au 3ème ou au 4ème cas.

Très basiquement, la démonstration de Gödel a consisté à écrire le paradoxe du menteur (Tous les crétois sont des menteurs, c'est un crétois qui le dit...) en utilisant l'arithmétique. Plus précisément, il a construit une formule de l'arithmétique qui affirme d'elle même qu'elle est indémontrable.

Le système formel qu'a utilisé Gödel pour sa démonstration est voisin de celui des Principia Mathematica de Whitehead et Russell. Ce système formel permet d'exprimer les relations arithmétiques courantes.
Nous ne referons pas bien sûr dans la suite la démonstration complète de Gödel qui est longue et difficile, mais nous essaierons d'en indiquer clairement les étapes.

La numération de Gödel et les métamathématiques
La première étape a consisté à assigner à chaque symbole du sytème formel un nombre différent. Puis Gödel a trouvé le moyen d'affecter un nombre à chaque formule (en faisant le produit des premiers nombres premiers élevés à la puissance du nombre représentant les symboles qui y figurent), puis à chaque suite de formule.
L'important est de comprendre qu'un nombre de Gödel étant donné, on peut déterminer si c'est une suite de formules (et si oui de quelles formules elle est composée), une formule (et si oui laquelle) ou un symbole.
Inversement, étant donné un symbole, une formule ou une suite de formules, on peut facilement calculer le nombre de Gödel associé.

Tous ces nombre qui représentent des formules ou des suites de formules représentent donc des faits de l'arithmétique, mais nous pouvons aussi nous intéresser à la méta-arithmétique, qui consiste à parler des faits qui concernent l'arithmétique. Par exemple, dire que

"Pour tout x, il existe y tel que y > 2x"

est un fait arithmétique, c'est à dire un fait qui concerne les nombres entiers. D'un autre côté, dire que

La formule "Pour tout x, il existe y tel que y > 2x" est démontrable en arithmétique

est un fait meta-arithmétiquen, c'est à dire un fait qui concerne l'arithmétique.

Les formules et suites de formules étant représentés par Gödel sous forme de nombres, celui-ci a ainsi pu exprimer des faits méta-arithmétiques par des formules arithmétiques... Par exemple, dire qu'une formule de nombre de Gödel g1 contient la formule de nombre de Gödel g2 revient plus ou moins, avec la méthode de Gödel à affirmer que g2 est un diviseur de g1, ce qui une propriété arithmétique, exprimant un fait méta-arithmétique.
Gödel a ainsi réussi à exprimer, en utilisant les nombres de Gödel et l'arithmétique (mais la formule reste assez complexe) que :

La formule de nombre de Gödel g1 est démontrable par la suite de formules de nombre de Gödel g2.

Dans la suite, nous appellerons cette formule G.

La preuve d'incomplétude
La suite du raisonnement a été de montrer que si G était était démontrable, alors la négation de G le serait aussi, et inversement. On aurait alors la possibilité de démontrer une formule et son constraire, ce qui est la définition de l'inconsistance vue plus haut. Par conséquent, si on suppose que le système formel employé est consistant (i.e. que l'arithmétique est consistante), alors on ne peut pas démontrer la formule G ni son contraire. On dit que G est indécidable. Or, la formule G dit que la formule G est indémontrable (rappellons la formule)

n : Il n'existe aucun nombre de Gödel qui représente une suite de formule qui soit la démonstration de la formule portant le nombre de Gödel n

Cette affirmation métamathématique (disant que G est indémontrable) est manifestement vraie, comme nous venons de le voir. Et elle est representée par une formule arithmétique, selon la methode de Gödel, qui est donc vraie elle aussi...

Gödel a donc au final construit une fomule arithmétique qui est vraie, et qu'on ne peut pas démontrer en utilisant un système formel de l'arithmétique si celui-ci est consistant.

En allant un peu plus loin, Gödel a montré que même en posant comme axiome que G soit vraie, on pourrait toujours trouver une formule vraie et indémontrable, ce qui signifie que si l'arithmétique est consistante, non seulement elle est incomplète, mais le sera toujours même si on y ajoute des axiomes supplémentaires.

Inconsistance de l'arithmétique ?
Par un raisonnement un peu similaire, Gödel a construit une formule, exprimée dans le système formel qui affirme que :

Si l'arithmétique est consistante, alors la fomule G est vraie.

Puis il démontre cette affirmation, toujours en utilisant le système formel. Ceci implique que si on pouvait démontrer dans le système formel, que l'arithmétique est consistante, alors, en utilisant la preuve donnnée par Gödel, il s'en suivrait que G serait démontrable dans le système formel. Or nous venons de voir que ce n'était pas le cas. Par conséquent, c'est qu'il est impossible de démontrer dans le système formel que l'arithmétique est consistante, ce qui a apporté une réponse au problème de Hilbert...

Les conséquences du théorème

Les deux théorèmes de 1931 de Gödel sur l'inconsistance et l'incomplétude de l'arihtmétique du premier ordre ont eu des répercussions importantes sur la pensée philiosophique moderne.

La première conséquence de ces théorèmes est que la Vérité ne peut pas être exprimée en terme de démonstrabilité. Une chose prouvable n'est pas nécéssairement vraie et une chose vraie n'est pas toujours prouvable. Beaucoup de philisophes ont pensé le contraire et ont essayé de définir la vérité comme étant égale aux choses démontrables. De manière générale, dans quasiment toutes les entreprises intellectuelles conséquentes, on peut exprimer des arguments mathématiques simples et on risque donc de rentrer dans le cadre du théorème de Gödel. Je peux ainsi prétendre des choses fausses sans qu'on ne puisse démontrer le contraire.

De la même manière, je peux prétendre des choses vraies sans pouvoir me justifier par une démonstration De la même manière que l'ensemble des vérités est plus important que l'ensemble de ce qui est démontrable, la réalité est plus importante que l'ensemble des connaissances possibles. Contrairement aux enseignements de nombreux philosophes, être raisonné n'est pas simplement une question de règles. La raison est créative et originale. Pour trouver des vérités dans un système donné, il faut pouvoir s'en extraire et pour cela il faut une raison qui soit capable non pas de simplement rajouter des axiomes à un système mais d'en créer un nouveau dans lequel l'ancienne vérité indémontrable deviendra au contraire tout à fait démontrable.

Glossaire:

Système Formel
Un système formel est composé d'une part de conventions qui permettent d'écrire des formules (liste des caractères utilisables et façon de les agencer) et d'autre part de règles de transformation, ou règles d'inférence, qui permettent de transformer une formule en une autre.

Axiome
Dans une théorie, un axiome est une formule de base, que l'on considère vraie sans démonstration. C'est en quelque sorte le "point de départ" qui servira à démontrer des théorèmes.

Théorème
Dans le cadre d'une théorie, un théorème est une formule que l'on peut démontrer comme étant vraie, en partant des axiomes et en procédant par déduction.

Preuve, démonstration
C'est la liste des étapes, non ambiguës (en utilisant les règles d'inférences si on travaille dans un système formel), qui permettent de passer d'une formule supposée vraie à une autre. On obtient alors la preuve que la formule obtenue est vraie.

Méthode axiomatique
Initialement utilisée par Euclide en géométrie, la méthode axiomatique consiste à accepter sans démonstration un petit nombre de vérités (les axiomes) et à les utiliser pour en déduire d'autres choses vraies (théorèmes)

Théorie formelle
Une théorie formelle est composée d'un système formel et d'un ensemble d'axiomes, exprimés dans ce système formel.

Règle d'inférence, règle de transformation
Dans le cadre d'un système formel, les règles d'inférences sont des règles précises, applicables mécaniquement, qui permettent de transformer une formule en une autre, c'est à dire de déduire d'une formule une autre formule.

Consistance
Une théorie formelle est consistante si elle n'admet aucune formule F telle que F et son contraire (non F) puissent être démontrés.

Complétude
Une théorie formelle est complète si il n'existe pas de formule F telle que ni F ni son contraire (non F) ne puissent être démontrés, c'est à dire si tout ce qui est vrai dans la théorie est démontrable dans la théorie.

Machine de Turing
La machine de Turing est le modèle théorique de tous les ordinateurs actuels, et reste particulièrement simple, même si nous ne pouvons pas la détailler ici en quelques lignes.

Programme informatique
Un programme informatique est une suite d'ordres non ambigus qui sont exécutables par une machine de Turing, mais aussi par un être humain, et qui ne laisse aucune part à la réflexion. L'utilisation d'un ordinateur se justifie uniquement par la rapidité d'exécution de ces ordres.