Je mens

Démontrer des théorèmes, c'est pas si compliqué que ça : on part de ce que l'on sait (des propositions déjà démontrées, qui s'appuient sur d'autres propositions démontrées [...] qui s'appuient sur les axiomes) et on utilise les règles d'inférence (le mode d'emploi des démonstrations, les règles de raisonnement autorisées). En étant suffisamment malin, on devrait pouvoir réussir à démontrer tout ce qui est vrai, et réfuter tout ce qui est faux...

Tout ? Non ! Il reste une poignée d'irréductibles propositions, impossible à démontrer ! Leur bannière, c'est le théorème de Gödel !

Au commencement...
300 ans avant Jésus-Christ, Euclide rédigeait le premier grand traité de mathématiques. Un livre rassemblant toutes les connaissances mathématiques de l'époque (géométriques et arithmétiques), chacunes démontrées de façon rigoureuse. Les règles d'inférences n'étaient pas encore bien connues (elles ne le seront qu'au XIXe siècle) mais chaque nouveaux théorème s'appuient sur les précédents, pour bâtir un édifice mathématique solide. Les fondations de la partie géométrique, ce sont les 5 axiomes d'Euclide :
- Par deux points passent un unique segment
- Tout segment est prolongeable en une droite
- On peut construire un cercle depuis tout point et de n'importe quel rayon donné
- Tous les angles droits sont égaux
- Le cinquième axiome

Le cinquième axiome, connu sous le nom "d'axiome des parallèles", peut s'énoncer de la façon suivante :

Par un point extérieur à une droite d passe une unique droite ne coupant pas la droite d

(On appelle ça une droite parallèle)

Avec ce cinquième axiome, Euclide savait qu'il touchait quelque chose de difficile. C'est le moins naturel des ces 5 axiomes, et Euclide attend le dernier moment pour l'utiliser. Si peu naturel que de nombreux mathématiciens s'étaient mis en tête de le démontrer à partir des 4 axiomes précédents.

Pour essayer de démontrer cet axiome, Lobatchevski (en 1840) a tenté la démonstration par l'absurde. On part du principe qu'il peut y avoir plusieurs parallèles différentes passant par un même point, et on regarde ce qu'il se passe. Si on trouve une contradiction, c'est que l'axiome était faux.
Malheureusement, Lobatchevski n'a pas réussit à aboutir à la moindre contradiction. Pire : il venait d'inventer une nouvelle géométrie, la géométrie hyperbolique, un endroit où les triangles peuvent avoir des angles nuls !

Une géométrie non-euclidienne, où des triangles monstres existent, cela ne plait pas vraiment... Il fallait tout faire pour montrer qu'une telle géométrie aboutirait à des contradictions !

Cela a été fait en 1868 par Beltrani en 1968, mais le théorème n'a pas du plaire à tout le monde : la géométrie hyperbolique est consistante (N'amène à aucune contradiction) si et seulement si la géométrie euclidienne l'est. Autrement dit, si on accepte la géométrie euclidienne, on doit accepter les autres géométries. La conséquence, c'est que l'axiome des parallèles est indémontrable, Euclide avait bien fait de le placer parmi ses axiomes !

Un énoncé est dit indécidable si on ne peut ni le prouver, ni l'infirmer. L'axiome des parallèles, vis à vis des autres axiomes d'Euclide est un indécidable de la théorie ! Une théorie dans laquelle il n'existe aucun énoncé indécidable est dit complet.

