verite mathematique, coherence logique et ... - Gallium, Inria

VERITE MATHEMATIQUE, COHERENCE LOGIQUE ET VERIFICATION INFORMATIQUE


1 Gérard HUET


1 Directeur de recherche à l'INRIA, Membre de l'Académie des Sciences


1

J'ai été très intéressé d'être invité à un colloque où on discute de laLa
vérité dans les sciences . C'est un problème philosophique posé depuis la
nuit des temps, à savoir : quels sont les moyens de connaissance justes ?
Ces discussions portent souvent sur le discours de la méthode
expérimentale, la possibilité de reproduire le résultat des expériences,
etc. et il semble bizarre qu'on examine les mathématiques, puisqu'on ne
sait même pas si c'est une science : c'est plutôt une sorte de firmament au-
dessus des sciences. Dans le langage courant, lorsqu'on a une certitude
absolue, on dit : « C'est mathématique », donc comment mettre en doute la
notion de vérité mathématique ? Cela paraît difficile mais peut-être y a-t-
il des problèmes cachés sous le tapis dans les mathématiques ? Il est
significatif qu'on n'ait pas trouvé de mathématicien pour faire cet exposé.
En dépit de mon doctorat de mathématiques, je suis un informaticien avant
d'être un mathématicien. Les mathématiciens se sont peut-être défaussés sur
un informaticien pour discuter de la vérité mathématique, avec l'idée que
si je dis quelque chose de non politiquement correct, ils pourrons toujours
me récuser comme incompétent !

Exemples de preuves mathématiques

Nous allons examiner quelques moyens de connaissance. Il y a d'abord les
moyens de perception directe : « Je l'ai vu de mes propres yeux » et c'est
donc là-dessus qu'est basée toute la vérification de la physique, c'est la
méthode expérimentale. Ce n'est pas forcément de vos yeux, peut-être à
travers un instrument. Mais l'idée est là : vous avez une perception
directe du phénomène qui agit sur vous indépendamment de votre volonté. Et
puis, parmi les autres moyens de connaissance, il y a la logique, notamment
le raisonnement et d'autres encore. Il y a toutes sortes de classifications
dans différentes traditions : l'induction, l'analogie, etc.. Les
bouddhistes admettent même un moyen de connaissance disant que si on n'a
pas d'appréhension du phénomène, il n'existe pas. Si le chien n'aboie pas,
il n'existe pas, en quelque sorte.

Nous allons donc déjà examiner la méthode expérimentale et le problème de
sa possible utilisation pour valider un raisonnement mathématique. La
réponse est surprenante, car dans une grande mesure, c'est possible. On
peut vérifier, par l'expérience, le résultat d'une preuve mathématique. Je
vais vous donner un exemple simple : j'ai deux bâtons dans chaque main, et
maintenant, et vidant mes mains sur la table, je fais la somme de tous les
bâtons : 2 + 2 = 4 ; vous pouvez le constater de vos yeux, il y a quatre
bâtons. C'est une preuve tout à fait matérielle qui ne peut pas être mise
en doute. Donc peut-on extrapoler et réduire toutes les preuves
mathématiques à une espèce de démonstration physique complètement
convaincante et existante de l'objet mathématique ? Dans une certaine
mesure, oui.

Je vais maintenant faire un raisonnement mathématique plus compliqué. Je
vais vous montrer qu'il existe un nombre infini de nombres premiers.
Comment procède la preuve ? On raisonne ainsi : imaginons que nous ayons un
nombre premier qui soit maximum, je vais vous donner un procédé pour en
construire un encore plus grand, comme cela, il y en a une infinité. Le
procédé est simple, il marche pour tout entier : vous prenez cet entier,
vous le multipliez par tous ses prédécesseurs (n - 1, etc.), donc vous
fabriquez « factorielle n » et vous lui ajoutez 1. Vous regardez donc ce
grand nombre : par qui est-il divisible ? Il ne l'est ni par 1, ni par 2,
ni par n. Donc soit il est lui-même premier, soit ses diviseurs sont des
nombres premiers qui vont être plus grands que n. Vous avez donc réussi à
exhiber un nombre premier plus grand que le nombre qui était donné comme
défi. Vous voyez, c'est une démonstration moins directe ; dans ce cas, je
n'ai pas de bâtons, je ne vais pas exhiber un grand nombre premier, cela ne
servirait pas mais je vous ai donné un procédé qui, si vous me donnez un
nombre arbitraire, permet alors de calculer un premier plus grand. C'est un
procédé de calcul mécanique, finitiste et c'est de la même essence. Tout
simplement, au lieu d'exhiber directement le résultat, j'ai fabriqué un jeu
à deux joueurs et je vous renvoie donc la question d'une certaine manière,
en disant : « Vous prétendez qu'il y a un nombre fini de nombres premiers,
alors donnez-moi le plus grand. » Vous le donnez, et à ce moment-là, je
calcule le nombre premier. Cela revient donc au même. C'est une
démonstration complètement effective et exempte de doute. Vous vous
demandiez : « Que va-t-il faire ? Il va nous amener un grand sac plein de
nombres premiers et nous dire : Regardez, il y en a une infinité. » Je
n'aurais pas pu faire cela. Je n'aurais pas pu construire un sac infini de
nombres premiers et vous auriez été bien en peine, si je l'avais fait, de
montrer qu'il était infini. Donc en fait, j'ai fait une paraphrase sur la
notion d'infini et je l'ai tournée en ce jeu qui ré-exprime la notion
d'infini, de manière à pouvoir construire la preuve de manière entièrement
finitiste.

