Qu’est-ce que la logique mathématique

Ce qu’étudie la logique

Toute connaissance qui ne s’obtient pas par observation directe s’obtient en raisonnant : de certaines affirmations que l’on accepte, on passe à une autre qui en découle. En géométrie, qui sait que les angles d’un triangle valent deux droits conclut qu’aucun triangle n’a deux angles obtus ; en médecine, qui sait qu’une certaine maladie produit de la fièvre, et que la personne examinée n’en a pas, écarte cette maladie. La logique est la discipline qui étudie quand ce passage est légitime, et la logique mathématique est celle qui l’étudie avec les méthodes des mathématiques : en définissant avec exactitude ses objets, qui sont des langages, des formules et des déductions, et en démontrant des théorèmes à leur sujet.

Pour énoncer avec précision ce qu’elle étudie, il convient de fixer d’abord le vocabulaire. Une proposition est une phrase déclarative dont il a un sens de dire qu’elle est vraie ou qu’elle est fausse : « $7$ est un nombre premier » est une proposition vraie ; « tout nombre pair est supérieur à $5$ », une proposition fausse. Ne sont pas des propositions, en revanche, les questions (« quelle heure est-il ? »), les ordres (« ferme la porte ») ni les expressions à variables libres, comme « $x$ est pair », dont la valeur dépend de ce que désigne $x$.

Un raisonnement est une liste de propositions, les prémisses, accompagnée d’une autre proposition, la conclusion, qui est présentée comme leur conséquence. Les prémisses peuvent être des propositions quelconques : vraies, fausses, connues ou simples suppositions ; la seule chose qui les distingue est la place qu’elles occupent dans le raisonnement. Nous écrirons les raisonnements avec les prémisses sur des lignes successives et la conclusion précédée de « donc » :

La logique n’est pas une théorie de la vérité

S’il en est ainsi, la logique n’a pas pour tâche de savoir si les prémisses d’un raisonnement sont vraies. Que $28$ soit multiple de $4$, c’est l’arithmétique qui le décide ; qu’une personne ait de la fièvre, le thermomètre ; qu’une bataille ait eu lieu en une certaine année, l’histoire. Il ne lui revient pas non plus de définir ce qu’est la vérité, question qui appartient à la philosophie. La logique admet que les propositions ont une valeur de vérité, quelle qu’elle soit, et étudie comment ces valeurs se rapportent les unes aux autres : en particulier, quand la vérité de certaines propositions oblige à la vérité d’une autre. Autrement dit, la logique n’est pas une théorie de la vérité, mais une théorie de la transmission de la vérité.

Or ce qui transmet la vérité ne dépend pas du thème du raisonnement, mais de sa structure. Que l’on compare le raisonnement précédent avec celui-ci : « si un animal est un mammifère, il respire de l’air ; la baleine est un mammifère ; donc la baleine respire de l’air ». Tous deux ont la même forme : « si quelque chose est $A$, il est $B$ ; $c$ est $A$ ; donc $c$ est $B$ ». La forme d’un raisonnement est ce qui reste lorsqu’on remplace ses termes non logiques (nombres, animaux, propriétés) par des lettres, en conservant les mots logiques : « non », « et », « ou », « si… alors », « tout », « quelque ». Chaque raisonnement que l’on obtient d’une forme en donnant un contenu à ses lettres en est une instance.

Une forme est valide lorsqu’aucune de ses instances n’a toutes ses prémisses vraies et sa conclusion fausse ; un raisonnement est valide lorsque sa forme l’est. Une instance à prémisses vraies et à conclusion fausse s’appelle un contre-exemple de la forme : d’où une forme est non valide exactement lorsqu’elle a un contre-exemple.

Dans les démonstrations de cette leçon, nous utiliserons une sténographie du français : $V(A)$ abrège « $A$ est vraie » et $F(A)$, « $A$ est fausse » ; $\neg$ abrège « non », $\wedge$ abrège « et », $\vee$ abrège « ou », $\Rightarrow$ abrège « si… alors » et $\Leftrightarrow$ abrège « si et seulement si » ; $\forall$ se lit « pour tout » et $\exists$, « il existe ». Ces signes ne sont ici que des abréviations de mots du métalangage, et les flèches doubles sont réservées dans tout le cours à cet usage. Dans la leçon suivante apparaîtront les signes à un seul trait, $\rightarrow$ et $\leftrightarrow$, avec $\neg$, $\wedge$ et $\vee$, comme abréviations d’un langage formel, avec un sens que le cours fixera avec exactitude ; la différence de trait entre les flèches rappellera à quel niveau l’on parle.

