Cours et exercices corrigés de L1 : Logique mathématique, quantificateurs et théorie des ensembles

1. Connecteurs, quantificateurs et négation

• Implication : $P \implies Q$ est fausse uniquement lorsque $P$ est vraie et $Q$ fausse ; elle équivaut à $(\neg P) \text{ ou } Q$.
• Contraposée : $P \implies Q$ équivaut à $\neg Q \implies \neg P$. La réciproque $Q \implies P$ n'a, en général, pas la même valeur de vérité.
• Négation : $\neg(P \text{ et } Q) \iff (\neg P) \text{ ou } (\neg Q)$ et $\neg(P \implies Q) \iff P \text{ et } \neg Q$.
• Négation des quantificateurs : on échange $\forall$ et $\exists$ et on nie la propriété finale :

$$\neg(\forall x \in E,\ P(x)) \iff \exists x \in E,\ \neg P(x) \qquad \neg(\exists x \in E,\ P(x)) \iff \forall x \in E,\ \neg P(x)$$

• Ordre des quantificateurs : « $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$ » est vraie (prendre $y = x + 1$), tandis que « $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$ » est fausse (aucun réel ne majore $\mathbb{R}$).

2. Modes de raisonnement et principe de récurrence

• Absurde : on suppose $\neg P$ et on aboutit à une contradiction. Disjonction des cas : on traite séparément des cas qui recouvrent toutes les situations. Analyse-synthèse : on détermine les solutions possibles (analyse), puis on vérifie qu'elles conviennent (synthèse).
• Récurrence simple : si $P(n_0)$ est vraie et si $\forall n \ge n_0,\ P(n) \implies P(n+1)$, alors $P(n)$ est vraie pour tout $n \ge n_0$.
• Récurrence forte : si $P(n_0)$ est vraie et si, pour tout $n \ge n_0$, $\big(P(n_0), \dots, P(n)\big) \implies P(n+1)$, alors $P(n)$ est vraie pour tout $n \ge n_0$. Exemple : tout entier $n \ge 2$ admet un diviseur premier.

Démonstration du principe de récurrence (à partir de la propriété : toute partie non vide de $\mathbb{N}$ admet un plus petit élément).
1. Posons $A = \{n \ge n_0 \mid P(n) \text{ est fausse}\}$ et supposons, par l'absurde, $A \neq \emptyset$. Soit $m = \min A$.
2. Comme $P(n_0)$ est vraie, $m \neq n_0$, donc $m - 1 \ge n_0$.
3. Par minimalité de $m$, $m - 1 \notin A$ : $P(m-1)$ est vraie.
4. L'hérédité appliquée à $n = m - 1$ donne $P(m)$ vraie, ce qui contredit $m \in A$. Donc $A = \emptyset$.

3. Applications : injectivité, surjectivité, bijectivité

Soit $f : E \to F$ une application.

• $f$ injective : $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ (tout élément de $F$ a au plus un antécédent).
• $f$ surjective : $\forall y \in F,\ \exists x \in E,\ y = f(x)$ (tout élément de $F$ a au moins un antécédent).
• $f$ bijective : injective et surjective. Il existe alors une unique application $f^{-1} : F \to E$ telle que $f^{-1} \circ f = \mathrm{Id}_E$ et $f \circ f^{-1} = \mathrm{Id}_F$.
• Images : pour $A \subset E$, $f(A) = \{f(x) \mid x \in A\}$ ; pour $B \subset F$, $f^{-1}(B) = \{x \in E \mid f(x) \in B\}$ (défini même si $f$ n'est pas bijective).
• Composition : si $g \circ f$ est injective, alors $f$ est injective ; si $g \circ f$ est surjective, alors $g$ est surjective.

Démonstration. Si $f(x) = f(x')$, alors $g(f(x)) = g(f(x'))$, donc $x = x'$ par injectivité de $g \circ f$. Si $z$ est dans l'ensemble d'arrivée de $g$, il existe $x$ tel que $z = g(f(x))$ : $z$ a l'antécédent $f(x)$ par $g$.

