CANAL-U

Texte de la 169e conférence de l'Université de tous les savoirs donnée le 17 juin 2000.

LES FONDEMENTS DES MATHÉMATIQUES

par Jean-Yves Girard

Le formalisme mathématique

Le XIXe siècle est le siècle de la réflexion sur l'analyse – la théorie des fonctions, des dérivées, des intégrales. Un travail impressionnant amène à découvrir, à côté des fonctions « classiques » comme sin x des passagers clandestins : par exemple une courbe sans tangente. Il devient alors nécessaire de se pencher sur la nature des objets mathématiques. C'est à cette question que prétend répondre la Théorie des Ensembles de Cantor, élaborée dans les années 1880, mais qui ne prendra sa forme définitive qu'au début du XXe siècle. La théorie des ensembles permet de reconstruire les nombres réels – utilisés en analyse – à partir des entiers naturels 0, 1, 2, …, qui eux, sont définis à partir de rien, du moins le pense-t-on : ainsi 0 c'est l'ensemble vide.

La Théorie des Ensembles est souvent présentée comme le langage des mathématiques. Rien n'est plus faux : s'il fallait manier les nombres réels en suivant leur définition « ensembliste », on ne pourrait plus résoudre... une simple équation du second degré. Ce qui est vrai par contre, c'est que la Théorie des Ensembles énonce pour la première fois l'unité de principe des mathématiques. Le fait de pouvoir – en principe seulement, mais c'est énorme – ramener toutes les mathématiques à des constructions ensemblistes, nous permet d'utiliser indifféremment des méthodes d'analyse ou d'algèbre – la calcul avec des lettres, des variables, des équations – pour résoudre un problème : elles ne se contrediront pas. Ce qui contraste avec la Physique, constituée d'îlots reliés par des passerelles incertaines[1].

Dans cette entreprise d'unification, un rôle central est dévolu à l’arithmétique – la mathématique des entiers naturels. C'est autour de 1900 qu'apparaît l'Arithmétique de Peano, un des formalismes les plus puissants qui soient.

L'Arithmétique de Peano AP

Nous allons survoler rapidement le Formalisme de Peano, ses termes, propositions, axiomes et règles.

Termes : 0 ; x, y, z... ; St ; t + t' ; t x t'

Ce qui se lit : un terme c'est soit l'expression zéro 0, sinon une variable x, y, z... sinon le successeur St d'un terme, sinon la somme de deux termes t + t’, sinon le produit de deux termes t.t'. Les termes sont la bureaucratie des objets, ici les entiers. Ainsi l'entier 6 sera-t-il représenté par SSSSSS0... Remarquez la touchante régression à la numération prébabylonnienne, 6 c'est 6 bâtons S... c'est ça la modernité !

Propositions : t = t' ; P ; ; ; P => P' ; ;

Ce qui se lit : une proposition est soit une égalité t = t’ entre deux termes, soit la négation d'une proposition, soit la disjonction, soit la conjonction, soit l’implication P => P' de deux propositions, soit une quantification « pour tout » ou « il existe » . Les propositions sont la bureaucratie des propriétés. Exemple : le cas d'exposant 3 du théorème de Fermat (on a écrit au lieu de .

Le fait d'écrire une proposition ne préjuge en rien de sa vérité : pour la bureaucratie formelle, toutes les propositions sont égales en droit, du moins pour le moment.

Axiomes : P => P, x = x...

Ces axiomes logiques sont souvent laissés à l'arbitraire des auteurs. Ils n'énoncent rien de très surprenant ; ce qui est par contre surprenant c'est qu'on puisse en faire quelque chose !

Ce deuxième groupe d'axiomes définit en quelque sorte somme et produit en termes de 0 et S : par exemple un terme clos (sans variable) sera démontré égal à une expression au moyen de ces axiomes. Les deux derniers axiomes sont spéciaux, ils forcent tous les entiers à être distincts.

Règles de démonstration :