Le théorème de Gödel
Oublions un peu la géométrie, et regardons un peu l'arithmétique, formalisée par Peano. Elle contient 5 axiomes, décrivant comment deux entiers peuvent être égaux. Avec la formalisation, on peut écrire des énoncés comme "Il existe une infinité de nombres premiers" ou "Il n'existe pas d'entiers x, y et z strictement positif tel xⁿ+yⁿ=zⁿ, avec n>2" (alias théorème de Fermat). Le premier énoncé est vrai, et démontrable parfaitement dans l'arithmétique de Peano. Le second est également vrai (puisque Wiles l'a démontré en 1994), mais est-il démontrable sans dépasser le cadre de l'arithmétique (Puisque Wiles l'a démontré dans un cadre plus grand, celui des ensembles) ? La question est ouverte !

Les peurs de la non-démontrabilité de Fermat sont tout à fait fondées, à cause du théorème de Gödel, donné en 1931 :

Dans toute théorie non-contradictoire suffisamment puissante pour formaliser l'arithmétique, il existe des énoncés indécidable

Cet énoncé est un théorème : qu'on le veuille ou non, il y a des trous dans l'arithmétique proposée par Peano, ou dans la théorie des ensembles proposées par Zermelo et Frankel (la théorie ZF, dans laquelle on retrouve celle de Peano) !

Pour démontrer son théorème, Gödel pousse le vice jusqu'à donner une façon explicite de fabriquer des énoncés indécidable. En partant d'un système formel S, il code une formule F qui dit "Je ne suis pas prouvable dans S", formule indécidable ! Cette démonstration constructive permet à un ordinateur de construire lui-même des énoncés indémontrables.

Conséquences
En donnant une démonstration constructive, Gödel s'est un peu tiré une balle dans le pied : se poser des questions auto-référentes de ce genre ("Je mens" ?), c'est simplement un travail de logiciens. Les mathématiciens puristes doivent alors se rassurer : puisqu'on a jamais d'énoncés aussi tordus, on ne devrait pas vraiment tomber sur ce genre de problèmes d'indécidabilité...

Enfin, tout ça, c'était avant que l'on cherche vraiment... Des énoncés indécidables, on peut en trouver des tas !

Dans l'arithmétique de Peano, il y a notamment :
- Le suites de Goodstein tendent vers (voir ici)
- Hercule contre l'hydre
- Les arbres de Kruskal : "Toute suite correcte d'arbres (un arbre de la suite n'est jamais sous-arbre d'un arbre placé plus loin) de type n (le 1er arbre possède moins de n branche, le 2e moins n+1 branches, etc.) est toujours finie."

Pour démontrer ces théorèmes, il faut utiliser les ordinaux, pur fruit de la théorie de ZF, inconnu chez Peano. Pourtant, les théorèmes peuvent clairement être énoncés sans faire appel à des notions d'infinis ou d'ensembles ! Ces énoncés ne sont donc pas si indécidables que ça, puisqu'il suffit d'agrandir un peu la théorie pour effacer toutes les traces d'indécidabilité.

Le deuxième gros secteur à être enclin à l'indécidabilité est celle de la théorie du calcul, qui se pose des questions du genre "Quelle est la probabilité qu'un programme s'arrête". Dans cette théorie où la machine de Turing règne en maitre, il n'est pas rare de voir des énoncés indécidables. C'est même d'ailleurs bien rare d'en voir des décidables !

Des exemples d'indécidables dans la théorie des ensembles sont moins nombreux, et aucun résultat important ne tombe dans les trous logiques causés par Gödel... Enfin, on l'espère, puisqu'il n'est pas impossible que parmi les grandes conjectures (nombres premiers jumeaux, Goldbach, Riemann...), certaines soient indécidables (vis à vis de Peano ou de ZF)...

On peut faire un parallèle avec l'axiome du choix (Qui d'ailleurs est indécidable vis à vis des autres axiomes) qui amène son lot de monstres mathématiques, mais qui, dans la pratique, ne pose jamais de problèmes : le théorème de Gödel amène son lot d'énoncés monstres, mais qui n'arrivent jamais dans la pratique, puisqu'il suffit généralement de passer de Peano à ZF pour effacer les problèmes, et que la théorie de la calcul  n'est qu'une affaire de codage, et n'intéresse que les logiciens ou les informaticiens. Jusqu'au jour où...

Axiome du choix, théorème de Gödel... Les débats sont loin d'être terminés.

"95% des mathématiciens se moquent éperdument de ce que peuvent faire tous les logiciens et tous les philosophes" [Jean Dieudonné]

---

Sources :
Les propositions indécidables - Pour la science N°265, novembre 1999
Promenade au pays des indécidables - Pour la science N°266, décembre 1999

Comments

[Ahmed Idrissi B.]

Le grand théorème de Fermat est démontrable sans dépasser le cadre de l'arithmétique :

www.happy-arabia.net/GTFpreuve.pdf

[l'Ecrivain]

Juste à propos de l'affirmation "Je mens": quant à moi, le problème n'existe qu'à partir du moment où on pense avoir à faire à des termes "objectifs", ce qui est une illusion.

L'affirmation "mentir" est subjective et doit être mise en rapport avec l'intention de celui qui la formule et non avec une valeur logique. Il faut également distinguer les valeurs "mensonger" et "faux".

La réponse est donc variable selon les situations, puisqu'on ne peut pas affirmer que l'intention est toujours la même selon les sujets. Mais dans le cas-type d'un logicien qui dit "je mens", son intention est d'introduire un paradoxe (et peu importe qu'il y parvienne ou non). Cette intention n'est pas mensongère.
L'affirmation "je mens" est donc fausse. Le fait qu'elle soit fausse ne la rends pas plus vrai, puisqu'elle n'est pas plus mensongère. Donc elle reste fausse.

Une phrase faisant appel à des notions plus neutres en apparence comme "Cette phrase est fausse" n'est pas bien différente. La solution ne soit pas du même ordre: encore là on peut résoudre le problème en tenant compte de la dimension subjective des valeurs de "vrai" et de "faux", qui se réfèrent à un contexte, et en introduisant une notion tierce "neutre".

[Robyn Slinger]

Je ne sais pas bien en quel endroit poster ceci, alors je saisis l'occasion ici de recommander la lecture de Logicomix :

http://www.logicomix.com/en/

De la page d'introduction :

Covering a span of sixty years, the graphic novel Logicomix was inspired by the epic story of the quest for the Foundations of Mathematics.

This was a heroic intellectual adventure most of whose protagonists paid the price of knowledge with extreme personal suffering and even insanity. The book tells its tale in an engaging way, at the same time complex and accessible. It grounds the philosophical struggles on the undercurrent of personal emotional turmoil, as well as the momentous historical events and ideological battles which gave rise to them.

The role of narrator is given to the most eloquent and spirited of the story’s protagonists, the great logician, philosopher and pacifist Bertrand Russell. It is through his eyes that the plights of such great thinkers as Frege, Hilbert, Poincaré, Wittgenstein and Gödel come to life, and through his own passionate involvement in the quest that the various narrative strands come together.

[Charles]

Bien sûr, toute comparaison a ses limites, mais celle que vous proposez me plaît assez. Ainsi, accepter ou refuser l'axiome du choix conduit à bâtir deux mondes mathématiques légèrement différents, tous deux également concevables du point de vue logique, dans le cadre de l'axiomatique de base de Zermelo-Fraenkel.

Je pense même que votre remarque recoupe une réalité en logique : un "modèle" est un ensemble de concepts réalisant entre eux des relations satisfaisant un ensemble d'axiomes donnés. (je ne suis pas logicien, cette définition est vague et sans doute un peu fausse sur les bords). Si on se donne une batterie A d'axiomes, et un axiome supplémentaire S, indécidable dans A, on peut construire des "modèles" de A, dans lesquel S est vrai, et d'autres dans lesquels S est faux. Un peu comme concevoir des univers physiques dans lesquelles la constante de Planck vaudrai 1000 fois sa valeur constatée "chez nous".

Cependant, en physique, le monde observable correspond à telles valeurs des constantes, pas à d'autres. En maths, je ne vois pas de notion de "monde observable" ... Préférer l'axiome du choix ou sa négation est affaire de goût, la "nature" n'impose rien.

Et la notion d'indécidabilité est déconcertante. Ainsi, il se pourrait que l'hypothèse de Riemann (une certaine fonction f(z) ne s'annule pas dans un certain domaine D) soit indécidable. Alors elle serait vraie. En effet, dire qu'elle est indécidable signifie qu'il n'y a pas de preuve que'elle est vraie, pas de preuve non plus qu'elle est fausse. Or une preuve qu'elle est fausse serait la localisation d'une zéro de f, dans D. Mais si un tel zéro existe, alors une démonstration le localisant existe (par encadrements de f dans une petite zone autour de ce zéro, on peut prouver la présence du zéro). Donc montrer que l'hypothèse de Riemann est indécidable aurait comme conséquence de
-montrer qu'il n'y a pas de zéro de f dans D (donc que l'hypothèse est vraie)
-montrer qu'aucune preuve, dans l'axiomatique ZF, de l'absence de zéro de f, n'existe.

Mais, vu le 2me point, on pourrait donc très bien supposer qu'un certain Z dans D est tel que f(Z)=0, cela n'induira pas de contradiction. Il n'y a pas de zéro dans D, mais supposer qu'il y en a un ne serait pas contradictoire (d'où l'impossibilité de prouver l'absence de zéros).

J'ignore si les maths ont déjà joué ce genre de coup tordu aux matheux : un énoncé significatif, indécidable, et vrai (par l'argument développé ci-dessus), et que l'on aurait fini par identifier comme tel.

[Tom Roud]

Un truc qui me frappe avec ton exemples tes parallèles : les énoncés indécidables ne sont-ils pas en fait l'équivalent mathématique des paramètres libres en physique, i.e. des objets non contraints décrivant différents "mondes mathématiques" de la même façon que les constantes physiques différentes peuvent décrire des univers différents ?