Prédicats et quantificateurs

Au chapitre 1, on a soigneusement refusé d’appeler « $x > 3$ » une proposition : impossible de dire si c’est vrai ou faux tant que $x$ n’est pas fixé. Pourtant les mathématiques débordent d’énoncés de ce genre. Comment leur rendre une valeur de vérité, et donc le droit d’entrer dans une démonstration ?

La réponse tient en deux gestes : nommer ces énoncés à trou, ce sont les prédicats, puis les fermer avec deux mots minuscules et redoutables, « pour tout » et « il existe ». À la fin de ce chapitre, tu sauras transformer n’importe quel énoncé ouvert en proposition, le nier correctement, et tu auras compris le piège qui fait trébucher tout le monde : l’ordre dans lequel on empile « pour tout » et « il existe ».

L’énoncé à trou

Reprends « $x > 3$ ». Ce n’est pas une proposition, mais ce n’est pas du bruit non plus : dès qu’on remplace $x$ par un nombre, la phrase devient vraie ($x = 5$) ou fausse ($x = 1$). C’est un formulaire avec une case à remplir.

Un prédicat Prédicat Énoncé contenant une ou plusieurs variables libres, dont la valeur de vérité dépend de ce que l'on substitue à ces variables. « x > 3 » est un prédicat : il n'est ni vrai ni faux tant que x n'est pas fixé ou quantifié. Une fois toutes ses variables fixées ou liées par un quantificateur, un prédicat devient une proposition. est exactement cela : un énoncé contenant une ou plusieurs variables, dont la valeur de vérité dépend de ce qu’on met dans les cases. On le note comme une fonction : $P(x)$, $Q(x, y)$. Ici $P(x)$ signifie « $x > 3$ », et :

• $P(5)$ est la proposition « $5 > 3$ », vraie.
• $P(1)$ est la proposition « $1 > 3$ », fausse.

Tant que la variable reste libre, $P(x)$ n’est ni vrai ni faux : il attend. Il y a deux façons de le faire passer à l’état de proposition. La première, on vient de la voir : substituer une valeur. La seconde, bien plus puissante, est de quantifier la variable, c’est-à-dire dire d’un coup quelque chose sur toutes les valeurs possibles, ou sur au moins une.

Sur quoi varie la variable : le domaine de discours

Avant de quantifier, une question qu’on ne peut pas esquiver : $x$ varie sur quoi ? Les entiers ? Les réels ? Les habitants d’une ville ? Cet ensemble de référence s’appelle le domaine de discours Domaine de discours L'ensemble des objets sur lesquels portent les variables d'un prédicat quantifié. La vérité d'un énoncé quantifié en dépend entièrement : « ∃x, x² = 2 » est faux sur les entiers mais vrai sur les réels. Préciser le domaine n'est donc pas un détail, c'est une partie de l'énoncé. , et il fait partie de l’énoncé au même titre que le prédicat.

Ce n’est pas un détail bureaucratique. Considère « il existe un nombre dont le carré vaut $2$ » :

• sur le domaine des entiers, c’est faux (aucun entier au carré ne donne $2$) ;
• sur le domaine des réels, c’est vrai ($\sqrt{2}$ existe).

Même prédicat, même quantificateur, vérités opposées : seul le domaine a changé. Retiens la règle : un énoncé quantifié sans domaine précisé est incomplet.

Les deux quantificateurs

Quantifier, c’est lier la variable : elle cesse d’être une case libre pour devenir le sujet d’une affirmation globale. Il y a deux manières de le faire.

Pour tout : ∀

Le quantificateur universel Quantificateur universel Le symbole ∀, qui se lit « pour tout » ou « quel que soit ». L'énoncé ∀x, P(x) est vrai lorsque le prédicat P est vrai pour chaque élément du domaine de discours, sans exception. Pour le mettre en défaut, il suffit d'un seul contre-exemple. se note $\forall$ et se lit « pour tout » ou « quel que soit ». L’énoncé

$$\forall x,\ P(x)$$

se lit « pour tout $x$ du domaine, $P(x)$ est vrai ». Il affirme que chaque élément, sans exception, satisfait le prédicat.

• Sur les entiers, $\forall n,\ n + 0 = n$ est vrai.
• Sur les entiers, $\forall n,\ n > 3$ est faux (prends $n = 2$).

Il existe : ∃

Le quantificateur existentiel Quantificateur existentiel Le symbole ∃, qui se lit « il existe ». L'énoncé ∃x, P(x) est vrai dès qu'au moins un élément du domaine de discours rend le prédicat P vrai. Cet élément s'appelle un témoin. L'existence n'exige pas l'unicité : un ou plusieurs témoins suffisent. se note $\exists$ et se lit « il existe ». L’énoncé

$$\exists x,\ P(x)$$

se lit « il existe au moins un $x$ du domaine tel que $P(x)$ est vrai ». Un tel $x$ s’appelle un témoin. Attention au sens courant : « il existe » ne veut pas dire « il existe un unique ». Un témoin suffit, plusieurs sont permis.

• Sur les entiers, $\exists n,\ n > 3$ est vrai ($n = 4$ est un témoin, $n = 100$ aussi).
• Sur les entiers, $\exists n,\ n^2 = 2$ est faux : aucun témoin.

Nier un quantificateur

Comment réfute-t-on « pour tout $x$, $P(x)$ » ? Pas en vérifiant tous les cas, ce serait sans fin. Il suffit d’un seul raté. Et symétriquement, nier « il existe » revient à dire « aucun », donc « tous échouent ». Ces deux règles sont la suite directe des lois de De Morgan du chapitre 1, étendues du fini à l’infini :

