David Madore's WebLog

2009-11-23 (lundi)

Logicomix, et faut-il 350 pages pour prouver 1+1=2 ?

Bertrand Russell est un de mes héros (ou quelque chose de ce genre), et comme je m'intéresse à l'épistémologie des mathématiques, il était logique que je sois au moins intrigué par l'idée d'une bande dessinée dont le principal personnage est Bertrand Russell et dont le thème est la quête des fondements des mathématiques. C'est peut-être surprenant, mais cette BD existe (pour l'instant seulement en anglais) : elle s'appelle Logicomix ; ses auteurs sont grecs, et l'un d'entre eux, Christos Papadimitriou (enfin, Χριστος Παπαδημητριου), chercheur en informatique à Berkeley, m'était d'ailleurs connu comme auteur de plusieurs bons ouvrages sur la théorie de la complexité algorithmique : j'ai été assez étonné de le savoir co-scénariste de cette BD. (Un autre des auteurs est connu pour un roman intitulé Oncle Petros et la Conjecture de Goldbach dans sa traduction française.) Bref, comme un effet Zahir assez peu surprenant fait que j'ai entendu parler plusieurs fois de Logicomix (et en bien !) ces dernières semaines je l'ai achetée.

On aura compris que je la recommande, mais il faut que je précise bien quelque chose : ce n'est pas une BD sur les mathématiques, et ce n'est donc pas en tant que mathématicien que je la recommande (d'ailleurs, en tant que mathématicien, j'ai plutôt quelques reproches à lui faire). Je la recommanderais aussi bien à ma maman, si ma maman aimait les BD. Il ne s'agit pas d'un livre portant sur la logique, donc, mais sur l'histoire de la logique ou plutôt, un chapitre particulier de l'histoire de la logique qui est celui des fondements des mathématiques. Les héros s'appellent Russell, Whitehead, Frege, Cantor, Hilbert, Poincaré, Wittgenstein et Gödel : même si de très brefs passages sont employés à expliquer sommairement une ou deux idées essentielles de logique, de mathématiques ou — comme on se l'imagine avec l'apparition de Wittgenstein dans la liste des personnages — de philosophie, ce n'est pas du tout le propos. Le propos est plutôt d'expliquer ce qui a motivé cette quête des fondements, comment Russell l'a personnellement vécue, et en particulier comment les Principia Mathematica ont été écrits (et le Tractatus Logico-Philosophicus). La dimension humaine est essentielle, par exemple sur l'opposition de Russell à la guerre ou la perte de sa foi, mais surtout dans deux idées : la logique comme façon d'éviter la folie, et la quête des fondements sous forme de mythe de Sisyphe avec quoi les protagonistes n'en ont jamais fini. Ce n'est pas non plus une biographie de Russell (ne serait-ce que parce que ça s'arrête, comme ça commence, en fait, en 1939, donc son engagement contre la guerre du Vietnam n'est pas mentionné). Et évidemment, on pourrait redire des choses sur l'exactitude historique (notamment de la thèse sur la folie des logiciens : par exemple, le fait que Cantor soit devenu fou est d'une part un peu exagéré, et d'autre part sans rapport avec son activité mathématique). Mais assez parlé de la BD elle-même.

