Les théorèmes d’incomplétude de Gödel

 

Dossier de Robin dans l’épisode #92.

Dans ce dossier, en toute humilité : « Qu’est ce qu’une théorie mathématique  », voire « qu’est ce que les mathématiques ?  »

Pour schématiser, on peut dire que les mathématiques ont deux facettes : trouver de nouvelles idées, de nouveaux objets, émettre des conjectures d’une part ; mettre en forme de façon rigoureuse les idées trouvées, démontrer de l’autre. Souvent, des mathématiciens sont plus à l’aise, plus connus pour l’un des deux aspect : On peut prendre pour la première catégorie l’exemple d’Évariste Galois, mathématicien génial mort à 20 ans, qui laissa des feuilles couvertes d’intuitions mathématiques mal rédigées, mal formulées, qui ont mis presque 100 ans à être comprises, mais qui ont révolutionné les mathématiques du XIXe et XXe siècle. Dans la deuxième catégorie, citons par exemple Cauchy, le pape de l’analyse, qui permit enfin à tous les mathématiciens de comprendre pourquoi le calcul intégral, que tout le monde utilisait depuis son invention par Newton et Leibniz, donnait de si bon résultats, et quelles étaient les conditions à respecter pour qu’il fonctionne effectivement.

Bien sûr, tous les mathématiciens font un peu les deux. Et les deux font partie intégrante du travail de tout mathématicien, et de l’avancée des mathématiques.
Pour être un peu plus concret, partons d’un exemple simple, qu’en principe tout le monde connaît, le théorème de Pythagore.

Rappelons son énoncé : dans un triangle ABC rectangle en A, AB2 + AC2 = BC2. Il ne faut pas oublier la deuxième partie tout aussi importante de ce théorème, sa réciproque : si dans un triangle ABC on a cette relation, alors le triangle est rectangle en A.

Avant d’être énoncé sous cette forme, avant même d’envisager le fait que ce soit une relation qui se trouve dans toute une catégorie de triangles, ce théorème a eu une préhistoire. Ainsi, plus de mille ans avant Pythagore, par exemple, les babyloniens avaient établi des listes de “triplets pythagoriciens” (qu’ils n’appelaient bien sûr pas comme ça!), des séries de trois nombres entiers qui peuvent être les trois côtés d’un triangle rectangle car ils vérifient la fameuse relation : par exemple 3, 4, 5, car 32 + 42 = 52, ou encore 5, 12 et 13. On ne sait pas comment ils ont trouvé ces triplets, on ne sait pas pourquoi ils les ont cherchés, mais il est évident qu’ils avaient compris, d’une manière ou d’une autre, quelque chose se rapprochant du fameux théorème.

Autre exemple : de nombreux maçons, encore aujourd’hui, savent utiliser une corde pour fabriquer un angle droit : il suffit de faire 13 noeuds espacés toujours d’une même distance, et de faire un triangle ayant pour côtés 3, 4, et 5 (l’unité étant la distance entre deux noeuds) :

Dans cette situation, il s’agit simplement d’un « truc  » qui a l’air de fonctionner sans que l’on se pose la question de savoir pourquoi ni de savoir si l’angle en question est bien exactement droit ou seulement à peu près.

L’étape suivante, c’est de réaliser que ce résultat est vrai pour tous les triangles rectangles, et que la réciproque est vraie. Ne serait-ce qu’avoir l’idée d’un tel énoncé est déjà assez tordu ! Et enfin la dernière étape pour que ça devienne vraiment des mathématiques, c’est de tenter de trouver une démonstration. On peut pour cela tenter de passer par la géométrie : l’égalité entre les nombres devient une égalité entre des surfaces. BC2 est l’aire du carré dont le côté correspond à l’hypoténuse du triangle, et AB2 AC2 les surfaces de carrés ayant pour côté les deux autres côtés du triangle.

Un dessin ou « puzzle  » de ce genre convaincra alors beaucoup de gens de la validité du théorème :

Il est évident que l’on peut réaliser ces deux dessins avec n’importe quel triangle rectangle (les quatre sont les mêmes). Or, entre les deux dessins, ils ont juste été déplacés dans un même grand carré. Les surfaces grises à gauche et à droite sont donc les mêmes, or à gauche il s’agit de l’hypoténuse du triangle blanc au carré, et à gauche des carrés des deux autres côtés de ce triangle.

Est-ce que ces deux dessins constituent une démonstration ? Attention… Un dessin ne prouve rien, comme on le voit dans cette autre situation :

