4. 함수 (iii): 상·선택공리·곱Functions (iii): Images, Choice, and Products

Both statements are false. A single function gives counterexamples for both. Let $A = \{1, 2\}$, $B = \{3, 4\}$, and consider the constant function $f = \{(1,3),(2,3)\} : A \to B$.

1. Let $C = \{1\}$ and $D = \{2\}$; then $C \subset A$ and $D \subset A$, and
   $$\hat{f}(C) = \{f(1)\} = \{3\} = \{f(2)\} = \hat{f}(D)$$
   so $\hat{f}(C) = \hat{f}(D)$. However $C = \{1\} \neq \{2\} = D$. Thus (1) is false.
2. Let $C = \{4\}$ and $D = \emptyset$; then $C \subset B$ and $D \subset B$. Since $ran\ f = \{3\}$, we have $4 \notin ran\ f$, so by the definition of the inverse image, $\check{f}(C) = \check{f}(\{4\}) = \emptyset$. On the other hand, since $D = \emptyset$, (vacuously) $\check{f}(D) = \check{f}(\emptyset) = \emptyset$. Thus
   $$\check{f}(C) = \emptyset = \check{f}(D)$$
   but $C = \{4\} \neq \emptyset = D$. Thus (2) is also false.

(This is exactly the claim of Remark 4.55.)

The flawed step is the following biconditional.

The ($\Rightarrow$) direction holds: the $x$ on the left already satisfies $x \in C_i$ and $y = f(x)$ for all $i \in I$, so that same $x$ serves as the witness for each $i$ on the right.

However, the ($\Leftarrow$) direction fails. The right side only says that for each $i \in I$ there exists some $x_i \in C_i$ with $y = f(x_i)$, and these $x_i$ may differ from one $i$ to another. In other words, the right side does not force the existence of a single $x \in \bigcap_{i \in I} C_i$ common to every $i \in I$.

Concrete counterexample: let $A = \{1,2\}$, $B = \{3,4\}$, $f = \{(1,3),(2,3)\} : A \to B$, and $I = \{1,2\}$, $C_1 = \{1\}$, $C_2 = \{2\}$. Then $\hat{f}(C_1) = \{3\} = \hat{f}(C_2)$, so

However, $C_1 \cap C_2 = \emptyset$, so

Thus the biconditional in question is not actually a true statement (the same counterexample is used again in Exercise 4.61).

An additional condition that repairs it is that $f$ be injective. Assume $f$ is injective and let $y \in \bigcap_{i \in I} \hat{f}(C_i)$. Then for each $i \in I$ there exists $x_i \in C_i$ such that $y = f(x_i)$. Since $f$ is injective, by (INJ) the pre-image of the same $y$ is unique, i.e. $x_i = x_j$ for all $i, j \in I$. Thus there is a single common element $x$ such that $x = x_i \in C_i$ for all $i \in I$ and $y = f(x)$. Therefore $x \in \bigcap_{i \in I} C_i$ and $y \in \hat{f}\left(\bigcap_{i \in I} C_i\right)$. This shows

and the reverse inclusion $\hat{f}\left(\bigcap_{i \in I} C_i\right) \subset \bigcap_{i \in I} \hat{f}(C_i)$ always holds by Theorem 4.59(2), regardless of $f$. Hence if $f$ is injective,

holds (cf. Exercise 4.61).

