(2) If $f$ is an injection of E into F, the canonical extension $\hat{f}$ of $f$ is an injection of $\mathfrak{P}(\mathrm{E})$ into $\mathfrak{P}(\mathrm{F})$.

(1) If $s$ is a section of $f$, then $f \circ s$ is the identity mapping of F, hence $\hat{f} \circ \hat{s}$ is the identity mapping of $\mathfrak{P}(\mathrm{F})$; therefore $\hat{f}$ is surjective and $\hat{s}$ is a section of $\hat{f}$ (§3, no. 8).

(2) The proposition is obvious if $E = \varnothing$, because then $\mathfrak{P}(E) = \{\varnothing\}$. If $E \ne \varnothing$ and if $r$ is a retraction of $f$, then $r \circ f$ is the identity mapping of $E$, so that $\hat{r} \circ \hat{f}$ is the identity mapping of $\mathfrak{P}(E)$; therefore $\hat{f}$ is injective, and $\hat{r}$ is a retraction of $\hat{f}$ (§3, no. 8).

(2) If $u$ is an injection of $E'$ into $E$ and $v$ a surjection of $F$ onto $F'$, then the mapping $f \mapsto v \circ f \circ u$ is surjective.

We shall assume that the sets $E$, $E'$, $F$, $F'$ are all non-empty, since otherwise the proposition is trivially verified.

(1) Let $s$ be a section of $u$ and let $r$ be a retraction of $v$ (§3, Definition 11). Then $r \circ (v \circ f \circ u) \circ s = I_F \circ f \circ I_E = f$, so that

is injective.

(2) Let $r'$ be a retraction of $u$ and let $s'$ be a section of $v$. For every mapping $f' : E' \to F'$ we have $v \circ (s' \circ f' \circ r') \circ u = f'$, which shows that the mapping $f \mapsto v \circ f \circ u$ is surjective.

Let $A$, $B$, $C$ be three sets and let $f$ be a mapping of $B \times C$ into $A$. For every $y \in C$ let $f(\mathord{\cdot}, y)$ be the partial mapping $x \mapsto f(x,y)$ of $B$ into $A$ (§ 3, no. 9); the function $y \mapsto f(\mathord{\cdot}, y)$ is a mapping of $C$ into $\mathfrak{F}(B, A)$. Conversely, for every mapping $g$ of $C$ into $\mathfrak{F}(B, A)$ there exists a unique mapping $f$ of $\mathrm{B} \times \mathrm{C}$ into A such that $g(y) = f(\bullet, y)$ for each $y \in \mathrm{C}$, namely the mapping $(x, y) \to (g(y))(x)$. Hence :

Similarly we define a canonical bijection of $\mathfrak{F}(\mathrm{B} \times \mathrm{C}, \mathrm{A})$ onto $\mathfrak{F}(\mathrm{B}, \mathfrak{F}(\mathrm{C}, \mathrm{A}))$. By reason of the one-to-one correspondence between mappings and functional graphs, these bijections give rise to canonical bijections of $\mathrm{A}^{\mathrm{B} \times \mathrm{C}}$ onto $(\mathrm{A}^{\mathrm{B}})^{\mathrm{C}}$ (resp. $(\mathrm{A}^{\mathrm{C}})^{\mathrm{B}}$).

Let

(§4, Proposition 1). The mapping $F\to F\circ U$ ($F\in A^I$) is a bijection of $A^I$ onto $A^K$ (Proposition 2). It is evident that the condition “for each $\iota\in I$, $F(\iota)\in X_\iota$” is equivalent to “for each $x\in K$, $(F\circ U)(x)\in X_{u(x)}$”, and the result follows.

In view of the remarks made above, it is enough to prove the following proposition :

For each $\iota\in I-J$ let $T_\iota$ denote the term $\tau_\iota(y\in X_\iota)$. Since $X_\iota\ne\varnothing$ by hypothesis, we have $T_\iota\in X_\iota$ for all $\iota\in I-J$ (Chapter I, §4, no. 1). If $G$ is the graph of $g$, the graph $G\cup\left(\displaystyle\bigcup_{\iota\in I-J}\{(\iota,T_\iota)\}\right)$ is the graph of a function which has the required properties, as is immediately verified.

Apply Proposition 5 to the subset $J=\{\alpha\}$ of $I$ and note that $\operatorname{pr}_\alpha$ is the composition of the canonical mapping of $X_\alpha^{\{\alpha\}}$ onto $X_\alpha$ and the mapping $\operatorname{pr}_{\{\alpha\}}$.