Le Modus Ponens est la base de tout raisonnement mathématique : je démontre un lemme P, puis je démontre P => Q – i.e. Q sous l'hypothèse P ; en recollant les morceaux, j'obtiens Q. L'induction est spécifique aux entiers : une propriété vérifiée en 0 et « qui passe au successeur » est vraie pour tout entier. Le raisonnement par récurrence est nécessaire, ne serait-ce que pour démontrer l'équation 0 + x = x. Une démonstration, c'est – en commençant par des axiomes – un enchaînement de règles, de façon à obtenir des théorèmes ; remarquez la précision implacable de la machine.

Mathématiques vs. Informatique

En dépit de certaines prises de position excessives, il est impossible de penser les mathématiques comme une activité purement formelle, bureaucratique : aucune équipe de bureaucrates n'aurait été capable de démontrer le théorème de Fermat en – disons – explorant les possibilités du formalisme Peanien, car il en a fallu des idées pour le démontrer, ce théorème ! D'ailleurs la démonstration automatique – par ordinateur – ne fonctionne pas, et ne fonctionnera jamais, à cause de ces fichues idées[2].

Par contre, les mathématiques sont bien formalisables, ce qui veut dire susceptibles d'être écrites dans un langage formel – mais seulement en principe, pensait-on. Ce qui n'était qu'un vœu pieux au début du XXe siècle est devenu réalité : les ordinateurs sont maintenant capables de vérifier les démonstrations mathématiques. Ça demande beaucoup de travail intelligent de la part du concepteur de logiciel, qui doit interpréter de nombreux raccourcis fulgurants du genre « on voit bien que... », car justement l'ordinateur n'est qu'un cybercrétin qui ne voit rien, ne sent rien, et passe son temps à vérifier les parenthèses fermantes comme d'autres à arracher leurs ailes aux mouches.

L'activité de l'ordinateur est vraiment « formelle », rappelez-vous ces doux messages, « syntax error », ou « UNE ERREUR FATALE EST APPARUE À 0028 :C000BCED DANS LE VXD VMM(01) + 0000ACED » : la précision absolue, sans qu'il y ait de pensée derrière, tels sont les langages informatiques. Le formalisme mathématique est une sorte de langage informatique : on « exécuterait » le langage mathématique en combinant des axiomes et des règles, avec la seule nuance -négligeable pour cet exposé- que le langage informatique est déterministe, -il s'exécute dans un ordre précis- alors que ce n'est pas le cas des mathématiques. Cette analogie est très précieuse, tant qu'on n'oublie pas que le formalisme n'est qu'un aspect des mathématiques.

Venons-y justement, au formalisme, et commençons par les machines, c'est plus facile. Très souvent l'ordinateur se met à mouliner, sans donner la moindre réponse : il calcule, calcule, et n'en sort plus. La question qui se pose (et qui est le problème de base des langages formels) : faut-il attendre, ou faire Ctrl-C, arrêter le programme ? C'est un dilemme vieux comme la ville de Rome : vous attendez le 64 Piazza Venezia, le 64 qui n'arrive pas ; que faire, attendre ou rentrer à pied ? Dans le premier cas on garde intacte la foi, dans le second on a la satisfaction de rentrer chez soi après une petite marche... Question, peut-on détecter la « mise en boucle » de l'ordinateur et donc l'opportunité de faire Ctrl-C ?

La réponse est pleine de bon sens : de même qu'il n'y a aucun service capable de vous dire si le bus finira par arriver, il n'y a aucun moyen de tester la mise en boucle. Une boucle, C'est l'absence d'information à l'état pur, on ne sait rien, mais on pourrait savoir, peut être dans 10 minutes, 10 jours etc. La réponse au problème d'arrêt des programmes est négative. Elle montre la différence de nature entre « ne pas savoir » et « savoir que non ». Cette nuance essentielle sous-tend la partie classique des fondements mathématiques. On la retrouvera sous diverses formes, en particulier la distinction récessif/expansif et le théorème de Gbdel.

La diagonale de Cantor

Dans notre parcours anachronique, retournons en 1880. C'est à ce moment que Cantor, l'inventeur de la Théorie des Ensembles, met au point une machine infernale, que l'on va retrouver dans toutes les questions de fondements... C'est le paradoxe à l'état natif ; à ce propos, rappelons que δόξα peut se lire « dogme, opinion, intuition... » : il y a donc différentes sortes de paradoxe. Celui de Cantor choque certaines intuitions, comme en son temps l'irrationalité de √2.

