Exercice 42

1. L'application $\Theta$ est bien définie : pour $x \in F$, l'application partielle $\varphi(x,\cdot)$ appartient à $E^{G}$, donc $\Theta(\varphi)$ est une application de $F$ dans $E^{G}$. Pour construire la réciproque, on fait le chemin inverse : à une application $\psi : F \to E^{G}$, qui associe à chaque $x \in F$ une application $\psi(x) : G \to E$, on associe l'application de deux variables $$\begin{array}{r|ccl} \Lambda(\psi) : & F \times G & \longrightarrow & E \\ & (x,y) & \longmapsto & \psi(x)(y) \end{array}$$ Soit $\varphi \in E^{F \times G}$. Pour tout $(x,y) \in F \times G$, on a $$\Lambda\big(\Theta(\varphi)\big)(x,y) = \Theta(\varphi)(x)(y) = \varphi(x,\cdot)(y) = \varphi(x,y),$$ donc $\Lambda \circ \Theta$ est l'identité de $E^{F \times G}$. Soit ensuite $\psi \in (E^{G})^{F}$ et $x \in F$. L'application $\Theta\big(\Lambda(\psi)\big)(x)$ est $y \mapsto \Lambda(\psi)(x,y) = \psi(x)(y)$, c'est-à-dire $\psi(x)$ ; donc $\Theta \circ \Lambda$ est l'identité de $(E^{G})^{F}$. Le théorème 1 du cours conclut. $$\boxed{\Theta \text{ est bijective, et } \Theta^{-1}(\psi) \text{ est l'application } (x,y) \mapsto \psi(x)(y).}$$

2. Se donner deux applications $u : E \to F$ et $v : E \to G$, c'est se donner, en chaque point $x$, le couple de leurs valeurs. On pose donc $$\begin{array}{r|ccl} \Pi : & F^{E} \times G^{E} & \longrightarrow & (F \times G)^{E} \\ & (u,v) & \longmapsto & \big(x \mapsto (u(x), v(x))\big) \end{array}$$ Notons $p : F \times G \to F$ et $q : F \times G \to G$ les deux projections, et associons à $w \in (F \times G)^{E}$ le couple $(p \circ w,\ q \circ w)$. D'une part, $p\big(u(x), v(x)\big) = u(x)$ et $q\big(u(x), v(x)\big) = v(x)$ : on retrouve $(u,v)$. D'autre part, pour tout $x \in E$, le couple $\big(p(w(x)), q(w(x))\big)$ est $w(x)$ : on retrouve $w$. Le théorème 1 du cours conclut encore. $$\boxed{\Pi \text{ est bijective, de réciproque } w \mapsto (p \circ w,\ q \circ w).}$$

3. On découpe une application définie sur $F \cup G$ en ses deux restrictions, en posant $$\begin{array}{r|ccl} \rho : & E^{F \cup G} & \longrightarrow & E^{F} \times E^{G} \\ & w & \longmapsto & (w_{|F},\ w_{|G}) \end{array}$$ Inversement, à $(u,v) \in E^{F} \times E^{G}$, on associe l'application $w : F \cup G \to E$ définie par $w(z) = u(z)$ si $z \in F$ et $w(z) = v(z)$ si $z \in G$. C'est ici que sert l'hypothèse : chaque élément de $F \cup G$ appartient à une seule des deux parties, ce qui rend la définition de $w$ cohérente. Les restrictions de $w$ à $F$ et à $G$ sont $u$ et $v$, et une application $w$ est le recollement de ses deux restrictions : les deux composées sont les identités. $$\boxed{w \mapsto (w_{|F},\ w_{|G}) \text{ est une bijection de } E^{F \cup G} \text{ sur } E^{F} \times E^{G}.}$$ Piège : sans la disjonction, $\rho$ reste définie, mais elle cesse d'être surjective dès que $E$ a deux éléments distincts $\alpha$ et $\beta$. Si $z \in F \cap G$, un couple $(u,v)$ tel que $u(z) = \alpha$ et $v(z) = \beta$ n'est pas atteint, puisque les deux restrictions d'une même application prennent la même valeur en $z$.

