Quantification et relations logiques [C1.I.3]

1. La quantification des clauses mathématiques

1.1. Principe de la quantification mathématique

La théorie des ensembles étant la trame conceptuelle de la mathématique, toutes les clauses mathématiques se ramènent essentiellement à des clauses « construites » à partir de clauses élémentaires, grâce aux opérations précédentes et ce qu’on appelle les quantifications.

En effet, les propriétés mathématiques d’un objet particulier ou générique sont décrites en relation à d’autres objets, et à l’intérieur de certains ensembles.

A cause de l’universalité de la méta-relation $\in$ entre les objets et les ensembles, pour obtenir toute la puissance expressive du langage mathématique il n’est nécessaire de compléter la combinaison des clauses élémentaires par les opérations logiques que par l’information concernant l’existence d’un objet ayant une « sous-propriété » ou l’universalité des objets ayant une telle sous-propriété. Par une « sous-propriété », nous entendons de manière informelle une propriété décrite par une partie d’une clause.

Exemple 1
Si $P$ est la clause « $x\geq 0$ et $x^2\neq 5$ », alors les clauses « $x\geq 0$ » et « $x^2\neq 5$ » expriment des sous-propriétés de la propriété générique exprimée par $P$.

Si l’on considère la propriété $P$ de l’exemple, il est naturel de se poser deux questions :
– existe-t-il un nombre réel $a$ ayant la propriété $P$ (c’est-à-dire tel que $P(a/x)$ est vrai) ?
– tous les nombres réels $a$ ont-ils la propriété $P$ ?

Ces deux possibilités correspondent aux deux types de quantifications, existentielle et universelle, et l’expression de ces deux types de faits suffit à compléter notre description du langage mathématique.

La quantification n’est pas un artifice de la science mathématique : elle correspond à l’addition de l’adverbe « tous » ou « tout » dans les expressions naturelles (pour la quantification universelle), ou de l’adverbe « certains » ou « certain » pour la quantification existentielle.

Ces deux quantifications étaient déjà bien connues dans l’Antiquité grecque; on les retrouve notamment chez Aristote, et à travers son héritage dans la logique de la scolastique médiévale.

Exemple 2
Un exemple de ces quantifications naturelles tiré de l’ancienne logique grecque (Aristote) est le suivant : « tous les hommes sont mortels ». Ici, l’expression « les hommes sont mortels » est complétée par le « quantificateur ‘tous' ». L’analogue pour le quantificateur existentiel est l’expression « certains hommes sont mortels ». La négation naturelle de « tous les hommes sont mortels » est « certains hommes ne sont pas mortels »; il existe une relation essentielle entre ces deux quantifications, liée à la négation, que nous aborderons ici dans le cadre mathématique propre.

Nous avons déjà vu des exemples de quantifications, et ils montrent que les énoncés mathématiques « intéressants » doivent souvent être construits à partir de clauses élémentaires contenant des variables libres, de manière à pouvoir affirmer quelque chose de plus élaboré que de simples relations particulières (même si certaines équations, entre nombres et fonctions par exemple, ont un intérêt mathématique essentiel; par exemple, l’étudiant(e) ou le lecteur pourra comprendre à son niveau, à la fin du semestre, la formule d’Euler, soit $e^{i\pi}+1=0$).

Nous avons aussi utilisé la quantification pour introduire des définitions, comme dans l’exemple de la divisibilité. Il s’agit donc d’un mode ubiquitaire de « transformation » des expressions mathématiques, qui « ferme » les clauses par rapport aux variables qu’elles contiennent.

1.2. La quantification existentielle

Si $P$ est une clause et $x$ une variable pour les éléments d’un ensemble $E$, la quantification existentielle de $P$ par $x$, notée « $\exists x\in E,\ P$ » (lire « il existe $x\in E$ tel que $P$ »), est la clause dont la signification est « il existe au moins un élément $a$ de $E$ tel que la clause obtenue en remplaçant $x$ par $a$ dans $P$, est valide ».

Remarque 1
i) La notation de la quantification peut varier selon les textes mathématiques : par exemple, on pourra écrire $(\exists x\in E)\ P$ pour $\exists x\in E,\ P$. En général, il n’y a aucune difficulté pour s’adapter à ces variations mineures : l’important est l’usage du symbole $\exists$.
ii) Il se peut que la variable $x$ n’apparaisse pas dans $P$, ou que $P$ possède d’autres variables libres que $x$ : nous ne présageons rien à ce sujet.

Si $x$ est la seule variable libre de $P$, alors la clause « $\exists x\in E,\ P$ » est un énoncé qui par définition est vrai exactement lorsqu’il existe un élément $a$ de $E$ tel que l’énoncé $P(a/x)$ est vrai. Cet énoncé est faux exactement lorsque pour aucun élément $a$ de $E$, l’énoncé $P(a/x)$ n’est vrai.

