C’est en cours de philo que j’en ai entendu parler pour la première fois ! Notre prof nous faisait un cours sur la logique et ses fondements, et c’est alors qu’elle le mentionna : le fameux théorème de Gödel, celui qui prouve que quoi qu’on fasse, il existe des énoncés mathématiques vrais, mais indémontrables. Les mathématiques resteront à tout jamais un édifice imparfait !

J’en fus évidemment tout retourné et fasciné : comment était-il possible qu’un truc pareil existe ? Comment prouver ce résultat pouvait même être du domaine de la science ?

Peut-on tout démontrer en mathématiques ?

Quand on fait des mathématiques, on manipule des énoncés. Un énoncé est une suite de symboles ou une phrase ayant un sens mathématique précis. Par exemple 2 + 2 = 4 ou « Il existe une infinité de nombres premiers » sont des énoncés mathématiques. Un énoncé mathématique est soit vrai, soit faux : par exemple 2 + 2 = 5 est un énoncé faux.

Quand on considère un énoncé mathématique, on ne sait pas forcément à l’avance s’il est vrai ou faux. Le travail du mathématicien, c’est justement d’essayer de savoir lesquels sont vrais et lesquels sont faux. Et pour cela, il utilise un outil : il fait des démonstrations.

Si un mathématicien arrive à démontrer un énoncé, on considère que cet énoncé est « vrai ». S’il démontre le contraire, alors on dit que l’énoncé est faux.

Les mathématiques reposent donc sur l’idée que si un énoncé est vrai, alors il doit en exister une démonstration, et il n’y a plus qu’à la trouver. Mais est-on sûr que tout ce qui est « vrai » est forcément « démontrable » ? Se pourrait-il qu’il existe des choses vraies mais indémontrable ?

Notez bien que s’il existe des choses vraies mais indémontrables, c’est un camouflet pour les mathématiciens, car cela signifie qu’il y a des questions mathématiques auxquelles ils ne peuvent pas répondre ! Pour couper court à cette inquiétude, au début du XXème siècle, quelques matheux et logiciens menés par David Hilbert ont voulu asseoir les maths sur des bases inattaquables. Ils ont donc cherché à montrer que si une affirmation mathématique est vraie, alors il en existe nécessairement une démonstration.

Malheureusement pour eux, en 1931, le jeune logicien tchèque Kurt Gödel a douché leurs espoirs avec un résultat aussi diabolique qu’inattendu : en mathématique, il existera toujours des énoncés vrais, et pourtant indémontrables. Même sur leur propre terrain de jeu, les maths ne sont donc pas toutes puissantes !

Mais pour comprendre exactement de quoi il retourne, il nous faut creuser un peu la notion de « démontrable ».

A quoi jouent les mathématiciens ?

axiomes et théorèmesPour démontrer des choses, les matheux utilisent ce qu’on appelle la méthode axiomatique. Ils se donnent certaines affirmations comme ingrédients de départ : ce sont les axiomes. Puis ils cherchent à les combiner selon les règles de la logique pour essayer d’aboutir à de nouvelles affirmations. Une affirmation déduite des axiomes est considérée comme « démontrée » (on peut alors la qualifier de théorème).

Pour illustrer le principe de la méthode axiomatique, on peut utiliser une analogie avec un échafaudage. Les axiomes, ce sont les bases de notre échafaudage, et les règles de la logique nous permettent de monter une structure qui repose sur ces axiomes. Chaque fenêtre à laquelle on accède grâce à notre échafaudage est une affirmation démontrée qui devient un théorème.

Toutes les mathématiques se font au moyen de la méthode axiomatique, mais il existe plusieurs choix possibles pour les axiomes. Si vous voulez faire de la géométrie dans le plan, vous allez partir des axiomes d’Euclide. Si vous avez envie de considérer uniquement les nombres entiers, vous pouvez vous tourner vers les axiomes de l’arithmétique de Peano. Pour vous faire une idée de ce à quoi ça ressemble, voici quelques uns de ces axiomes :

  • 0 est un nombre
  • Tout nombre possède un suivant
  • 0 n’est le suivant d’aucun nombre
  • Si x=y et y=z, alors x=z
  • etc.

Enfin si vous voulez faire des maths plus subtiles, vous devez utiliser un système d’axiomes plus travaillé. Aujourd’hui, LE système d’axiomes sur lequel reposent toutes les mathématiques modernes, c’est celui de la théorie des ensembles de Zermelo-Frenkel (noté ZFC pour les intimes). Ça veut dire que si de nos jours un mathématicien dit « J’ai démontré ceci », alors c’est sous-entendu « en utilisant les axiomes de ZFC ».

Ce que dit le théorème de Gödel

Godel_EinsteinNous avons vu que la notion de « démontrabilité » est toujours relative à un système d’axiomes. Cela veut dire qu’une certaine affirmation mathématique peut très bien être démontrable avec un système, mais pas avec un autre ! Ce dont ont voulu s’assurer Hilbert et sa bande au début du XXème siècle, c’est qu’il était possible de construire un système d’axiomes parfait, tel que toutes les propositions mathématiques vraies y soient démontrables. Un tel système serait dit « complet ».

Et c’est précisément cet espoir que Gödel a ruiné : il a démontré que dès que l’on veut faire au minimum de l’arithmétique des nombres entiers, quel que soit le système d’axiomes qu’on utilise, il existera toujours des énoncés vrais mais indémontrables. On dit que ces énoncés sont indécidables.

