Exercise 2, § 5

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

Let $A$ and $B$ be two sets. For a subset $G$ of $A \times B$, the image of $\{x\}$ under the correspondence $G$ is $G\langle\{x\}\rangle = \{ y \in B \mid (x, y) \in G \}$. We verify that the assignment $x \mapsto G\langle\{x\}\rangle$ defines a mapping from $A$ into $\mathfrak{P}(B)$. For each $x \in A$, $G\langle\{x\}\rangle$ is a subset of $B$, hence an element of $\mathfrak{P}(B)$. The assignment is functional because each $x \in A$ determines a unique set $G\langle\{x\}\rangle$. Its graph $\Phi(G) = \{ (x, G\langle\{x\}\rangle) \mid x \in A \}$ is a subset of $A \times \mathfrak{P}(B)$ and satisfies the condition that for each $x \in A$ there is exactly one $Y \in \mathfrak{P}(B)$ with $(x, Y) \in \Phi(G)$. Therefore $\Phi(G)$ is a functional graph with domain $A$ and values in $\mathfrak{P}(B)$, i.e., $\Phi(G) \in (\mathfrak{P}(B))^A$. Thus we have a mapping $\Phi : \mathfrak{P}(A \times B) \to (\mathfrak{P}(B))^A$.

Conversely, let $H$ be an element of $(\mathfrak{P}(B))^A$. Then $H$ is a functional graph with domain $A$ such that $H(x) \subseteq B$ for each $x \in A$. Define $\Delta(H) = \{ (x, y) \in A \times B \mid y \in H(x) \}$. Clearly $\Delta(H) \subseteq A \times B$, so $\Delta(H) \in \mathfrak{P}(A \times B)$. This defines a mapping $\Delta : (\mathfrak{P}(B))^A \to \mathfrak{P}(A \times B)$.

We show that $\Delta$ is the inverse of $\Phi$.

Take any $G \in \mathfrak{P}(A \times B)$. For $(x, y) \in A \times B$ we have $(x, y) \in \Delta(\Phi(G)) \iff y \in \Phi(G)(x) = G\langle\{x\}\rangle \iff (x, y) \in G$. Hence $\Delta(\Phi(G)) = G$.

Take any $H \in (\mathfrak{P}(B))^A$. For each $x \in A$, $\Phi(\Delta(H))(x) = \Delta(H)\langle\{x\}\rangle = \{ y \in B \mid (x, y) \in \Delta(H) \} = \{ y \in B \mid y \in H(x) \} = H(x)$. Since the graphs of two mappings with the same domain are equal when their values coincide everywhere, $\Phi(\Delta(H)) = H$.

Therefore $\Phi$ is a bijection of $\mathfrak{P}(A \times B)$ onto $(\mathfrak{P}(B))^A$, and its inverse is $\Delta$.