Exercice 25

1. L'application $\mathcal{P}(E) \to \{0,1\}^{E}$, $A \mapsto \mathbf{1}_{A}$, admet pour réciproque l'application $\chi \mapsto \chi^{-1}(\{1\})$ : en effet, l'ensemble des points où $\mathbf{1}_{A}$ vaut $1$ est $A$, et une fonction $\chi$ à valeurs dans $\{0,1\}$ est l'indicatrice de $\chi^{-1}(\{1\})$. D'après la question 2, il y a $2^{p}$ applications de $E$ dans $\{0,1\}$, et deux ensembles en bijection ont le même cardinal, d'après le lemme 2 du cours. $$\boxed{\mathrm{card}\,\mathcal{P}(E) = \mathrm{card}\,\{0,1\}^{E} = 2^{p}}$$

2. Applications. On raisonne par récurrence sur $p$, pour tout ensemble $F$ à $n$ éléments. Si $p = 0$, l'ensemble $E$ est vide, et il existe une seule application de $E$ dans $F$, celle de graphe vide : on a bien $n^{0} = 1$. Supposons le résultat vrai au rang $p$, et soit $E$ à $p + 1$ éléments, $a \in E$ et $E' = E \setminus \{a\}$, qui a $p$ éléments. On considère $$\begin{array}{r|ccl} \Phi : & F^{E} & \longrightarrow & F \\ & \varphi & \longmapsto & \varphi(a) \end{array}$$ Pour $y \in F$, la fibre $\Phi^{-1}(\{y\})$ est formée des applications qui envoient $a$ sur $y$. La restriction $\varphi \mapsto \varphi_{|E'}$ est une bijection de cette fibre sur $F^{E'}$, dont la réciproque prolonge une application de $E'$ en envoyant $a$ sur $y$. Chaque fibre a donc $n^{p}$ éléments, et le lemme des bergers donne $\mathrm{card}(F^{E}) = n \times n^{p} = n^{p+1}$.

Injections. Notons $A(p,n)$ le nombre d'injections d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments, qui ne dépend que de $p$ et $n$ d'après le lemme 2 du cours. On montre par récurrence sur $p$ que $A(p,n) = n(n-1)\cdots(n-p+1)$, produit de $p$ facteurs, pour tout $n$. Le cas $p = 0$ est le même que ci-dessus. Pour l'hérédité, on reprend $a$, $E'$ et l'application $\varphi \mapsto \varphi(a)$, restreinte aux injections. Si $n = 0$, il n'y a aucune application de $E \neq \varnothing$ dans $F = \varnothing$, et le produit, qui contient le facteur $n = 0$, est nul. Si $n \geqslant 1$, une injection qui envoie $a$ sur $y$ envoie $E'$ dans $F \setminus \{y\}$, et la restriction est une bijection de la fibre au-dessus de $y$ sur l'ensemble des injections de $E'$ dans $F \setminus \{y\}$, qui a $n - 1$ éléments d'après le lemme 3. Le lemme des bergers donne $$A(p+1, n) = n \times A(p, n-1) = n \times (n-1)(n-2)\cdots(n-p).$$ Bijections. D'après le théorème 2 du cours, une application de $E$ dans lui-même est bijective si et seulement si elle est injective : il y en a $A(p,p) = p!$. $$\boxed{n^{p} \text{ applications} \qquad n(n-1)\cdots(n-p+1) \text{ injections} \qquad p! \text{ bijections de } E \text{ sur } E}$$ Le nombre d'injections est nul lorsque $p > n$, puisque le produit contient alors le facteur $n - n = 0$ : c'est le principe des tiroirs.

3. Les applications de $E$ dans $F$ qui ne sont pas surjectives sont, pour $n = 2$, celles qui ne prennent qu'une valeur : ce sont les deux applications constantes. $$\boxed{2^{4} - 2 = 14 \text{ surjections}}$$ À retenir : pour dénombrer, on passe souvent au complémentaire. Pour $n = 3$, il faudrait retirer les applications qui évitent une valeur, en prenant garde de ne pas compter deux fois les constantes : c'est le principe d'inclusion-exclusion du chapitre de dénombrement.

4. Les parties $A \cap B$ et $B \setminus A$ de $B$ sont finies, d'après le lemme 3 du cours. Elles sont disjointes et ont pour réunion $B$, donc, d'après le lemme 4, $$\mathrm{card}(B) = \mathrm{card}(A \cap B) + \mathrm{card}(B \setminus A).$$ De même, $A$ et $B \setminus A$ sont finies, disjointes, et ont pour réunion $A \cup B$. Le lemme 4 montre que $A \cup B$ est fini, et donne $$\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B \setminus A) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B).$$

$$\boxed{\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B)}$$ Pour $A = \{1,2\}$ et $B = \{2,3\}$, on trouve bien $2 + 2 - 1 = 3$. Les éléments de $A \cap B$ sont comptés deux fois dans $\mathrm{card}(A) + \mathrm{card}(B)$, et la soustraction corrige ce double comptage : c'est le premier cas de la formule du crible, que le chapitre 21 généralisera à $n$ parties.