Cela signifie qu’il n’existe pas de système d’axiomes complet, et c’est pour cela que l’on appelle ce théorème, le théorème d’incomplétude.

Pour reprendre l’analogie avec l’échafaudage, on peut y mettre autant de piliers qu’on veut, il existera toujours des fenêtres de l’immeuble qu’on ne pourra pas atteindre !

Les implications pratiques du théorème de Gödel

En théorie, le théorème de Gödel est une catastrophe. Il nous dit que, aussi sophistiqués et nombreux que soient nos axiomes de départ, on va se retrouver avec des énoncés indécidables. Cela veut dire qu’il y a peut être des milliers de mathématiciens en train de passer leurs journées à chercher des démonstrations … de choses indémontrables !

Heureusement, en pratique, presque tout le monde se fiche du théorème de Gödel. En effet on s’est rendu compte que malgré tout, les propositions indécidables sont tellement tordues qu’on ne les croise pour ainsi dire jamais, et donc la quasi-totalité des propositions vraies « normales » sont démontrables avec les systèmes d’axiomes qu’on utilise. On est donc convaincus que l’on dispose de suffisamment de bon piliers à notre échafaudage pour atteindre toutes les fenêtres intéressantes.

Ainsi si aujourd’hui un mathématicien lambda cherche à faire une démonstration, sa principale crainte sera de ne pas être assez fort pour la trouver. Mais presque à aucun moment il n’envisage sérieusement que cette proposition soit « indémontrable ».  Les conséquences pratiques du théorème de Gödel sont donc très limitées.

Une saveur de la démonstration

Je ne voudrais pas passer trop de temps à parler de la démonstration proprement dite. D’une part on la trouve décrite un peu partout  d’autre part je trouve que c’est ce qui obscurcit souvent les présentations vulgarisées du théorème. Ceux qui ont mal à la tête peuvent arrêter là ! (N’oubliez pas que Gödel est mort fou, tout comme d’autres logiciens ayant traité des questions similaires comme Cantor, Zermelo, Post, Frege, Wittgenstein…enfin d’après Logicomix)

Pour démontrer son diabolique théorème, Gödel fait essentiellement une preuve « constructive » : il donne une recette pour fabriquer plus ou moins explicitement un énoncé arithmétique indécidable, et ce quel que soit le système d’axiomes de départ. Pour se faire une idée de ce dont il s’agit, Gödel mime en quelque sorte le paradoxe du menteur.

Vous connaissez certainement ce paradoxe, c’est celui d’un Crétois qui affirme « Tous les Crétois sont des menteurs ». Mais alors, lui-même dit-il la vérité à ce moment précis ? Une variante encore plus compacte de ce paradoxe, c’est l’énoncé « Cette phrase est fausse ». Alors, est-elle fausse…ou vraie ?

Le principe de la démonstration de Gödel, c’est de construire un énoncé qui dit « Je ne suis pas démontrable ». Vous voyez que si cet énoncé est vrai, alors…il n’est pas démontrable. Il est donc bien « indécidable » et le système d’axiomes est bien « incomplet ». En revanche si cet énoncé est faux, alors il est démontrable, et là c’est la catastrophe : on a un système d’axiomes qui démontre des choses fausses ! On dit que le système est inconsistant. D’ailleurs pour être précis, ce qu’a démontré Gödel, c’est qu’un système d’axiomes (contenant au moins l’arithmétique) est soit incomplet, soit inconsistant. Pas d’autre alternative.

Dans le détail, la démo repose sur une idée conceptuelle géniale, et sur une astuce diabolique.

L’idée conceptuelle géniale, c’est celle de la réflexion arithmétique des propositions méta-arithmétiques. Qu’est-ce que ça veut dire ? Si je dit « 2 + 2 = 4 », je fait un énoncé arithmétique. Si je dis « 2 + 2 = 4 est démontrable à partir des axiomes de Peano », je fais un énoncé « méta-arithmétique ». L’idée géniale de Gödel, c’est d’arriver à lier les deux. En gros il a montré que :

Pour tout énoncé E, il existe un autre énoncé S(E) tel que : E est démontrable si et seulement si S(E) est vrai.

Ce travail se fait au moyen d’une méthode de codage qui permet de transformer tout énoncé en un nombre entier et toute démonstration en une suite de nombres entiers. La démontrabilité de E se traduit donc comme une propriété arithmétique sur des suites de nombres, c’est l’énoncé S(E). Ensuite l’astuce diabolique, c’est ensuite de trouver UN énoncé particulier, noté G, tel que « S(G) = non-G ». En appliquant le résultat précédent pour cet énoncé particulier G, on obtient alors l’affirmation

G est démontrable si et seulement si G est faux.

Donc soit G est vrai et il est donc indémontrable (et on a l’incomplétude), soit il est faux et démontrable (et on a l’inconsistance). Une fois de plus, si vous vous intéressez aux détails de cette démonstration, il faut creuser un peu plus et il y a plusieurs endroits où c’est décrit (par exemple ici).

Pour aller (vraiment) plus loin…

Pour ceux qui ont tenu jusque là et qui se posent quelques questions métaphysiques, voici quelques pistes de réflexion, sur des choses au sujet desquelles je ne suis moi même pas très à l’aise. Commentaires les bienvenus !

Pour commencer, il existe quand même quelques exemples de propositions indécidables et à peu près compréhensibles. Par exemple le théorème de Goodstein, qui concerne des simples suites de nombres (un peu comme