Ensembles et applications SM

(\(\Rightarrow\)) Si \(A = B\), tout élément de \(A\) est dans \(B\) (donc \(A \subset B\)) et tout élément de \(B\) est dans \(A\) (donc \(B \subset A\)).

(\(\Leftarrow\)) Supposons \(A \subset B\) et \(B \subset A\). Soit \(x\) quelconque.

\(\bullet\) Si \(x \in A\), par \(A \subset B\), \(x \in B\).

\(\bullet\) Si \(x \in B\), par \(B \subset A\), \(x \in A\).

Donc \(x \in A \Leftrightarrow x \in B\), ce qui équivaut à \(A = B\). \(\square\)

(b) Transitivité. Soient \(x \in A\). Comme \(A \subset B\), \(x \in B\). Comme \(B \subset C\), \(x \in C\). Donc \(x \in A \Rightarrow x \in C\), ce qui prouve \(A \subset C\).

(a) et (c) sont immédiates par la définition. \(\square\)

Démonstration par récurrence sur \(n\).

Initialisation (\(n = 0\)). Si \(\mathrm{Card}(E) = 0\), alors \(E = \emptyset\) et \(\mathcal{P}(\emptyset) = \{\emptyset\}\), qui a \(1 = 2^0\) élément.

Hérédité. Supposons la propriété vraie pour tout ensemble à \(n\) éléments. Soit \(E\) un ensemble de cardinal \(n + 1\). Fixons \(a \in E\) et posons \(E' = E \setminus \{a\}\) (qui a \(n\) éléments).

Les parties de \(E\) se répartissent en deux catégories disjointes :

• celles qui ne contiennent pas \(a\) : ce sont exactement les parties de \(E'\).

• celles qui contiennent \(a\) : ce sont exactement les ensembles de la forme \(A \cup \{a\}\) avec \(A \subset E'\).

La première catégorie a \(\mathrm{Card}(\mathcal{P}(E')) = 2^n\) éléments par hypothèse de récurrence. Pour la seconde, l’application
\[\Phi : \mathcal{P}(E') \to \bigl\{\, B \subset E \;|\; a \in B\,\bigr\}, \quad A \mapsto A \cup \{a\}\]
est bijective : son inverse est \(B \mapsto B \setminus \{a\}\). La seconde catégorie a donc aussi \(2^n\) éléments. Donc
\[\mathrm{Card}(\mathcal{P}(E)) = 2^n + 2^n = 2^{n+1}.\]
\(\square\)

\(\overline{(\overline{A})} = A\) : pour tout \(x \in E\),
\[x \in \overline{(\overline{A})} \;\Leftrightarrow\; (x \in E \wedge x \notin \overline{A}) \;\Leftrightarrow\; (x \in E \wedge x \in A) \;\Leftrightarrow\; x \in A,\]
la dernière équivalence venant de \(A \subset E\). \(\square\)

Commutativité de \(\cap\) : pour tout \(x \in E\),
\[x \in A \cap B \;\Leftrightarrow\; (x \in A) \wedge (x \in B) \;\Leftrightarrow\; (x \in B) \wedge (x \in A) \;\Leftrightarrow\; x \in B \cap A,\]
grâce à la commutativité de la conjonction logique. Les autres propriétés se démontrent de manière analogue, en remontant aux propriétés des connecteurs logiques. \(\square\)

Distributivité de \(\cap\) sur \(\cup\). Pour tout \(x \in E\) :
\[\begin{align*} x \in A \cap (B \cup C) &\;\Leftrightarrow\; (x \in A) \wedge \bigl((x \in B) \vee (x \in C)\bigr) \\ &\;\Leftrightarrow\; \bigl((x \in A) \wedge (x \in B)\bigr) \vee \bigl((x \in A) \wedge (x \in C)\bigr) \quad \text{(distributivité de } \wedge \text{ sur } \vee \text{)} \\ &\;\Leftrightarrow\; (x \in A \cap B) \vee (x \in A \cap C) \\ &\;\Leftrightarrow\; x \in (A \cap B) \cup (A \cap C). \end{align*}\]

Loi de De Morgan. Pour tout \(x \in E\) :
\[\begin{align*} x \in \overline{A \cap B} &\;\Leftrightarrow\; x \notin A \cap B \\ &\;\Leftrightarrow\; \overline{\bigl((x \in A) \wedge (x \in B)\bigr)} \\ &\;\Leftrightarrow\; (x \notin A) \vee (x \notin B) \quad \text{(De Morgan logique)} \\ &\;\Leftrightarrow\; (x \in \overline{A}) \vee (x \in \overline{B}) \\ &\;\Leftrightarrow\; x \in \overline{A} \cup \overline{B}. \end{align*}\]
\(\square\)

\((1) \Rightarrow (2)\) : Supposons \(A \subset B\). Toujours \(A \cap B \subset A\). Réciproquement, soit \(x \in A\) ; alors \(x \in B\) par hypothèse, donc \(x \in A \cap B\). Conclusion : \(A \cap B = A\).

\((2) \Rightarrow (1)\) : Si \(A \cap B = A\) et \(x \in A\), alors \(x \in A \cap B\), donc \(x \in B\). Donc \(A \subset B\).

Les équivalences \((1) \Leftrightarrow (3)\) et \((1) \Leftrightarrow (4)\) se démontrent de façon analogue. \(\square\)

\(x \in A \bigtriangleup B\) ssi \(x\) appartient à exactement un des deux ensembles, c’est-à-dire \(x \in A \cup B\) mais \(x \notin A \cap B\).

Formellement, \(x \in A \bigtriangleup B \Leftrightarrow (x \in A \setminus B) \vee (x \in B \setminus A) \Leftrightarrow \bigl((x \in A) \wedge (x \notin B)\bigr) \vee \bigl((x \in B) \wedge (x \notin A)\bigr)\), qui est précisément la condition « \(x\) appartient à un seul des deux ». Ce « ou exclusif » s’écrit aussi \((x \in A \cup B) \wedge (x \notin A \cap B)\). \(\square\)

(d) Image réciproque d’une réunion. Soit \(x \in E\).
\[\begin{align*} x \in f^{-1}(B \cup B') &\;\Leftrightarrow\; f(x) \in B \cup B' \\ &\;\Leftrightarrow\; \bigl(f(x) \in B\bigr) \vee \bigl(f(x) \in B'\bigr) \\ &\;\Leftrightarrow\; (x \in f^{-1}(B)) \vee (x \in f^{-1}(B')) \\ &\;\Leftrightarrow\; x \in f^{-1}(B) \cup f^{-1}(B'). \end{align*}\]

(c) Inégalité stricte pour l’intersection. Soit \(y \in f(A \cap A')\) : il existe \(x \in A \cap A'\) avec \(y = f(x)\). Alors \(x \in A\), donc \(y \in f(A)\) ; et \(x \in A'\), donc \(y \in f(A')\). D’où \(y \in f(A) \cap f(A')\).

Contre-exemple à l’égalité. Prendre \(f : \mathbb{R} \to \mathbb{R}\), \(x \mapsto x^2\), \(A = \{-1\}\), \(A' = \{1\}\). Alors \(A \cap A' = \emptyset\), donc \(f(A \cap A') = \emptyset\). Mais \(f(A) = f(A') = \{1\}\), donc \(f(A) \cap f(A') = \{1\} \neq \emptyset\). \(\square\)

(d). Supposons \(g \circ f = \mathrm{id}_E\) et \(f \circ g = \mathrm{id}_F\).

\(f\) injective : si \(f(x_1) = f(x_2)\), en appliquant \(g\) : \(g(f(x_1)) = g(f(x_2))\), c’est-à-dire \(x_1 = x_2\) (puisque \(g \circ f = \mathrm{id}_E\)).

\(f\) surjective : soit \(y \in F\). Posons \(x = g(y) \in E\). Alors \(f(x) = f(g(y)) = (f \circ g)(y) = \mathrm{id}_F(y) = y\). Donc \(y\) admet \(x\) pour antécédent.

Conclusion : \(f\) est bijective. Pour tout \(y \in F\), l’unique antécédent de \(y\) est \(x = g(y)\) ; donc \(f^{-1}(y) = g(y)\), soit \(g = f^{-1}\). \(\square\)

(a) Associativité. Pour tout \(x \in E\) :
\[\bigl((h \circ g) \circ f\bigr)(x) = (h \circ g)(f(x)) = h(g(f(x))) \quad ; \quad \bigl(h \circ (g \circ f)\bigr)(x) = h\bigl((g \circ f)(x)\bigr) = h(g(f(x))).\]
Les deux applications coïncident sur \(E\), donc sont égales.

(c) Injectivité. Supposons \(f, g\) injectives. Soit \(x_1, x_2 \in E\) tels que \((g \circ f)(x_1) = (g \circ f)(x_2)\). Alors \(g(f(x_1)) = g(f(x_2))\). Comme \(g\) est injective, \(f(x_1) = f(x_2)\). Comme \(f\) est injective, \(x_1 = x_2\). Donc \(g \circ f\) est injective.

(e) Inverse de la composée. Si \(f, g\) bijectives, \(g \circ f\) est bijective d’après (c) et (d). Montrons \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\) en utilisant la caractérisation : il suffit de vérifier que \((f^{-1} \circ g^{-1}) \circ (g \circ f) = \mathrm{id}_E\) et \((g \circ f) \circ (f^{-1} \circ g^{-1}) = \mathrm{id}_G\).

Par associativité :
\[(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ \mathrm{id}_F \circ f = f^{-1} \circ f = \mathrm{id}_E.\]
Symétriquement pour l’autre. \(\square\)