4. Relations d'équivalence, classes et ensemble quotient

Une relation $\sim$ sur $E$ est une relation d'équivalence si elle est réflexive ($x \sim x$), symétrique ($x \sim y \implies y \sim x$) et transitive ($x \sim y$ et $y \sim z \implies x \sim z$).

• Classe de $x$ : $\bar{x} = \{y \in E \mid y \sim x\}$. Ensemble quotient : $E/\!\sim$, ensemble des classes.
• Exemple : la congruence modulo $n$ sur $\mathbb{Z}$ ($a \equiv b \ [n] \iff n \mid b - a$) a $n$ classes $\bar{0}, \dots, \overline{n-1}$ ; le quotient est noté $\mathbb{Z}/n\mathbb{Z}$.

Théorème : les classes d'équivalence forment une partition de $E$.
Démonstration.
1. Chaque classe est non vide car $x \in \bar{x}$ (réflexivité), et la réunion des classes est $E$.
2. Supposons $\bar{x} \cap \bar{y} \neq \emptyset$ et soit $z$ dans l'intersection : $z \sim x$ et $z \sim y$, donc $x \sim y$ (symétrie puis transitivité).
3. Si $t \in \bar{x}$, alors $t \sim x$ et $x \sim y$, donc $t \sim y$ : $\bar{x} \subset \bar{y}$. Par symétrie des rôles, $\bar{x} = \bar{y}$. Deux classes sont donc disjointes ou égales.

5. Relations d'ordre, majorants et bornes

Une relation $\preceq$ sur $E$ est une relation d'ordre si elle est réflexive, antisymétrique ($x \preceq y$ et $y \preceq x \implies x = y$) et transitive.

• L'ordre est total si deux éléments sont toujours comparables, partiel sinon. Exemples d'ordres partiels : l'inclusion sur $\mathcal{P}(E)$ (si $E$ a au moins deux éléments), la divisibilité sur $\mathbb{N}^{\ast}$ ($2$ et $3$ ne sont pas comparables).
• Pour $A \subset E$ : $M$ est un majorant de $A$ si $\forall a \in A,\ a \preceq M$ ; c'est le plus grand élément de $A$ si de plus $M \in A$ (il est alors unique).
• La borne supérieure de $A$, si elle existe, est le plus petit des majorants de $A$ ; elle n'appartient pas nécessairement à $A$.

6. Ensembles finis et dénombrement

Soient $E$, $F$ finis, $|E| = p$, $|F| = n$.

• Réunion : $|A \cup B| = |A| + |B| - |A \cap B|$. Produit : $|E \times F| = pn$. Applications : $|F^E| = n^p$.
• Injections de $E$ dans $F$ ($p \le n$) : $n(n-1)\cdots(n-p+1) = \dfrac{n!}{(n-p)!}$ ; permutations de $E$ : $p!$.
• Parties à $p$ éléments d'un ensemble à $n$ éléments : $\binom{n}{p} = \dfrac{n!}{p!\,(n-p)!}$, avec $\binom{n}{p} = \binom{n}{n-p}$ et la formule de Pascal $\binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}$.
• Binôme : $(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}$ dans un anneau commutatif.
• Si $|E| = |F|$ est fini, pour $f : E \to F$ : $f$ injective $\iff$ $f$ surjective $\iff$ $f$ bijective.

Théorème : $|\mathcal{P}(E)| = 2^p$.
Démonstration. L'application $\Phi : \mathcal{P}(E) \to \{0, 1\}^E$ qui à $A$ associe sa fonction indicatrice $\mathbf{1}_A$ est bijective : sa réciproque associe à $g : E \to \{0,1\}$ la partie $g^{-1}(\{1\})$. Donc $|\mathcal{P}(E)| = |\{0,1\}^E| = 2^p$. (Variante : $\sum_{k=0}^p \binom{p}{k} = (1+1)^p$.)