La question est celle du dénombrement : on sait énumérer les entiers pairs 0, 2, 4, 6, …, une liste infinie d'ailleurs. On saurait faire la liste de tous les programmes dans un langage de programmation donné, par exemple en les rangeant par taille croissante, et à taille égale par ordre alphabétique, mais saurait-on faire une liste de toutes les listes infinies ? La réponse de Cantor, négative, est le célèbre argument diagonal : soient Ll, L2, L3, ... toutes les listes infinies – disons – de zéros et de uns. Désignons par Lm[n] le nième élément de la liste Lm ; on peut alors former une liste M = 1 - Ll [l], 1 - L2 [2], 1 - L3 [3], … , i.e. M[n] = 1 – Ln[n]. Mais M fait elle-même partie de la liste, soit M = LN, et on conclut que LN [N] = M[N] = 1 - LN [N], rideau !

L'expansivité

La question générale qui se pose pour les langages formels est la suivante peut-on traiter les informations négatives ? Par information négative, j'entends une information absente, par exemple quelque chose qui n'a pas été énoncé. Dans les années 1960, des informaticiens peu inspirés ont cru répondre positivement, en prenant l'exemple de ces cases que l'on ne remplit pas, et qui sont interprétées par des options par défaut : la machine verrait qu'on ne répond pas...

C'était aller bien vite en besogne, en négligeant ce petit détail : on ne remplit pas la case, mais on appuie sur la touche Retour, ce qui a pour conséquence de dire à la machine : « je n'ai pas répondu ». Une fois reçu ce message, elle peut continuer, sinon elle attendrait comme un bon toutou. Nous revoilà en train d'attendre un bus, et de retour... au problème d'arrêt. Et c'est justement le paradoxe de Cantor qui permet de démontrer l'impossibilité du « test de mise en boucle », i.e. l'impossibilité de traiter des informations négatives.

Ce type de comportement des langages informatiques, on va l'appeler expansivité : ils sont expansifs, car ils n'acceptent que de l'information positive, et plus on leur en donne, plus ils sont contents, i.e. plus ils nous donnent de réponses : pensez à une recherche de fichiers sur un ordinateur.

Le langage mathématique est expansif pour les mêmes raisons : il accumule les théorèmes, et plus il en a, plus il en produit. Ce n'est pas le cas général, pensez à la médecine : une vérité médicale c'est quelque chose qu'on a pas encore infirmée, voyez le sang contaminé, ou le débat sur les OGM : en médecine la vérité est plutôt récessive, elle s'amenuise avec l'information.

Les paradoxes

Comme nous l'avons dit, il y a plusieurs sortes de paradoxes. Les plus profonds sont les paradoxes de l’intuition, qui souvent résistent à toute tentative de réduction. La courbe sans tangente, ou encore la courbe de Peano qui passe par tous les points d'un carré et qui nous fait douter de la différence entre une ligne et un plan, ce sont de vrais paradoxes de l'intuition.

Mais il y a aussi les paradoxes formels, moins profonds peut-être, mais plus spectaculaires. Ainsi le paradoxe de Russell[3] (1905) produit une contradiction dans la théorie des ensembles naïve[4]. On rappelle que cette contradiction est obtenue en considérant l'ensemble , pour lequel on peut démontrer à la fois que et que. Le principe de logique nous dit d'autre part que d'une contradiction on peut déduire n'importe quoi ce qui brise le ressort du formalisme.

Dès 1900, le grand mathématicien Hilbert propose de démontrer la cohérence (i.e. la non-contradiction) de l'arithmétique AP. Vers 1920, il récidive avec un programme « finitiste » très élaboré, dont nous allons reparler. Il s'agit bien d'une réduction des paradoxes aux seuls paradoxes formels, en négligeant ceux de l'intuition ; il est vrai que les paradoxes formels sont plus graves sur le moment, mais ceux de l'intuition perdurent. C'est un peu comme si l'on menait une guerre en ne nourrissant que le front, sans se soucier de l'arrière...

