Assertions, prédicats et quantificateurs

La logique mathématique est dite binaire : un énoncé mathématique ne peut prendre que deux valeurs de vérité, vrai (noté $V$ ou $1$) et faux (noté $F$ ou $0$). Il n'y a pas de troisième possibilité, et un énoncé ne peut pas être les deux à la fois.

1. $\sqrt{2} \notin \mathbb{Q}$ est une assertion vraie.
2. « $x > 1$ avec $x \in \mathbb{R}$ » n'est pas une assertion : sa vérité dépend de la valeur de $x$.
3. « Tout entier pair supérieur ou égal à $4$ est la somme de deux nombres premiers » est une assertion : elle est soit vraie, soit fausse — même si personne ne sait aujourd'hui laquelle (c'est la conjecture de Goldbach).
4. $[0, 2[ \,\cap\, [4, 3[ \,=\, [4, 2[$ est une assertion vraie : les deux membres sont l'ensemble vide. Pourquoi $[4, 3[$ et $[4, 2[$ sont-ils vides ?

Soit $\mathcal{P}$ une assertion. Dans une copie :

1. On écrit « Supposons $\mathcal{P}$ » au lieu de « Supposons que $\mathcal{P}$ est vraie ».
2. On écrit « Montrons $\mathcal{P}$ » au lieu de « Montrons que $\mathcal{P}$ est vraie ».
3. Si on écrit « On a $\mathcal{P}$ », alors forcément $\mathcal{P}$ est vraie.

$\mathcal{P}(x)$ : « $x^2 + x + 1 = 0$ avec $x \in \mathbb{R}$ » est un prédicat. $\mathcal{P}(x)$ n'est pas une assertion, mais $\mathcal{P}(0)$ et $\mathcal{P}(\sqrt{2})$ sont des propositions — toutes deux fausses, d'ailleurs. Que peut-on faire de la variable $x$, sans lui donner de valeur, pour transformer $\mathcal{P}(x)$ en assertion ?

Un prédicat peut dépendre de plusieurs variables : on note $\mathcal{P}(x, y)$ un énoncé dépendant de deux variables.

Soient $E$ un ensemble et $\mathcal{P}(x)$ un énoncé mathématique dépendant d'une variable $x \in E$.

1. Pour dire « Il existe $x \in E$ tel que $\mathcal{P}(x)$ », on écrit « $\exists\, x \in E : \mathcal{P}(x)$ ».
2. Le symbole $\exists$ est appelé quantificateur existentiel.
3. Pour dire « Pour tout $x \in E$ on a $\mathcal{P}(x)$ », on écrit « $\forall\, x \in E : \mathcal{P}(x)$ ».
4. Le symbole $\forall$ est appelé quantificateur universel.
5. Pour dire « Il existe un unique élément $x$ de $E$ tel que $\mathcal{P}(x)$ », on écrit « $\exists!\, x \in E : \mathcal{P}(x)$ ».

1. « $\forall\, x \in E : \mathcal{P}(x)$ » est une assertion, qui est vraie si pour tout $x \in E$ on a $\mathcal{P}(x)$.
2. « $\exists\, x \in E : \mathcal{P}(x)$ » est une assertion, qui est vraie s'il existe au moins un élément $x \in E$ tel que $\mathcal{P}(x)$ est vraie.
3. « $\exists!\, x \in E : \mathcal{P}(x)$ » est une proposition, qui est vraie s'il existe un unique élément $x \in E$ tel que $\mathcal{P}(x)$ est vraie.

Un prédicat dont toutes les variables sont quantifiées est donc devenu une assertion : c'est la réponse à la question laissée ouverte plus haut.

1. $\forall\, x \in \mathbb{R} : x^2 + 1 \geq 2x$ est une proposition vraie — c'est l'inégalité $(x-1)^2 \geq 0$ déguisée.
2. « $\exists\, x \in \mathbb{R} : x^2 + x + 1 = 0$ » est une proposition fausse. Comment rédigerait-on proprement la justification de ces deux affirmations ?

Si un énoncé mathématique dépend de plusieurs variables, on peut quantifier successivement chaque variable. Soit $\mathcal{P}(x, y)$ un énoncé dépendant de deux variables.

1. Les propositions « $\forall\, x \in E\ \forall\, y \in F : \mathcal{P}(x, y)$ » et « $\forall\, y \in F\ \forall\, x \in E : \mathcal{P}(x, y)$ » ont la même valeur de vérité : on dit qu'elles sont équivalentes.
2. Même chose pour les propositions « $\exists\, x \in E\ \exists\, y \in F : \mathcal{P}(x, y)$ » et « $\exists\, y \in F\ \exists\, x \in E : \mathcal{P}(x, y)$ ».
3. La proposition « $\forall\, x \in E\ \exists\, y \in F : \mathcal{P}(x, y)$ » signifie : pour tout $x \in E$, il existe $y \in F$ — $y$ dépend de $x$ — tel que $\mathcal{P}(x, y)$.
4. Les propositions « $\forall\, x \in E\ \exists\, y \in F : \mathcal{P}(x, y)$ » et « $\exists\, y \in F\ \forall\, x \in E : \mathcal{P}(x, y)$ » ne sont pas équivalentes.

1. $\forall\, x \in \mathbb{R}\ \forall\, y \in \mathbb{R} : x^2 + y^2 \geq 2|xy|$ est une proposition vraie.
2. $\forall\, x \in \mathbb{R}\ \exists!\, n \in \mathbb{Z} : n \leq x < n+1$ est une proposition vraie : c'est l'existence et l'unicité de la partie entière. L'entier $n$ dépend de $x$.
3. Soit $f : I \to \mathbb{R}$ une fonction. La proposition « $\exists\, M \in \mathbb{R}\ \forall\, x \in I : f(x) \leq M$ » signifie que $f$ est majorée sur $I$.

Lire et écrire un énoncé quantifié. Petit dictionnaire, à savoir parcourir dans les deux sens :

Deux règles de lecture :

1. On lit de gauche à droite : chaque variable introduite peut dépendre de toutes celles introduites avant elle.
2. Une phrase française cache souvent ses quantificateurs (« un carré est toujours positif » signifie $\forall\, x \in \mathbb{R} : x^2 \geq 0$) : les faire apparaître est le premier pas de toute démonstration.

Démontrer un énoncé quantifié :

1. Pour montrer « $\forall\, x \in E : \mathcal{P}(x)$ », on fixe $x$ en écrivant « Soit $x \in E$ », puis on démontre que $\mathcal{P}(x)$ est vraie.
2. Pour montrer « $\forall\, x \in E\ \forall\, y \in F : \mathcal{P}(x, y)$ », on fixe les deux variables par « Soient $x \in E$ et $y \in F$ », puis on montre que $\mathcal{P}(x, y)$ est vraie.
3. Pour montrer « $\forall\, x \in E\ \exists\, y \in F : \mathcal{P}(x, y)$ », on fixe $x$ par « Soit $x \in E$ », puis on cherche un $y \in F$ qui convient — il a le droit de dépendre de $x$.