Dénombrement

Montrons les deux implications.

$\boldsymbol{(\Rightarrow)}$ Supposons que $\text{card}\, E = \text{card}\, F = n$. Par la Définition 1.1, il existe une bijection $\varphi : \llbracket 1, n \rrbracket \to E$ et une bijection $\psi : \llbracket 1, n \rrbracket \to F$. Alors $\psi \circ \varphi^{-1} : E \to F$ est une composée de bijections, donc une bijection de $E$ sur $F$.

$\boldsymbol{(\Leftarrow)}$ Supposons qu'il existe une bijection $f : E \to F$. Montrons que $\text{card}\, E = \text{card}\, F$. Par la Définition 1.1, il existe un entier $n \in \mathbb{N}^*$ et une bijection $\varphi : \llbracket 1, n \rrbracket \to E$. Alors $f \circ \varphi : \llbracket 1, n \rrbracket \to F$ est une bijection, ce qui montre, par définition, que $\text{card}\, F = n = \text{card}\, E$.

Le cas $E = \emptyset$ : si $\text{card}\, E = \text{card}\, F = 0$, alors $E = F = \emptyset$ et l'application vide est la seule bijection de $E$ sur $F$.

Soit $E$ un ensemble fini de cardinal $n = \text{card}\, E$ et $A \subseteq E$.

$A$ est fini. Par la Définition 1.1, il existe une bijection $\varphi : \llbracket 1, n \rrbracket \to E$. Notons $I = \varphi^{-1}(A) \subseteq \llbracket 1, n \rrbracket$. La restriction $\varphi|_{I} : I \to A$ est alors bijective. Or toute partie $I$ de $\llbracket 1, n \rrbracket$ est finie (elle est en bijection avec $\llbracket 1, \text{card}\, I \rrbracket$ en réordonnant ses éléments). Donc $A$ est fini et $\text{card}\, A = \text{card}\, I \le n = \text{card}\, E$.

Cas d'égalité. Si $A = E$, alors clairement $\text{card}\, A = \text{card}\, E$. Réciproquement, si $\text{card}\, A = \text{card}\, E = n$, alors $A \subseteq E$ et $|A| = n$ impliquent $A = E$ (on ne peut pas avoir une partie stricte de $\llbracket 1, n \rrbracket$ de cardinal $n$).

Posons $n_E = \text{card}\, E$, $n_F = \text{card}\, F$, $n_{\cap} = \text{card}(E \cap F)$. On remarque que $\{E \setminus F,\, E \cap F,\, F \setminus E\}$ est une partition de $E \cup F$ (les trois ensembles sont disjoints deux à deux et leur réunion est $E \cup F$).

Par la Proposition 1.4 appliquée à cette partition :
$$\text{card}(E \cup F) = \text{card}(E \setminus F) + \text{card}(E \cap F) + \text{card}(F \setminus E).$$

De même, $\{E \setminus F,\, E \cap F\}$ est une partition de $E$, donc par la Proposition 1.4 :
$$\text{card}\, E = \text{card}(E \setminus F) + \text{card}(E \cap F),$$
d'où $\text{card}(E \setminus F) = \text{card}\, E - \text{card}(E \cap F)$.

De même, $\text{card}(F \setminus E) = \text{card}\, F - \text{card}(E \cap F)$.

En substituant :
$$\text{card}(E \cup F) = (\text{card}\, E - n_{\cap}) + n_{\cap} + (\text{card}\, F - n_{\cap}) = \text{card}\, E + \text{card}\, F - \text{card}(E \cap F).$$

On raisonne par récurrence sur $n$, le nombre de parties de la partition.

Initialisation ($n = 1$). La partition est $(A_1)$ avec $E = A_1$, donc $\text{card}\, E = \text{card}\, A_1$. C'est immédiat.

Hérédité. Supposons le résultat vrai pour une partition en $n$ parties. Soit $(A_i)_{1 \le i \le n+1}$ une partition de $E$. Posons $E' = \bigsqcup_{i=1}^{n} A_i$. Alors $(A_1, \dots, A_n)$ est une partition de $E'$, donc par hypothèse de récurrence :
$$\text{card}\, E' = \sum_{i=1}^{n} \text{card}\, A_i.$$