On a arrangé les mêmes pièces de couleur pour former deux fois un même triangle… Mais en bas, celui ci a un trou ! On vient donc de démontrer qu’un trou de la taille d’un carreau, c’est la même chose que pas de trou du tout, donc 1 = 0 !

Il y a bien sûr une explication: les deux « triangles  » sont en fait des quadrilatères. Ce qui apparaît comme l’hypoténuse est en réalité formé de deux segment de droites, avec un angle légèrement rentrant dans un cas et sortant dans l’autre; c’est à peine visible, mais ça suffit à faire une différence de surface d’un carreau.
Un peu d’attention et de réflexion auraient pu suffire à nous faire voir la supercherie, mais nous voilà mis en garde : il faut se méfier comme la peste de l’intuition, elle peut nous jouer des tours…

Moralité, il faut de la « rigueur  ».

Et tout d’abord, se mettre bien d’accord sur la définition des objets que l’on utilise, tous les mots doivent avoir une signification précise, sur laquelle tout le monde s’accorde. Même les notions les plus simples comme le point, la droite, le cercle doivent être définis le plus précisément possible. Même si la rigueur absolue n’existe malheureusement pas : pour définir un mot, on est obligé d’utiliser des mots, que l’on doit à nouveau définir avec des mots… Il est donc nécessaire de considérer que certains mots de base sont connus de tous.

On rencontre le même problème pour les démonstrations : démontrer, c’est décomposer quelque chose qui n’a pas l’air évident (comme par exemple le théorème de Pythagore) en une succession de petites étapes de raisonnement plus simples. C’est tenter de mettre tout le monde d’accord, comme pour n’importe quelle argumentation, en s’assurant à chaque pas que personne n’a d’objection. Les syllogismes en sont un très bon exemple : si le théorème est « Socrate est mortel  », on peut le démontrer à ceux qui en douteraient en faisant un raisonnement par étape : « Tous les hommes sont mortels  », d’accord ? « Socrate est un homme  » toujours d’accord ? Alors la conclusion s’impose.

Restent deux problème : pourquoi admet-on certaines phrases comme vraies a priori ? (ici « tous les hommes sont mortels  » et « Socrate est un homme  ») Et pourquoi admet on que ces deux phrases impliquent cette conclusion ?

Comme pour les définitions, on est obligé de se mettre d’accord sur un matériel minimum, que tout le monde est prêt à admettre. Un raisonnement rigoureux, par la suite, sera un raisonnement qui se servira des définitions des objets, pour arriver, en partant des vérités admises, les « axiomes  » ou « postulats  », et en suivant des déductions logiques également admises, au résultat souhaité.

LA référence dans le domaine, l’oeuvre la plus ancienne connue qui suit cette démarche à la lettre s’appelle « Les éléments  », et est signée Euclide. Cette œuvre, qui date du troisième siècle avant JC, est restée un modèle jusqu’à aujourd’hui de ce qu’est une théorie mathématique. Elle a été traduite, éditée partout dans le monde (après la bible, c’est le livre le plus édité !)

Le premier de ces livres parle de géométrie, Euclide y pose 5 axiomes propres à ce chapitre :

  1. à partir de deux points, il est possible de tracer un segment.
  2. Il est toujours possible de prolonger un segment en ligne droite autant que l’on veut.
  3. À partir de deux points, il est possible de tracer un cercle (ayant l’un pour centre et passant par l’autre)
  4. Tous les angles droits sont les mêmes (on peut les superposer)1
  5. Par un point extérieur à une droite, il passe une et une seule droite parallèle à cette droite.2

En ne se servant que de cela, Euclide démontre pas à pas tous les résultats connus de son époque, jusqu’à démontrer, à la 47e et dernière étape… le théorème de Pythagore !

Pas question de tout reproduire ici bien sûr, mais au moins la première proposition qu’il parvient à démontrer : étant donnés deux points, je peux tracer un triangle équilatéral. (Ah ben oui, forcément, ça ne peut pas aller très loin !)

Le premier axiome permet de tracer le segment reliant les deux points. Le troisième permet de tracer successivement les cercles ayant l’un des deux points pour centre et passant par l’autre. On obtient un troisième point, que l’on relie aux deux autres grâce au premier axiome.

Et voilà, il est maintenant permis de tracer des triangles équilatéraux !