Exemple 3
i) Si $m$ et $n$ dénotent des entiers relatifs génériques, la relation « $m$ divise $n$ » (« $m|n$ ») a été définie par une quantification existentielle. En effet, si $P$ est la clause « $m.d=n$ », où $d$ est une nouvelle variable générique pour un entier relatif, la relation $m|n$ est définie par la clause $\exists d\in\mathbb Z,\ P$, soit « $\exists d\in\mathbb Z,\ m.d=n$ », dont la signification intuitive est qu’il existe un entier relatif $d$ pour lequel $m.d=n$, ce qui traduit effectivement l’idée que $n$ est un multiple de $m$.
ii) Si $x$ est une variable pour un nombre réel, nous avons affirmé dans la leçon précédente que la clause $P$ : « $x\geq 0$ » est équivalente à $Q$ : « $x$ est un carré » (c’est une propriété de l’ensemble $\mathbb R$, que nous démontrerons ultérieurement). L’expression rigoureuse de $Q$ se fait à l’aide d’un quantificateur existentiel, sous la forme « $\exists y\in\mathbb R,\ y^2=x$ », clause comprenant la variable libre $x$ et la variable $y$ pour un nombre réel, quantifiée existentiellement.
iii) Si $m$ et $n$ dénotent des entiers naturels génériques, la relation habituelle $m\leq n$ peut se définir à partir de l’addition et d’une quantification existentielle, par la clause $\exists p\in\mathbb N,\ m+p=n$, pour $p$ une nouvelle variable pour un entier naturel. Noter l’analogie avec la définition de la divisibilité.

Remarque 2
Lorsqu’on écrit une clause sous forme symbolique, on ne précise pas les ensembles correspondants aux éléments génériques dénotés par les variables libres : cela est précisé dans le contexte. Par contraste, sous la forme dans laquelle nous présentons ici la quantification, on a tendance à écrire l’ensemble correspondant à chaque variable quantifiée (« $\exists x\in E,\ P$ » plutôt que « $\exists x\ P$ »). Il n’est cependant pas interdit d’omettre l’ensemble de référence dans la quantification, surtout lorsque toutes les variables se rapportent au même ensemble. Le symbolisme n’est pas forcément synonyme de formalisme.

1.3. La quantification universelle

Si $P$ est une clause et $x$ une variable pour les éléments d’un ensemble $E$, la \emph{quantification universelle de $P$ par $x$, notée « $\forall x\in E,\ P$ » (lire « pour tout $x\in E$, $P$ ») est la clause dont la signification est « pour tous les éléments $a$ de $E$, la clause obtenue en substituant $x$ par $a$ dans $P$, est valide ».

Remarque 3
Comme pour la quantification existentielle, on peut trouver des variations de cette notation, que nous emploierons occasionnellement, comme par exemple $(\forall x\in E)\ P$.

Si $x$ est la seule variable libre de $P$, alors la clause « $\forall x\in E,\ P$ » est un énoncé qui est vrai exactement lorsque pour tout élément $a$ de $E$, l’énoncé $P(a/x)$ est vrai. Il est donc faux exactement lorsqu’il existe un élément $a$ de $E$ pour lequel $P(a/x)$ est faux (c’est la version mathématique de « tous les hommes sont mortels »).

On voit ainsi qu’il existe une « dualité » entre la quantification existentielle et la quantification universelle, qui passe par la négation et est analogue d’une dualité entre la disjonction et la conjonction. Nous aurons l’occasion d’y revenir dans deux sections.

Remarque 4
De manière analogue au rapport existant entre l’équivalence logique et la validité universelle de l’équivalence de deux clauses, il existe un rapport entre la quantification universelle et la validité universelle. Si $P$ est une clause possédant une unique variable libre $x$ pour les éléments d’un ensemble $E$, alors $P$ est universellement valide si et seulement si l’énoncé « $\forall x\in E,\ P$ » est vrai, ce qui découle immédiatement des définitions.

Exemple 4
i) Si $P$ est la clause « $(x\geq 0)\Rightarrow(\exists y\in\mathbb R,\ y^2=x)$ », avec $x$ un nombre réel générique (« si $x$ est positif, alors $x$ est un carré), alors l’énoncé $\forall x,\ P$ est vrai car $P$ est universellement valide (voir l’exemple précédent).
ii) Un entier naturel $p$ est appelé un nombre premier s’il est différent de $1$ et n’est divisible que par $1$ et lui-même. On peut exprimer cette propriété par la clause suivante, un peu complexe, où $p$ est un entier naturel générique : « $(p\neq 1)\wedge (\forall n\in\mathbb N,n|p\Rightarrow((n=1)\vee (n=p)))$ ». C’est un bon exercice que de décomposer cette écriture symbolique pour comprendre pourquoi elle exprime que $p$ est un nombre premier.
iii) Contrairement aux nombres réels, tout nombre complexe possède une racine carrée ! Ceci peut s’exprimer symboliquement par l’énoncé « $\forall z\in \mathbb C,\exists w\in \mathbb C,\ w^2=z$ ». On observe ici une combinaison des deux types de quantification.

1.4. Exercices

Exercice 1
i) Utiliser une quantification existentielle pour exprimer la relation $m<n$ entre deux entiers naturels à partir de la seule addition et du nombre $1$.
ii) L’énoncé $\exists x,\ x^2=2$, où $x$ dénote un nombre réel générique, est-il vrai ?
iii) Exprimer symboliquement la propriété « $0$ est le plus petit entier naturel » (c’est-à-dire : « $0$ est inférieur à tout entier naturel ») à l’aide de la relation $\leq$ et d’une quantification universelle.
iv) Ecrire un énoncé faux comportant une quantification universelle.

2. Relations entre les opérations logiques simples