La récessivité

Drôle d'idée que de démontrer la cohérence des mathématiques par des méthodes mathématiques. C'est comme un Parlement qui voterait sa propre amnistie. Hilbert ne tombe pas tout à fait dans ce panneau : on n'a pas droit à toutes les méthodes disponibles dans AP, seulement à un petit noyau inconstestable ( ?) de méthodes finitistes. Ce n'est pas vraiment le Parlement qui décrète l'amnistie, c'est une commission parlementaire faite de « sages ».

Ce club de sages, c'est essentiellement les propriétés récessives. Il s'agit d'identités universelles, du genre, ou encore.

Par exemple, on pourrait essayer de montrer qu'un théorème a toujours (propriété récessive) un nombre pair de symboles ; si P est démontrable, il a donc un nombre pair de symbole, et sa négation qui en a un nombre impair n'est pas démontrable... Mais c'est vraiment trop naïf !

Le Popperisme

Le philosophe néo-positiviste Popper a repris à son compte et développé les thèses de Hilbert. Selon lui, un énoncé scientifique n'a de valeur que s'il existe un protocole capable – en principe – de le prendre en défaut. Ce qui se justifie à peu près avec les lois de la physique, que l'on vérifie à un certain degré de précision, ce protocole de vérification étant susceptible de prendre la loi en défaut. Cette approche avantage des activités para-scientifiques comme la médecine, le « jusqu'ici ça va » étant l'exemple même de scientificité selon Popper. Il semble tout de même qu'un bon conducteur c'est celui qui connaît son code... et non pas celui qui n'a pas (encore eu) d'accident.

En mathématiques, vérifier à la précision 1/N, c'est vérifier jusqu'à l'entier N, par exemple vérifier pour n < 1010. On voit que le Popperisme mathématique accorde un sens aux seuls énoncés récessifs, tout comme Hilbert. Au fait, la cohérence formelle est une propriété récessive, douée de scientificité selon Popper : on peut la résumer par « jusqu'ici pas de contradiction ». Elle a effectivement un protocole de mise en défaut, la découverte d'une contradiction, qui pourrait en l'occurrence être écrite noir sur blanc, comme c'est d'ailleurs arrivé avec le paradoxe de Russell. Que la cohérence soit récessive ne devrait guère nous étonner : Hilbert n'allait pas refuser toute signification à sa propriété favorite, la cohérence.

La relation entre récessif et expansif est simple : une propriété est expansive quand sa négation est récessive. Exemple « être démontrable »[5] est expansive, alors que « ne pas être démontrable »[6] est récessive.

Le théorème de Gödel

Le formalisme est lui-même un objet mathématique, remarque Hilbert dès 1904. Cela vient de la rigueur implacable des langages formels ; de plus cette remarque est une pièce essentielle du programme de Hilbert, qui veut utiliser des moyens mathématiques pour arriver à ses fins.

Bizarrement il faut attendre 1931 et le logicien G6del pour que cette remarque soit vraiment prise au sérieux :

- Les objets du formalisme de AP, termes, propositions, sont représentés par des nombres de Gödel : . « Banale » énumération des propositions, dans laquelle certains ont voulu voir des significations cachées, quasi-numérologiques. Enfin, pas si banale que ça si on pense aux difficultés techniques auxquelles s'est heurté Gödel à l'époque.

- Les propriétés du formalisme sont représentées par des propositions de l'arithmétique de Peano AP, ainsi « P est démontrable » devient, tandis que « AP est cohérente » devient CohAP. Ces propositions n'ont pas de sens arithmétique immédiat.

Un recyclage somme toute assez facile de la diagonale de Cantor permet alors de produire une proposition G qui est littéralement, i.e. sa non-prouvabilité. S'achemine-t-on vers une nouvelle version du paradoxe du menteur « Je mens » et donc vers une contradiction de AP ?