Histoire de mieux comprendre encore ce qu’est une théorie mathématique, regardons les problèmes que se sont posés des mathématiciens par la suite sur ce premier livre des éléments. Quoiqu’impressionnés par le travail d’Euclide, ceux-ci ont trouvé que le cinquième axiome était bien trop compliqué par rapport aux autres. Si on regarde ça de près, c’est vrai que les 4 premiers donnent vraiment les éléments de base permettant de faire de la géométrie : tracer des segments, des droites, des cercles, et des angles droits. Alors que le 5e, ne serait-ce qu’à énoncer, est bien plus complexe… Certains ont donc essayé de le démontrer à partir des quatre premiers, autrement dit de le transformer en théorème d’une théorie qui n’aurait pour base que les 4 premiers axiomes. Mais ils s’y sont cassés les dents. Et pour cause… Au 19e siècle, soudain, quelqu’un réalise une chose toute simple : sur la Terre, qui est plus ou moins une sphère, on sait très bien ce que veut dire « aller tout droit  » : il s’agit de suivre le chemin le plus court pour aller d’un point à un autre ; est-ce une droite ? Non, en suivant une droite, on décollerait du sol ! Pourtant, on sent que la notion d’aller tout droit sur une sphère n’est pas très différente de celle d’aller tout droit sur un plan, et est en tout cas tout aussi intuitive. En gros, il s’agit de prendre le plus court chemin pour aller d’un point à un autre. Que se passe-t-il si on prend cette propriété comme nouvelle définition d’une droite, quel que soit le « monde  » dans lequel on vit ? Évidemment, suivant la forme de celui-ci, une « droite  » n’a pas toujours la même forme. Sur une sphère, par exemple, il s’agira d’un « grand cercle  », un cercle dont le centre est au centre de la sphère : tout autre cercle est plus « tordu  », et le suivre pour aller d’un point à un autre est donc toujours plus long que de suivre le morceau du grand cercle qui passe par les deux points. Mais une fois admis l’idée qu’une « droite  » puisse être un cercle, les 4 premiers axiomes restent évidemment vrais : on peut tracer des segments, des droites, des cercles, des angles droits sur une sphère. Ces propriétés peuvent donc être prises comme axiome indépendamment du monde dans lequel on se place. En revanche, si on prend un point qui n’est pas sur une droite, on ne trouvera aucune droite parallèle à droite passant par ce point, et même il est impossible de trouver deux droites parallèles : deux grands cercles d’une sphère se coupent nécessairement…

Moralité : le cinquième axiome est nécessaire si l’on veut faire de la géométrie à plat. Il est indépendant des 4 premiers. Cela signifie qu’avec les 4 premiers, on ne pourra ni le démontrer, ni démontrer qu’il est faux, puisqu’il existe des mondes, des « modèles  », dans lesquels il est vrai, et d’autres dans lequel il est faux. Démarre alors la géométrie « absolue  » faite de tous les résultats que l’on peut démontrer avec les quatre premiers axiomes, et qui seront vrais dans tous les mondes géométriques possibles, la géométrie « euclidienne  » ou plane, dans laquelle on rajoute le cinquième axiome d’Euclide, la géométrie sphérique, où celui-ci est remplacé par « il ne passe aucune parallèle  », et enfin la géométrie « hyperbolique  », dans lequel il est remplacé par « il passe une infinité de parallèles  » (chose qui arrive quand on se trouve sur une surface de type selle de cheval…)

Ainsi, le choix des axiomes détermine un certain « monde  » et les mathématiciens peuvent choisir celui qui les arrange le mieux en fonction du problème qu’ils se posent…

Revenons à nos moutons. À la fin du XIXe siècle, beaucoup de nouvelles théories étaient nées, et des mathématiciens ont voulu trouver des axiomes pour tout, remettre de l’ordre, plus ou moins comme Euclide. Mais quels axiomes choisir ? Quels objets de base définir ?

David Hilbert, très grand mathématicien allemand, parvint à finir le travail pour la géométrie, à l’aide de 20 axiomes. (le système d’Euclide n’était pas parfait !)
Un bon choix d’axiome doit réunir deux qualités : il doit permettre de démontrer tous les résultats vrais, on appelle cette propriété la « complétude  ». Et il doit bien sûr être « consistant  », c’est à dire ne pas démontrer une chose et son contraire, sans quoi il démontre tout, donc n’importe quoi !

Le problème de la « bonne  » théorie se posait notamment pour toutes les mathématiques utilisant des nombres. Pendant un bon moment les “ensembles“, des “collections d’objets”, une notion assez intuitive, était en vogue. On peut par exemple, pour définir les nombres, parler de l’ensemble vide, celui qui n’a aucun élément, puis parler de l’ensemble qui contient l’ensemble vide, qui a un élément, et ainsi, de proche en proche, construire des ensembles qui ont n’importe quel nombre d’éléments, donc les nombres entiers.