¬(∀x, P(x)) ≡ ∃x, ¬P(x) | ¬(∃x, P(x)) ≡ ∀x, ¬P(x)

En clair : nier « tous vérifient $P$ » donne « il en existe un qui ne le vérifie pas » ; nier « il en existe un qui vérifie $P$ » donne « tous ne le vérifient pas ». Le quantificateur bascule, et la négation glisse à l’intérieur, sur le prédicat. C’est exactement le mouvement de De Morgan ($\lnot$ transforme $\land$ en $\lor$), vu ici comme un « et » infini qui devient un « ou » infini.

De la première règle naît l’outil le plus économique des mathématiques. Pour démolir une affirmation universelle, on exhibe un contre-exemple Contre-exemple Un élément du domaine qui rend faux un énoncé universel. Pour réfuter « ∀x, P(x) », il suffit d'exhiber un seul x tel que P(x) est faux : c'est la traduction directe de l'équivalence ¬(∀x, P(x)) ≡ ∃x, ¬P(x). Un contre-exemple démolit une conjecture sans qu'il soit besoin d'en dire plus. : un seul élément du domaine où le prédicat est faux. Un contre-exemple ne « discute » pas une conjecture, il la tue.

Le piège : l’ordre des quantificateurs

Voici le point qui fait trébucher tout le monde, et la vraie raison d’être de ce chapitre. Quand on empile deux quantificateurs différents, leur ordre change le sens. Compare :

∀x ∃y, R(x, y) | ∃y ∀x, R(x, y)

• $\forall x\, \exists y,\ R(x, y)$ : « pour chaque $x$, il existe un $y$ (qui peut dépendre de $x$) tel que $R$ ». Chacun a son partenaire, possiblement différent.
• $\exists y\, \forall x,\ R(x, y)$ : « il existe un $y$ qui marche pour tous les $x$ à la fois ». Un partenaire universel, le même pour tout le monde.

L’analogie qui grave la différence : « tout le monde a une mère » ($\forall x\, \exists y$, $y$ est la mère de $x$) est vrai. « il existe une mère de tout le monde » ($\exists y\, \forall x$) est faux, heureusement. Mêmes mots, ordre inversé, vérités opposées.

Manipule-le toi-même ci-dessous. La grille est la relation $R(x, y)$ : une case cochée signifie « $x$ est relié à $y$ ». Elle démarre sur la diagonale : chacun est relié à lui-même, et à personne d’autre. Ta mission : laisse l’énoncé sur $\forall x\, \exists y$ et lis le verdict, puis clique « Échanger les axes » pour passer à $\exists y\, \forall x$ sans rien changer d’autre. Le même tableau, deux verdicts.

Pour se convaincre du sens des flèches, le diagramme suivant met côte à côte les deux lectures sur la diagonale. À gauche, chaque $x$ pointe vers son propre témoin : trois flèches, l’énoncé universel-existentiel tient. À droite, on cherche un seul $y$ que tous atteignent : aucune colonne ne reçoit trois flèches, l’énoncé existentiel-universel tombe.

En une phrase

Un prédicat est un énoncé à trou ; le quantifier par « pour tout » ou « il existe » sur un domaine précis le referme en une proposition vraie ou fausse, sa négation échange les deux quantificateurs, et leur ordre n’est jamais innocent.

Vers le chapitre 3

On a parlé sans cesse du « domaine de discours », l’ensemble sur lequel varient les variables, en se contentant d’une idée intuitive : une collection d’objets. Mais qu’est-ce qu’un ensemble, au juste ? Comment le décrit-on, comment teste-t-on qu’un objet lui appartient, comment en fabrique-t-on de nouveaux à partir d’anciens ? Les quantificateurs de ce chapitre vont devenir le langage même de cette construction : « $A \subseteq B$ » se dira « $\forall x,\ x \in A \Rightarrow x \in B$ ». C’est tout le chapitre 3, la théorie des ensembles.

Exercices

Prends une feuille et un crayon. Les corrigés sont juste en dessous, regarde-les seulement après avoir essayé.

Exercice 1 : nier proprement

Le domaine est l’ensemble des êtres humains. Soit l’énoncé « tout le monde aime au moins une personne », écrit $\forall x\, \exists y,\ A(x, y)$ où $A(x, y)$ signifie « $x$ aime $y$ ». Écrire sa négation en faisant glisser le $\lnot$ jusqu’au prédicat, puis la traduire en français courant.

Exercice 2 : l’ordre décide

Le domaine est l’ensemble des entiers strictement positifs $\{1, 2, 3, \dots\}$. On pose $R(x, y)$ : « $y > x$ ». Déterminer si $\forall x\, \exists y,\ R(x, y)$ est vrai, puis si $\exists y\, \forall x,\ R(x, y)$ est vrai. Justifier chaque réponse.

Sources

• Frege, G. (1879). Begriffsschrift. Louis Nebert. L’acte de naissance de la notation des quantificateurs.
• Euler, L. (1732). « Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus. » Commentarii academiae scientiarum Petropolitanae. La réfutation de la conjecture de Fermat sur les nombres de Fermat.

Pour aller plus loin

• Cori, R. & Lascar, D. (2003). Logique mathématique, tome 1. Dunod. Le traitement rigoureux du calcul des prédicats.
• Velleman, D. J. (2019). How to Prove It. Cambridge University Press. Chapitres 2 et 3, excellents sur les quantificateurs et leur négation.
• Halmos, P. (1960). Naive Set Theory. Van Nostrand. Pour préparer le chapitre 3 en douceur.