Non : rien ne nous dit que vérité et prouvabilité coïncident, et alors « Je ne suis pas prouvable » ne veut plus dire « Je ne suis pas vrai ». En regardant de près, il y a une seule possibilité de s'en sortir, i.e. de préserver la cohérence de AP : c'est que G soit vraie, auquel cas elle n'est pas prouvable. C'est ce qu'on appelle le premier théorème d'incomplétude.

Un travail pervers de... formalisation du premier théorème mène au second théorème : on peut prendre pour proposition vraie, mais non prouvable, la proposition CohAP qui exprime la cohérence de AP : « Si AP est cohérente, elle ne prouve pas sa propre cohérence ».

Il importe de remarquer que G, tout comme CohAP sont récessives, mais non prouvables. Par contre la prouvabilité de G, comme celle de CohAP est expansive. G, CohAP ne sont donc pas équivalentes à leur prouvabilité : c'est la distinction entre récessif et expansif, c'est la différence entre ne pas savoir et savoir que non, entre ne pas pouvoir démontrer et démontrer que non. On en est toujours au problème d'arrêt, en résumé :

Négations et négationnistes

Un tel résultat ne vous vaut pas beaucoup d'amis. Les réactions au théorème de Gödel furent vives, et presque toutes de nature négative, voire négationniste.

Commençons par ceux produisent régulièrement des réfutations du théorème de Gödel. C'est compatible avec une certaine vision du Popperisme, pour laquelle tout est faux, il suffit d'attendre, tous des pourris d'ailleurs... Une réfutation du théorème de Gödel – par ailleurs démontré – induisant une contradiction dans AP, on voit que ces personnes – au demeurant particulièrement stimulées par le millésime 2000 – ne cherchent rien d'autre qu'à démolir cet échafaudage prétentieux, les mathématiques. La réfutation du théorème de Gödel, c'est leur « gaz sarin » à eux. Mais vous pouvez dormir sur vos deux oreilles, car n'est pas le Capitaine Némo qui veut...

D'ailleurs qui réfute le théorème le renforce : en effet AP devient contradictoire, mais le théorème c'est « si AP est cohérente... », et comme du faux on déduit n'importe quoi... Ce théorème est insubmersible ! En particulier, il n'y a aucun protocole susceptible de le mettre en défaut ; il n'aurait donc aucune scientificité si on suit Popper... à moins que ce ne soit le Popperisme qui manque d'envergure !

Après les clowns, les nostalgiques de la solution finale -pour reprendre cette expression typique du scientisme allemand- du problème de la cohérence. Là c'est plus tordu, on salue en Gödel le plus grand logicien de tous les temps, on monte en épingle les bizarreries des nombres de Gödel, on en fait une espèce de super-puzzle. Cet ensevelissement sous les fleurs est caractéristique de ce monument de vulgarité « Gödel-Escher-Bach ». Le message implicite est clair, le théorème de Gödel est un résultat artificiel, contre nature, qui ne peut altérer la marche triomphante de la science positive.

Pourtant il est bien simple ce théorème. Il dit que le Parlement ne peut pas se faire amnistier par une sous-commission, même pas par lui-même : il faut au moins qu'il s'adjoigne des membres extérieurs, n'est-ce pas le bon sens ? Ou encore, qu'on ne peut pas revisser ses lunettes en les gardant sur le nez.

Évidemment ce n'est pas tous les jours que le bon sens peut s'exprimer de façon aussi radicale. Mais il faut bien dire que Hilbert avait tendu une sacrée perche en cherchant une solution formelle au problème de la cohérence. En fait le formalisme se réfute lui-même par saturation de simplifications scientistes : démontrer la cohérence dans les mathématiques. Vous l'avez voulu, Georges Dandin !

Le post-Gödelisme

Ce qui est le plus critiquable dans l'idéologie formaliste, c'est ce rôle central tenu par la cohérence. Comme le faisait remarquer le logicien Kreisel, qui a beaucoup oeuvré contre les abus du formalisme : « Les doutes quant à la cohérence sont plus douteux que la cohérence elle-même ». D'autre part il y a tant et tant de théories cohérentes sans le moindre intérêt qu'on ne voit pas la raison de s'obnubiler sur cet aspect relativement marginal des formalismes. D'ailleurs que dirait-on d'un contrôle technique des véhicules qui ne s'intéresserait qu'à une seule question, la bonne marche du moteur, et qui laisserait passer des voitures sans direction, sans freins ?

