Impossible

Piste verte Le 12 mai 2011  - Ecrit par  Étienne Ghys Voir les commentaires (12)
Lire l'article en  

Impossible n’est pas français — dit-on — mais impossible est-il
mathématique ?

Voici quelques mots qu’on peut trouver au détour des articles
mathématiques d’aujourd’hui :

vrai, démontrable, probable, presque sûr, calculable, cohérent,
effectif, décidable...

Depuis un peu moins de cent ans, les mathématiciens ont dû s’y faire ; entre le vrai et le faux, le possible et l’impossible, il y a des nuances.
Ils en ont mis du temps !
Chacun sait bien que dans la vie de tous les jours, il n’est pas toujours facile de distinguer le vrai du faux et que parfois, c’est tout simplement impossible.

Et pourtant, les mathématiques sont encore souvent présentées comme un monde caricatural et froid où on a raison ou tort.

Le dix-neuvième siècle avec son optimisme et ses certitudes a laissé la place à un vingtième siècle plein de doutes et de complexités.
Et cette évolution ne se rencontre bien sûr pas seulement dans le domaine des mathématiques.
Il suffit d’évoquer le « principe d’incertitude » en mécanique quantique ou la relativité d’Einstein pour constater que les physiciens ont également remis en question quelques-unes de leurs certitudes, à peu près à la même époque.
D’ailleurs, on trouverait beaucoup de situations analogues à l’extérieur du domaine des sciences.

La quadrature du cercle

La quadrature du cercle est un problème impossible.
En fait, il s’agit d’un problème de géométrie du plan, qui remonte à l’Antiquité.
On se donne un cercle et on dispose d’une règle et d’un compas.

La quadrature du cercle

Michael Maier, Atlanta Fugens, 1618, emblème XXI, quadrature du cercle philosophale

Le défi consiste à construire un carré dont la superficie est la même que celle entourée par le cercle.
Pourquoi cette question est-elle intéressante ?
Pour dire la vérité, aujourd’hui ce n’est plus très intéressant.
Mais on peut considérer qu’il fut un temps où un arpenteur pouvait avoir envie de trouver la superficie d’un bassin circulaire.
Nous savons que cette superficie est $\pi R^2$ où $R$ désigne le rayon du cercle et où $\pi$ désigne cette constante célèbre qui vaut approximativement $3,14...$.
Autrement dit, la quadrature du cercle consiste à déterminer la valeur de $\pi$ à l’aide d’une règle et d’un compas.
A quoi bon, puisque ma calculette m’informe que $\pi =3,14159265358979...$ et que ceci satisfera tous les arpenteurs du monde pendant bien longtemps encore ?
Il n’empêche que cette énigme a hanté les géomètres pendant de nombreux siècles, jusqu’à ce que, en 1882, le mathématicien Lindemann montre que

c’est impossible !

C’est un peu comme si ce nombre $\pi$ n’existait pas, puisqu’on ne peut pas le construire.
Mais bien sûr, pour construire, il faut des outils et dans ce cas il s’agit d’une règle et d’un compas.
Si on m’autorise à utiliser d’autres outils, comme par exemple un ordinateur, je peux écrire un petit programme qui va afficher sur mon écran les décimales de $\pi$ une à une.
Peut-être que mon ordinateur mettra très longtemps pour trouver la millième décimale, mais il finira bien par la calculer.
Le nombre $\pi$ n’est pas constructible avec une règle et un compas mais il est (en principe) calculable avec un ordinateur (avec une précision arbitraire).

L’incomplétude

Au début du vingtième siècle, les logiciens ont donné une bonne leçon de modestie aux mathématiciens, mais aussi aux scientifiques et aux philosophes.
De même que certains nombres existent bel et bien mais ne peuvent être construits, certains énoncés ne peuvent être ni démontrés ni infirmés.
Il s’agit du théorème de Gödel, datant de 1931.
Il n’est pas question ici de l’énoncer avec précision : cela nécessiterait de longs développements [1].

Kurt Gödel (1906-1978)

