3. 모임과 집합 (ii): 순서쌍·곱·그래프Classes and Sets (ii): Ordered Pairs, Products, and Graphs

Suppose that $\{x, y\} = \{u, v\}$. We complete the proof dividing it into the two cases that $x = y$ or $x \neq y$.

• (Case 1: $x = y$). Since $u \in \{u, v\}$ and $\{x, y\} = \{u, v\}$, $u \in \{x, y\}$ by the axiom of extent. Thus, by the definition of the doubleton, $u = x$ or $u = y$. Since $x = y$, we finally have $u = x = y$. Analogously, $v = x = y$. Therefore $u = v = x = y$.
• (Case 2: $x \neq y$). Since $x \in \{x, y\}$ and $\{x, y\} = \{u, v\}$, $x \in \{u, v\}$ by the axiom of extent. Thus, by the definition of the doubleton, $x = u$ or $x = v$. We consider the cases $x = u$ or $x = v$ separately.
  1. ($x = u$). Since $y \in \{x, y\}$ and $\{x, y\} = \{u, v\}$, $y \in \{u, v\}$ by the axiom of extent. Thus, by the definition of the doubleton, $y = u$ or $y = v$. If $y = u$, then $y = u = x$ and it is contradiction to the fact that $x \neq y$. In other words, $y = u$ is impossible. Therefore we have $y = v$. In this case, we are done.
  2. ($x = v$). Since $y \in \{x, y\}$ and $\{x, y\} = \{u, v\}$, $y \in \{u, v\}$ by the axiom of extent. Thus, by the definition of the doubleton, $y = u$ or $y = v$. If $y = v$, then $y = v = x$ and it is contradiction to the fact that $x \neq y$. In other words, $y = v$ is impossible. Therefore we have $y = u$.

Recall that $\emptyset$ is a set by the axiom of the empty set. Moreover, $\{a, \emptyset\}$ is a set by the axiom of doubleton. Finally, since $\{a\} \subset \{a, \emptyset\}$, $\{a\}$ is a set by the axiom of subset.

Since $a$ and $b$ elements, the doubleton $\{a, b\}$ is a set by the axiom of doubleton. Moreover, $\{a\}$ is a set by Lemma 3.52. Therefore by the definition of the ordered pair $(a, b)$ and the axiom of doubleton again, $(a, b)$ is a set.

Suppose that $(a, b) = (c, d)$. Then by the definition of the ordered pairs,

Then by Theorem 3.46,

or

We consider these cases separately.

• (Case 1: $\{a\} = \{c\}$ and $\{a, b\} = \{c, d\}$). Since $\{a\} = \{c\}$, we have
  $$a = c \tag{3.13}$$

  by the definition of the singleton. From $\{a, b\} = \{c, d\}$, applying Theorem 3.46 again, we have

  $$a = c \ \wedge \ b = d \quad \text{or} \quad a = d \ \wedge \ b = c.$$

  In the first case, we have $a = c$ and $b = d$. Thus we are done. In the second case, by using (3.13), we have $d = a = c = b$. Thus the conclusion of the theorem holds.

• (Case 2: $\{a\} = \{c, d\}$ and $\{a, b\} = \{c\}$). Since $c \in \{c, d\} = \{a\}$, we have $c = a$. Similarly, since $d \in \{c, d\} = \{a\}$ and $b \in \{a, b\} = \{c\}$, we have $d = a$ and $b = c$. Therefore
  $$b = c = a = d$$

  and we are done.

1. By the definition of the Cartesian product, the associative law, Theorem 2.19(2), commutative law, and the definition of the intersection,
   $$\begin{aligned} (x, y) \in A \times (B \cap C) \ &\iff \ x \in A \quad \text{and} \quad y \in B \cap C \\ &\iff \ x \in A \quad \text{and} \quad (y \in B \quad \text{and} \quad y \in C) \\ &\iff \ x \in A \quad \text{and} \quad y \in B \quad \text{and} \quad y \in C \\ &\iff \ x \in A \quad \text{and} \quad x \in A \quad \text{and} \quad y \in B \quad \text{and} \quad y \in C \\ &\iff \ (x \in A \quad \text{and} \quad y \in B) \quad \text{and} \quad (x \in A \quad \text{and} \quad y \in C) \\ &\iff \ (x, y) \in (A \times B) \quad \text{and} \quad (x, y) \in (A \times C) \\ &\iff \ (x, y) \in (A \times B) \cap (A \times C). \end{aligned}$$