Il existe de nombreux procédés de preuve en mathématiques. Par exemple, ce
que nous avons fait à l'instant est de l'arithmétique, mais nous pouvons
également faire de l'algèbre. Par exemple, concernant l'addition, je vous
ai montré que 2 + 2 = 4, mais ceci est un cas particulier d'un résultat
beaucoup plus général qui est que n + m = m + n. On dit que l'addition est
commutative. Alors pour tout m et pour tout n, vous pouvez me donner m et n
et je vais vous calculer n + m et m + n et nous allons voir que c'est la
même chose. Mais vous me demandez un procédé qui va montrer d'un seul coup
toutes ces égalités. C'est donc à cela que sert l'algèbre : pouvoir
exprimer des propriétés universelles ; pour tout n et pour tout m, n + m =
m + n. Ceci est quelque chose qu'on prouve par récurrence. Le procédé de
récurrence vous dit que si une propriété est vraie de 0 et si étant vraie
pour n, elle est vraie pour n + 1, alors la propriété est vraie de tous les
entiers. Donc un raisonnement par récurrence est une sorte de processus
itérateur qui vous donne le moyen de connaître une propriété (ici des
nombres entiers) par un procédé itératif. Et ainsi là, la commutativité de
l'addition va se prouver par une récurrence ou plus exactement, par deux
récurrences emboîtées.

L'autre jour, je zappais sur mon téléviseur et je suis tombé sur
« Questions pour un champion ». Il s'agissait d'une question de
mathématiques. Je me suis demandé ce qu'ils pouvaient bien poser comme
question de mathématiques, alors que dans cette émission, on vous demande
qui a gagné Wimbledon en 1937 ou de donner trois capitales de pays
commençant par K et toutes sortes de savoirs encyclopédiques farfelus ; Je
me demandais s'ils allaient demander si tel grand nombre est premier ou
quelle était la vingtième décimale de pi, et la question était : « Prenez
les cinq premiers nombres impairs, additionnez-les et multipliez par 0,
quel est le résultat ? » J'étais atterré du niveau de connaissances
mathématiques moyen de la population estimé par les meneurs du jeu
« Questions pour un champion » et cela doit donc quelque part refléter une
grave carence de notre société. Imaginer qu'il faille être un champion en
mathématiques pour savoir que zéro annule, cela met la barre assez bas.
J'étais un peu déprimé et je n'y ai plus repensé. Ensuite, en préparant mon
exposé, je me suis dit : mais au fond, cette question était assez maligne,
parce que ceux qui ont voulu faire le calcul ont compté 1 + 3 + 5 + 7...
Ils ont perdu du temps, par rapport à ceux qui étaient plus malins, qui ont
attendu la fin de la question et qui ont tout de suite répondu : « 0 »,
parce qu'ils ont employé l'algèbre, ils n'ont pas fait le calcul, ils ont
employé la règle algébrique : x*0 = 0. La question aurait été totalement
triviale, si on avait demandé 0*x, par la définition de la multiplication,
alors que là, cela demandait justement de connaître cette égalité
algébrique. Il y avait donc une utilisation de l'algèbre comme étant un
raccourci calculatoire, par rapport à la méthode « bébête » qui consistait
à faire tout le calcul. Si je vous pose le problème de la valeur de: « (214
+ 217)* 0 », là il n'est plus question de faire le calcul, il faut le faire
nécessairement par l'algèbre. Le problème était plus malin qu'on pensait.

Je vais vous donner un dernier exemple de preuve mathématique un peu plus
compliquée mais toujours sur les nombres premiers : je vous ai convaincus
qu'il y a un nombre infini de nombres premiers ; pour un nombre premier, il
y en a toujours un qui est plus loin. Mais c'est loin « factoriel n », donc
n'y en a-t-il pas un plus près ? Par exemple, pour un nombre premier donné,
existe-t-il toujours un nombre premier plus grand que lui mais inférieur à
son double ? On peut se poser ce problème-là et essayer déjà si c'est vrai
pour les petits premiers. Vous regardez : 3*2 = 6, oui, il y a 5. Là c'est
bon. 5*2 = 10, oui il y a 7. C'est bon et vous pouvez aller plus loin pour
vous en convaincre mais là, le procédé qui dit : « J'ai essayé avec les
cent premiers nombres premiers et cela marche, donc c'est bon ». Mais ce
n'est pas bon, parce que vous n'avez pas employé