(Translator's note: the subscript $\bigcap_{i \in C_i} \hat{f}(C_i)$ printed in the last line of the proof of Theorem 4.59(2) is a typo for $\bigcap_{i \in I} \hat{f}(C_i)$ — the same kind of typo ($\bigcap_{i \in D_i}$) occurs in the last line of the proof of Theorem 4.58(2).)

This equality does not hold in general. We disprove it.

Let $A = \{1,2\}$, $B = \{3,4\}$, and $f = \{(1,3),(2,3)\} : A \to B$. Let $I = \{1,2\}$, $C_1 = \{1\}$, and $C_2 = \{2\}$. Then $\hat{f}(C_1) = \{3\} = \hat{f}(C_2)$, so

However, $C_1 \cap C_2 = \emptyset$, so

Therefore

and the equality fails.

Note, however, that by Theorem 4.59(2) the inclusion $\hat{f}\left(\bigcap_{i \in I} C_i\right) \subset \bigcap_{i \in I} \hat{f}(C_i)$ always holds regardless of $f$ (indeed $\emptyset \subset \{3\}$ in the counterexample above, so this inclusion is not violated). Moreover, as seen in Exercise 4.60, if $f$ is injective, then the reverse inclusion also holds, so the equality holds.

First we show that $g \subset B \times A$ (by Notation 4.53(1), $\check{f}(y) = \check{f}(\{y\})$). Let $y \in B$. Since $f : A \to B$ is surjective, by (SURJ) there exists $x \in A$ such that $y = f(x)$. That is, $x \in \check{f}(\{y\})$, so $\check{f}(\{y\}) \neq \emptyset$. On the other hand, by the definition of the inverse image, $\check{f}(\{y\})$ is a subclass of $A$. Moreover, since $r$ is a choice function for $A$, $A$ is a set by Definition 4.62, and hence its subclass $\check{f}(\{y\})$ is a set by the axiom of subset. Therefore, by the definition of the power set, $\check{f}(\{y\}) \in \mathcal{P}(A)$, and since $\check{f}(\{y\}) \neq \emptyset$,

Hence, by the definition of a choice function (Definition 4.62),

Thus each element $(y, r(\check{f}(\{y\})))$ of $g$ satisfies $y \in B$ and $r(\check{f}(\{y\})) \in A$, so $g \subset B \times A$. In particular, $g$ is a graph.

Next we use Theorem 4.8 to show that $g : B \to A$ is a function.

By the definition of $g$, $(y, r(\check{f}(\{y\}))) \in g$ for every $y \in B$. Thus $dom\ g = B$. Moreover, we already showed $ran\ g \subset A$ above.

Finally we show that $g$ satisfies (F2). Let $(y, a_1) \in g$ and $(y, a_2) \in g$. By the definition of $g$, $a_1 = r(\check{f}(\{y\})) = a_2$ (since $r$ is a function, its value at $\check{f}(\{y\})$ is unique). Thus (F2) holds.

Therefore $g$ is a graph satisfying (F2), with $dom\ g = B$ and $ran\ g \subset A$. By Theorem 4.8, $g : B \to A$ is a function.

Define $\gamma : \prod_{i \in I} A_i \to A_1 \times A_2$ by $\gamma(f) = (f(1), f(2))$; then $\gamma$ is the desired bijective function.

By Example 4.68, $\prod_{i \in I} A_i = \{f_1, f_2, f_3, f_4\}$, where

By the definition of $\gamma$,

These are exactly the four elements of $A_1 \times A_2 = \{(a,c),(a,d),(b,c),(b,d)\}$, and they are four distinct values.

Since the four elements of the domain $\prod_{i \in I} A_i = \{f_1,f_2,f_3,f_4\}$ correspond to four distinct images $\gamma(f_1), \dots, \gamma(f_4)$, by (INJ) $\gamma$ is injective. Moreover, since these four images are exactly all the elements of $A_1 \times A_2$, by (SURJ) $\gamma$ is surjective. Therefore $\gamma$ is both injective and surjective, so by Definition 4.14(3) it is bijective.

We use Theorem 4.8 to show that $p_j$ is a function. By Notation 4.70,

First we show that $p_j \subset \left(\prod_{i \in I} A_i\right) \times A_j$. Let $a \in \prod_{i \in I} A_i$. By the definition of the product (Definition 4.67), $a$ is a function from $I$ to $A = \bigcup_{i \in I} A_i$, and $a(i) \in A_i$ for all $i \in I$. In particular, $a_j = a(j) \in A_j$. Thus each element $(a, a_j)$ of $p_j$ satisfies $a \in \prod_{i \in I} A_i$ and $a_j \in A_j$, so $p_j \subset \left(\prod_{i \in I} A_i\right) \times A_j$. In particular, $p_j$ is a graph.

By the definition of $p_j$, $(a, a_j) \in p_j$ for every element $a$ of $\prod_{i \in I} A_i$. Thus $dom\ p_j = \prod_{i \in I} A_i$. Moreover, we already showed $ran\ p_j \subset A_j$ above.

Finally we show that $p_j$ satisfies (F2). Let $(a, y_1) \in p_j$ and $(a, y_2) \in p_j$. By the definition of $p_j$, there exist $a', a'' \in \prod_{i \in I} A_i$ such that $(a,y_1) = (a', (a')_j)$ and $(a,y_2) = (a'',(a'')_j)$ (we write the elements as $a'$, $a''$ so as not to confuse them with the coordinate notation $a_j$ of Notation 4.70). By the property of the ordered pair (Theorem 3.54), $a' = a = a''$, $y_1 = (a')_j$, and $y_2 = (a'')_j$. Since $a' = a''$, we have $y_1 = (a')_j = (a'')_j = y_2$. Thus (F2) holds.

Therefore $p_j$ is a graph satisfying (F2), with $dom\ p_j = \prod_{i \in I} A_i$ and $ran\ p_j \subset A_j$. By Theorem 4.8, $p_j : \prod_{i \in I} A_i \to A_j$ is a function.

Write $C_B := \{(x,1):x\in B\} \cup \{(x,0): x \notin B \text{ and } x \in A\}$ and $C_D := \{(x,1):x\in D\} \cup \{(x,0): x \notin D \text{ and } x \in A\}$. Then (4.11) says $C_B = C_D$. Our goal is to show

First we show $\{(x,1):x\in B\} \subset \{(x,1):x\in D\}$. Let $(x,1) \in \{(x,1):x\in B\}$. Since $\{(x,1):x\in B\} \subset C_B$ and $C_B = C_D$,

Suppose $(x,1)$ belongs to the second part; then there exists $x' \notin D$ such that $(x,1) = (x',0)$. By the equality of ordered pairs (Theorem 3.54), we get $1 = 0$, which contradicts the hypothesis of Theorem 4.73 that 2 is a class consisting of two different elements $0$ and $1$. Thus $(x,1)$ must belong to the first part, i.e. there exists $x' \in D$ such that $(x,1) = (x',1)$. By Theorem 3.54 again, $x = x' \in D$. Therefore $(x,1) \in \{(x,1):x\in D\}$.

The reverse inclusion $\{(x,1):x\in D\} \subset \{(x,1):x\in B\}$ is obtained by the exact same argument with the roles of $B$ and $D$ interchanged, since $C_D = C_B$.

By the two inclusions and the axiom of extent,

That is, (4.11) implies (4.12).