De plus, $\{E', A_{n+1}\}$ est une partition de $E$ en deux parties disjointes. Par la Proposition 1.3 appliquée à $E' \cup A_{n+1} = E$ avec $E' \cap A_{n+1} = \emptyset$ :
$$\text{card}\, E = \text{card}\, E' + \text{card}\, A_{n+1} = \sum_{i=1}^{n} \text{card}\, A_i + \text{card}\, A_{n+1} = \sum_{i=1}^{n+1} \text{card}\, A_i.$$

Le résultat est établi par récurrence.

On observe que $\{A, \bar{A}\}$ est une partition de $E$ : en effet, $A$ et $\bar{A} = E \setminus A$ sont disjoints par définition du complémentaire, non vides (si l'un était vide, l'égalité de cardinal serait triviale), et leur réunion est $E$.

Par la Proposition 1.4 appliquée à cette partition en deux parties :
$$\text{card}\, E = \text{card}\, A + \text{card}(\bar{A}).$$

On en déduit immédiatement :
$$\text{card}(\bar{A}) = \text{card}\, E - \text{card}\, A.$$

Posons $p = \text{card}\, E$ et $q = \text{card}\, F$. Par la Définition 1.1, il existe des bijections $\varphi : \llbracket 1, p \rrbracket \to E$ et $\psi : \llbracket 1, q \rrbracket \to F$.

L'application
$$\Phi : \llbracket 1, p \rrbracket \times \llbracket 1, q \rrbracket \to E \times F, \quad (i, j) \mapsto (\varphi(i), \psi(j))$$
est bijective (elle est injective car $\varphi$ et $\psi$ le sont, et surjective car tout $(x, y) \in E \times F$ s'écrit $(\varphi(i), \psi(j))$ avec $i = \varphi^{-1}(x)$ et $j = \psi^{-1}(y)$).

Or l'ensemble $\llbracket 1, p \rrbracket \times \llbracket 1, q \rrbracket$ a $pq$ éléments (on peut le mettre en bijection avec $\llbracket 1, pq \rrbracket$ par l'ordre lexicographique). Donc $E \times F$ est fini et
$$\text{card}(E \times F) = pq = \text{card}\, E \times \text{card}\, F.$$

On procède par récurrence sur $p \ge 1$.

Initialisation ($p = 1$). $\prod_{i=1}^{1} E_i = E_1$ est fini et $\text{card}\, E_1 = \prod_{i=1}^{1} \text{card}\, E_i$. C'est immédiat.

Hérédité. Supposons le résultat vrai au rang $p$. On a
$$\prod_{i=1}^{p+1} E_i = \left(\prod_{i=1}^{p} E_i\right) \times E_{p+1}.$$
Par hypothèse de récurrence, $\prod_{i=1}^{p} E_i$ est fini et $\text{card}\left(\prod_{i=1}^{p} E_i\right) = \prod_{i=1}^{p} \text{card}\, E_i$. Par la Proposition 1.5 :
$$\text{card}\left(\prod_{i=1}^{p+1} E_i\right) = \text{card}\left(\prod_{i=1}^{p} E_i\right) \times \text{card}\, E_{p+1} = \prod_{i=1}^{p} \text{card}\, E_i \times \text{card}\, E_{p+1} = \prod_{i=1}^{p+1} \text{card}\, E_i.$$

Le résultat est établi par récurrence.

Posons $p = \text{card}\, E$ et $q = \text{card}\, F$. Par la Définition 1.1, il existe des bijections $\varphi : \llbracket 1, p \rrbracket \to E$ et $\psi : \llbracket 1, q \rrbracket \to F$.

Tout élément de $F^E$ est une application de $E$ dans $F$. Via $\varphi$, on peut identifier $F^E$ avec l'ensemble des applications de $\llbracket 1, p \rrbracket$ dans $F$. Plus précisément, l'application
$$\Phi : F^E \to F^{\llbracket 1,p \rrbracket}, \quad f \mapsto f \circ \varphi$$
est bijective (de bijection réciproque $g \mapsto g \circ \varphi^{-1}$).

Or une application de $\llbracket 1, p \rrbracket$ dans $F$ est entièrement déterminée par les $p$ valeurs $(f(1), \dots, f(p)) \in F^p$. Par le Corollaire 1.2 (produit cartésien de $p$ copies de $F$) :
$$\text{card}(F^{\llbracket 1,p \rrbracket}) = \text{card}(F^p) = (\text{card}\, F)^p = q^p.$$

Donc $F^E$ est fini et $\text{card}(F^E) = (\text{card}\, F)^{\text{card}\, E}$.

Soit $E$ un ensemble fini de cardinal $n$. Pour toute partie $A \subseteq E$, notons $\mathbf{1}_A : E \to \{0, 1\}$ sa fonction indicatrice, définie par $\mathbf{1}_A(x) = 1$ si $x \in A$ et $\mathbf{1}_A(x) = 0$ sinon.

L'application
$$\Phi : \mathcal{P}(E) \to \{0,1\}^E, \quad A \mapsto \mathbf{1}_A$$
est bijective : elle est injective (si $\mathbf{1}_A = \mathbf{1}_B$ alors $A = B$) et surjective (pour $f \in \{0,1\}^E$, la partie $A = f^{-1}(\{1\})$ vérifie $\mathbf{1}_A = f$).

Par la Proposition 1.1, $\text{card}\, \mathcal{P}(E) = \text{card}(\{0,1\}^E)$.

Or, par la Proposition 1.6 appliquée à $F = \{0,1\}$ (de cardinal $2$) et $E$ (de cardinal $n$) :
$$\text{card}(\{0,1\}^E) = 2^n = 2^{\text{card}\, E}.$$

Donc $\mathcal{P}(E)$ est fini et $\text{card}\, \mathcal{P}(E) = 2^{\text{card}\, E}$.

Montrons les deux points séparément.

(i) $f$ injective, $F$ fini $\Rightarrow$ $E$ fini et $\text{card}\, E \le \text{card}\, F$.

Posons $n = \text{card}\, F$. Comme $f$ est injective, $f$ induit une bijection de $E$ sur $\text{Im}\, f \subseteq F$. Par la Proposition 1.2, $\text{Im}\, f$ est fini et $\text{card}(\text{Im}\, f) \le \text{card}\, F = n$. Comme $E$ est en bijection avec $\text{Im}\, f$, par la Proposition 1.1, $E$ est fini et $\text{card}\, E = \text{card}(\text{Im}\, f) \le n = \text{card}\, F$.

(ii) $f$ surjective, $E$ fini $\Rightarrow$ $F$ fini et $\text{card}\, E \ge \text{card}\, F$.

Posons $p = \text{card}\, E$. Comme $f$ est surjective, pour tout $y \in F$, la fibre $f^{-1}(\{y\})$ est non vide. Les fibres $(f^{-1}(\{y\}))_{y \in F}$ forment une partition de $E$ (elles sont deux à deux disjointes, non vides, et leur réunion est $E$). Par la Proposition 1.4 :
$$p = \text{card}\, E = \sum_{y \in F} \text{card}(f^{-1}(\{y\})) \ge \sum_{y \in F} 1 = \text{card}\, F.$$
Ceci implique en particulier que $F$ est fini (car $\text{card}\, F \le p < +\infty$) et $\text{card}\, E \ge \text{card}\, F$.

L'application $f : E \to F$ induit, par restriction du codomaine, une application surjective $\tilde{f} : E \to \text{Im}\, f$ (par définition de l'image). Comme $E$ est fini et $\tilde{f}$ est surjective, la Proposition 1.8 (ii) donne que $\text{Im}\, f$ est fini et $\text{card}(\text{Im}\, f) \le \text{card}\, E$.