La cohérence, malgré tous les efforts de réflexion, reste un sujet hautement idéologique : « Je sais qu'une démonstration de cohérence de ZF n'a pas de valeur, mais ça me rassurerait d'en voir une. »[7] Rassurer contre quel danger et par quelles méthodes ? Au même titre que ce produit indémodable, l'assurance contre l'explosion de la Terre. Alors il n'est pas étonnant qu'on cherche toujours à prolonger le programme de Hilbert, quitte à le replâtrer un peu.

Ce qui est le plus étonnant, ce n'est pas tant ce besoin de croire des épigones de Hilbert, mais la réussite paradoxale de certains travaux, comme ceux de Gentzen dans les années 1930. Conçus en vue d'un replâtrage du programme de Hilbert, ils n'ont rien replâtré du tout. Par contre, ils ont amené – mais beaucoup plus tard, disons après 1970 - un renouveau de la problématique des fondements.

Comment relisons-nous Gentzen de nos jours ? Son travail, qui porte sur l'étude de l'interaction entre une preuve de P et une preuve de (en cas de contradiction), se traduit informatiquement en l'interaction entre un programme (correspondant à la preuve de P) et son environnement (correspondant à la preuve de ), typiquement entre un argument et une fonction. C'est ce qu'on a appelé le paradigme de Curry-Howard (~1970).

Ces idées devaient être raffinées au moyen de la logique linéaire (~1985), qui introduit une symétrie entre le programme et son environnement. La nouveauté par rapport à la logique ancienne (dite maintenant classique) est qu'il s'agit d'un point de vue procédural (la logique linéaire ne réfère à ses propres procédures) et non plus réaliste (la logique classique réfère à une « réalité » externe).

La ludique ou l'extinction du Popperisme

La logique linéaire explique les mathématiques de façon ludique, comme une espèce de jeu.

Deux machines discutent en vase clos. Chacune peut choisir un dessein, i.e. un programme qui « teste l'autre ». Alors

Consensus : Soit au bout d'un moment l'une des deux finit par jeter l'éponge.

Dissensus : Soit elles se chamaillent à l'infini.

Nous dirons que ont des comportements duaux quand ne se permet que les desseins « consensuels » avec les desseins de et vice-versa.

correspond à l'interprétation procédurale suivante : pour tout test dans, c'est moi qui ai (avec le dessin que j'ai choisi) le dernier mot dans l'interaction. Ça ressemble à du Popperisme, passer une infinité de tests, mais ce n'en est pas. En effet, quels sont donc ces tests de ? Ce sont ceux pour lesquels il n'y a pas dissensus (i.e. récusation) avec un dessein de ; a dans sa besace d'autres desseins qui ne sont pas là pour avoir le dernier mot, seulement pour récuser certains tests embarrassants. La nouveauté par rapport au Popperisme, c'est donc que la notion-même de test est testable, ce qui permet de sortir du carcan récessif/expansif. On peut en principe donner un sens interactif à toutes les mathématiques courantes.

Les desseins sont des sortes de démonstration dans laquelle on se permet une erreur de logique, très volontaire : le daimon , celui qui jette l'éponge, celui qui n'attend pas le bus ; c'est une espèce d'axiome sauvage. Les mathématiques s'expliqueraient finalement hors de toute réalité externe, par une interaction entre objets (les desseins) de même nature, une dualité moniste.

[1] Bourbaki a introduit le néologisme la Mathématique dans le même esprit il faudrait dire les Physiques.

[2] Le premier théorème d'incomplétude est une réfutation de la démonstration automatique.

[3] Bertrand Russell qui s'est illustré dans bien d'autres domaines.

[4] Théorie corrigée depuis en la théorie ZF de Zermelo-Fraenkel.

[5] Et rappelons-le « le bus arrive ».

[6] Ainsi que « le bus ne viendra pas ».

[7] Propos tenus par le logicien formaliste K. Schütte à l'auteur, 1972.