4. D'après l'exercice 25, l'ensemble des applications d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments a $n^{p}$ éléments. Les ensembles $F \times G$ et $F \cup G$ ont $bc$ et $b + c$ éléments, d'après les lemmes 6 et 4 du cours, et le lemme 6 donne aussi le cardinal des produits $F^{E} \times G^{E}$ et $E^{F} \times E^{G}$. Enfin, deux ensembles en bijection ont le même cardinal, d'après le lemme 2. Les questions 1, 2 et 3 donnent alors, dans cet ordre : $$\boxed{a^{bc} = (a^{c})^{b} \qquad\qquad b^{a}\,c^{a} = (bc)^{a} \qquad\qquad a^{b + c} = a^{b}\,a^{c}}$$ Ces trois règles, que l'on démontrerait d'ordinaire par récurrence, deviennent ici des évidences : chacune affirme seulement que deux façons de ranger les mêmes données en contiennent autant l'une que l'autre. Elles valent pour tous les entiers naturels, y compris $0$, avec la convention $0^{0} = 1$, qui est celle que dicte l'exercice 25 : il existe une application, et une seule, de $\varnothing$ dans $\varnothing$.

5. Comme dans le cours, on identifie une relation binaire sur $F$ à son graphe, qui est une partie de $F \times F$ ; l'ensemble des relations binaires sur $F$ est donc $\mathcal{P}(F \times F)$. Pour une relation $\mathcal{R}$ et $x \in F$, notons $\mathcal{R}(x) = \{y \in F \mid x \,\mathcal{R}\, y\}$, et $\Sigma(\mathcal{R})$ l'application $x \mapsto \mathcal{R}(x)$ de $F$ dans $\mathcal{P}(F)$. Inversement, à une application $s : F \to \mathcal{P}(F)$, on associe la relation $\mathcal{R}_{s}$ de graphe $\{(x,y) \in F \times F \mid y \in s(x)\}$.

• Pour toute relation $\mathcal{R}$, on a $y \in \Sigma(\mathcal{R})(x) \iff x \,\mathcal{R}\, y$ : la relation associée à $\Sigma(\mathcal{R})$ est $\mathcal{R}$.

• Pour toute application $s$ et tout $x \in F$, on a $\mathcal{R}_{s}(x) = \{y \mid y \in s(x)\} = s(x)$ : l'application associée à $\mathcal{R}_{s}$ est $s$.

D'après le théorème 1 du cours, $\Sigma$ est une bijection de $\mathcal{P}(F \times F)$ sur $\mathcal{P}(F)^{F}$. Si $F$ a $n$ éléments, $\mathcal{P}(F)$ en a $2^{n}$, d'après la question 1 de l'exercice 25, et la question 2 du même exercice donne $(2^{n})^{n}$ applications de $F$ dans $\mathcal{P}(F)$. Avec la première règle de la question 4 : $$\boxed{\text{Il y a } (2^{n})^{n} = 2^{n^{2}} \text{ relations binaires sur un ensemble à } n \text{ éléments.}}$$ On retrouve le résultat de la question 1 de l'exercice 28, qui comptait directement les parties de $F \times F$. La bijection $\Sigma$ n'est d'ailleurs autre que celle de la question 1 pour $E = \{0,1\}$, lue à travers la bijection $A \mapsto \mathbf{1}_{A}$ de l'exercice 25 : la relation correspond à l'indicatrice de son graphe, application de deux variables, et $\mathcal{R}(x)$ à l'application partielle $\mathbf{1}_{\mathcal{R}(x)} = \mathbf{1}_{G}(x,\cdot)$, où $G$ est le graphe de $\mathcal{R}$.

À retenir : une application de deux variables est la même chose qu'une application qui, à la première variable, associe une application de la seconde. En informatique, ce passage s'appelle la curryfication, du nom du logicien Haskell Curry ; la question 5 en est une illustration familière, puisque décrire une relation par la liste, pour chaque $x$, des éléments $y$ auxquels il est relié, c'est représenter un graphe par ses listes d'adjacence.