If we have $\mathrm{X}_\iota \neq \emptyset$ for each $\iota \in \mathrm{I}$, then it follows from Corollary 1 that $\prod\limits_{\iota \in \mathrm{I}} \mathrm{X}_\iota \neq \emptyset$; conversely, if $\prod\limits_{\iota \in \mathrm{I}} \mathrm{X}_\iota \neq \emptyset$, the relation $\mathrm{pr}_\alpha\Big(\prod\limits_{\iota \in \mathrm{I}} \mathrm{X}_\iota\Big) \subset \mathrm{X}_\alpha$ shows that $\mathrm{X}_\alpha \neq \emptyset$ for each $\alpha \in \mathrm{I}$.

Hence, if we have a family $(\mathrm{X}_\iota)_{\iota \in \mathrm{I}}$ of non-empty sets, we may introduce (as an auxiliary constant) a function $f$ with domain I such that $f(\iota) \in \mathrm{X}_\iota$ for all $\iota \in \mathrm{I}$. In practice one says : "take an element $x_\iota$ in each $\mathrm{X}_\iota$". Intuitively, we have thus "chosen" an element $x_\iota$ in each set $\mathrm{X}_\iota$; the introduction of the logical sign $\tau$ and the criteria governing its use absolve us from the necessity of formulating an "axiom of choice" to legalize this operation (cf. Summary of Results, §4, no. 10).

Conversely, if $\prod\limits_{\iota \in \mathrm{I}} \mathrm{X}_\iota \subset \prod\limits_{\iota \in \mathrm{I}} \mathrm{Y}_\iota$, and if $\mathrm{X}_\iota \neq \emptyset$ for each $\iota \in \mathrm{I}$, then $\mathrm{X}_\iota \subset \mathrm{Y}_\iota$ for each $\iota \in \mathrm{I}$.

The first assertion is obvious, and the second follows from Proposition 1, Corollary 5, because we have then, for each $\alpha \in \mathrm{I}$,

of $\prod\limits_{\iota \in \mathrm{I}} \mathrm{X}_\iota$ into the product set $\prod\limits_{\lambda \in \mathrm{L}} \Big(\prod\limits_{\iota \in \mathrm{J}_\lambda} \mathrm{X}_\iota\Big)$ is bijective ("associativity" of products of sets).

From the interpretation of $\mathrm{pr}_{\mathrm{J}_\lambda} f$ as the graph of the restriction of the function whose graph is $f$ (no. 4), it follows that the statement that the mapping $f \to (\mathrm{pr}_{\mathrm{J}_\lambda} f)_{\lambda \in \mathrm{L}}$ is bijective means that, for each family $(v_\lambda)_{\lambda \in \mathrm{L}}$, where $v_\lambda$ is a mapping of $\mathrm{J}_\lambda$ into $\bigcup\limits_{\iota \in \mathrm{I}} \mathrm{X}_\iota$, there exists a unique mapping $u$ of I into $\bigcup_{\iota \in I} X_\iota$ such that $v_\lambda$ is the restriction of $u$ to $J_\lambda$ for each $\lambda \in L$. But this is a consequence of the hypothesis that $(J_\lambda)_{\lambda \in L}$ is a partition of I (§4, Proposition 8).

¶ The bijection defined in Proposition 7, and its inverse bijection are said to be canonical.

Remarks

Then we have

("distributivity" of union over intersection, and of intersection over union).

Let $x$ be an element of $\bigcup_{\lambda \in L} \left( \bigcap_{\iota \in J_\lambda} X_{\lambda, \iota} \right)$ and let $f$ be any element of I. There exists an index $\lambda$ such that $x \in \bigcap_{\iota \in J_\lambda} X_{\lambda, \iota}$; consequently $x \in X_{\lambda, f(\lambda)}$ and hence

Since this is true for each $f \in I$, we have

Conversely, let $x$ be an object which does not belong to the set

Then for each $\lambda \in L$ we have $x \notin \bigcap_{\iota \in J_\lambda} X_{\lambda, \iota}$, which means that the set $J'_\lambda$ of indices $\iota \in J_\lambda$ such that $x \notin X_{\lambda, \iota}$ is not empty for each $\lambda \in L$. By Proposition 5, Corollary 2, there exists a functional graph $f$ with domain L such that for each $\lambda \in L$ we have $f(\lambda) \in J'_\lambda$. Consequently $f \in I$ and $x \notin X_{\lambda, f(\lambda)}$ for each $\lambda \in L$; hence