Mais au début du XXe siècle, les redoutables paradoxes de Bertrand Russel viennent tout ébranler, alors qu’ils paraissent pourtant enfantins :
Peut-on par exemple parler de l’ « ensemble de tous les ensembles  » ? Si c’est un ensemble, il doit se contenir lui-même? Sinon, ce n’est pas un ensemble ?
Pire, le fameux « paradoxe du barbier  » : imaginez un pays dans lequel il n’y a qu’un barbier, et que celui-ci rase tous les gens qui ne se rasent pas eux-mêmes, et seulement ceux-ci. Nous nous retrouvons avec deux ensembles bien définis. Mais qui rase donc le barbier ? S’il se rase lui-même, le barbier ne devrait pas le raser, mais c’est lui le barbier ! Et s’il ne se rase pas, alors le barbier (lui, donc) devrait le raser. Vous suivez ?! On ne s’en sort pas, c’est un cauchemar.

Bref, les meilleurs mathématiciens et logiciens suaient sang et eau sur ce problème au début du XXe siècle (le même Russel, dans un travail commun avec Whitehead, vont jusqu’à prendre 350 pages pour démontrer… que 1 + 1 = 2 !)

Pendant ce temps, d’autres mathématiciens, et non des moindres, trouvaient ce travail inutile : pour eux, cette démarche enlève tout son sens aux mathématiques, celles-ci n’avanceront jamais ainsi, c’est une mécanique vaine. Il faut garder la place de l’intuition, et ne pas penser que même muni d’un système d’axiomes parfait, on parviendra à faire avancer les maths de façon automatique. Une citation de Henri Poincaré, très grand mathématicien également, mais français, montre très clairement sa position :

« Un naturaliste, qui n’aurait jamais étudié l’éléphant qu’au microscope, croirait-il connaître suffisamment cet animal ?
Eh bien ! En Mathématiques, il y a quelque chose d’analogue. Le logicien décompose pour ainsi dire chaque démonstration en un très grand nombre d’opérations élémentaires ; quand on aura examiné ces opérations les unes après les autres et qu’on aura constaté que chacune d’elles est correcte, croira-t-on avoir compris le véritable sens de la démonstration ?  »

Hilbert est au contraire passionné par cette quête, et persuadé qu’elle aboutira. On doit pouvoir trouver un système parfait, dans lequel tout pourra être démontré ou réfuté. Admettant que l’on peut avoir plusieurs modèles, plusieurs mondes derrière un même système d’axiomes, il va même jusqu’à affirmer que l’on pourrait donner d’autres noms aux objets mathématiques sans problème : remplacer par exemple “point” par “bière” et “droite” par “table”, et affirmer que par deux bières, il passe une et une seule table. Pourquoi pas ? Tant que la cohérence de l’ensemble « définitions/Postulats/démonstration  » n’est pas atteint, ce n’est pas gênant. La seule chose qui compte, c’est la validité relative des enchaînements de propositions.

Tombe de David Hilbert à Göttingen avec l’épitaphe:
Wir müssen wissen
Wir werden wissen (source: Wikipédia)

Plein d’optimisme, il lança un jour à la communauté mathématique une phrase restée célèbre: « Wir müssen wissen, wir werden wissen  » : « nous devons savoir, nous saurons  », phrase qui fut carrément gravée comme épitaphe sur sa tombe…

Ça y est, tous les éléments sont enfin en place pour introduire le résultat de Kurt Gödel, alors tout jeune logicien de 25 ans.

En 1931, son théorème détruit le rêve de Hilbert à tout jamais : il démontre qu’une théorie permettant de définir les nombres entiers, quelle qu’elle soit, ne sera jamais parfaite. Plus précisément, soit ce système d’axiome permettra de démontrer des résultats faux, soit il existera au moins un résultat vrai qui ne pourra pas être démontré à partir de ces axiomes. Très difficile à lire dans sa version rigoureuse, la démonstration repose pourtant sur une idée toute simple : il arrive à formuler rigoureusement, à partir des axiomes en question, la phrase : « Je ne suis pas démontrable à partir de ces axiomes  ». Dès lors, si l’on arrive à démontrer cette proposition, cela signifie que la théorie n’est pas cohérente, puis qu’elle permet de démontrer un résultat faux. Et si l’on n’y parvient pas, cela signifie que la théorie n’est pas complète, puisqu’elle ne permet pas de démontrer un résultat… manifestement vrai !