La proposition dit ce que garantit la validité ; il convient de voir avec la même clarté ce qu’elle ne garantit pas. Des huit combinaisons possibles entre la validité du raisonnement, la vérité de toutes ses prémisses et la vérité de sa conclusion, une seule est exclue, celle du raisonnement valide à prémisses vraies et à conclusion fausse ; toutes les autres se rencontrent.

Il s’ensuit la règle pratique que la leçon mettra en œuvre : pour montrer qu’un raisonnement n’est pas valide, il ne suffit pas de signaler qu’une prémisse ou la conclusion est fausse, et pour montrer qu’il est valide, il ne suffit pas que tout y soit vrai ; la première chose exige d’exhiber un contre-exemple de sa forme, et la seconde, un argument qui vaille pour toutes les instances.

Langue naturelle et langage formel

La définition de la validité repose sur deux opérations : reconnaître la forme d’un raisonnement et décider si une proposition est vraie ou fausse. Toutes deux supposent que chaque phrase n’a qu’une seule lecture. La langue naturelle, le français, le chinois ou l’arabe, que les êtres humains apprennent sans instruction formelle et utilisent pour communiquer, ne remplit pas cette condition : sa souplesse, qui la rend apte à la poésie, à la conversation et à la nuance, la rend aussi ambiguë.

• Ambiguïté lexicale : un mot a plusieurs sens. « Je cherche un avocat » peut désigner un juriste ou un fruit.
• Ambiguïté syntaxique : une phrase admet plusieurs structures. « Le double de trois plus quatre » peut valoir $2 \cdot 3 + 4 = 10$ ou $2 \cdot (3 + 4) = 14$.
• Ambiguïté de portée : on ne sait pas sur quelle partie de la phrase porte un mot logique. « Tous les élèves n’ont pas réussi » peut signifier qu’aucun n’a réussi ou que les élèves n’ont pas tous réussi.
• Connecteurs imprécis : le « ou » tantôt admet que les deux branches de l’alternative soient réalisées (« on demande un diplôme ou de l’expérience »), tantôt l’exclut (« fromage ou dessert ») ; le « si… alors » exprime tantôt une cause, tantôt une règle, tantôt une simple succession.

À l’ambiguïté s’ajoute un trait plus profond : la langue naturelle peut parler d’elle-même. Elle contient les mots « phrase », « vrai » et « définir », et avec eux elle peut former des phrases qui se réfèrent à elles-mêmes, comme « cette phrase contient cinq mots ». Cette autoréférence est, en général, inoffensive ; mais, comme on le verra, combinée avec la notion de vérité, elle produit des phrases qui ne peuvent être ni vraies ni fausses.

Un langage formel est conçu pour éliminer ces deux sources de difficulté. On fixe un alphabet, une collection de symboles, et des règles de formation qui disent, sans laisser place à l’interprétation, quelles suites de symboles sont des expressions bien formées ; le sens de chaque expression est fixé ensuite par des définitions tout aussi précises. Ainsi, demander si une suite de symboles appartient au langage est une question qui se tranche mécaniquement, en vérifiant des règles, et chaque expression se lit d’une seule manière. Le langage de ce cours, que construit la leçon sur le langage de la logique propositionnelle, a un alphabet de deux symboles seulement, le cercle $\sigO$ et le disque $\sigI$, et une seule règle de formation.

Le prix en est la souplesse : un langage formel ne sert pas à converser, et chaque langage formel n’exprime que ce que ses règles permettent. Il n’est pas vrai, cependant, que l’on sacrifie tout le pouvoir expressif : les langages formels de la logique du premier ordre suffisent pour écrire presque toutes les mathématiques. Ce que l’on sacrifie, c’est l’ambiguïté et l’autoréférence incontrôlée ; ce que l’on gagne, c’est la possibilité de démontrer des théorèmes sur le langage lui-même.

Langage objet et métalangage