D’une certaine manière, les juristes connaissaient ce théorème depuis longtemps.
Simplifions à l’extrême le problème qui se présente à la justice.
Il s’agit de déterminer si un accusé est innocent ou coupable d’un crime.
Pour cela, la cour d’assises possède un certain nombre d’outils, mis à sa disposition par le code pénal par exemple.
Elle dispose également d’un certain nombre de faits, témoignages etc. établis lors de l’enquête.
Et ensuite, la machine judiciaire travaille.
Parfois elle peut établir l’innocence, parfois elle peut établir la culpabilité.
Mais parfois, elle reconnaît qu’elle ne peut établir ni l’un ni l’autre ; les outils dont elle dispose sont insuffisants pour conclure et c’est l’acquittement.
Il y a longtemps que les juristes ont compris qu’ils ne peuvent pas toujours accéder à la vérité !

Lorsqu’on raisonne, on a à sa disposition un certain nombre d’énoncés « solides » sur lesquels on peut s’appuyer : on les appelle les axiomes.
Et puis, on dispose de quelques règles de raisonnement : le code pénal du matheux.
Il s’agit d’établir si un énoncé est vrai ou faux.
Parfois on arrive à montrer qu’il est faux.
Parfois qu’il est vrai.
Et parfois, il est impossible d’arriver à l’un ou à l’autre.
Insistons : ce n’est pas que je n’ai pas réussi à le faire, c’est qu’on peut démontrer qu’il existe des énoncés dont la vérité/fausseté ne peut pas être démontrée.
On dit qu’ils sont indécidables.

Notre méthode mathématique manque de puissance.

On pourrait dire qu’il suffit d’augmenter le nombre d’axiomes, d’ajouter quelques règles de raisonnement, pour ajouter de la puissance aux mathématiques, mais le théorème de Gödel est implacable.
Quels que soient les axiomes qu’on ajoute on sera face à une alternative bien désagréable.
Soit on a ajouté trop d’axiomes et notre machine à raisonner sera tellement mauvaise qu’elle en deviendra contradictoire et permettra de démontrer tout et son contraire ; soit il restera des énoncés indécidables.
Nous devons donc accepter le fait que certaines vérités nous sont inaccessibles.
Belle leçon.

Vrai ou faux ?

JPEG - 31.1 ko
La Vérité, abstraction personnifiée
Jules Joseph Lefebvre (1870)

On peut alors se demander ce que signifient les mots « vrai » et « faux ».
On pourrait penser naïvement qu’un énoncé est vrai si on peut le démontrer et faux si on peut démontrer sa négation. Mais alors, le théorème de Gödel nous conduirait à la conclusion que certains énoncés ne sont ni vrais ni faux.
Cela ne nous semble pas acceptable.
Il faut bien que tous les énoncés soient vrais ou faux !

Revenons à notre analogie juridique.
Lorsqu’une cours d’assise prononce un acquittement parce qu’elle n’a pu prouver la culpabilité d’un accusé, elle ne se prononce pas sur cette culpabilité et pourtant, l’accusé est coupable ou il ne l’est pas.

C’est un peu la même chose en mathématiques.
On considère souvent que les raisonnements mathématiques et les axiomes sont un moyen d’explorer un « monde mathématique abstrait » (qu’on appelle un modèle) dans lequel tous les énoncés sont vrais ou faux.
Le théorème de Gödel prend alors une forme plus impressionnante : certains énoncés sont vrais (dans le modèle) et pourtant ne peuvent pas être démontrés.

Le fait pour un énoncé d’être démontrable dépend du système d’axiomes utilisés alors que sa véracité dépend du modèle mathématique choisi, celui qu’on se propose d’étudier.

Ensuite vient la question du choix du modèle utilisé par les mathématiciens.
Il s’agit maintenant d’une discussion de nature philosophique.
La plupart des mathématiciens pensent que leur travail consiste à explorer un monde mathématique qui a une véritable « existence », presque concrète, et qui est commun à tous les êtres humains (ou même extra-terrestres ?).
Autrement dit, beaucoup de mathématiciens pensent qu’il existe une modèle privilégié qu’ils visitent, et que chaque énoncé mathématique est donc vrai ou faux.