Conséquence immédiate de ce théorème d’ « incomplétude  », un deuxième énoncé tout aussi désagréable pour Hilbert et ses partisans : il sera à tout jamais impossible de démontrer, en restant dans le cadre d’une théorie, le fait qu’elle ne comporte pas de contradiction. Bref, pour la théorie parfaite, vous pouvez aller vous rhabiller.

Cela n’empêcha pas les mathématiciens de continuer à vouloir être rigoureux, on ne se refait pas. Mais depuis, ils savent malgré tout que certaines conjectures qu’ils voudraient démontrer s’avéreront peut-être un jour « indécidables  », ni vraies ni fausses dans la théorie dans laquelle ils travaillent. C’est le cas pour un certain nombre de propositions, que l’on est donc obligé de rajouter à un système d’axiome déjà existant pour être « dans le bon cadre  ». L’exemple le plus connu est sans doute « l’axiome du choix  », qui dit tout simplement qu’il est possible, quels que soient la liste d’ensembles à laquelle on fait face, de choisir un élément dans chacun des ensembles. Prudence, ce n’est pas si évident qu’on pourrait croire.

Évidemment, travailler des années pour trouver une démonstration, et découvrir qu’elle ne peut pas exister, c’est rageant !

Ce théorème en tous cas ne change pas fondamentalement les choses pour les mathématiciens : bien peu se préoccupent des fondements de leur théories, tant qu’elles marchent !

Une sorte d’épilogue :
Le formalisme à la Hilbert a vécu et vit encore de beaux jours, avec notamment le collectif Bourbaki, nom de code d’un groupe de mathématiciens français, qui s’est lancé dans les éléments de mathématiques, dans la droite ligne d’Euclide et d’Hilbert, dont le premier tome sur les éléments est sorti en 1939, et qui est toujours actif (évidemment, les membres se renouvellent !)

L’apparition des ordinateurs a aussi un rôle important : la possibilité de calculer ou non un résultat devient centrale. Un ordinateur fonctionne un peu comme une « théorie parfaite  », et la question de savoir ce qui est ou non démontrable a été grandement remplacée aujourd’hui par la question de savoir ce qui est « calculable  » ou non.

Autre question : certains résultats importants ont été démontrés grâce à des ordinateurs. C’est certain que Poincaré n’aurait pas été content, car on ne comprend pas du tout pourquoi le résultat est vrai. Mais pour autant, peut on douter du fait qu’il l’est ?

1 Cet axiome peut sembler étrange. Il faut savoir que la définition des angles droits est assez tordue pour que l’on ait des raisons de s’inquiéter ; la voici en substance : quand deux droites se croisent, si deux angles consécutifs autour de ce croisement sont les mêmes, ce sont des angles droits.

2 Pour les curieux, qui veulent un petit extrait de l’original, traduction par B. Vitrac. Notez que j’ai pris pour 5e axiome (ici les « demandes  ») une proposition plus simple, qui est mathématiquement équivalente à celle proposée ici (si l’une est vraie, l’autre aussi).

Définitions

1. Un point est ce dont il n’y a aucune partie
2. Une ligne est une longueur sans largeur
3. Les limites d’une ligne sont des points
4. Une ligne droite est celle qui est placée de manière égale par rapport aux points qui sont sur elle
(…)
23. Des droites parallèles sont celles qui étant dans le même plan et indéfiniment prolongées de part et d’autre, ne se rencontrent pas, ni d’un côté, ni de l’autre

Demandes

1. Qu’il soit demandé de mener une ligne droite de tout point à tout point
2. Et de prolonger continûment en ligne droite une ligne droite limitée.
3. Et de décrire un cercle à partir de tout centre et au moyen de tout intervalle.
4. Et que tous les angles droits soient égaux entre eux.
5. Et que, si une droite tombant sur deux droites fait les angles intérieurs et du même côté plus petits que deux droits, les deux droites, indéfiniment prolongées, se rencontrent du côté où sont les angles plus petits que deux droits.

Notions communes

1. Les choses égales à une même chose sont égales entre elles.
2. Et si, à des choses égales, des choses égales sont ajoutées, les touts sont égaux.
3. Et si, à partir de choses égales, des choses égales sont retranchées, les restes sont égaux.
4. Et si, à des choses inégales, des choses égales sont ajoutées, les touts sont inégaux.
5. Et les doubles du même sont égaux entre eux.
6. Et les moitiés du même sont égales entre elles.
7. Et les choses qui s’ajustent les unes sur les autres sont égales entre elles.
8. Et le tout est plus grand que la partie.
9. Et deux droites ne contiennent pas une aire.

Derniers épisodes