Langage et sens : des objets, des propriétés et des quantificateurs
Le calcul des propositions traite chaque affirmation comme un bloc indivisible : « il pleut » devient $P$, et l’on ne regarde jamais à l’intérieur. Le raisonnement le plus célèbre de l’histoire de la logique lui échappe pourtant complètement :
Tous les hommes sont mortels. Socrate est un homme. Donc Socrate est mortel.
Pour le calcul des propositions, ce sont trois affirmations sans rapport, $P$, $Q$ et $R$, et rien ne permet de tirer $R$ de $P$ et $Q$. Pour attraper ce raisonnement, il faut ouvrir les propositions et regarder ce qu’elles contiennent : des objets (Socrate) et des propriétés de ces objets (être un homme, être mortel). C’est ce que fait le calcul des prédicats, qu’on appelle aussi logique du premier ordre : les deux noms désignent la même chose.
On s’autorise à dire « pour tout objet $x$ », mais pas « pour toute propriété $P$ ». Quantifier sur les propriétés elles-mêmes, c’est passer au second ordre.
La différence a l’air technique, mais elle se fait sentir très vite. Le principe de récurrence dit : « pour toute propriété $P$, si $P(0)$ et si $P(n)$ entraîne $P(n+1)$, alors $P$ est vraie de tous les entiers ». C’est un énoncé du second ordre. Au premier ordre, on devra se contenter d’écrire une récurrence séparée pour chaque propriété qu’on sait exprimer par une formule : on verra au chapitre suivant que ce n’est pas tout à fait la même chose.
Le calcul des propositions ne voit qu'une boîte noire ; le calcul des prédicats distingue ce dont on parle (le terme) de ce qu'on en dit (le prédicat).
Le langage s’enrichit de deux sortes d’ingrédients.
Un prédicat dont on a rempli les places, comme $\mathit{Mortel}(\mathit{socrate})$ ou $2\lt 3$, forme une formule atomique. Elle joue exactement le rôle des variables propositionnelles d’autrefois : on la combine avec les mêmes connecteurs $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$, et tout ce que l’on sait du calcul des propositions reste vrai.
| Calcul des propositions | Calcul des prédicats | |
|---|---|---|
| briques | variables propositionnelles $P$, $Q$… | formules atomiques $\mathit{Mortel}(\mathit{socrate})$, $x\lt y$… |
| connecteurs | $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$ | les mêmes |
| nouveautés | des termes (les objets) et deux quantificateurs, $\forall$ et $\exists$ | |
| un modèle | une ligne de table de vérité | une structure : des objets et le sens de chaque symbole |
Deux symboles permettent de parler de tous les objets à la fois, ou d’au moins l’un d’eux :
Le syllogisme de Socrate s’écrit enfin :
et cette fois, la conclusion découle bien des prémisses : la première affirme que, pour chaque objet, être un homme entraîne être mortel, en particulier pour Socrate.
« Tous les hommes sont mortels » s’écrit $\forall x,(\mathit{Homme}(x)\rightarrow \mathit{Mortel}(x))$, et non $\forall x,(\mathit{Homme}(x)\land \mathit{Mortel}(x))$. Cette dernière formule affirme que tout est un homme mortel, y compris les chaises et les nombres premiers.
À l’inverse, « un homme au moins est mortel » s’écrit $\exists x,(\mathit{Homme}(x)\land \mathit{Mortel}(x))$, et non $\exists x,(\mathit{Homme}(x)\rightarrow \mathit{Mortel}(x))$. Cette dernière est vraie dès qu’il existe un objet qui n’est pas un homme : une chaise suffit, puisqu’une implication dont la prémisse est fausse est vraie.
Règle pratique : $\forall$ va avec $\rightarrow$, $\exists$ va avec $\land$.
Nier un quantificateur, c’est le retourner : « il est faux que tous les cygnes soient blancs » veut dire « il existe un cygne qui n’est pas blanc ».
Ce sont les lois de De Morgan, version quantificateurs, et la dualité $\Box$/$\Diamond$ de la logique modale n’en est qu’un cas particulier. La boîte est un « pour tout » qui ne porte que sur les mondes accessibles, et le diamant un « il existe » :
La logique modale se traduit ainsi tout entière dans le calcul des prédicats (on parle de traduction standard) : c’en est un fragment, que la boîte et le diamant permettent d’écrire sans variables.
Les quantificateurs sont nés en 1879 dans la Begriffsschrift (« idéographie ») de Gottlob Frege, l’acte de naissance de la logique moderne. Sa notation, qui s’étalait en deux dimensions sur la page, était si déroutante qu’elle rebuta la plupart de ses contemporains. Charles Peirce, de l’autre côté de l’Atlantique, aboutit indépendamment à la même idée quelques années plus tard.
Les symboles actuels sont venus après coup : le $\exists$, un E retourné pour « existe », apparaît chez Giuseppe Peano en 1897, et le $\forall$, un A retourné pour alle (« tous » en allemand), chez Gerhard Gentzen en 1935, par analogie.
Quand plusieurs quantificateurs se suivent, leur ordre change tout le sens de la phrase.
À gauche, chacun aime quelqu'un, mais pas forcément la même personne. À droite, une même personne (ici Chloé) est aimée de tous. La formule de droite entraîne celle de gauche, mais pas l'inverse.
On prête à l’humoriste américain Sam Levenson cette annonce alarmée : « Toutes les quinze secondes, une femme met un enfant au monde quelque part. Il faut absolument retrouver cette femme et l’arrêter ! »
Toute la blague tient dans l’inversion des quantificateurs. La statistique dit $\forall t\ \exists f$ (« à chaque instant, il y a une femme qui accouche »), et le personnage entend $\exists f\ \forall t$ (« il y a une femme qui accouche à chaque instant »).
Les mathématiciens connaissent bien le phénomène. Une fonction est continue sur un intervalle si $\forall x\ \forall\varepsilon\ \exists\delta\ldots$, et uniformément continue si $\forall\varepsilon\ \exists\delta\ \forall x\ldots$ : dans le second cas, le même $\delta$ doit convenir pour tous les $x$. La fonction $x\mapsto 1/x$ sur $]0,1]$ est continue sans être uniformément continue.
Dans $\displaystyle\sum_{i=1}^{n} i$, la lettre $i$ est muette : on pourrait l’appeler $k$ sans rien changer, et le résultat ne dépend que de $n$. Les quantificateurs fonctionnent de la même façon. Dans $\forall x,\mathit{Homme}(x)$, la variable $x$ est liée par le quantificateur ; une variable qu’aucun quantificateur ne lie est libre.
Chaque quantificateur lie les occurrences de sa variable qui se trouvent dans sa portée. La variable $z$, qu'aucun quantificateur ne lie, est libre.
Une formule sans variable libre est un énoncé (on dit aussi une formule close) : une fois qu’on sait de quel monde on parle, il est vrai ou faux.
Une formule avec une variable libre n’est ni vraie ni fausse tant qu’on n’a pas choisi la valeur de cette variable : elle exprime une propriété. Ainsi $\exists y,(x=y+y)$, où $x$ est libre et $y$ liée, dit « $x$ est pair ». Elle est vraie pour $x=6$ et fausse pour $x=7$. C’est exactement en ce sens que, dans le lemme de diagonalisation, une formule $S(x)$ « exprime une propriété $S$ ».
On ne remplace pas une variable libre n’importe comment. Dans $\exists y,(x=y+y)$, remplacer $x$ par $y$ donne $\exists y,(y=y+y)$, qui ne dit plus « $y$ est pair » mais « zéro existe » : la variable $y$ s’est fait capturer par le quantificateur. Il faut d’abord renommer la variable muette, par exemple en $\exists u,(x=u+u)$, comme on le ferait avec un indice de sommation.
En calcul des propositions, un modèle se contentait de dire quelles variables étaient vraies. Il faut maintenant décrire tout un petit monde. Une structure se compose :
On évalue ensuite une formule comme on s’y attend : une formule atomique en regardant si les objets désignés sont dans la relation, les connecteurs comme en calcul des propositions, et $\forall x,\phi$ en vérifiant $\phi$ pour chaque objet du domaine (respectivement au moins un pour $\exists x,\phi$).
Une même formule peut être vraie dans une structure et fausse dans une autre. Voici trois structures pour un langage qui ne contient qu’une relation $R$ (dessinée par des flèches) :
L'énoncé $\forall x\,\exists y\,R(x,y)$ est vrai dans les deux premières structures et faux dans la troisième, où la dernière marche n'a pas de successeur.
Ces dessins vous rappellent quelque chose ? Un système de transition de la logique modale n’est rien d’autre qu’une structure pour un langage réduit à une relation binaire, l’accessibilité. Et l’énoncé $\forall x,\exists y,R(x,y)$ est exactement la propriété « non borné à droite » qui caractérise l’axiome $\text{(D)}$. La différence est de point de vue : le calcul des prédicats décrit le graphe avec des quantificateurs, la logique modale s’y promène de monde en monde.
On note $\mathcal{M}\models\phi$ quand l’énoncé $\phi$ est vrai dans la structure $\mathcal{M}$. Un énoncé vrai dans toutes les structures est dit universellement valide : c’est l’analogue des tautologies. Par exemple, $\exists y,\forall x,R(x,y)\rightarrow\forall x,\exists y,R(x,y)$ est universellement valide, mais pas sa réciproque, comme le montre le panneau de gauche de la figure sur l’ordre des quantificateurs.
Pendant plus de deux mille ans, la logique s’est confondue avec la syllogistique d’Aristote, qui classe les raisonnements du type « tout $P$ est $Q$, tout $R$ est $P$, donc tout $R$ est $Q$ » (le syllogisme que les scolastiques appelaient Barbara). Kant pouvait écrire en 1787, dans la préface de la Critique de la raison pure, que la logique n’avait pas fait un pas en avant depuis Aristote et semblait donc « close et achevée ». En langage moderne, la syllogistique n’est qu’un tout petit morceau du calcul des prédicats, celui où les prédicats n’ont qu’une place ; elle ne sait rien dire des relations comme « aimer » ou « être plus petit que ».
Lewis Carroll, professeur de logique à Oxford, s’amusait à fabriquer des chaînes de syllogismes délirantes. Celle-ci est tirée de sa Logique symbolique (1896) :
Aucun canard ne valse. Aucun officier ne refuse jamais de valser. Toutes mes volailles sont des canards.
Que peut-on en conclure ? Avec des prédicats, la chaîne se déroule toute seule : $\mathit{Volaille}(x)\rightarrow\mathit{Canard}(x)\rightarrow\neg\mathit{Valse}(x)\rightarrow\neg\mathit{Officier}(x)$, la dernière flèche étant la contraposée de « tout officier valse ». D’où la conclusion de Carroll : aucune de mes volailles n’est officier.
Le langage dispose presque toujours d’un prédicat spécial, l’égalité $=$, qui permet de compter. « Il y a au moins deux objets » s’écrit $\exists x,\exists y,\neg(x=y)$, et l’on écrit de même « il y a au moins trois objets », « au moins cent objets », « exactement sept objets ». Mais aucune formule ne dit « le domaine est fini ». Ce n’est pas un manque d’astuce : c’est un théorème, que l’on rencontrera au chapitre suivant.