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 ?

Pour 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

Nous 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 la conjecture de Syracuse) : il est indécidable dans l’arithmétique de Peano, mais heureusement démontrable dans la théorie ZFC.

Un exemple plus sophistiqué, c’est le problème de Whitehead : c’est un énoncé de théorie des groupes pas trop difficile à comprendre (après le bac quand même), et pourtant indécidable même dans ZFC ! De même, un des exemples les plus connus est l’hypothèse du continu : existe-t-il un ensemble de nombres qui soit « plus grand » que N mais « plus petit » que R ? C’est indécidable !

Enfin, si on utilise la théorie des ensembles de Zermelo-Frenkel au sens strict (notée ZF), alors il existe un énoncé indécidable qu’on appelle l’axiome du choix. On choisit en général de l’ajouter à la liste des axiomes de ZF, pour obtenir la théorie ZFC.

Autre point pour ceux qui veulent creuser : Gödel a démontré un deuxième théorème d’incomplétude ! Le premier théorème dit que tout système est soit incomplet, soit inconsistant. L’incomplétude est un problème, mais l’inconsistance est une catastrophe ! On aimerait donc pouvoir s’assurer qu’un système donné est incomplet plutôt qu’inconsistant. Ce que dit le deuxième théorème, c’est qu’on ne peut pas démontrer la consistance d’un système formel en restant à l’intérieur de celui-ci.

Il y a quelque chose qui m’a longtemps troublé avec cette idée de propositions indécidables. Si on obtient une proposition vraie mais indécidable, alors on peut décider de l’ajouter comme axiome. Rien de bien troublant. Mais on peut aussi très bien décider d’ajouter son contraire à notre liste d’axiomes. Puisque la proposition est indécidable, on ne crée pas d’inconsistance. Mais qu’est-ce qu’on obtient si on fait ça ? Un système d’axiomes dont un axiome est une proposition « fausse ». N’est-ce pas paradoxal ?

Pour résoudre la difficulté, il faut creuser la notion de « vrai ». J’ai insisté sur le fait que la notion de « démontrable » était relative à un système d’axiomes. Par contre je suis passé vite sur la notion de « vrai », comme si elle était universelle et intrinsèque. En fait elle ne l’est pas, elle est relative à ce qu’on appelle un « modèle ». Pour l’arithmétique, il n’y a pas trop de débat sur quel est le modèle. Mais par exemple pour la géométrie, il y a plusieurs choix ! Le modèle classique est celui de la géométrie euclidienne. Pour trouver un système d’axiomes qui colle avec ce modèle, il faut prendre le 5ème axiome d’Euclide dans sa forme familière (une seule parallèle à une droite passe par un point donné). Mais si vous changez de modèle, par exemple la géométrie riemannienne, il vous faut un autre système d’axiomes qui va bien, et que l’on peut obtenir en modifiant le 5ème axiome (aucune parallèle ne passe par un point donné).

Donc si on choisit d’ajouter aux axiomes de Peano une proposition indécidable fausse, on obtient un système d’axiomes qui ne représente plus correctement l’arithmétique. Si j’ai bien compris, on peut considérer à la place des modèles d’arithmétique « non-standard », mais dont j’imagine que l’intérêt est limité (contrairement à la géométrie, où les modèles non-euclidiens ont un intérêt physique).

Mais pour les mathématiques de la théorie des ensemble, quel est le modèle raisonnable qui nous dit ce qui est vrai et ce qui est faux ? Une solution serait le modèle de l’Univers Constructible de Gödel, dans lequel l’axiome du choix (comme l’hypothèse du continu) sont « vrais » … mais je ne suis pas sûr de comprendre pourquoi !

Si vous êtes très malin, vous avez peut être eu l’idée de trouver un contre-exemple au théorème de Gödel et de construire un système d’axiomes parfait de la manière suivante : prendre toutes les propositions vraies, et les déclarer toutes « axiomes ». Même si ça n’est pas très intéressant en pratique, ça semble échapper à Gödel. La raison en est que Gödel suppose un système d’axiomes « récursivement énumérable »  récursif. Cela signifie que les axiomes ont le droit d’être en nombre infini, mais il doit exister une procédure « finie » pour décider si une proposition donnée fait partie des axiomes ou non. Un système d’axiomes qui ne soit pas récursif n’a aucun intérêt pratique, puisqu’on ne peut jamais vérifier en temps fini si quelque chose est un axiome !

Enfin dernier point, les conséquences informatiques du théorème de Gödel sont souvent discutées (voire on trouve parfois le théorème énoncé sous cette forme) : la première conséquence, c’est qu’il n’existe pas de programme qui puisse dire si une proposition donnée est un théorème ou non. Une autre conséquence reliée, c’est qu’il n’existe pas de programme qui puisse dire avec certitude si un autre programme va terminer en temps fini, ou non (voir ici).

Bon j’ai largement dépassé 2000 mots, j’arrête. Vous pouvez reprendre vos activités normales !