Dénombrement

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}$.

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.$$