Essayez-donc de demander à des mathématiciens ce que le mot « vrai » signifie pour eux et vous verrez que les réponses sont rarement claires.
En fait, bien peu sont ceux qui se sont posés cette question qui est pourtant au cœur de leur activité.

Un « exemple »

Pendant longtemps, les mathématiciens pensaient que ce théorème de Gödel n’était qu’une élucubration de logiciens et que tous les énoncés de la vie (mathématique !) de tous les jours sont décidables, en pratique.
Et pourtant, il existe des exemples relativement concrets d’énoncés indécidables.
Malheureusement, il sont un peu compliqués pour qu’on puisse les expliquer ici  [2].

Voici cependant un énoncé « qui pourrait bien être vrai et indécidable ».
On dit que deux nombres premiers [3]
sont jumeaux s’ils diffèrent de 2, comme par exemple 3 et 5, ou 5 et 7, ou encore 881 et 883.
On se demande depuis longtemps s’il existe une infinité de nombres premiers jumeaux [4].

L’énoncé « Il existe une infinité de nombres premiers jumeaux » décrit une propriété des entiers naturels.
Dire qu’il est vrai ou faux dépend du choix d’un modèle pour les entiers naturels, mais là encore, la plupart des mathématiciens pensent que l’ensemble des entiers naturels « existe », c’est-à-dire qu’ils en privilégient un modèle particulier.
L’énoncé est donc vrai ou faux, même si je suis incapable d’en dire plus.

Il est possible qu’un jour un mathématicien en trouvera une démonstration ou une démonstration de sa négation, mais il est aussi possible que cet énoncé soit indécidable et faux ou encore indécidable et vrai.

Calculable

Supposons que vous souhaitiez carreler votre cuisine avec des carreaux du
type suivant.

Ce sont tout simplement des carrés dont chaque côté est colorié.
Vous vous imposez une règle : vous ne vous autorisez à placer un carreau à côté d’un autre que si les côtés adjacents possèdent la même couleur [5].
Comme nous parlons de mathématiques, nous n’hésiterons pas à supposer notre cuisine infinie :-) mais je suppose quand même qu’il n’y a qu’un nombre fini de couleurs (disons, bleu, rouge, vert et noir par exemple) et que les types de pavés que je me propose d’utiliser me sont donnés a priori (6 dans l’exemple ci-dessus).

Comment déterminer si c’est possible ?
On aimerait programmer un ordinateur pour qu’il réponde à la question.
On entrerait comme données dans le programme le nombre de types de carrés dont on dispose, les couleurs des côtés, et on presserait sur la touche « Enter ».
Le programme calculerait et répondrait « Oui, c’est possible, vos carrés colorés peuvent en effet paver votre cuisine infinie », ou « Non, c’est impossible ».

Eh bien, un tel programme n’existe pas.
C’est un théorème de Robert Berger, datant de 1966 et fondé sur un résultat fondamental de Turing de 1936.

Alan Turing (1912-1954)

Autrement dit, certains problèmes ne peuvent pas être résolus par un ordinateur, aussi puissant soit-il. C’est une autre forme d’indécidabilité.

Compliqué

L’arrivée des ordinateurs nous a fait prendre conscience d’un autre fait dont la portée scientifique et philosophique est considérable.
Certains faits sont vrais et démontrables mais leurs démonstrations sont si longues que tout se passe comme si elles n’existaient pas.
Reprenons l’exemple de mon ordinateur auquel je demande de calculer les décimales du nombre $\pi$.
Supposons que je cherche la milliardième décimale par exemple.
Si je m’y prends mal, si mon programme est naïf, il est clair que mon ordinateur va commencer un calcul démesurément long et le temps dont il aura besoin sera très probablement largement supérieur à l’âge de l’univers !
A quoi bon un tel calcul ?
Quel est le sens de la phrase « je peux calculer la milliardième décimale de $\pi$ » s’il me faut attendre de telles durées, ce que je ne peux évidemment pas admettre.
Peut-être que je m’y suis mal pris ?
Peut-être qu’en donnant des instructions différentes au même ordinateur, il pourrait trouver la milliardième décimale en un quart d’heure ?