and thus

This completes the proof of the first formula. The second formula follows by applying the first to the family $((\complement_A X_{\lambda, \iota})_{\iota \in J_\lambda})_{\lambda \in L}$, where A denotes the union $\bigcap_{\lambda \in L} \left( \bigcap_{\iota \in J_\lambda} X_\lambda \right)$.

Let $\alpha$, $\beta$ be two distinct objects; apply the formulae of Proposition 8 (with $L = \{\alpha,\ \beta\}$, $J_\alpha = I$, $J_\beta = K$) to the family $((Z_{\lambda,\, \mu})_{\mu \in J_\lambda})_{\lambda \in L}$, where $Z_{\alpha,\, \iota} = X_\iota$ for all $\iota \in I$ and $Z_{\beta,\, \varkappa} = Y_\varkappa$ for each $\varkappa \in K$. By the existence of the canonical bijection of $\coprod_{\lambda \in L} J_\lambda$ onto $I \times K$ (no. 3) and by Proposition 1 of § 4 we obtain the formulae stated.

and (if $L \neq \emptyset$ and $J_\lambda \neq \emptyset$ for each $\lambda \in L$)

("distributivity" of product over union and over intersection). The first formula is trivially true if $L = \emptyset$ or if $J_\lambda = \emptyset$ for some $\lambda \in L$. If not, let $g$ be an element of $\prod_{\lambda \in L} \left( \bigcap_{\iota \in J_\lambda} X_{\lambda,\, \iota} \right)$. For each $\lambda \in L$ there exists an index $\iota \in J_\lambda$ such that $g(\lambda) \in X_{\lambda,\, \iota}$; in other words, the set $H_\lambda$ of indices $\iota \in J_\lambda$ such that $g(\lambda) \in X_{\lambda,\, \iota}$ is not empty. By Corollary 2 to Proposition 5 there is therefore a functional graph $f$ with domain L such that

for each $\lambda \in L$, i.e., $g(\lambda) \in X_{\lambda,\, f(\lambda)}$. Hence we have $g \in \prod_{\lambda \in L} X_{\lambda,\, f(\lambda)}$ and consequently $g \in \bigcup_{f \in I} \left( \prod_{\lambda \in L} X_{\lambda,\, f(\lambda)} \right)$. Conversely, if

there is a functional graph $f \in I$ such that for every $\lambda \in L$ we have

and, a fortiori, $g(\lambda) \in \bigcup_{\iota \in J_\lambda} X_{\lambda, \iota}$. This completes the proof of the first formula. The proof of the second formula is analogous but simpler, and we leave it to the reader.

If we set

then, by virtue of the first formula of Proposition 9, it is sufficient to show that $\mathrm{P}_f \neq \emptyset$ for all $f \in I$ and that $\mathrm{P}_f \cap \mathrm{P}_g = \emptyset$ whenever $f$ and $g$ are distinct elements of I. The first point follows from Proposition 5, Corollary 2. As to the second, if $f \neq g$, there exists $\lambda \in L$ such that

and therefore, by virtue of the hypothesis, $X_{\lambda, f(\lambda)} \cap X_{\lambda, g(\lambda)} = \emptyset$. It follows that there is no graph belonging to $\mathrm{P}_f \cap \mathrm{P}_g$; for if G were such a graph, we would have $\mathrm{G}(\lambda) \in X_{\lambda, f(\lambda)} \cap X_{\lambda, g(\lambda)} = \emptyset$, which is absurd.

and, if I and K are non-empty,

The proof follows the pattern of the proof of the Corollary to Proposition 8.

Both sides of the equality to be proved are functional graphs. A graph $f$ belongs to the left-hand side if and only if, for each $\varkappa \in K$, $f \in \prod_{\iota \in I} X_{\iota, \varkappa}$; that is, if and only if $f(\iota) \in X_{\iota, \varkappa}$ for all $(\iota, \varkappa) \in I \times K$. For $f$ to belong to the right-hand side it is necessary and sufficient that $f(\iota) \in \bigcap_{\varkappa \in K} X_{\iota, \varkappa}$ for each $\iota \in I$, i.e., that $f(\iota) \in X_{\iota, \varkappa}$ for each pair $(\iota, \varkappa) \in I \times K$. This completes the proof.

Apply Proposition 10 to the case where K (resp. I) is a set consisting of two distinct elements.