Pour étudier un langage, il faut en parler, et pour en parler il faut un autre langage. Le langage objet est le langage que l’on étudie ; le métalangage est le langage dans lequel on l’étudie. Dans une grammaire latine écrite en français, le latin est le langage objet et le français le métalangage. Dans ce cours, le langage objet sera le langage formel des cercles et des disques, et le métalangage sera le français, enrichi de signes mathématiques et de lettres grecques, $\varphi$, $\psi$, qui désigneront des formules quelconques du langage objet sans lui appartenir.

La distinction est centrale pour une raison précise : les affirmations que le cours démontrera sur le langage formel (que toute formule se lit d’une seule manière, que tout ce qui est déductible est vrai) ne sont pas des formules du langage formel, mais des phrases du métalangage. C’est pourquoi on les appellera des métathéorèmes, pour les distinguer des théorèmes que le système déductif produit à l’intérieur du langage objet.

Une forme élémentaire de la distinction est celle qui sépare l’usage d’une expression de sa mention. Dans « Rome est une ville », on utilise le mot pour parler de la ville ; dans « “Rome” a quatre lettres », on mentionne le mot, et les guillemets l’indiquent : la phrase parle du mot, non de la ville. Confondre les deux produit des énoncés absurdes, comme « Rome a quatre lettres », ou des raisonnements fallacieux, comme « Rome est une ville ; “Rome” est un mot de quatre lettres ; donc une ville est un mot de quatre lettres ».

Les paradoxes du langage

Une contradiction est une affirmation accompagnée de sa négation, comme $V(A) \wedge \neg V(A)$. Un paradoxe est un raisonnement qui, partant d’hypothèses qui semblent acceptables et avançant par des pas qui semblent valides, aboutit à une contradiction. Par la proposition sur ce que garantit la validité, si les pas sont réellement valides, une hypothèse est fausse : résoudre un paradoxe consiste à trouver laquelle. Il convient de ne pas confondre le paradoxe avec l’ambiguïté, qui n’est que la multiplicité des lectures, ni avec ce qui est simplement surprenant.

Le menteur

Le plus ancien paradoxe de ce genre est attribué à Eubulide de Milet, au IVe siècle avant notre ère. Sous sa forme précise, il ne parle pas de mentir, ce qui suppose l’intention de tromper, mais de fausseté : soit $m$ la phrase « la phrase $m$ est fausse ». Pour obtenir la contradiction, deux hypothèses suffisent, qu’il convient d’écrire explicitement.

• Bivalence (B) : toute proposition est vraie ou fausse, et non les deux ; être fausse équivaut à ne pas être vraie.
• Schéma de vérité (T) : une phrase est vraie si et seulement si ce qu’elle dit est le cas. Par exemple, « la neige est blanche » est vraie si et seulement si la neige est blanche.

Le théorème ne dit pas que la logique est contradictoire, mais que les deux hypothèses ne peuvent être maintenues ensemble pour un langage qui contient la phrase $m$. Il y a donc trois issues : abandonner la bivalence et admettre des phrases sans valeur de vérité ; restreindre le schéma de vérité ; ou empêcher le langage de former la phrase $m$. La troisième est celle d’Alfred Tarski, en 1933 : le prédicat « est vraie » d’un langage n’appartient pas à ce langage, mais à son métalangage. Dans un tel langage, $m$ n’est pas une phrase bien formée, et le paradoxe ne peut pas être énoncé.

Le paradoxe de Berry

Publié par Bertrand Russell en 1906, qui l’attribua à George Berry, bibliothécaire à Oxford, ce paradoxe n’utilise pas le mot « vrai », mais le mot « définir ». On dit qu’une expression du français définit un nombre naturel lorsqu’elle le décrit de telle sorte qu’on puisse l’identifier sans ambiguïté : « le plus petit nombre premier supérieur à dix » définit $11$. Considérons l’expression « le plus petit nombre naturel impossible à définir en moins de vingt mots », qui doit être lue telle qu’elle est écrite, et appelons $b$ le nombre qu’elle prétend définir. Les nombres naturels, dans ce cours, sont $1, 2, 3, \ldots$