Mais là encore, les logiciens nous ont forcé à la modestie.
Il existe des énoncés pas très compliqués qui sont démontrables mais qu’on ne peut pas démontrer en un temps raisonnable.
Les longueurs des preuves sont incommensurablement plus longues que les longueurs des énoncés qu’il s’agit de démontrer.
Il est possible de les démontrer mais il est impossible de le faire dans un temps utile.
Ils sont donc hors de portée de notre entendement.

Probable

L’ADN d’un suspect retrouvé sur les lieux du crime est-il une preuve de culpabilité ?
A strictement parler, il n’est pas impossible que deux personnes différentes aient exactement le même ADN mais c’est très très très peu probable [6].
Si deux personnes lancent mille fois consécutivement une pièce de monnaie, quelle est la probabilité qu’ils réalisent exactement la même suite de piles et de faces ?
Une chance sur

10
715
086
071
862
673
209
484
250
490
600
018
105
614
048
117
055
336
074
437
503
883
703
510
511
249
361
224
931
983
788
156
958
581
275
946
729
175
531
468
251
871
452
856
923
140
435
984
577
574
698
574
803
934
567
774
824
230
985
421
074
605
062
371
141
877
954
182
153
046
474
983
581
941
267
398
767
559
165
543
946
077
062
914
571
196
477
686
542
167
660
429
831
652
624
386
837
205
668
069
376

Autant dire que c’est « impossible ».

La théorie des probabilités a pris un essor formidable pendant le vingtième siècle.
Là encore, il s’agit de repenser le possible et l’impossible et ce nouvel outil a une puissance incroyable.
Voir à ce sujet l’article de François Sauvageot.

Alors, en effet, les mathématiques d’aujourd’hui ne sont plus celles du vrai ou du faux, et elles proposent des approches bien plus subtiles : vrai, démontrable, probable, calculable, cohérent, effectif, décidable etc.

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive, les relecteurs dont le pseudonyme est le suivant : Xavier Buff, levangileselonsaintmatheux et Jérôme Germoni.

Article édité par François Sauvageot

Notes

[1J’espère que Images des Mathématiques consacrera bientôt un article à ce théorème fondamental. En attendant, cet article est disponible, mais un peu difficile.

[2Le lecteur intéressé peut lire cet article.

[3Rappelons qu’un nombre entier supérieur ou égal à 2 est appelé premier s’il ne peut pas s’écrire comme le produit de deux entiers plus petits. Par exemple 5 est premier mais 6 ne l’est pas puisqu’il est égal à 2 fois 3. Saurez-vous déterminer si 8999737 est premier ? Combien de temps mettrez-vous pour le savoir ? Combien de temps prendrait votre ordinateur ?

[4Voir cet article de Wikipedia.

[5Il n’est permis ni de les retourner ni de les faire tourner : on ne peut que les translater.

[6Oublions le cas des jumeaux.

Partager cet article

Pour citer cet article :

Étienne Ghys — «Impossible » — Images des Mathématiques, CNRS, 2011

Crédits image :

La quadrature du cercle - http://fr.wikipedia.org/wiki/Quadrature_du_cercle
Kurt Gödel (1906-1978) - http://www-groups.dcs.st-and.ac.uk/ history/Biographies/Godel.html
Alan Turing (1912-1954) - http://www-history.mcs.st-and.ac.uk/Mathematicians/Turing.html
La Vérité, abstraction personnifiée - http://fr.wikipedia.org/wiki/Fichier:Truth.jpg

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • Impossible

    le 12 mai 2011 à 10:31, par Aurélien Djament

    Bonjour à tous,

    merci à Étienne Ghys pour ce joli article. Une question sur la conjecture des nombres premiers jumeaux : est-elle citée à simple titre d’exemple, comme aurait pu l’être n’importe quel autre problème résistant aux assauts des mathématiciens depuis très longtemps, ou y a-t-il des motifs spécifiques à cette conjecture qui laissent soupçonner qu’elle pourrait être indécidable ?

    Bien cordialement,

    A.D.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?