2. We leave the proof of (2) as an exercise.
3. By the definition of the Cartesian product, the associative law, the commutative law, the definition of the intersection,
   $$\begin{aligned} (x, y) \in (A \times B) \cap (C \times D) \ &\iff \ (x, y) \in A \times B \quad \text{and} \quad (x, y) \in C \times D \\ &\iff \ x \in A \quad \text{and} \quad y \in B \text{ and } x \in C \quad \text{and} \quad y \in D \\ &\iff \ (x \in A \text{ and } x \in C) \quad \text{and} \quad (y \in B \quad \text{and} \quad y \in D) \\ &\iff \ x \in A \cap C \quad \text{and} \quad y \in B \cap D \\ &\iff \ (x, y) \in (A \cap C) \times (B \cap D). \end{aligned}$$

1. $$\begin{aligned} (x, y) \in (G \circ H) \circ J \ &\iff \ \exists z \ni (x, z) \in J \quad \text{and} \quad (z, y) \in (G \circ H) \\ &\iff \ \exists z \ni (x, z) \in J \quad \text{and} \quad \exists w \ni (z, w) \in H \quad \text{and} \quad (w, y) \in G \\ &\iff \ (\exists z \text{ and } \exists w) \ni (x, z) \in J \quad \text{and} \quad (z, w) \in H \quad \text{and} \quad (w, y) \in G \\ &\iff \ \exists w \ni (\exists z \ni (x, z) \in J \quad \text{and} \quad (z, w) \in H) \quad \text{and} \quad (w, y) \in G \\ &\iff \ \exists w \ni (x, w) \in H \circ J \quad \text{and} \quad (w, y) \in G \\ &\iff \ (x, y) \in G \circ (H \circ J). \end{aligned}$$
2. $$\begin{aligned} (x, y) \in (G^{-1})^{-1} \ &\iff \ (y, x) \in G^{-1} \\ &\iff \ (x, y) \in G. \end{aligned}$$
3. $$\begin{aligned} (x, y) \in (G \circ H)^{-1} \ &\iff \ (y, x) \in G \circ H \\ &\iff \ \exists z \ni (y, z) \in H \quad \text{and} \quad (z, x) \in G \\ &\iff \ \exists z \ni (z, y) \in H^{-1} \quad \text{and} \quad (x, z) \in G^{-1} \\ &\iff \ \exists z \ni (x, z) \in G^{-1} \quad \text{and} \quad (z, y) \in H^{-1} \\ &\iff \ (x, y) \in H^{-1} \circ G^{-1}. \end{aligned}$$

1. $$\begin{aligned} x \in \mathit{dom}\, G \ &\iff \ \exists y \ni (x, y) \in G \\ &\iff \ \exists y \ni (y, x) \in G^{-1} \\ &\iff \ x \in \mathit{ran}\, G^{-1}. \end{aligned}$$
2. The proof of (2) is left as an exercise.
3. $$\begin{aligned} x \in \mathit{dom}\, (G \circ H) \ &\implies \ \exists y \ni (x, y) \in (G \circ H) \\ &\implies \ \exists y \ni (\exists z \ni (x, z) \in H \quad \text{and} \quad (z, y) \in G) \\ &\implies \ \exists y \text{ and } \exists z \ni (x, z) \in H \quad \text{and} \quad (z, y) \in G \\ &\implies \ \exists z \ni (x, z) \in H \\ &\implies \ x \in \mathit{dom}\, H. \end{aligned}$$
4. The proof of (4) is left as an exercise.

By Theorem 3.64(iii),

Thus it is sufficient to show

Let $x \in \mathit{dom}\, H$. Then by the definition of the domain,

By the definition of the range,

Moreover, by the assumption that $\mathit{ran}\, H \subset \mathit{dom}\, G$,

Thus by the definition of the domain of $G$,

Finally, combining (3.14) and (3.15), we have