L’exposé courant, qui se borne à observer que l’expression a moins de vingt mots, omet la moitié de l’argument : que le nombre $b$ existe, ce qui exige la finitude du vocabulaire et le choix du premier nombre manquant. L’hypothèse en défaut est la seconde : « définir » n’est pas une relation précise du français, car l’expression qui définit $b$ utilise le mot « définir » lui-même, et son sens dépend des expressions que l’on compte comme définitions. Dans un langage formel $L$, on peut préciser ce que signifie « définissable dans $L$ », mais cette notion ne s’exprime que dans le métalangage ; l’expression qui définit $b$ n’appartient pas à $L$, et la contradiction disparaît : $b$ n’est pas définissable dans $L$ avec peu de symboles, bien qu’il le soit dans le métalangage.

Le barbier et l’ensemble de Russell

On raconte d’ordinaire le paradoxe du barbier ainsi : dans un village, il y a un barbier, homme du village, qui rase tous les hommes du village qui ne se rasent pas eux-mêmes, et seulement ceux-là. Le barbier se rase-t-il lui-même ? Les mots « et seulement ceux-là » sont essentiels : un barbier qui raserait tous ceux qui ne se rasent pas eux-mêmes, sans la restriction, pourrait se raser aussi lui-même sans aucune contradiction. Le paradoxe est un cas particulier d’un lemme général, de forme diagonale, qu’il convient de démontrer une fois pour toutes.

La conclusion du barbier est inoffensive : personne n’avait affirmé qu’un tel barbier existait. Il n’en va pas de même de sa version en théorie des ensembles. En 1902, Russell écrivit à Gottlob Frege que son système, qui prétendait fonder l’arithmétique sur la logique, admettait le principe de compréhension suivant : pour toute propriété, il y a un ensemble dont les éléments sont exactement les objets qui l’ont. Appliqué à la propriété de ne pas s’appartenir à soi-même, le principe affirme qu’il existe l’ensemble

À la différence du barbier, l’existence de $Z$ n’était pas ici une supposition d’un récit, mais un principe de la théorie. Le paradoxe de Russell ne se résout pas en déclarant que $Z$ n’existe pas, mais en réformant la théorie : la théorie axiomatique des ensembles de Zermelo, de 1908, ne permet de former, avec une propriété, que des sous-ensembles d’un ensemble déjà donné, et avec cette restriction la contradiction ne se déduit pas.

Ce qui n’est pas un paradoxe

On a parfois appelé « paradoxe de l’ensemble vide » l’observation que l’ensemble vide existe bien qu’il n’ait pas d’éléments, comme si un objet existant devait être fait d’objets existants. Il n’y a là aucune contradiction : un ensemble n’est pas fait de ses éléments comme un mur de ses briques, mais il est déterminé par eux, et la collection des éléments d’un ensemble peut n’en avoir aucun, comme une boîte vide reste une boîte. Qu’un fait surprenne ne le rend pas paradoxal ; le paradoxe exige de déduire une contradiction, et ici on n’en déduit aucune.

Comment un langage formel les traite

De ce qui précède, il suit qu’un langage formel n’évite pas les paradoxes par magie, mais de deux manières précises. La première est qu’il peut manquer des ressources qui les produisent. Le langage de la logique propositionnelle, que construit ce cours, n’a pas de phrases qui se réfèrent à elles-mêmes ni de prédicat de vérité : on ne peut pas y écrire la phrase du menteur, et sa sémantique attribue à chaque formule, pour chaque assignation de valeurs aux variables, une valeur de vérité unique. La seconde est que, dans des langages plus riches, le paradoxe devient un théorème : le raisonnement du menteur, mené avec rigueur, démontre que la vérité d’un langage suffisamment expressif n’est pas définissable dans ce même langage (Tarski) ; celui du barbier et de Russell démontre que certaines collections ne sont pas des ensembles ; et des arguments apparentés à celui de Berry sont au cœur des théorèmes d’incomplétude de Kurt Gödel, de 1931. Ainsi, ce qui dans la langue naturelle est une perplexité est, dans un langage formel, une information.

Les quatre piliers de la logique mathématique

La logique mathématique est née à la fin du XIXe siècle et au début du XXe, avec Frege, Peano, Russell et David Hilbert, en réponse à une question précise : sur quels fondements reposent les mathématiques, et ces fondements sont-ils exempts de contradiction. On la divise aujourd’hui en quatre grandes branches, qui s’entrelacent constamment.