⁂ Les Principia Mathematica sont peut-être bien le livre le plus abscons[#] de l'univers. Non seulement c'est de la logique formelle aride au possible, mais en plus les notations ne sont plus du tout celles qu'on utilise de nos jours (par exemple, l'ensemble vide — enfin, la classe vide — est noté par un lambda majuscule, un système de points est utilisé là où nous mettrions des parenthèses, le et logique est aussi noté par un point et l'implication par un symbole ⊃), sans même compter les notations spécifiques de l'ouvrage, les abréviations qu'ils utilisent pour « alléger » les démonstrations ou la numérotation un peu déroutante ; et, évidemment, les fondements des mathématiques ont évolué depuis cette première tentative. Que le lecteur non-mathématicien s'imagine donc que la page reproduite ci-contre (et on pourrait en trouver de bien pires) est aussi imperméable à 99% des mathématiciens qu'elle l'est à lui. Il est suggéré dans la BD (je ne sais pas si Russell a vraiment émis cette opinion) que la seule personne qui ait lu le texte était Kurt Gödel ; et, de fait, les Principia sont sans doute autant célèbres pour le fait que c'est sur ce système que Gödel a initialement fondé son théorème d'incomplétude que pour être la première axiomatisation parfaitement rigoureuse de ce qui pourrait en théorie englober l'ensemble des mathématiques.

Par contre, il est vrai que la proposition énoncée sous le numéro *110·643 en haut de la page que je reproduis signifie bien ce qu'elle semble signifier : 1+1=2 (et le commentaire qui suit la démonstration est succulent : the above proposition is occasionally useful). Cette proposition intervient à la page 83 du second tome des Principia (dans la seconde édition), sachant que le premier tome comporte lui-même quelque chose comme 680 pages[#2]. Cela a valu aux Principia une renommée particulière, celle d'être le livre qui prend énormément de pages pour montrer 1+1=2 ; le énormément est parfois placé dans les 350, parce que la proposition *54·43, qui dit essentiellement que si deux ensembles ont chacun un élément et sont disjoints, alors leur union a deux éléments, est située page 362 du premier tome — ou 360 ou 379 selon les éditions — et suivie du commentaire : From this proposition it will follow, when arithmetical addition has been defined, that 1+1=2.

Ceci a malheureusement donné naissance au mythe selon lequel, en logique formelle, pour prouver quelque chose d'aussi évident que 1+1=2, il faut des centaines et des centaines de pages. C'est faux pour plusieurs raisons. D'abord parce que Whitehead et Russell n'avaient pas pour but d'arriver à cette proposition de la façon la plus rapide possible (même dans leur système on aurait pu faire ça de façon beaucoup plus économique). Ensuite, parce que leur système semble impossiblement compliqué aux yeux d'un logicien mathématique moderne[#3] : il est vrai qu'on ne cherche plus tellement à produire des systèmes qui fondent « toutes les mathématiques », mais même dans la mesure où on en choisit un, on peut espérer que la démonstation de 1+1=2 ne sera pas immensément compliquée (s'agissant de ZFC, le système orthodoxe pour fonder les mathématiques, la difficulté sera surtout d'écrire 1+1=2, c'est-à-dire, de définir qui sont ce ‘1’, ce ‘2’ et ce ‘+’ qui interviennent dans cette affirmation ; une fois cela fait, l'énoncé devrait sans doute être assez évident). J'avais lu quelque part un texte qui se voulait un peu sensationnaliste sur la longueur des démonstrations en logique formelle (où il concluait qu'il faudrait des quadrilliards de symboles pour démontrer le théorème des nombres premiers ou je ne sais quoi de ce genre) ; mais j'avais fini par me convaincre que l'auteur parlait probablement de démonstrations dites sans coupures (ce qui signifie, en très très gros, sans utiliser de lemme ou proposition intermédiaire ou quoi que ce soit de ce genre, mais en réécrivant à chaque fois la démonstration complète de ce qui aurait tenu lieu de lemme) : s'il y a des moyens d'éliminer les coupures dans une démonstration, ce moyen fait exploser la taille des démonstrations, c'est même un fait essentiel de la logique, et personne ne veut lire une démonstration sans coupures du théorème des nombres premiers ou même de 1+1=2.

[#] D'accord, on peut toujours trouver pire. Finnegan's Wake, par exemple ? Alors, pour lancer un petit troll, disons que les Principia sont peut-être bien le livre le plus abscons parmi ceux qui ont un sens. (Plusieurs trolls, d'ailleurs : sur le fait de savoir si Joyce écrivait du pur charabia, et sur celui de savoir si de la logique peut avoir un sens ou autres questions qui auraient irrité Wittgenstein.)

[#2] Enfin, la proposition de loi sur la réforme du healthcare aux États-Unis fait autour de 2000 pages : je ne sais pas ce qui est le plus impressionnant, en fait.

[#3] La théorie ramifiée des types de Russell est assez éloignée de la façon dont on conçoit, de nos jours, les fondements des mathématiques (depuis que Zermelo a convaincu tout le monde de l'opportunité d'une théorie purement du premier ordre, avec une seule sorte d'objets — les ensembles). Pour un point de vue moderne sur la théorie de Russell (et son rapport avec les théories modernes), voir ce texte de Harvey Friedman ; cet article n'est pas mal non plus, pour remettre les choses dans le contexte et expliquer ce qu'est l'axiome de réductibilité.

Commentaires

2009-11-13 (Friday)

Gratuitous Literary Fragment #124 (the Trinity)

What the Christian Trinity means is fairly evident to anyone—anyone except Christians, that is. It is the divine family: a family comprising the Father, the Son and, plainly, the Mother. The all-male clergy mustn't have liked the idea of worshipping a goddess, and indeed now the very word sounds pagan; so about the time when they were busy making up the Nicene creed and kicking Arius and other heretics out of the Church, they managed to seemingly remove the Mother-of-God from the divine Trinity and replace Her with a placeholder, the Holy Ghost. Nobody knows what that Holy Spirit is supposed to be: obviously, as a hypostase, it was just fabricated from a few vague references in the Gospels where the phrase is used as a propitiatory saying when baptising (the blasphemy against the Holy Ghost shall not be forgiven unto men). The real third member of the Trinity, in fact, the most important member of the Trinity, is the Mother. No religion is originally without a female deity. Already the Jews had been deft in suppressing or disguising references to the mother-goddess Asherah, consort of El, in the Torah, though Genesis 1:27 still says that Elohim (אֱלוֹהִים—grammatically plural) created man and woman in their image. Some Protestant branches adore only Jesus and were thus quite successful in extinguishing mariolatry; the Eastern Orthodox churches followed a similar route. But the Catholics? For them, the removal was only seemingly achieved. For they don't pray to the Father—they don't even so much pray to the Son: they pray to the Mother-of-God, and visiting any staunchly Catholic country makes it completely obvious who the third and highest part of the Trinity is: just count the number of Santa Maria this and that. But those are only the dominant sects. Many more must have worshipped the Trinity as it originally stood. In fact, the point is made black on white in the Qur'an (sura 5 verse 116, يٰعِيسَى ٱبْنَ مَرْيَمَءَ أَنْتَ قُلْتَ لِلنَّاسِ ٱتَّخِذُونِي وَأُمِّيَ إِلٰهَيْنِ مِنْ دُونِ ٱللّٰهِ): Christians are accused of being tritheistic because the have put two other Gods beside Allah—Jesus and his Mother. The Qur'an may be mistaken about many things, but on this count it is clearly right.

Je reconnais avoir totalement plagié, en écrivant ça, la thèse que quelqu'un, que je ne dénoncerai pas, m'a tenue récemment (et presque ses paroles, d'ailleurs), même si j'ai complété avec une explication que quelqu'un d'autre m'a faite sur un sujet proche. Dans l'ensemble, considérez que toutes les idées intéressantes ne sont pas de moi et que toutes les erreurs, par contre, ont été ajoutées par moi. (Je trouve l'idée intéressante, même si je ne suis pas complètement convaincu qu'elle soit historiquement si correcte.)

Comments

2009-11-09 (lundi)

Discours de commémoration du 9 novembre

Klaus Wowereit, Nicolas Sarkozy, Dmitrij Medvedev, Gordon Brown, Hillary Clinton (et par écran interposé, Barack Obama), et évidemment Angela Merkel, ont chacun fait un petit discours pour commémorer le 20^e anniversaire de la chute du mur de Berlin[#]. Je trouve qu'ils ont tous été très mauvais. Je ne fais pas référence au fait que le contenu des discours sont convenus au point d'en devenir totalement vides : cela fait partie des règles de l'exercice pour une commémoration, ce serait presque une faute de goût de vraiment dire quelque chose en une telle occasion, et les gens qui se plaignent que c'est creux sont des ignares qui ne savent pas apprécier l'art rhétorique pour ce qu'il est censé être… Mais le but est de faire au moins des phrases jolies et bien tournées (avec la difficulté supplémentaire qu'il ne faut ni dire la même chose que le voisin, ni froisser le président russe en donnant à l'URSS un mauvais rôle), et les dire avec une voix qui fait rêver. On pourrait croire qu'avec le staff que ces gens-là ont, l'un d'eux aurait su produire quelque chose à la hauteur : eh bien non, même en tenant compte des pertes à la traduction simultanée, aucun d'eux n'a rempli son contrat. Même pas Obama, qui est pourtant en général un orateur extraordinaire.

Voici à quoi ressemble un vrai discours, prononcé par quelqu'un qui parle très bien : je suis surpris qu'on n'y ait pas fait la moindre référence, d'ailleurs. Ou même celui-ci dont, quoi qu'on puisse penser de son auteur et de ses idées (et de la thèse que ce discours précis a constribué à la chute de ce mur), il faut reconnaître qu'il est par moments rhétoriquement remarquable.

Je crois que j'aurais préféré entrendre les aînés parler, en fait (mais je n'ai trouvé ni enregistrement ni transcription de cette conférence). Je soupçonne qu'ils sont plutôt meilleurs. (Quoique, finalement… le 9 novembre 1989, ce jour-là non plus, personne n'avait été capable de produire un discours convenable.)

[#] Je sais que 20 est un nombre plus rond que 15, et je sais qu'on est toujours embarrassé (en ce jour qui est, entre autres anniversaires, celui de la proclamation de la république de Weimar) par le souvenir de la Nuit de Cristal du 9 novembre 1938, mais je suis épaté par les kilos qu'on en fait cette semaine alors qu'il y a cinq ans il n'y avait vraiment rien eu du tout.

Commentaires

2009-11-09 (lundi)

Déploiement policier

Mon poussinet et moi étions attablés, hier, à un café au croisement des Gobelins, vers le milieu de l'après-midi, quand des policiers ont coupé le boulevard Saint-Marcel (celui qui était devant nous) et neutralisé les Gobelins, et nous avons vu passer, en plusieurs convois, un nombre incroyable de forces de l'ordre (des policiers et des gendarmes, en nombre à peu près égal) : j'estime, même si c'est difficile d'être précis, qu'il devait y en avoir un bon millier (l'ordre de grandeur au moins est bon : cinq convois d'environ 25 véhicules chacun, avec probablement autour de huit policiers ou gendarmes par camionnette). Curieux de savoir quelle manifestation monstre (nous n'avions entendu parler de rien) pouvait nécessiter le déploiement d'autant de troupes, nous avons remonté les Gobelins (qui étaient, donc transformés en parking pour forces de l'ordre comme, nous l'avons vite vu, toutes les autres voies menant à la place). Arrivés place d'Italie (complètement coupée à la circulation), nous découvrons la cause de toute cette agitation : un rassemblement, en effet, qui avait l'air d'être d'un mouvement de sympathie pour les sans-papiers (ils n'avaient quasiment aucune banderole, et guère qu'un haut-parleur qu'on comprenait mal). À tout casser : deux cents personnes sur la place, et encore, je dois compter les badauds en disant ça. Cinq fois plus de policiers plus gendarmes, donc.

Je ne sais pas combien ça coûte, de mobiliser tous ces hommes (un dimanche, qui plus est), et je ne sais pas quels sont les coûts indirects à couper tous les grands axes d'un quartier (boulevard Saint-Marcel, avenue des Gobelins, boulevard de l'Hôpital, boulevard Vincent Auriol, avenue d'Italie, boulevard Blanqui), fût-ce le week-end, mais, même si je n'aime pas jouer les grincheux du combien ça coûte au contribuable, c'était du délire complet pour seize douzaines de péquenots. Soit quelqu'un aux RG a mal prévu le coup et j'espère qu'il va se prendre un bon coup sur les doigs, soit le délire de surencadrement policier de la moindre manifestation a été poussé encore plus loin que son hyperbole habituelle.

Commentaires

2009-11-02 (lundi)

De quoi parlent les mathématiques ?

Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. (Les mathématiques peuvent être définies comme la discipline dans laquelle on ne sait jamais de quoi on parle, ni si ce qu'on dit est vrai.) — Bertrand Russell (Recent Work on the Principles of Mathematics)

Je vais peut-être décevoir (ou au contraire rassurer ?) mon lecteur en avouant que je n'ai aucune intention d'essayer de répondre à la question qui sert de titre à cette entrée ; je vais tout au plus essayer de vulgariser un élément de réponse à une minuscule partie de cette question (ou d'une question proche), sur laquelle on peut dire des choses « techniquement » (c'est-à-dire : logiquement) précises. C'est déjà tout un programme.

La plupart des mathématiciens (et même si ce n'est pas vraiment mon avis, je dois reconnaître qu'il est très répandu) conviendront que l'activité d'un mathématicien est de produire des théorèmes et des démonstrations. Par opposition, disons, aux définitions, exemples ou conjectures, qui forment certainement aussi une partie importante de l'activité en question, mais à laquelle l'opinion dont je parle attribue moins d'importance ou de dignité. Une démonstration est un argument logique plus ou moins formel qui suit certaines règles codifiées pour partir d'axiomes ou d'hypothèses et arriver à une conclusion : un énoncé qui est la conclusion d'une démonstration (connue !) est un théorème (ou une proposition, un lemme, un corollaire, selon sa difficulté, son importance et sa relation logique ou didactique à d'autres énoncés du sujet en cours de développement). Les règles du raisonnement, un peu comme celles des scolastiques d'autrefois (barbara, celarent, darii, ferio), sont supposées assez évidentes pour qu'on doute assez peu qu'elles préservent la vérité lorsqu'elles sont correctement appliquées : si les hypothèses de la démonstration sont vraies alors la conclusion l'est aussi ; donc, tout théorème produit à partir d'axiomes vrais est également vrai.

Mais quels sont les axiomes ? Un certain consensus, apparu au cours du XX^e siècle, et maintenant assez fermement enraciné dans, disons, le dogme officiel des mathématiques, est que les axiomes qui fondent les mathématiques sont ceux de la théorie des ensembles de Zermelo-Fraenkel (en abrégé ZFC : le ‘C’ précise l'inclusion de l'axiome du choix, qui n'est pas du tout ce dont j'ai envie de parler à présent), les règles de raisonnement étant celles de la logique du premier ordre. Autrement dit, sauf mention explicite du contraire, ce qu'un mathématicien appelle théorème est un théorème de ZFC, et sa démonstration pourrait être rendue complètement formelle (une manipulation syntaxique fondée sur des règles de réécritures à partir des axiomes de ZFC pour arriver à ce théorème comme conclusion). C'est du moins le dogme officiel parce que, dans la pratique, beaucoup de mathématiciens non logiciens seraient probablement incapables de citer les axiomes de ZFC (ou de d'expliciter les règles de raisonnement de façon formelle et automatique) ; et la tâche d'expliciter complètement la démonstration de n'importe quel théorème modérément compliqué à partir des axiomes fondamentaux et en suivant les règles mécaniques est au mieux titanesque (même si les progrès de la vérification formelle ont montré qu'on pouvait arriver à des choses). Mais le dogme a le bon goût d'éviter des discussions sur les fondements des mathématiques que beaucoup de mathématiciens trouvent oiseuses ; il asseoit les mathématiques sur des bases solides et non dénuées d'élégance (et où, par exemple, la notion d'infini n'a plus rien de mystérieux ou de précaire) :

Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können. (Du paradis que Cantor nous a créé, nul ne doit nous chasser.) — David Hilbert (Über das Unendliche)

Les théorèmes mathématiques habituels (c'est-à-dire, en excluant pour l'instant des mathématiques tout ce qui est trop près de la logique) portent sur des objets comme les groupes, les anneaux, les espaces topologiques, les variétés différentiables, les fonctions de la variable réelle, les espaces de Banach, que sais-je encore, et, bien sûr, les entiers (disons, les entiers naturels). Bizarrement, aucun de ces objets n'« existe » dans ZFC : la seule chose (le seul type d'objet) que ZFC connaît, ce sont des ensembles. (Un ensemble est un objet mathématique très simple : il contient des objets, appelés ses éléments : il ne retient de chaque élément possible que sa présence ou son absence dans l'ensemble — il ne peut pas y avoir plusieurs fois le même élément dans l'ensemble.) Les éléments des ensembles considérés par ZFC sont eux-mêmes des ensembles, dont les éléments sont eux-mêmes des ensembles, et ainsi de suite (et un des axiomes de ZFC, l'axiome de régularité ou axiome de fondement, affirme qu'à jouer au petit jeu de passer de façon répétée d'un ensemble à un élément de celui-ci, en un nombre fini d'étapes on aboutit toujours à l'ensemble vide qui n'a plus d'éléments et qui met donc fin au jeu). Tout autre objet mathématique (groupe, entier naturel, nombre réel, faisceau étale) doit être pour ainsi dire « codé » comme un ensemble, ce codage n'étant pas très différent dans son esprit de celui qui vaut dans un ordinateur et qui fait qu'une page Web, une image ou une musique est représentée, au final, par une suite de 0 et de 1 : quelque part, se demander quels sont les éléments du nombre réel π (puisqu'il doit être codé comme un entier) est à peu près aussi intéressant ou intelligent, comme question, que se demander quel est le premier bit (0 ou 1) de la 5^e symphonie de Beethoven. L'avantage du codage, toutefois, c'est que ZFC n'a pas à s'embarrasser à connaître toutes les notions farfelues que les mathématiciens inventent : il ne connaît que les ensembles, tout le reste est écrit sous forme de définitions préalables aux théorèmes.

Ce codage (et donc, ce dogme orthodoxe selon lequel toutes les mathématiques sont écrites dans le langage de ZFC ; ou en tout cas, l'illusion que ce dogme est suivi) a au moins deux inconvénients. Le premier, c'est qu'il est au moins intellectuellement insatisfaisant de penser qu'un théorème qui devrait porter sur la structure algébrique, disons, du groupe de Mathieu est, en fait, écrit sur un codage particulier et accidentel de ce groupe comme un ensemble : les ensembles ont juste ceci pour eux que c'est la structure de données (pour parler de nouveau comme un informaticien) la plus simple qui permettait de coder toutes les mathématiques, mais cette structure est assez déconnectée de celle à laquelle on s'intéresse vraiment. Le second inconvénient, c'est que les ensembles apportent leurs subtilités logiques dont on ne voudrait peut-être pas, et que, finalement, ZFC est beaucoup trop fort pour faire toutes les mathématiques usuelles. Je vais essayer d'expliciter.

⁂

Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk. (Les entiers ont été faits par Dieu, tout le reste est l'œuvre de l'homme.) — Leopold Kronecker (cité par Heinrich Martin Weber)

La majorité des mathématiciens (et peut-être de tous les gens qui comprennent la question) conviendront probablement qu'un énoncé portant uniquement sur les entiers naturels, un énoncé arithmétique, par exemple pour tout entier n≥3, les seules solutions de xⁿ+yⁿ=zⁿ avec x,y,z entiers sont celles où l'un de ces trois nombres est nul, a un sens bien défini, et donc qu'il est vrai ou faux. (Techniquement, par énoncés arithmétiques je veux parler d'énoncés en logique du premier ordre et dans le langage de l'arithmétique — avec, disons, les opérations + et ×, l'exponentiation pouvant se définir au prix d'un petit travail.) Bref, il s'agit d'une certaine forme de platonisme : l'idée, au moins atténuée, que les entiers naturels existent réellement, et qu'il y a un sens à se poser des questions, même si on ne peut pas forcément y répondre, portant sur une infinité d'entre eux, tant que ces questions sont mathématiquement bien formulées. (J'ai déjà ranté à ce sujet, d'ailleurs.) Il y a sans doute aussi des gens qui objecteront que la question de savoir si le 10↑(10↑(10↑100))-ième nombre premier se termine par 1, 3, 7 ou 9, bien qu'il s'agisse d'un énoncé arithmétique et même complètement fini, est une question dénuée de sens puisque jamais personne ne pourra mener le calcul, mais ces gens sont rarement mathématiciens, et je soupçonne les quelques mathématiciens qui soutiennent ce genre de thèses de le faire plus par provocation que par conviction (si on refuse l'idée qu'une infinité d'entiers naturels existe réellement, je me demande comment on explique le hasard faisant que x×y, aussi loin qu'on pousse le calcul expérimentalemnt, a toujours l'air de valoir y×x, et je me demande comment on peut faire des mathématiques).

En revanche, pour un énoncé portant non plus sur les entiers mais sur les ensembles (ou, du coup, tout ce qui peut être codé avec eux, c'est-à-dire, tout), l'idée qu'il existe un vrai intangible sur ces concepts est plus douteuse. On sait, par exemple, que ZFC ne résout pas la question suivante : tout ensemble de nombres réels peut soit être mis en correspondance avec (c'est-à-dire, a “autant” d'éléments que) tous les nombres réels soit avec un ensemble d'entiers. Même si le consensus parmi les théoriciens des ensembles est maintenant qu'il est préférable de considérer cet énoncé (l'hypothèse du continu) comme faux, la question de savoir s'il est « vraiment » faux (sic !) est une question plutôt dénuée de sens : la situation est plutôt quelle sorte d'ensembles on veut considérer, quelle sorte d'ensembles est souhaitable, quelle sorte d'ensembles (Menschenwerke) se comporte bien pour les mathématiques qu'on veut faire. Un peu comme la question du cinquième postulat d'Euclide : ce dernier est vrai sur le plan mais faux sur la sphère, donc la question de savoir s'il est vrai ou faux n'a pas lieu, ce qui faut se demander est si on veut faire de la géométrie plane, de la géométrie hyperbolique, de la géométrie sphérique (ou encore autre chose). On peut choisir de faire de la théorie des ensembles avec l'hypothèse du continu, ou sans (et dans ce cas, avec éventuellement telle ou telle autre hypothèse pour la remplacer). En revanche, s'agissant des entiers naturels, on a l'impression qu'on n'a pas une telle liberté : s'il y a des énoncés sur les entiers naturels que ZFC ne tranche pas (et il y en a forcément, je vais y venir), on n'a pas la liberté de considérer tels entiers naturels plutôt que tels autres — parce que les entiers naturels ils sont censés vraiment exister, pouvoir être écrits, au moins théoriquement et conceptuellement, avec un stylo sur un papier. Dans le langage de Kronecker, Dieu les a créés, nous n'avons pas le pouvoir de les choisir ; de façon moins théiste, il existe un modèle privilégié de l'arithmétique (peut-être lié à l'univers physique dans lequel nous vivons, d'ailleurs).

⁂

On pourrait être tenté d'en conclure qu'au lieu de faire de la théorie des ensembles on devrait faire de l'arithmétique. Il existe un système formel censé codifier l'arithmétique : ce sont les axiomes de Peano (ou l'arithmétique de Peano, ici je parle de la théorie du premier ordre). Il est beaucoup moins évident d'imaginer comment coder les théorèmes mathématiques parlant d'objets sophistiqués en termes d'entiers naturels qu'en termes d'ensembles, mais imaginons qu'on s'intéresse uniquement aux théorèmes portant sur les entiers. Les axiomes de Peano sont une conséquence de ceux de ZFC (sur l'ensemble ω des entiers naturels codés dans ZFC), donc tout énoncé arithmétique qui découle des axiomes de Peano découle aussi de ZFC. La question se pose de savoir si la réciproque est vraie : les énoncés arithmétiques démontrés par ZFC (et qui se trouvent être arithmétiques) sont aussi démontrables à partir des axiomes de Peano (et qui sont, eux, forcément arithmétiques). La réponse est inattendue : c'est non, certainement pas ! et pourtant, en pratique, si….

La réponse non vient du génie de Gödel. La première remarque à faire, c'est que les démonstrations mathématiques, une fois qu'on précise complètement le cadre dans lequel on les fait, peuvent elles-mêmes être étudiées comme un objet mathématique (et la question de savoir si machin ou truc est un théorème devient une question mathématique). Et il y a mieux : cette question est une question arithmétique, puisque les démonstrations et les théorèmes, étant des objets essentiellement finis, peuvent très bien se coder comme des entiers (par exemple, imaginez-en une représentation informatique quelconque, et lisez la suite de 0 et de 1 comme un grand nombre : les détails n'ont aucune importance), et que les règles de démonstration, une fois mécanisées, peuvent s'exprimer comme des opérations arithmétiques (compliquées, mais explicitables) sur ces entiers. Donc des affirmations comme machin est un théorème de ZFC ou truc ne découle pas des axiomes de Peano deviennent elles-mêmes des affirmations arithmétiques (qui peuvent elles-mêmes faire l'objet d'une démonstration, par exemple dans ZFC, ou dans l'arithmétique de Peano). La deuxième remarque, c'est qu'il y a une façon (astucieuse, mais pas très compliquée) de produire un énoncé arithmétique G, qui affirme G n'est pas un théorème (selon ce que vous voudrez : un théorème de ZFC, un théorème de l'arithmétique de Peano) ; c'est-à-dire en quelque sorte un énoncé qui dit : je ne suis pas un théorème. C'est un peu difficile à visualiser, mais c'est un énoncé vraiment arithmétique, c'est-à-dire portant sur des entiers naturels, et qui dit que si vous manipulez des entiers d'une certaine manière (codant les règles de déduction et les axiomes dans le système que vous avez choisi : ZFC, Peano), vous ne tomberez pas sur un entier codant une démonstration de ce G lui-même.

Or si on fait l'hypothèse que l'énoncé G qui dit je ne suis pas un théorème de l'arithmétique de Peano (je choisis Peano pour l'exemple) soit un théorème de l'arithmétique de Peano, il devrait être vrai (sinon ce sont les axiomes de Peano qui sont faux). Étant vrai, puisqu'il affirme ne pas être un théorème, il ne devrait pas être un théorème, et on a une contradiction à ce qu'on a supposé. C'est donc le contraire de cette hypothèse qui est vrai : G n'est pas un théorème de l'arithmétique de Peano ; et, n'étant pas un théorème, il est vrai (puisque c'est ce qu'il dit). Ça ressemble aussi à une contradiction, mais cette fois ce n'en est pas une : G est vrai, mais l'arithmétique de Peano n'arrive pas à le démontrer — elle est trop faible pour ça. Pourtant, nous, nous avons réussi à démontrer G (je viens de le faire en concluant G est vrai). Le secret, c'est que nous n'avons pas travaillé dans l'arithmétique de Peano ; il n'est pas évident de voir exactement à quel endroit on en est sorti (et c'est encore moins évident vu que je n'ai pas explicité les axiomes de Peano), mais c'est dans la partie du raisonnement où j'ai écrit il devrait être vrai (sinon ce sont les axiomes de Peano qui sont faux) : le problème est que dans la mesure où machin est un entier naturel codant un énoncé arithmétique, dire machin est un théorème (de Peano) est bien un énoncé arithmétique, mais dire machin est vrai ne l'est pas (on peut bien dire machin est vrai, lorsque machin est quelque chose d'explicite, en disant juste machin, mais on ne peut pas définir la vérité d'un entier codant un énoncé : ce point est subtil, mais crucial). Par contre, ma démonstration est correcte dans ZFC (dans ZFC, il est facile de coder la relation machin est vrai des entiers naturels) : donc, dans ZFC, l'énoncé arithmétique G (et, du coup, le fait qu'il ne soit pas un théorème de Peano) est bien un théorème ! C'est là le fameux théorème de Gödel.

C'est un théorème très glissant que celui de Gödel, parce qu'il en existe quantité de variantes, et parce que les démonstrations font intervenir un système formel qui dit qu'un énoncé est ou n'est pas un théorème d'un autre système formel, et parfois des choses plus compliquées : on s'y perd facilement, quand on n'a pas l'habitude. Mais l'idée générale est très simple, et de façon très informelle, c'est que si je dis à quelqu'un tu ne peux pas prouver que j'ai raison !, alors j'ai forcément raison, et il ne peut pas le prouver. (La différence, c'est que dans le langage courant, on peut facilement créer des paradoxes, dire des choses comme cette phrase est fausse : dans le langage mathématique, on ne peut pas, donc le génie de Gödel a été de s'apercevoir qu'on pouvait quand même exploiter des phrases auto-référentielles.)

De façon générale, si vous avez une théorie formelle T (par exemple l'arithmétique de Peano, ou ZFC) qui permet de faire de l'arithmétique, et qui a des règles codables dans l'arithmétique, vous pouvez considérer un énoncé arithmétique G qui affirme T ne démontre pas G. Si T démontrait G, alors certainement elle démontrerait T démontre G (à partir d'une démonstration de G vous trouvez facilement une démonstration du fait qu'il existe une démonstration de G), c'est-à-dire précisément la négation de G : donc T démontrerait à la fois G et sa négation, et T est incohérente (elle démontre tout et son contraire). A contrario, ceci signifie qu'en ajoutant à T la simple hypothèse T est cohérente (qui, de nouveau, est un énoncé arithmétique), on permet à cette nouvelle théorie T′ de démontrer G ; or si T ne démontrait pas G, c'est qu'elle est bien strictement plus faible que T′, donc elle ne démontre pas la cohérence de T. C'est là le second théorème de Gödel : une théorie T cohérente ne peut pas démontrer sa propre cohérence.

⁂

Je reviens à mes moutons.

Je viens d'expliquer pourquoi ZFC prouve des énoncés arithmétiques que les axiomes de Peano ne permettent pas de prouver : explicitement, les axiomes de Peano sont cohérents (c'est-à-dire …ne permettent pas de prouver 0=1) est un énoncé arithmétique qui est un théorème de ZFC mais qui ne découle pas des axiomes de Peano. Voici donc un énoncé, portant uniquement sur des entiers naturels, qu'on ne sait pas démontrer sans passer par des ensembles. Et qui suggère la question épistémologique suivante : si on n'est pas convaincu que les ensembles « existent » dans le même sens que les entiers existent, sur quoi est-on fondé pour accepter les conséquences arithmétiques de ZFC ? (Pourquoi ces ensembles, qui n'existent peut-être pas vraiment, ont-ils des conséquences bien tangibles sur les entiers qui, eux, existent ?)

Le théorème de Gödel s'applique bien sûr aussi à ZFC lui-même si celui-ci est cohérent : il permet de dire que ZFC, s'il et cohérent, ne peut pas montrer sa cohérence (qui est pourtant un énoncé arithmétique). Bien sûr, Peano peut encore moins. On peut néanmoins montrer la cohérence de ZFC en ajoutant à ZFC des axiomes plus forts, comme l'existence de certains « gros » ensembles (un cardinal inaccessible), mais, évidemment, la théorie ainsi augmentée ne prouvera pas sa propre cohérence (si elle est cohérente).

Une façon plus inattendue de lire le théorème de Gödel est la suivante : supposons qu'un mathématicien ait démontré non pas l'hypothèse de Riemann (remplacez par votre conjecture préférée) mais l'énoncé suivant : l'hypothèse de Riemann est un théorème de ZFC (cela aussi dans ZFC). Doit-on en conclure que l'hypothèse de Riemann est démontrée ? La première réaction est de dire oui : si on a démontré que l'hypothèse de Riemann a une démonstration dans ZFC, c'est qu'elle a une démonstration, donc elle est un théorème. Pourtant, ce n'est pas le cas (c'est exactement le même problème que celui qui consistait, plus haut, à tenir dans Peano le raisonnement que si G est une conséquence des axiomes de Peano qui sont vrais, alors il est certainement vrai) : certainement ZFC croit à la véracité de ses propres axiomes, mais il ne peut pas formaliser la notion de vérité de façon à pouvoir dire que toute conséquence de ces axiomes est elle-même vraie. D'ailleurs, si on remplace l'hypothèse de Riemann par 0=1 dans le raisonnement, on ne peut pas dire dans ZFC que 0=1 est un théorème de ZFC (i.e., ZFC est incohérent) soit équivalent à 0=1 (i.e., que ce n'est pas le cas), car cela reviendrait à prouver la cohérence de ZFC, or Gödel nous prédit justement qu'on ne peut pas y arriver (sauf si c'est faux…). Dans le cas de l'hypothèse de Riemann, notre mathématicien aurait en fait démontré qu'elle découle de ZFC plus l'axiome d'existence d'un cardinal inaccessible (comme on n'a pas moins, ou pas plus, de raison de croire à la possibilité et aux conséquences arithmétiques d'un cardinal inaccessible qu'à celles de l'univers de ZFC, on peut s'estimer satisfait, mais néanmoins les règles du dogme officiel n'ont pas été satisfaites).

De façon générale, il est sans doute étonnant d'apprendre que si on ajoute à ZFC une infinité d'axiomes (un schéma d'axiomes) affirmant pour tout énoncé P que si P est un théorème de ZFC, alors P, on a fait une addition tout à fait substantielle au système. Épistémologiquement, ceci pose la question de savoir si on doit croire à ce schéma, et pourquoi. (Pour ceux qui aiment les grands cardinaux, il découle du schéma d'axiomes selon lequel toute classe close cofinale — explicitement définie — d'ordinaux contient un cardinal inaccessible.) Ne pas y croire est déplaisant : si on croit que ZFC dit la vérité, on serait bien obligé de le croire quand il dit qu'il démontre un théorème ! Mais y croire est également déplaisant : car une fois qu'on ajoute ce schéma d'axiomes, il faudrait le rajouter à nouveau pour la théorie ainsi modifiée, et ainsi de suite… mais ce et ainsi de suite cache beaucoup de poussière, de surprise, et de grands ordinaux chafouins. ((Pour ceux qui voudraient en savoir plus, je renvoie au très bon livre de Torkel Franzén, Inexhaustibility: a non-exhaustive treatment.))

⁂

Je reviens une nouvelle fois à mes moutons.

J'ai expliqué pourquoi ZFC prouve des énoncés arithmétiques que les axiomes de Peano ne permettent pas de prouver, et que c'est une question épistémologique épineuse de savoir pourquoi on doit croire à de tels énoncés (ou si on doit croire à certains énoncés au-delà de ZFC mais dont la véracité a l'air d'être sous-entendue par celle de ZFC). Néanmoins, on a une surprise pour ainsi dire dans le sens inverse quand on découvre que : vraisemblablement, tous les théorèmes arithmétiques des mathématiques usuelles (c'est-à-dire, hors de la logique et des champs proches, ou de tous théorèmes conçus exprès pour réfuter cette affirmation), démontrés dans ZFC, sont en fait démontrables dans l'arithmétique de Peano (et même dans des théories encore beaucoup plus faibles : par exemple l'arithmétique de Peano dans laquelle le schéma de récurrence est limité à des formules bien particulières, genre des formules semi-décidables par une machine de Turing). En particulier, le théorème de Fermat-Wiles devrait, vraisemblablement, découler des axiomes de Peano. Je dis vraisemblablement parce que c'est quelque chose qui fait débat : tous les logiciens ont l'air fortement convaincus de ce fait (voici un article qui expose très bien la situation et le point de vue des logiciens), les mathématiciens non logiciens sont généralement plus sceptiques ; et évidemment, on ne connaît pas de démonstration du théorème de Fermat-Wiles dans l'arithmétique de Peano : on pense juste qu'il devrait y en avoir une (et on a des idées sur la façon de la faire, mais ça ne peut évidemment pas être complètement systématique puisque, je l'ai prouvé, il existe des théorèmes arithmétiques de ZFC qui ne découlent pas de Peano : le point important est que ces choses-là n'arrivent pas dans les « vraies » mathématiques).

Devrait-on s'en réjouir ? Ce n'est pas clair. Le côté positif de cette constatation (si elle est vraie), c'est que les questions épistémologiques sur la véracité des conséquences arithmétiques de ZFC n'ont pas à nous tracasser : les vrais théorèmes mathématiques n'en ont pas besoin. Et ces vrais théorèmes sont fondés dans une théorie beaucoup plus élémentaire, donc plus vraisemblable, que ZFC. Le côté négatif, c'est que ce n'est pas ce qu'on fait, justement : on démontre nos théorèmes dans ZFC, qui est (au moins arithmétiquement) beaucoup trop forte pour ce dont les mathématiques ont besoin. On fait inutilement intervenir des constructions qu'on pourrait qualifier de douteuses. Mais les démonstrations reformulées dans l'arithmétique de Peano deviendraient probablement incompréhensibles ! Et un autre côté négatif, ou une autre façon de présenter le même, c'est que les mathématiques n'utilisent pas, et de très loin, toute la puissance de raisonnement qu'elles s'autorisent elles-mêmes (par le dogme orthodoxe) à suivre. C'est assez triste.

Sur ce dernier point, d'ailleurs, un thème récurrent de la logique est que la force des méthodes de raisonnement peut se mesurer sur une échelle graduée par des ordinaux : le fait que les mathématiques hors de la logique n'utilisent jamais de techniques de démonstration logiquement très fortes se voit au fait qu'il n'y a jamais de récurrence sur des ordinaux supérieurs ou égaux à ε₀.

Commentaires