Posons $n = \text{card}\, E = \text{card}\, F$. Il suffit de montrer le cycle d'implications : (i) $\Rightarrow$ (ii), (ii) $\Rightarrow$ (iii), (iii) $\Rightarrow$ (i).

(i) $\Rightarrow$ (ii). Toute bijection est en particulier surjective. Immédiat.

(ii) $\Rightarrow$ (iii). Supposons $f$ surjective. Par la Proposition 1.8 (ii), $\text{card}\, E \ge \text{card}\, F$, soit $n \ge n$. Les fibres $(f^{-1}(\{y\}))_{y \in F}$ forment une partition de $E$ (par définition de $f$ surjective), donc par la Proposition 1.4 :
$$n = \sum_{y \in F} \text{card}(f^{-1}(\{y\})) \ge \text{card}\, F = n.$$
L'égalité impose que toutes les fibres sont de cardinal $1$, c'est-à-dire $f$ est injective.

(iii) $\Rightarrow$ (i). Supposons $f$ injective. Par la Proposition 1.8 (i), $\text{card}\, E \le \text{card}\, F$, soit $n \le n$. Comme $f$ est injective, $f$ induit une bijection de $E$ sur $\text{Im}\, f$, donc $\text{card}(\text{Im}\, f) = n = \text{card}\, F$. Par la Proposition 1.2, $\text{Im}\, f \subseteq F$ et $\text{card}(\text{Im}\, f) = \text{card}\, F$ impliquent $\text{Im}\, f = F$. Donc $f$ est surjective, et comme elle est aussi injective, elle est bijective.

Les fibres $(f^{-1}(\{y\}))_{y \in F}$ forment une partition de $E$ : elles sont deux à deux disjointes, leur réunion est $E$ (car $f$ est définie sur $E$ tout entier), et chacune est non vide (car pour tout $y \in F$, $\text{card}(f^{-1}(\{y\})) = r \ge 1$ puisque $r \in \mathbb{N}$ et si $r = 0$ alors $F$ serait vide, ce qui est trivial).

Par la Proposition 1.4 appliquée à cette partition :
$$\text{card}\, E = \sum_{y \in F} \text{card}(f^{-1}(\{y\})) = \sum_{y \in F} r = r \times \text{card}\, F.$$