• Théorie de la démonstration : elle étudie les démonstrations formelles comme des objets mathématiques, c’est-à-dire comme des suites finies de formules qui suivent des règles explicites ; elle se demande ce qui peut être démontré dans un système, si un système est cohérent et comment des démonstrations se transforment en d’autres. L’unité de déduction de ce cours en est un premier contact.
• Théorie des modèles : elle étudie la relation entre un langage formel et les structures qui l’interprètent, ses modèles ; elle se demande quelles structures satisfont un ensemble de formules et quelles propriétés des structures peuvent s’exprimer dans un langage donné. L’unité de sémantique, avec ses assignations de valeurs de vérité, en est la version la plus élémentaire.
• Théorie des ensembles : elle étudie les ensembles à l’aide d’axiomes précis, comme celle de Zermelo et Fraenkel, dans laquelle on peut écrire presque toutes les mathématiques ; elle est née, en bonne partie, de la nécessité d’éviter le paradoxe de Russell.
• Théorie de la calculabilité : elle étudie quels problèmes peuvent être résolus par une procédure mécanique et lesquels ne le peuvent pas. La logique propositionnelle est décidable, comme le verra le cours : il existe une procédure qui décide en un nombre fini d’étapes si une formule est valide ; la logique des prédicats, en revanche, ne l’est pas.

Aucun pilier ne s’étudie en profondeur sans toucher aux autres : la complétude, résultat central de ce cours, est à la fois un théorème de la théorie de la démonstration et de la théorie des modèles, et la décidabilité qu’on en tire appartient à la calculabilité.

La carte du cours

Le cours parcourt, pour le langage le plus simple de la logique, le langage propositionnel, le chemin complet d’une théorie logique, en quatre unités.

1. Langage : la syntaxe. On construit le langage objet avec son alphabet de deux symboles et sa règle de formation, on démontre que chaque formule se lit d’une seule manière, on apprend à démontrer par récurrence et par induction, et l’on traduit dans le langage formel des énoncés et des raisonnements de la langue naturelle, en signalant ce que la traduction conserve et ce qu’elle perd.
2. Déduction : on fixe un système d’axiomes et de règles d’inférence, et l’on définit ce que signifie qu’une formule $\varphi$ se déduise d’un ensemble de formules $\Gamma$, ce qui s’écrit $\Gamma \vdash \varphi$. C’est la face syntaxique de la validité : manipuler des symboles selon des règles, sans prêter attention à leur sens.
3. Sémantique : on attribue à chaque formule une valeur de vérité pour chaque assignation, et l’on définit ce que signifie que $\varphi$ soit conséquence de $\Gamma$, ce qui s’écrit $\Gamma \models \varphi$ : toute assignation qui rend vraies les formules de $\Gamma$ rend vraie $\varphi$. C’est la face sémantique de la validité, la définition de cette leçon rendue précise.
4. Métathéorie : on démontre que les deux faces coïncident. La correction dit que tout ce qui est déductible est conséquence, et la complétude, que toute conséquence est déductible. On étudie ensuite la compacité et une méthode mécanique, la résolution, pour décider si un ensemble de formules peut être satisfait.

S’il en est ainsi, le cours est le premier exemple complet d’une théorie mathématique dont l’objet est le raisonnement lui-même ; et toutes ses affirmations sur le langage formel seront, comme on l’a vu dans cette leçon, des phrases du métalangage démontrées avec la rigueur des mathématiques.

Problèmes résolus

Les problèmes suivants mettent en œuvre, par difficulté croissante, les distinctions de la leçon : réfuter un raisonnement dont les phrases sont toutes vraies, séparer les lectures d’un énoncé ambigu, classer des expressions du langage objet et du métalangage, et analyser deux raisonnements d’apparence paradoxale pour décider s’ils le sont.

Problèmes proposés

Les deux premiers problèmes mettent en œuvre la validité et l’ambiguïté ; le troisième, l’usage et la mention ; les deux derniers demandent d’analyser un paradoxe nouveau et d’appliquer le lemme diagonal hors de la linguistique. Chacun a une indication, qu’il vaut mieux n’ouvrir qu’après avoir cherché.