1.2.3 Quantificateurs. Le raisonnement mathématique.

Définition 1.2.5 (Quantificateur universel)
Soit p(x) un prédicat sur l'ensemble E. Le quantificateur universel $\forall$ lui associe la proposition :

$$\forall x \in E,\ p(x) \stackrel{d\acute{e}f}{\equiv} (\{x \in E/p(x)\}=E)$$

qui est donc vraie si tous les élements de E vérifient la propriété p. On la lit : « Pour tout x dans E, p(x) ».

«  $\forall x \in E,\ p(x)$ » s'écrit aussi «  $\forall y \in E,\ p(y)$ », ou «  $\forall \square \in E,\ p(\square)$ », ou encore « tout élément de $E$ vérifie $p$ »; ce n'est pas un prédicat dont la valeur de vérité dépend d'une variable, mais une proposition vraie ou fausse ; la lettre $x$ (ou $y$ ou $\square$) n'y figure pas vraiment, en ce sens qu'elle ne désigne pas un objet déterminé ^1.24.

Exemple :

Soit $p(x)$ le prédicat « $x$ est mortel » sur l'ensemble $H$ des êtres humains. «  $\forall x \in H,\ p(x)$ » est la proposition « Tout humain est mortel » (Platon).

Définition 1.2.6 (Quantificateur existentiel)
Soit p(x) un prédicat sur l'ensemble E. Le quantificateur existentiel $\exists$ lui associe la proposition :

$$\exists\, x \in E,\ p(x) \stackrel{d\acute{e}f}{\equiv} (\{x \in E/p(x)\}= \emptyset)$$

qui est donc vraie s'il existe au moins un élement de E vérifiant la propriété p. On la lit : « Il existe x dans E, p(x) ».^1.25

Les propositions «  $\forall x \in E,\ p(x)$ » et «  $\exists\, x \in E,\ p(x)$ » s'appellent des propositions quantifiées : on y compte (quantifie) les éléments de E vérifiant la propriété $p$.

Théorème 1.2.4 (Négation des propositions quantifiées)

non( $\forall x \in E,\ p(x)$) $\equiv \exists\, x \in E,\ \overline{p(x)}$

non( $\exists\, x \in E,\ p(x)$) $\equiv \forall x \in E,\ \overline{p(x)}$

Démonstration :

Il est clair que $\overline{\{x \in E/p(x)\}= E} \equiv \{x \in E/p(x)\}\neq E$. Si l'ensemble $\{x \in E/p(x)\}$ est différent de $E$, son complémentaire dans $E$, qui est égal à $\{x \in E/\overline{p(x)}\}$, n'est pas vide, donc contient un élement au moins.

Exemple :

La négation de « Tout humain est mortel » est « Il existe au moins un humain immmortel », et non pas « Tout humain est immortel », ni « Tout non humain est immortel », ni « Il existe un non humain immortel »: pour prouver que « Tout humain est mortel » est une proposition fausse, il faut trouver une exception, un humain non mortel. En mathématiques, une telle exception s'appelle un contre-exemple (voir 1.2.3).

Pour trouver la négation d'une proposition quantifiée, on remplace donc mécaniquement $\forall$ par $\exists$, et vice versa, et le prédicat qui suit par sa négation. Mais ceci ne dispense pas de réfléchir au sens de ces propositions, comme le montre l'exemple précédent.

Exercice 1..14
Écrire les négations des propositions suivantes :

$p \equiv \forall\ x \in {\mathbb{R}},\ x^2 \in {\mathbb{Q}} \Longrightarrow x \in {\mathbb{Q}}$

$q \equiv \forall\ \varepsilon \in ]0,+\infty[,\ \exists\, n_0 \in {\mathbb{N}}... ...\mathbb{N}},\ n \geqslant n_0 \Longrightarrow \vert x_n - l\vert < \varepsilon$

(pour fixer les idées, $x_0,x_1,x_2,\,\ldots,x_k,\ldots$ et $l$ sont des nombres réels).

Remarques sur cet exercice:

La proposition p est fausse : $\sqrt{2}$ fournit un contre-exemple.

La proposition $q$ affirme que $l$ est la limite de la suite $(x_n)_{n \in {\mathbb{N}}}$ : elle dit que pour $n$ assez grand ( $n \geqslant n_0$), $x_n$ est aussi proche que l'on veut de $l$ ( $\vert x_n - l\vert < \varepsilon$). Sa négation affirme qu'il existe un $\varepsilon > 0$ tel que, même si $n_0$ est grand, il y a au moins un $n$ plus grand ($n > n_0$) pour lequel $x_n$ est loin de $n$ ( $\vert x_n - l\vert > \varepsilon$). Mais il n'est pas indispensable de savoir cela pour écrire la négation de $q$.

Tout ce qui précède nous permet de distinguer trois types de raisonnement en mathématiques :

Le raisonnement par déduction :

Pour démontrer le théorème $\forall x \in E,\ H(x) \Longrightarrow C(x)$, on suppose que $x$ vérifie l'hypothèse $H(x)$, et on en déduit que la conclusion $C(x)$ est vraie.

Le raisonnement par l'absurde :

Pour démontrer la proposition $\forall x \in E,\ H(x) \Longrightarrow C(x)$, qui est identique à $\forall x \in E,\ \overline{C(x)} \Longrightarrow \overline{H(x)}$^1.26, on suppose que $x$ ne vérifie pas la conclusion $C(x)$, et on en déduit une contradicion avec l'hypothèse $H(x)$.

Le raisonnement par contre-exemple :

Pour démontrer que la proposition $\forall x \in E,\ H(x) \Longrightarrow C(x)$ est fausse, c'est-à-dire que $\exists\, x \in E,\ H(x)$. $\overline{C(x)}$ est vraie, on cherche un $x \in E$ - un contre-exemple - vérifiant $H(x)$ et ne vérifiant pas $C(x)$.

Il existe un quatrième mode de raisonnement, le raisonnement par récurrence, que nous verrons au chapitre suivant.

Exercice 1..15
En utilisant un raisonnement par contre-exemples, démontrez que :

$A \cap B = A \cap C \Longrightarrow B = C$ est faux.

$A \cup B = A \cup C \Longrightarrow B = C$ est faux.

Dans cet exercice on n'a pas précisé l'ensemble de référence pour les prédicats. Il s'agit de l'ensemble ${\mathfrak{P}}(E)$ des sous-ensembles d'un ensemble $E$. La première proposition s'écrirait alors $\forall A \in {\mathfrak{P}}(E),\ \forall B \in {\mathfrak{P}}(E),\ \forall C \in {\mathfrak{P}}(E),\ A \cap B = A \cap C \Longrightarrow B = C$. On évitera si possible es notations si lourdes.^1.27

Exercice 1..16
En décomposant $B,\ C,\ A \cap B,\ A \cap C, \ A \cup B,\ A \cup C$ en sous-ensembles élémentaires fonctions de $A$ $B$ $C$, démontrez que :

$$\left. \begin{array}{l} A \cap B = A \cap C\\ A \cup B = A \cup C\\ \end{array}\right\rbrace \Longrightarrow B = C$$