陶哲轩Analysis I习题的参考解答及思考（第3章）

第3章

版本

Analysis I（第3版）。

章节3.1

练习3.1.1

题目：

Show that the definition of equality in Definition 3.1.4 is reflexive, symmetric, and transitive.

Definition 3.1.4的内容：

(Equality of sets). Two sets \( A \) and \( B \) are equal, \( A = B \), iff every element of \( A \) is an element of \( B \) and vice versa. To put it another way, \( A = B \) if and only if every element \( x \) of \( A \) belongs also to \( B \), and every element \( y \) of \( B \) belongs also to \( A \).

证明：

证明自反性，即\( A = A \)。

正向：\( \forall x \in A \)，有\( x \in A \)。

反向：\( \forall x \in A \)，有\( x \in A \)。

对，看起来像废话，因为都是同一个集合。

证毕。

证明对称性，即如果\( A = B \)，则有\( B = A \)。

因为\( A = B \)，故\( \forall x \in A \)，有\( x \in B \)， \( \forall y \in B \)，有\( y \in A \)。

两句话顺序调换下，改下变量名，变成：\( \forall x \in B \)，有\( x \in A \)，\( \forall y \in A \)，有\( y \in B \)，故\( B = A \)。

证毕。

证明传递性，即如果\( A = B \)且\( B = C \)，则\( A = C \)。

\( A = B \)，故\( \forall x \in A \)，有\( x \in B \)， \( \forall y \in B \)，有\( y \in A \)。

\( B = C \)，故\( \forall x \in B \)，有\( x \in C \)， \( \forall y \in C \)，有\( y \in B \)。

综上，\( \forall x \in A \)，有\( x \in B \)，进而\( x \in C \)， \( \forall y \in C \)，有\( y \in B \)，进而有\( y \in A \)，故\( A = C \)。

证毕。

练习3.1.2

题目：

Using only Definition 3.1.4, Axiom 3.1, Axiom 3.2, and Axiom 3.3, prove that the sets \( \emptyset , \{ \emptyset \}, \{ \{ \emptyset \} \}, and \{ \emptyset, \{ \emptyset \} \} \) are all distinct (i.e., no two of them are equal to each other).

证明：

\( \emptyset \)和其他几个集合均不相等，因为其他几个集合都至少有一个元素，而\( \emptyset \)没有。

\( \{ \emptyset \} \neq \{ \{ \emptyset \} \} \)，因为若\( x \in \{ \emptyset \} \)，根据公理3.3，有\( x = \emptyset \)，若\( x \in \{ \{ \emptyset \} \} \)，根据公理3.3，有\( x = \{ \emptyset \} \)，而\( \emptyset \neq \{ \emptyset \} \)，故如果一个元素属于\( \{ \emptyset \} \)，那么必不属于\( \{ \{ \emptyset \} \} \)，反之亦然，结论就是两个集合不相等。

\( \{ \emptyset \} \neq \{ \emptyset, \{ \emptyset \} \} \)，因为后者存在一个元素\( \{ \emptyset \} \)，该元素不属于前者。

\( \{ \{ \emptyset \} \} \neq \{ \emptyset, \{ \emptyset \} \} \)，因为后者存在一个元素\( \emptyset \)，该元素不属于前者。

证毕。

注：如果要严格证明，还需要说明通过公理3.1、公理3.2、公理3.3构造各个集合的完整过程，比较啰嗦，这里省略了。

练习3.1.3

题目：

Prove the remaining claims in Lemma 3.1.13.

Lemma 3.1.13的内容：

Lemma 3.1.13. If \( a \) and \( b \) are objects, then \( \{ a, b \} = \{ a \} \cup \{ b \} \). If \( A, B, C \) are sets, then the union operation is commutative (i.e., \( A \cup B = B \cup A) \) and associative (i.e., \( (A \cup B) \cup C = A \cup (B \cup C) \)). Also, we have \( A \cup A = A \cup \emptyset = \emptyset \cup A = A \).

证明：

结合律已经证明了，我们只需要证剩下的。

先证明：如果\( a, b \)是对象，则\( \{ a, b \} = \{ a \} \cup \{ b \} \)。

根据公理3.3，\( \forall x \in \{ a, b \} \)，有\( x = a \)或\( x = b \)，如果\( x = a \)，则\( x \in \{ a \} \)，进而\( x \in \{ a \} \cup \{ b \} \)，如果\( x = b \)，则\( x \in \{ b \} \)，进而\( x \in \{ a \} \cup \{ b \} \)。

反之，\( \forall x \in \{ a \} \cup \{ b \} \)，有\( x \in \{ a \} \)或\( x \in \{ b \} \)。如果\( x \in \{ a \} \)，则\( x = a \)，进而\( x \in \{ a, b \} \)，如果\( x \in \{ b \} \)，则\( x = b \)，进而\( x \in \{ a, b \} \)。

证毕。

接着证明交换律。

\( \forall x \in A \cup B \)，有\( x \in A \)或\( x \in B \)，如果\( x \in A \)，则\( x \in B \cup A \)，如果\( x \in B \)，则\( x \in B \cup A \)。

反过来，\( \forall x \in B \cup A \)，则\( x \in B \)或\( x \in A \)，如果\( x \in B \)，则\( x \in A \cup B \)，如果\( x \in A \)，则\( x \in A \cup B \)。

综上，\( A \cup B = B \cup A \)。

证毕。

下面证明\( A \cup A = A \cup \emptyset = \emptyset \cup A = A \)。

先证\( A \cup A = A \)，\( \forall x \in A \cup A \)，有\( x \in A \)或\( x \in A \)，不管怎么样，都有\( x \in A \)，反之，\( \forall x \in A \)，则\( x \in A \cup A \)，综上\( A \cup A = A \)。

\( A \cup \emptyset = A \)和\( \emptyset \cup A = A \)两个只需要证一个即可，因为并集符合交换律，我们证前面这个。 \( \forall x \in A \cup \emptyset \)，有\( x \in A \)或\( x \in \emptyset \)，\( x \in \emptyset \)是不可能的，故\( x \in A \)，反之，\( \forall x \in A \)，有\( x \in A \cup \emptyset \)，综上\( A \cup \emptyset = A \)。

证毕。

练习3.1.4

题目：

Prove the remaining claims in Proposition 3.1.18.

Proposition 3.1.18的内容：

(Sets are partially ordered by set inclusion). Let \( A, B, C \) be sets. If \( A \subseteq B \) and \( B \subseteq C \) then \( A \subseteq C \). If \( A \subseteq B \) and \( B \subseteq A \), then \( A = B \). Finally, if \( A \subsetneq B \) and \( B \subsetneq C \) then \( A \subsetneq C \).

证明：

证明如果\( A \subseteq B \)且\( B \subseteq C \)，则\( A \subseteq C \)：

因为\( A \subseteq B \)，\( \forall x \in A \)，有\( x \in B \)，又\( B \subseteq C \)，所以\( x \in C \)，综上，\( \forall x \in A \)有\( x \in C \)，即\( A \subseteq C \)。

证毕。

证明如果\( A \subseteq B \)且\( B \subseteq A \)，则\( A = B \)：

如果\( A \neq B \)，则要么\( \exists x \in A \)且\( x \notin B \)，要么\( \exists x \in B \)且\( x \notin A \)（或者同时都满足），如果\( \exists x \in A \)且\( x \notin B \)，这和\( A \subseteq B \)矛盾，故不可能，如果\( \exists x \in B \)且\( x \notin A \)，这和\( B \subseteq A \)矛盾，故不可能，综上，\( A = B \)。

证毕。

证明如果\( A \subsetneq B \)且\( B \subsetneq C \)，则\( A \subsetneq C \)：

因为\( A \subsetneq B \)，\( \forall x \in A \)，有\( x \in B \)，又\( B \subsetneq C \)，所以\( x \in C \)，综上，\( \forall x \in A \)有\( x \in C \)，即\( A \subseteq C \)。

现在还差证明\( A \neq C \)，假设\( A = C \)，则\( \forall x \in C \)，有\( x \in A \)，进而\( x \in B \)，加上\( B \subsetneq C \)，得\( \forall x \in B \)，有\( x \in C \)，于是有\( B = C \)，这和\( B \subsetneq C \)矛盾，故\( A \neq C \)。

证毕。

练习3.1.5

题目：

Let \( A, B \) be sets. Show that the three statements \( A \subseteq B \), \( A \cup B = B \), \( A \cap B = A \) are logically equivalent (any one of them implies the other two).

注：

为了证明\( \text{命题}A \equiv \text{命题}B \equiv \text{命题}C \)，我们只需要证明 \( \text{命题}A \Rightarrow \text{命题}B \)， \( \text{命题}B \Rightarrow \text{命题}C \)， \( \text{命题}C \Rightarrow \text{命题}A \)，然后利用传递性，很容易证明两两命题相互等价。

证明：

证明\( A \subseteq B \Rightarrow A \cup B = B \)：

我们需要证明\( A \cup B \)的所有元素都属于\( B \)，B的所有元素也都属于\( A \cup B \)。 \( \forall x \in A \cup B \)，有\( x \in A \)或\( x \in B \)，如果\( x \in A \)，则\( x \in B \)（因为\( A \subseteq B \)），如果\( x \in B \)，那么正好，反之，\( \forall x \in B \)，有\( x \in A \cup B \)，综上，\( A \cup B = B \)。

证毕。

证明\( A \cup B = B \Rightarrow A \cap B = A \)：

因为\( A \cup B = B \)，故\( \forall x \in A \cup B \)，有\( x \in B \)，反之，\( \forall x \in B \)，有\( x \in A \cup B \) （后面这个方向没给出什么特别有用的信息，不用考虑）。

\( \forall x \in A \cup B \)，有\( x \in A \)或\( x \in B \)，这两种情况下都有\( x \in B \)，我们可以推出：\( \forall x \in A \)，有\( x \in B \)。

现在证明\( A \cap B = A \)。

\( \forall x \in A \cap B \)，有\( x \in A \)，反之\( \forall x \in A \)，有\( x \in B \)（我们前面证的），综上，\( A \cap B = A \)。

证毕。

证明\( A \cap B = A \Rightarrow A \subseteq B \)：

因为\( A \cap B = A \)，故\( \forall x \in A \cap B \)，\( x \in A \)，\( \forall x \in A \)，\( x \in A \cap B \) （后面这句话没什么价值，可以无视），由\( \forall x \in A \cap B \)，\( x \in A \)，可以推出\( \forall x \in B \)，有\( x \in A \)，即\( A \subseteq B \)。

证毕。

练习3.1.6

题目：

Prove Proposition 3.1.28. (Hint: one can use some of these claims to prove others. Some of the claims have also appeared previously in Lemma 3.1.13.)

Proposition 3.1.28的内容：

(Sets form a boolean algebra). Let \( A, B, C \) be sets, and let \( X \) be a set containing \( A, B, C \) as subsets.

1. (Minimal element) We have \( A \cup ∅ \) = A and \( A \cap \emptyset = \emptyset \).
2. (Maximal element) We have \( A \cup X = X \) and \( A \cap X = A \).
3. (Identity) We have \( A \cap A = A \) and \( A \cup A = A \).
4. (Commutativity) We have \( A \cup B = B \cup A \) and \( A \cap B = B \cap A \).
5. (Associativity) We have \( (A \cup B) \cup C = A \cup (B \cup C) \) and \( (A \cap B) \cap C = A \cap (B \cap C) \).
6. (Distributivity) We have \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \) and \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \).
7. (Partition) We have \( A \cup (X \setminus A) = X \) and \( A \cap (X \setminus A) = \emptyset \).
8. (De Morgan laws) We have \( X \setminus (A \cup B) = (X \setminus A) \cap (X \setminus B) \) and \( X \setminus (A \cap B) = (X \setminus A) \cup (X \setminus B) \).

以下是证明。

先证明交换律、结合律、分配律，方便其他命题的证明使用。

• 命题4

  证明\( A \cup B = B \cup A \)：

  \( \forall x \in A \cup B \)，有\( x \in A \)或\( x \in B \)，如果\( x \in A \)，则\( x \in B \cup A \)，如果\( x \in B \)，则\( x \in B \cup A \)。

  反之，\( \forall x \in B \cup A \)，有\( x \in B \)或\( x \in A \)，如果\( x \in B \)，则\( x \in A \cup B \)，如果\( x \in A \)，则\( x \in A \cup B \)。

  证毕。

  证明\( A \cap B = B \cap A \)：

  \( \forall x \in A \cap B \)，有\( x \in A \)且\( x \in B \)，进而有\( x \in B \)且\( x \in A \)（逻辑与的两个子句是可以交换顺序的，语义不变），故\( x \in B \cap A \)。

  反之，\( \forall x \in B \cap A \)，有\( x \in B \)且\( x \in A \)，进而有\( x \in A \)且\( x \in B \)，故\( x \in A \cap B \)。

  证毕。

• 命题5

  证明\( (A \cup B) \cup C = A \cup (B \cup C) \)：

  \( \forall x \in (A \cup B) \cup C \)，有\( x \in A \cup B \)或\( x \in C \)。

  1. 如果\( x \in A \cup B \)，则\( x \in A \)或\( x \in B \)。
     1. 如果\( x \in A \)，则\( x \in A \cup (B \cup C) \)。
     2. 如果\( x \in B \)，则\( x \in B \cup C \)，进而有\( x \in A \cup (B \cup C) \)。
  2. 如果\( x \in C \)，则\( x \in B \cup C \)，进而有\( x \in A \cup (B \cup C) \)。

  反之，\( \forall x \in A \cup (B \cup C) \)，有\( x \in A \)或\( x \in B \cup C \)。

  1. 如果\( x \in A \)，则\( x \in A \cup B \)，进而有\( x \in (A \cup B) \cup C \)。
  2. 如果\( x \in B \cup C \)，则\( x \in B \)或者\( x \in C \)。
     1. 如果\( x \in B \)，则\( x \in A \cup B \)，进而有\( x \in (A \cup B) \cup C \)。
     2. 如果\( x \in C \)，则\( x \in (A \cup B) \cup C \)。

  证毕。

  证明\( (A \cap B) \cap C = A \cap (B \cap C) \)：

  \( \forall x \in (A \cap B) \cap C \)，有\( x \in A \cap B \)且\( x \in C \)，即\( x \in A \)且\( x \in B \)且\( x \in C \)，由于\( x \in B \)且\( x \in C \)，故\( x \in B \cap C \)，综上，\( x \in A \cap (B \cap C) \)。

  反之，\( \forall x \in A \cap (B \cap C) \)，有\( x \in A \)且\( x \in B \cap C \)，即\( x \in A \)且\( x \in B \)且\( x \in C \)，由于\( x \in A \)且\( x \in B \)，故\( x \in A \cap B \)，综上，\( x \in (A \cap B) \cap C \)。

  证毕。

• 命题6

  证明\( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)：

  \( \forall x \in A \cap (B \cup C) \)，有\( x \in A \)且\( x \in B \cup C \)，即\( x \in A \)且（\( x \in B \)或\( x \in C \)），这相当于（\( x \in A \)且\( x \in B \)）或（\( x \in A \)且\( x \in C \)），于是有\( x \in A \cap B \)或\( x \in A \cap C \)，即\( x \in (A \cap B) \cup (A \cap C) \)。

  反之，\( \forall x \in (A \cap B) \cup (A \cap C) \)，有\( x \in A \cap B \)或\( x \in A \cap C \)。

  1. 如果\( x \in A \cap B \)，则\( x \in A \)且\( x \in B \)，因为\( x \in B \)，故\( x \in B \cup C \)，综上，\( x \in A \cap (B \cup C) \)。
  2. 如果\( x \in A \cap C \)，则\( x \in A \)且\( x \in C \)，因为\( x \in C \)，故\( x \in B \cup C \)，综上，\( x \in A \cap (B \cup C) \)。

  证毕。

  证明\( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \)：

  \( \forall x \in A \cup (B \cap C) \)，有\( x \in A \)或\( x \in B \cap C \)。

  1. 如果\( x \in A \)，则同时有\( x \in A \cup B \)以及\( x \in A \cup C \)，即\( x \in (A \cup B) \cap (A \cup C) \)。
  2. 如果\( x \in B \cap C \)，则\( x \in B \)且\( x \in C \)，

  证毕。

• 命题1

  \( \emptyset \subseteq A \)，根据练习3.1.5以及交换律，\( A \cup \emptyset = A \)，\( A \cap \emptyset = \emptyset \)。

  证毕。

• 命题2

  \( A \subseteq X \)，根据练习3.1.5，\( A \cup X = X \)，\( A \cap X = A \)。

  证毕。

• 命题3

  \( A \subseteq A \)，根据练习3.1.5，\( A \cup A = A \)，\( A \cap A = A \)。

  证毕。

• 命题7

  证明\( A \cup (X \setminus A) = X \)：

  \( \forall x \in A \cup (X \setminus A) \)，有\( x \in A \)或\( x \in X \setminus A \)，如果\( x \in A \)，则由于\( A \subseteq X \)，于是有\( x \in X \)，如果\( x \in X \setminus A \)，则有\( x \in X \)。

  反之，\( \forall x \in X \)，有两种情况，\( x \in A \)或\( x \notin A \)，如果\( x \in A \)，则\( x \in A \cup (X \setminus A) \)，

  证毕。

  证明\( A \cap (X \setminus A) = \emptyset \)：

  \( \forall x \in A \cap (X \setminus A) \)，有\( x \in A \)且\( x \in X \setminus A \)，即\( x \in A \)且\( x \in X \)且\( x \notin A \)，不存在对象\( x \)能同时满足\( x \in A \)及\( x \notin A \)的，故\( \forall x \)，有\( x \notin A \cap (X \setminus A) \)，即\( A \cap (X \setminus A) = \emptyset \)。

  证毕。

• 命题8

  证明\( X \setminus (A \cup B) = (X \setminus A) \cap (X \setminus B) \)：

  \( \forall x \in X \setminus (A \cup B) \)，有\( x \in X \)且\( x \notin A \cup B \)。因为\( x \notin A \cup B \)，故\( x \notin A \)且\( x \notin B \)。因为\( x \in X \)且\( x \notin A \)，故\( x \in X \setminus A \)。因为\( x \in X \)且\( x \notin B \)，故\( x \in X \setminus B \)。综上，有\( x \in (X \setminus A) \cap ( X \setminus B ) \)。

  反之，\( \forall x \in (X \setminus A) \cap (X \setminus B) \)，有\( x \in X \setminus A \)且\( x \in X \setminus B \)，即\( x \in X \)且\( x \notin A \)且\( x \notin B \)。因为\( x \notin A \)且\( x \notin B \)，故\( x \notin A \cup B \) 再加上\( x \in X \)，可得\( x \in X \setminus (A \cup B) \)。

  证毕。

  证明\( X \setminus (A \cap B) = (X \setminus A) \cup (X \setminus B) \)：

  \( \forall x \in X \setminus (A \cap B) \)，有\( x \in X \)且\( x \notin A \cap B \)。因为\( x \notin A \cap B \)，故\( x \notin A \)或\( x \notin B \)。如果\( x \notin A \)，此时加上\( x \in X \)，有\( x \in X \setminus A \)。如果\( x \notin B \)，此时加上\( x \in X \)，有\( x \in X \setminus B \)。综上，有\( x \in (X \setminus A) \cup (X \setminus B) \)。

  反之，\( \forall x \in (X \setminus A) \cup (X \setminus B) \)，有 \( x \in X \setminus A \)或\( x \in X \setminus B \)，即\( x \in X \)且（\( x \notin A \)或\( x \notin B \)）。由\( x \notin A \)或\( x \notin B \)，可得\( x \notin A \cap B \)，再加上\( x \in X \)，可得\( x \in X \setminus (A \cap B) \)。

  证毕。

练习3.1.7

题目：

Let \( A, B, C \) be sets. Show that \( A \cap B \subseteq A \) and \( A \cap B \subseteq B \). Furthermore, show that \( C \subseteq A \) and \( C \subseteq B \) if and only if \( C \subseteq A \cap B \). In a similar spirit, show that \( A \subseteq A \cup B \) and \( B \subseteq A \cup B \), and furthermore that \( A \subseteq C \) and \( B \subseteq C \) if and only if \( A \cup B \subseteq C \).

以下是证明。

• 命题\( A \cap B \subseteq A \)

  \( \forall x \in A \cap B \)，有\( x \in A \)，故\( A \cap B \subseteq A \)。

  证毕。

• 命题\( A \cap B \subseteq B \)

  \( \forall x \in A \cap B \)，有\( x \in B \)，故\( A \cap B \subseteq B \)。

  证毕。

• 命题\( C \subseteq A \)且\( C \subseteq B \)\( \equiv \)\( C \subseteq A \cap B \)

  必要性：

  因为\( C \subseteq A \)且\( C \subseteq B \)，故\( \forall x \in C \)，有\( x \in A \)且\( x \in B \)，即\( \forall x \in C \)，有\( x \in A \cap B \)，故\( C \subseteq A \cap B \)。

  充分性：

  因为\( C \subseteq A \cap B \)，故\( \forall x \in C \)，有\( x \in A \cap B \)，即 \( \forall x \in C \)，有\( x \in A \)且\( x \in B \)，故\( C \subseteq B \)且\( C \subseteq B \)。

  证毕。

• 命题\( A \subseteq A \cup B \)

  \( \forall x \in A \)，有\( x \in A \cup B \)，故\( A \subseteq A \cup B \)。

  证毕。

• 命题\( B \subseteq A \cup B \)

  \( \forall x \in B \)，有\( x \in A \cup B \)，故\( B \subseteq A \cup B \)。

  证毕。

• 命题\( A \subseteq C \)且\( B \subseteq C \)\( \equiv \)\( A \cup B \subseteq C \)

  必要性：

  因为\( A \subseteq C \)且\( B \subseteq C \)，故\( \forall x \in A \)，有\( x \in C \)， \( \forall x \in B \)，有\( x \in C \)。

  \( \forall x \in A \cup B \)，有\( x \in A \)或\( x \in B \)，如果\( x \in A \)，则有\( x \in C \)，如果\( x \in B \)，则也有\( x \in C \)，综上，\( A \cup B \subseteq C \)。

  充分性：

  因为\( A \cup B \subseteq C \)，故\( \forall x \in A \cup B \)，有\( x \in C \)，即\( x \in A \)有\( x \in C \)，\( x \in B \)也有\( x \in C \)，这说明\( A \subseteq C \)且\( B \subseteq C \)。

  证毕。

练习3.1.8

题目：

Let \( A, B \) be sets. Prove the absorption laws \( A \cap (A \cup B) = A \) and \( A \cup (A \cap B) = A \).

证明\( A \cap (A \cup B) = A \)：

\( \forall x \in A \cap (A \cup B) \)，有\( x \in A \)，反之，\( \forall x \in A \)，有\( x \in A \cup B \)，故\( x \in A \cap (A \cup B) \)。

证毕。

证明\( A \cup (A \cap B) = A \)：

\( \forall x \in A \cup (A \cap B) \)，有\( x \in A \)或\( x \in A \cap B \)，如果\( x \in A \)，这刚好是我们要的，如果\( x \in A \cap B \)，则也有\( x \in A \)。

反之，\( \forall x \in A \)，有\( x \in A \cup (A \cap B) \)。

证毕。

练习3.1.9

题目：

Let \( A, B, X \) be sets such that \( A \cup B = X \) and \( A \cap B = \emptyset \). Show that \( A = X \setminus B \) and \( B = X \setminus A \).

证明\( A = X \setminus B \)：

因为\( A \subseteq A \cup B \)，\( A \cup B \subseteq X \)，故\( A \subseteq X \)，即\( \forall x \in A \)，\( x \in X \)。

\( \forall x \in A \)，假设\( x \in B \)，则\( x \in A \cap B \)，这与\( A \cap B = \emptyset \)矛盾，故\( x \notin B \)。

综上，\( \forall x \in A \)，有\( x \in X \)且\( x \notin B \)，即\( A \subseteq X \setminus B \)。

反之，\( \forall x \in X \setminus B \)，有\( x \in X \)且\( x \notin B \)，假设\( x \notin A \)，则我们有\( x \notin A \)且\( x \notin B \)，即\( x \notin (A \cup B = X) \)，矛盾，故\( x \in A \)。

综上，\( \forall x \in X \setminus B \)，有\( x \in A \)。

证毕。

证明\( B = X \setminus A \)：

因为\( B \subseteq A \cup B \)，\( A \cup B \subseteq X \)，故\( B \subseteq X \)，即\( \forall x \in B \)，\( x \in X \)。

\( \forall x \in B \)，假设\( x \in A \)，则\( x \in A \cap B \)，这与\( A \cap B = \emptyset \)矛盾，故\( x \notin A \)。

综上，\( \forall x \in B \)，有\( x \in X \)且\( x \notin A \)，即\( B \subseteq X \setminus A \)。

反之，\( \forall x \in X \setminus A \)，有\( x \in X \)且\( x \notin A \)，假设\( x \notin B \)，则我们有\( x \notin A \)且\( x \notin B \)，即\( x \notin (A \cup B = X) \)，矛盾，故\( x \in B \)。

综上，\( \forall x \in X \setminus A \)，有\( x \in B \)。

证毕。

练习3.1.10

题目：

Let \( A \) and \( B \) be sets. Show that the three sets \( A \setminus B \), \( A \cap B \), and \( B \setminus A \) are disjoint, and that their union is \( A \cup B \).

证明\( (A \setminus B) \cap (A \cap B) = \emptyset \)：

\( \forall x \in A \setminus B \)，有\( x \in A \)且\( x \notin B \)，而\( x \in A \cap B \)要求\( x \in B \)，而\( x \notin B \)，故\( x \notin A \cap B \)。

反之，\( \forall x \in A \cap B \)，有\( x \in A \)且\( x \in B \)，而\( x \in A \setminus B \)要求\( x \notin B \)，而\( x \in B \)，故\( x \notin A \setminus B \)。

证毕。

证明\( (A \setminus B) \cap (B \setminus A) = \emptyset \)：

\( \forall x \in A \setminus B \)，有\( x \in A \)且\( x \notin B \)，而\( x \in B \setminus A \)要求\( x \notin A \)，而\( x \in A \)，故\( x \notin B \setminus A \)。

反之，\( \forall x \in B \setminus A \)，有\( x \in B \)且\( x \notin A \)，而\( x \in A \setminus B \)要求\( x \notin B \)，而\( x \in B \)，故\( x \notin A \setminus B \)。

证毕。

证明\( (A \cap B) \cap (B \setminus A) = \emptyset \)：

\( \forall x \in A \cap B \)，有\( x \in A \)且\( x \in B \)，而\( x \in B \setminus A \)要求\( x \notin A \)，而\( x \in A \)，故\( x \notin B \setminus A \)。

反之，\( \forall x \in B \setminus A \)，有\( x \in B \)且\( x \notin A \)，而\( x \in A \cap B \)要求\( x \in B \)，而\( x \notin B \)，故\( x \notin A \cap B \)。

证毕。

证明\( (A \setminus B) \cup (A \cap B) \cup (B \setminus A) = A \cup B \)：

\( \forall x \in (A \setminus B) \cup (A \cap B) \cup (B \setminus A) \)，有\( x \in A \setminus B \)或\( x \in A \cap B \)或\( x \in B \setminus A \)。

1. 如果\( x \in A \setminus B \)，则\( x \in A \)，进而\( x \in A \cup B \)。
2. 如果\( x \in A \cap B \)，则\( x \in A \)，进而\( x \in A \cup B \)。
3. 如果\( x \in B \setminus A \)，则\( x \in B \)，进而\( x \in A \cup B \)。

反之，\( \forall x \in A \cup B \)，有\( x \in A \)或\( x \in B \)，更具体的，有三种情况：

1. \( x \in A \)且\( x \in B \)，此时\( x \in A \cap B \)，进而\( x \in (A \setminus B) \cup (A \cap B) \cup (B \setminus A) \)。
2. \( x \in A \)且\( x \notin B \)，此时\( x \in A \setminus B \)，进而\( x \in (A \setminus B) \cup (A \cap B) \cup (B \setminus A) \)。
3. \( x \notin A \)且\( x \in B \)，此时\( x \in B \setminus A \)，进而\( x \in (A \setminus B) \cup (A \cap B) \cup (B \setminus A) \)。

证毕。

练习3.1.11

题目：

Show that the axiom of replacement implies the axiom of specification.

证明：

这里替换公理中的属性用符号\( P(x, y) \)表示，规范公理的属性则用符号\( Q(x) \)表示。

令\( P(x, y) \)为属性：若\( Q(x) \)为真，则\( y = x \)，若\( Q(x) \)为假，则\( y \)不存在（替换公理要求至多有一个\( y \)使得\( P(x, y) \)为真，故符合条件的\( y \)也可以是0个）。

将\( P(x, y) \)代入替换公理，可以得到集合\( \{ x \in A : Q(x) \} \)是存在的。

证毕。

章节3.2

练习3.2.1

题目：

Show that the universal specification axiom, Axiom 3.8, if assumed to be true, would imply Axioms 3.2, 3.3, 3.4, 3.5, and 3.6. (If we assume that all natural numbers are objects, we also obtain Axiom 3.7.) Thus, this axiom, if permitted, would simplify the foundations of set theory tremendously (and can be viewed as one basis for an intuitive model of set theory known as “naive set theory”). Unfortunately, as we have seen, Axiom 3.8 is “too good to be true”!

注：

这里要特别注意，很多公理用词都是“当且仅当”或者符号\( \Leftrightarrow \)，即它们不仅要求得到的集合\( A \)中的元素全部符合要求，还要求所有符合要求的元素都在\( A \)中。

证明公理3.8蕴含公理3.2：

令\( P(x) \)为一个恒假属性，也就是\( \forall x \)，有\( P(x) \)为假。

将\( P(x) \)代入公理3.8，得：存在一个集合\( A \)，\( \forall x \)，有\( x \notin A \)，这个集合就是\( \emptyset \)。

证毕。

证明公理3.8蕴含公理3.3：

令\( a, b \)为两个对象（可相同，可不相同）。

令\( P(x) \)为属性：\( x = a \)。

将\( P(x) \)代入公理3.8，得：存在一个集合\( A \)，\( \forall \)对象\( x \)， \( x \in A \)当且仅当\( x = a \)，这个\( A \)就是我们要的单例集。

令\( Q(x) \)为属性：\( x = a \)或\( x = b \)。

将\( Q(x) \)代入公理3.8，得：存在一个集合\( B \)，\( \forall \)对象\( x \)， \( x \in B \)当且仅当\( x = a \)或\( x = b \)，这个\( B \)就是我们要的双例集。

证毕。

证明公理3.8蕴含公理3.4：

令\( A, B \)为两个集合，令\( P(x) \)为属性：\( x \in A \)或\( x \in B \)。

将\( P(x) \)代入公理3.8，得：存在一个集合\( C \)，\( \forall \)对象\( x \)， \( x \in C \)当且仅当\( x \in A \)或\( x \in B \)，这个集合\( C \)就是我们要的并集。

证毕。

证明公理3.8蕴含公理3.5：

令\( A \)为一个集合，令\( P(x) \)为任意关于\( x \in A \)的属性，即给定一个\( x \in A \)，\( P(x) \)为真或者假，该属性仅适用于对象\( x \in A \)，它对于\( x \notin A \)的真假值是未定义的，我们拓展该属性，构造属性\( Q(x) \)，\( \forall \)对象\( x \)，如果\( x \in A \)，则\( Q(x) \)的真假值和\( P(x) \)一样，如果\( x \notin A \)，则\( Q(x) \)一律为假。

将\( Q(x) \)代入公理3.8，得：存在一个集合\( B \)， \( \forall \)对象\( x \)，\( x \in B \)当且仅当\( x \in A \)且\( P(x) \)为真。

证毕。

证明公理3.8蕴含公理3.6：

令\( A \)为一个集合，令\( P(x, y) \)为一个关于\( x \in A, y \)的属性，该属于针对任意\( x \in A \)，至多有一个\( y \)使得\( P(x, y) \)为真，该属性仅适用于对象\( x \in A \)（\( y \)则没限制），它对于\( x \notin A \)的真假值是未定义的。

令\( Q(y) \)为一个关于\( y \)的属性：若\( \exists x \in A \)，使得\( P(x, y) \)为真，则\( Q(y) \)为真，否则\( Q(y) \)为假（\( Q(y) \)为假对应\( P(x, y) \)为假或者未定义的情况）。

将\( Q(y) \)代入公理3.8，得：存在一个集合\( B \)， \( \forall \)对象\( y \)，\( y \in B \)当且仅当\( \exists x \in A \)，使得\( P(x, y) \)为真。

证毕。

证明公理3.8蕴含公理3.7（假设所有自然数均是对象）：

“假设所有自然数均是对象”这句话是有歧义的，问题是什么样的对象才算自然数，按照公理3.7，一个对象只有和它所处的集合中的其他对象均符合Peano公理，我们才叫它自然数，单独给一个对象，我们根本不知道它有没有违反Peano公理（因为这还看处于同一集合的其他元素是否都不违反），但公理3.8中，给定任意一个对象，它根本没有“所处的集合”这个概念，那我们怎么知道它是不是自然数呢？举个例子，读者可能会想这么证明，令\( P(x) := x \text{符合Peano公理} \)，然后将\( P(x) \)代入公理3.8，企图得到所有符合Peano公理的对象的集合，也就是自然数集合，但是问题在于Peano公理有几条涉及不止一个对象，但靠参数\( x \)，我们无法验证\( x \) 是否满足Peano公理，于是读者可能会想这样修正：令\( P(x) := x \text{及其所属集合的其他对象均符合Peano公理} \)，这里的问题是，\( x \)没有“所属集合”这个概念，公理3.8都还没用呢，哪里来的集合，故该\( P(x) \)也是非法的。所以怎么解释“假设所有自然数均是对象”这句话？有几种可能的解释：

1. 在对象宇宙中，一开始就有某些对象被我们定性为自然数，另一些则是非自然数，所有这些自然数一起组成的集合本来就符合Peano公理。
2. 在对象宇宙中，一开始就有某些对象被我们定性为自然数，另一些则是非自然数，所有这些自然数一起组成的集合中会存在一些元素导致整个集合违反Peano公理，针对这种情况，我们似乎可以先用公理3.8得到所有集合组成的集合\( \Omega \)，然后再用公理3.8，从\( \Omega \)中过滤掉那些不符合Peano公理的集合，得到过滤后的集合\( \Omega' \)，但问题是，集合\( \Omega' \)可能为空，你不好说明是否至少有一个集合满足Peano公理，除非附加一条公理：给定任意属性\( P(x) \)，在对象宇宙中（这句话可以去掉），存在至少一个对象，使得\( P(x) \)为真。

先按第一种解释来进行证明：

令\( P(x) \)为属性：\( x \)是自然数。

将\( P(x) \)代入公理3.8，便得到了集合\( A \)，\( \forall \)对象\( n \)， \( n \in A \)当且仅当\( n \)是自然数，即自然数集存在。

证毕。

再按第二种解释来进行证明：

根据公理3.8，存在所有集合的集合\( \Omega \)。

令\( P(x) \)为属性：\( x \in \Omega \)且\( x \)满足Peano公理。

将\( P(x) \)代入公理3.8，则会得到一个集合\( \Omega' = \{ \mathbf{N}_0, \mathbf{N}_1, \dots \} \)， \( \forall \)对象\( A \)，\( A \in \Omega' \)当且仅当\( A \in \Omega \)（即\( A \)是集合）且\( A \)满足Peano公理，由于我们假设所有自然数均是对象，因此\( \Omega' \)非空，此时任取一个\( A \in \Omega' \)均可作为自然数集，即自然数集是存在的。

证毕。

练习3.2.2

题目：

Use the axiom of regularity (and the singleton set axiom) to show that if \( A \) is a set, then \( A \notin A \). Furthermore, show that if \( A \) and \( B \) are two sets, then either \( A \notin B \) or \( B \notin A \) (or both).

这个命题说明集合不会出现自包含以及相互包含的情况。

证明\( A \notin A \)：

因为\( A \)是一个集合（对象），我们可以得到单例集\( \{ A \} \)，根据正则公理，集合\( \{ A \} \)中至少存在一个对象\( x \)， \( x \)不是集合或\( x \)是集合且\( x \cap \{ A \} = \emptyset \)，而\( \{ A \} \)中只有一个集合对象\( A \)，故只有可能是后面这种情况，现在，我们假设\( A \in A \)，则\( \forall x \in \{ A \} \)，有\( x = A \)，此时\( x \cap \{ A \} \neq \emptyset \)，不满足正则公理，故假设不成立，只能\( A \notin A \)。

证毕。

证明\( A \notin B \)或\( B \notin A \)：

因为\( A, B \)是集合，可以得到双例集\( \{ A, B \} \)，根据正则公理，集合\( \{ A, B \} \)中至少存在一个对象\( x \)， \( x \)不是集合或\( x \)是集合且\( x \cap \{ A, B \} = \emptyset \)，而\( \{ A, B \} \)中的对象均是集合，故只有可能是后面这种情况，现在，我们假设\( A \in B \)且\( B \in A \)，则\( \forall x \in \{ A, B \} \)，有\( x = A \)或\( x = B \)，如果\( x = A \)，则\( x \cap \{ A, B \} \neq \emptyset \)，如果\( x = B \)，则也有\( x \cap \{ A, B \} \neq \emptyset \)，也就是不管\( x \)怎么取，均有\( x \cap \{ A, B \} \neq \emptyset \)，这不满足正则公理，故假设不成立，只能\( A \notin B \)或\( B \notin A \)。

证毕。

练习3.2.3

题目：

Show (assuming the other axioms of set theory) that the universal specification axiom, Axiom 3.8, is equivalent to an axiom postulating the existence of a “universal set” \( \Omega \) consisting of all objects (i.e., for all objects \( x \), we have \( x \in \Omega \)). In other words, if Axiom 3.8 is true, then a universal set exists, and conversely, if a universal set exists, then Axiom 3.8 is true. (This may explain why Axiom 3.8 is called the axiom of universal specification). Note that if a universal set \( \Omega \) existed, then we would have \( \Omega \in \Omega \) by Axiom 3.1, contradicting Exercise 3.2.2. Thus the axiom of foundation specifically rules out the axiom of universal specification.

证明：

必要性：

令\( P(x) \)为永真属性，即\( \forall x \)，有\( P(x) \)为真。

将\( P(x) \)代入公理3.8，得到的就是宇集\( \Omega \)。

充分性：

令\( P(x) \)为属性：\( \forall \)对象\( x \)，有\( P(x) \)为真或\( P(x) \)为假。

将\( \Omega \)和\( P(x) \)代入规范公理，得到集合\( A \)，\( \forall x \in A \)，有\( x \in \Omega \)且\( P(x) \)为真，由于\( \Omega \)包含了所有对象，故\( A \)中包含了所有使得\( P(x) \)为真的对象\( x \)，即公理3.8成立。

证毕。

章节3.3

练习3.3.1

题目：

Show that the definition of equality in Definition 3.3.7 is reflexive, symmetric, and transitive. Also verify the substitution property: if \( f, \tilde{f} : X \to Y \) and \( g, \tilde{g} : Y \to Z \) are functions such that \( f = \tilde{f} \) and \( g = \tilde{g} \), then \( g \circ f \) = \( \tilde{g} \circ \tilde{f} \).

证明函数的定义具有自反性：

令\( f: X \to Y \)为一个函数。

\( f \)和\( f \)的定义域和值域都一样，且\( \forall x \in X \)，有\( f(x) = f(x) \)，故\( f = f \)。

证毕。

证明函数的定义具有对称性：

令\( f: X \to Y \)和\( g: Z \to W \)为两个函数。

如果\( f = g \)，\( f \)和\( g \)具有相同的定义域和值域，即\( X = Z \)且\( Y = W \)，除此之外，还有\( \forall x \in X \)，有\( f(x) = g(x) \)，由于\( X = Z \)，故\( \forall z \in Z \)，有\( g(z) = f(z) \)，即\( g = f \)。

证毕。

证明函数的定义具有传递性：

令\( f: X \to Y \)，\( g: Z \to W \)，\( h: I \to O \)为三个函数。

如果\( f = g \)且\( g = h \)，则\( X = Z \)且\( Y = W \)且\( Z = I \)且\( W = O \)，除此之外，还有\( \forall x \in X \)，\( f(x) = g(x) \)以及\( \forall z \in Z \)，\( g(z) = h(z) \)。由于\( X = Z \)且\( Z = I \)，故\( X = Z = I \)，进而\( \forall i \in I \)，\( f(i) = g(i) = h(i) \)，由于\( Y = W \)且\( W = O \)，故\( Y = O \)，综上，有\( f = h \)。

证毕。

证明函数的复合满足代入公理：

由于\( f = \tilde{f} \)，故\( \forall x \in X \)，有\( f(x) = \tilde{f}(x) \)。

由于\( g = \tilde{g} \)，故\( \forall y \in Y \)，有\( g(y) = \tilde{g}(y) \)。

综上，得\( \forall x \in X \)，有\( (g \circ f)(x) = g(f(x)) = g(\tilde{f}(x)) = \tilde{g}(\tilde{f}(x)) = (\tilde{g} \circ \tilde{f})(x) \)，除此之外，\( g \circ f \)和\( \tilde{g} \circ \tilde{f} \)有相同的定义域和值域\( X \to Z \)，故\( g \circ f = \tilde{g} \circ \tilde{f} \)。

证毕。

练习3.3.2

题目：

Let \( f: X \to Y \) and \( g: Y \to Z \) be functions. Show that if \( f \) and \( g \) are both injective, then so is \( g \circ f \); similarly, show that if \( f \) and \( g \) are both surjective, then so is \( g \circ f \).

证明如果\( f \)和\( g \)都是单射，那么\( f \circ g \)也是单射：

因为f是单射，故\( \forall x, y \in X \)，若\( x \neq y \)，则\( f(x) \neq f(y) \)。

因为g是单射，故\( \forall x, y \in Y \)，若\( x \neq y \)，则\( g(x) \neq g(y) \)。

故，\( \forall x, y \in X \)，若\( x \neq y \)，则\( f(x) \neq f(y) \)，进而有\( g(f(x)) \neq g(f(y)) \)，即\( f \circ g \)是单射函数。

证毕。

证明如果\( f \)和\( g \)都是满射，那么\( f \circ g \)也是满射：

因为\( f \)是满射，故\( \forall y \in Y \)，\( \exists x \in X \)，\( f(x) = y \)。

因为\( g \)是满射，故\( \forall z \in Z \)，\( \exists y \in Y \)，\( g(y) = z \)。

综上，\( \forall z \in Z \)，\( \exists y \in Y \)，\( g(y) = z \)，进而\( \exists x \in X \)，\( f(x) = y \)，于是有\( g(f(x)) = g(y) = z \)，简而言之，\( \forall z \in Z \)，\( \exists x \in X \)，\( (g \circ f)(x) = z \)。

证毕。

练习3.3.3

题目：

When is the empty function injective? surjective? bijective?

解答：

令\( f: \emptyset \to X \)为空函数。

1. \( f \)无需附加条件便是单射函数了。
2. 当\( X \)为空集时，\( f \)满射。
3. 综上，当\( X \)为空集时，\( f \)双射。

练习3.3.4

题目：

In this section we give some cancellation laws for composition. Let \( f: X \to Y \), \( \tilde{f}: X \to Y \), \( g: Y \to Z \) and \( \tilde{g}: Y \to Z \) be functions. Show that if \( g \circ f = g \circ \tilde{f} \) and \( g \) is injective, then \( f = \tilde{f} \). Is the same statement true if \( g \) is not injective? Show that if \( g \circ f = \tilde{g} \circ f \) and \( f \) is surjective, then \( g = \tilde{g} \). Is the same statement true if \( f \) is not surjective?

证明如果\( g \circ f = g \circ \tilde{f} \)且\( g \)单射, 则\( f = \tilde{f} \)：

假设\( f \neq \tilde{f} \)，则\( \exists x \in X \)，\( f(x) \neq \tilde{f}(x) \)，由于\( g \)单射，故\( g(f(x)) \neq g(\tilde{f}(x)) \)，这和\( g \circ f = g \circ \tilde{f} \)矛盾，故假设不成立，有\( f = \tilde{f} \)。

证毕。

如果\( g \)不单射，则该命题不成立，反例：

令\( f: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \}, \tilde{f}: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \}, g: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \} \)， \( g(0) = 1, g(1) = 1, g(2) = 3 \)， \( f(0) = 0, f(1) = 2, f(2) = 1 \)， \( \tilde{f}(0) = 1, \tilde{f}(1) = 2, \tilde{f}(2) = 0 \)。

证明如果\( g \circ f = \tilde{g} \circ f \)且\( f \)满射, 则\( g = \tilde{g} \)：

假设\( g \neq \tilde{g} \)，则\( \exists y \in Y \)，\( g(y) \neq \tilde{g}(y) \)，由于\( f \)满射，\( \exists x \in X \)，\( f(x) = y \)，此时\( (g(f(x)) = g(y)) \neq (\tilde{g}(f(x)) = \tilde{g}(y)) \)，这和\( g \circ f = \tilde{g} \circ f \)矛盾，故假设不成立，有\( g = \tilde{g} \)。

证毕。

如果\( f \)不满射，则该命题不成立，反例：

令\( f: \{ 0, 1 \} \to \{ 0, 1, 2 \}, g: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \}, \tilde{g}: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \} \), \( f(0) = 0, f(1) = 1 \)， \( g(0) = 0, g(1) = 1, g(2) = 1 \)， \( \tilde{g}(0) = 0, \tilde{g}(1) = 1, \tilde{g}(2) = 2 \)。

练习3.3.5

题目：

Let \( f: X \to Y \) and \( g: Y \to Z \) be functions. Show that if \( g \circ f \) is injective, then \( f \) must be injective. Is it true that \( g \) must also be injective? Show that if \( g \circ f \) is surjective, then \( g \) must be surjective. Is it true that \( f \) must also be surjective?

证明如果\( g \circ f \)单射，则\( f \)单射：

假设\( f \)不单射，即\( \exists x_0, x_1 \in X, x_0 \neq x_1 \)，\( f(x_0) = f(x_1) \)，进而\( g(f(x_0)) = g(f(x_1)) \)，即\( g \circ f \)非单射，矛盾，故假设不成立，\( f \)是单射的。

证毕。

\( g \)不一定要是单射的，\( g \)不单射，意味着至少有两个不同的\( y_0, y_1 \in Y, y_0 \neq y_1 \)，\( g(y_0) = g(y_1) \)，但如果\( f \)非满射，则\( g \circ f \)整个映射过程中不一定会涉及\( y_0, y_1 \)，如果不涉及，就不影响\( g \circ f \)为单射函数，当然，如果\( f \)双射，此时\( g \)就也得是单射了。

证明如果\( g \circ f \)满射，则\( g \)满射：

假设\( g \)不满射，即\( \exists z \in Z \)，\( \forall y \in Y \)，有\( g(y) \neq z \)，又\( \forall x \in X \)，\( f(x) \in Y \)，因此\( g(f(x)) \neq z \)，即\( g \circ f \)非满射，矛盾，故假设不成立，\( g \)是满射的。

证毕。

\( f \)不一定要是满射的，举个例子，如果\( f \)的值域比\( g \)的定义域“大”，则不一定会影响\( g \circ f \)为满射函数。

练习3.3.6

题目：

Let \( f: X \to Y \) be a bijective function, and let \( f^{-1}: Y \to X \) be its inverse. Verify the cancellation laws \( f^{−1}(f(x)) = x \) for all \( x \in X \) and \( f(f^{−1}(y)) = y \) for all \( y \in Y \). Conclude that \( f^{−1} \) is also invertible, and has \( f \) as its inverse (thus \( (f^{−1})^{−1} = f \)).

证明\( f^{−1}(f(x)) = x \)：

\( \forall x \in X \)，记\( f(x) = y \)，则根据逆函数的定义，有\( f^{-1}(y) = x = f^{-1}(f(x)) \)。

证毕。

证明\( f(f^{−1}(y)) = y \)：

\( \forall y \in Y \)，记\( f^{-1}(y) = x \)，根据逆函数的定义， \( \exists x \in X \)，\( f(x) = y = f(f^{-1}(y)) \)。

证毕。

证明\( f^{−1})^{−1} = f \)：

首先，\( (f^{−1})^{−1} \)和\( f \)的定义域和值域是一样的。

下面证明输入相同，两个函数的输出就相同。

\( \forall x \in X \)，记\( f(x) = y \)，根据逆函数的定义，有\( f^{-1}(y) = x \)，再根据逆函数的定义，有\( (f^{-1})^{-1}(x) = y \)，至此可以看到，输入相同，输出就相同。

证毕。

练习3.3.7

题目：

Let \( f: X \to Y \) and \( g: Y \to Z \) be functions. Show that if \( f \) and \( g \) are bijective, then so is \( g \circ f \), and we have \( (g \circ f)^{−1} = f^{−1} \circ g^{−1} \).

证明如果\( f \)和\( g \)均双射，则\( g \circ f \)也双射：

\( f \)单射，\( g \)单射，根据练习3.3.5，有\( g \circ f \)单射。

\( f \)满射，\( g \)满射，根据练习3.3.5，有\( g \circ f \)满射。

综上，有\( g \circ f \)双射。

证毕。

证明 \( (g \circ f)^{−1} = f^{−1} \circ g^{−1} \)：

两者的定义域和值域一样，都是\( Z \to X \)。

\( \forall z \in Z \)，记\( (g \circ f)^{−1}(z) = x \)，根据逆函数的定义，有\( g(f(x)) = z \)，进而根据练习3.3.6，两边复合上\( g^{-1} \)，左边 = \( g^{-1}(g(f(x))) = f(x) \)，右边 = \( g^{-1}(z) \)，进一步两边复合上\( f^{-1} \)，左边 = \( f^{-1}(f(x)) = x \)，右边 = \( f^{-1}(g^{-1}(z)) \)，由于左边 = 右边，故\( f^{-1}(g^{-1}(z)) = x \)。

综上，\( \forall z \in Z \)，记\( (g \circ f)^{−1}(z) = x \)，有\( f^{-1}(g^{-1}(z)) = x \)。

证毕。

练习3.3.8

题目：

If \( X \) is a subset of \( Y \), let \( \iota_{X \to Y}: X \to Y \) be the inclusion map from \( X \) to \( Y \), defined by mapping \( x \to x \) for all \( x \in X \), i.e., \( \iota_{X \to Y}(x) := x \) for all \( x \in X \). The map \( \iota_{X \to X} \) is in particular called the identity map on \( X \).

1. Show that if \( X \subseteq Y \subseteq Z \) then \( \iota_{Y \to Z} \circ \iota_{X \to Y} = \iota_{X \to Z} \).
2. Show that if \( f: A \to B \) is any function, then \( f = f \circ \iota_{A \to A} = \iota_{B \to B} \circ f \).
3. Show that, if \( f: A \to B \) is a bijective function, then \( f \circ f^{−1} = \iota_{B \to B} \) and \( f^{-1} \circ f = \iota_{A \to A} \).
4. Show that if \( X \) and \( Y \) are disjoint sets, and \( f: X \to Z \) and \( g: Y \to Z \) are functions, then there is a unique function \( h: X \cup Y \to Z \) such that \( h \circ \iota_{X \to X \cup Y} = f \) and \( h \circ \iota_{Y \to X \cup Y} = g \).

以下是证明。

• 命题1

  这两个函数的定义域和值域都一样。

  \( \forall x \in X \)，\( (\iota_{Y \to Z} \circ \iota_{X \to Y})(x) = \iota_{Y \to Z}(\iota_{X \to Y}(x)) = \iota_{Y \to Z}(x) = x \)， \( \iota_{X \to Z}(x) = x \)。

  证毕。

• 命题2

  首先，这三个函数的定义域和值域都一样。

  还剩下证明输入相同则输出相同。

  证明\( f = f \circ \iota_{A \to A} \)：

  \( \forall a \in A \)，记\( f(a) = b \)，则\( (f \circ \iota_{A \to A})(a) = f(\iota_{A \to A}(a)) = f(a) = b \)。

  证毕。

  证明\( f \circ \iota_{ A \to A } = \iota_{B \to B} \circ f \)：

  \( \forall a \in A \)，记\( (f \circ \iota_{ A \to A })(a) = b \)，则\( (\iota_{B \to B} \circ f)(a) = \iota_{B \to B}(b) = b \)

  证毕。

• 命题3

  证明\( f \circ f^{−1} = \iota_{B \to B} \)：

  这两个函数的定义域和值域都一样。

  \( \forall b \in B \)，\( (f \circ f^{-1})(b) = f(f^{-1}(b)) = b \)， \( \iota_{B \to B}(b) = b \)。

  证毕。

  证明\( f^{-1} \circ f = \iota_{A \to A} \)：

  这两个函数的定义域和值域都一样。

  \( \forall a \in A \)，\( (f^{-1} \circ f)(a) = f^{-1}(f(a)) = a \)， \( \iota_{A \to A}(a) = a \)。

  证毕。

• 命题4

  证明存在性：

  构造函数\( h: X \cup Y \to Z \)：若\( x \in X \)，则\( h(x) = f(x) \)，若\( x \in Y \)，则\( h(x) = g(x) \)。

  因为\( X \)和\( Y \)不相交，故\( \forall x \in X \)，以上映射规则仅会给\( x \)赋一个值，即\( h \)满足作为函数的条件。

  \( h \circ \iota_{X \to X \cup Y} \)和\( f \)的定义域和值域都一样，且，\( \forall x \in X \)，记\( (h \circ \iota_{X \to X \cup Y})(x) = z \)，则\( h(\iota_{X \to X \cup Y}(x)) = h(x) = z \)，根据\( h \)的构造规则，有\( h(x) = f(x) \)，综上，有\( h \circ \iota_{X \to X \cup Y} = f \)。

  \( h \circ \iota_{Y \to X \cup Y} \)和\( g \)的定义域和值域都一样，且，\( \forall y \in Y \)，记\( (h \circ \iota_{Y \to X \cup Y})(y) = z \)，则\( h(\iota_{Y \to X \cup Y}(y)) = h(y) = z \)，根据\( h \)的构造规则，有\( h(y) = g(y) \)，综上，有\( h \circ \iota_{Y \to X \cup Y} = g \)。

  证毕。

  证明唯一性：

  假设存在另一个不同的函数\( h': X \cup Y \to Z \)满足条件。

  由于两个函数不相同，故\( \exists x \in X \cup Y \)，\( h'(x) \neq h(x) \)。

  1. 若\( x \in X \)，则\( h \circ \iota_{X \to X \cup Y} = h(x) = f(x) \)， \( h' \circ \iota_{X \to X \cup Y} = h'(x) = f(x) \)，故\( h'(x) = h(x) \)。
  2. 若\( x \in Y \)，则\( h \circ \iota_{Y \to X \cup Y} = h(x) = g(x) \)， \( h' \circ \iota_{Y \to X \cup Y} = h'(x) = g(x) \)，故\( h'(x) = h(x) \)。

  所有情况下，都有\( h'(x) = h(x) \)，这和两函数不相同矛盾，故假设不成立，函数\( h \)是唯一的。

  证毕。

章节3.4

练习3.4.1

题目：

Let \( f: X \to Y \) be a bijective function, and let \( f^{-1}: Y \to X \) be its inverse. Let \( V \) be any subset of \( Y \). Prove that the forward image of \( V \) under \( f^{−1} \) is the same set as the inverse image of \( V \) under \( f \); thus the fact that both sets are denoted by \( f^{−1}(V) \) will not lead to any inconsistency.

证明：

为了方便说明，证明中将\( V \)在\( f \)下的逆象记作\( f^{-1}(V) \)，将\( V \)在\( f^{-1} \)下的前象记作\( g^{-1}(V) \)。

现在我们的任务就是证明\( f^{-1}(V) = g^{-1}(V) \)。

根据逆象的定义，有\( \forall x \in f^{-1}(V) \)，\( f(x) \in V \)，我们要证明\( x \)也属于\( g^{-1}(V) \)，假设\( x \notin g^{-1}(V) \)，即\( \forall y \in V \)，\( g^{-1}(y) \neq x \)，这和\( f^{-1} \)满射矛盾（注意，虽然我们记作\( g^{-1} \)，但函数实际上还是\( f^{-1} \)），故假设不成立，有\( x \in g^{-1}(V) \)。

反之，根据前象的定义，\( \forall x \in g^{-1}(V) \)， \( \exists y \in V \)，使得\( f^{-1}(y) = x \)，进而根据逆函数的定义，现在我们要证明\( x \)也属于\( f^{-1}(V) \)，这要求\( f(x) \in V \)，将\( f^{-1}(y) = x \)两边同时复合上\( f \)，得到\( f(x) = y \in V \)，满足要求。

证毕。

练习3.4.2

题目：

Let \( f: X \to Y \) be a function from one set \( X \) to another set \( Y \), let \( S \) be a subset of \( X \), and let \( U \) be a subset of \( Y \). What, in general, can one say about \( f^{−1}(f(S)) \) and \( S \)? What about \( f(f^{−1}(U)) \) and \( U \)?

\( f^{−1}(f(S)) \)和\( S \)的关系：

\( S \subseteq f^{−1}(f(S)) \)。

证明：

假设\( \exists x \in S \)，\( x \notin f^{-1}(f(S)) \)，这意味着\( f(x) \notin f(S) \)，然而根据前象的定义，\( f(x) \in f(S) \)，故矛盾，假设不成立，我们有\( S \subseteq f^{-1}(f(S)) \)。

证毕。

\( f(f^{−1}(U)) \)和\( U \)的关系：

\( f(f^{-1}(U)) \subseteq U \)，因为\( U \)中可能有对象找不到能映射到它的输入。

证明：

假设\( \exists y \in f(f^{-1}(U)) \)，\( y \notin U \)，根据前象的定义，有\( \exists x \in f^{-1}(U) \)，\( f(x) = y \)，进一步根据该\( x \)属于\( f^{-1}(U) \)，可以得到\( f(x) \in U \)，又\( f(x) = y \)，即\( y \in U \)，矛盾，故假设不成立，有\( f(f^{-1}(U)) \subseteq U \)。

证毕。

练习3.4.3

题目：

Let \( A, B \) be two subsets of a set \( X \), and let \( f: X \to Y \) be a function. Show that \( f(A \cap B) \subseteq f(A) \cap f(B) \), that \( f(A) \setminus f(B) \subseteq f(A \setminus B) \), \( f(A \cup B) = f (A) \cup f(B) \). For the first two statements, is it true that the \( \subseteq \) relation can be improved to \( = \)?

证明\( f(A \cap B) \subseteq f(A) \cap f(B) \)：

\( \forall y \in f(A \cap B) \)，有\( \exists x \in A \cap B \)，\( f(x) = y \)，即（\( x \in A \)且\( f(x) = y \)）以及（\( x \in B \)且\( f(x) = y \)），也就是\( y \in f(A) \)且\( y \in f(B) \)，即\( y \in f(A) \cap f(B) \)。

证毕。

不能将两者的关系提升到\( = \)，反例如下：

令\( f: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \}, A = \{ 0, 1 \}, B = \{ 1, 2 \} \)， \( f(0) = 100, f(1) = 200, f(2) = 100 \)。

证明\( f(A) \setminus f(B) \subseteq f(A \setminus B) \)：

\( \forall y \in f(A) \setminus f(B) \)，有\( y \in f(A) \)且\( y \notin f(B) \)。因为\( y \in f(A) \)，有\( \exists x \in A \)，\( f(x) = y \)，因为\( y \notin f(B) \)，有\( \forall b \in B \)，\( f(b) \neq y \)，故\( x \notin B \)。综上，\( \exists x \in A \setminus B \)，\( f(x) = y \)，即\( y \in f(A \setminus B) \)。

证毕。

不能将两者的关系提升到\( = \)，反例如下：

令\( f: \{ 0, 1, 2 \} \to \{ 0, 1, 2 \}, A = \{ 0, 1 \}, B = \{ 2 \} \)， \( f(0) = 100, f(1) = 200, f(2) = 200 \)。

证明\( f(A \cup B) = f(A) \cup f(B) \)：

\( \forall y \in f(A \cup B) \)，有\( \exists x \in A \cup B \)，\( f(x) = y \)，即（\( \exists x in A \)，\( f(x) = y \)）或（\( \exists x in B \)，\( f(x) = y \)），即\( y \in f(A) \)或\( y \in f(B) \)，即\( y \in f(A) \cup f(B) \)。

反之，\( \forall y \in f(A) \cup f(B) \)，有\( y \in f(A) \)或\( y \in f(B) \)，即（\( \exists x \in A \)，\( f(x) = y \)）或（\( \exists x \in B \)，\( f(x) = y \)），即\( \exists x \in A \)或\( x \in B \)，使得\( f(x) = y \)，即\( \exists x \in A \cup B \)，\( f(x) = y \)，即\( y \in f(A \cup B) \)。

证毕。

练习3.4.4

题目：

Let \( f : X \to Y \) be a function from one set \( X \) to another set \( Y \), and let \( U, V \) be subsets of \( Y \). Show that \( f^{−1}(U \cup V) = f^{−1}(U) \cup f^{−1}(V) \), that \( f^{−1}(U \cap V) = f^{−1}(U) \cap f^{−1}(V) \), and that \( f^{−1}(U \setminus V) = f^{−1}(U) \setminus f^{−1}(V) \).

证明\( f^{−1}(U \cup V) = f^{−1}(U) \cup f^{−1}(V) \)：

\( \forall x \in f^{−1}(U \cup V) \)，有\( f(x) \in U \cup V \)，即\( f(x) \in U \)或\( f(x) in V \)。

1. 如果\( f(x) \in U \)，则有\( x \in f^{-1}(U) \)，进而有\( x \in f^{-1}(U) \cup f^{-1}(V) \)。
2. 如果\( f(x) \in V \)，则有\( x \in f^{-1}(V) \)，进而有\( x \in f^{-1}(U) \cup f^{-1}(V) \)。

所有情况都有\( x \in f^{-1}(U) \cup f^{-1}(V) \)。

反之，\( \forall x \in f^{-1}(U) \cup f^{-1}(V) \)，则\( x \in f^{-1}(U) \)或\( x \in f^{-1}(V) \)。

1. 如果\( x \in f^{-1}(U) \)，则\( f(x) \in U \)，进而有\( f(x) \in U \cup V \)，即\( x \in f^{-1}(U \cup V) \) 。
2. 如果\( x \in f^{-1}(V) \)，则\( f(x) \in V \)，进而有\( f(x) \in U \cup V \)，即\( x \in f^{-1}(U \cup V) \) 。

所有情况都有\( x \in f^{-1}(U \cup V) \)。

证毕。

证明\( f^{−1}(U \cap V) = f^{−1}(U) \cap f^{−1}(V) \)：

\( \forall x \in f^{-1}(U \cap V) \)，有\( f(x) \in U \cap V \)，即\( f(x) \in U \)且\( f(x) \in V \)，故\( x \in f^{-1}(U) \)且\( x \in f^{-1}(V) \)，即\( x \in f^{-1}(U) \cap f^{-1}(V) \)。

反之，\( \forall x \in f^{-1}(U) \cap f^{-1}(V) \)，有\( x \in f^{-1}(U) \)且\( x \in f^{-1}(V) \)，即\( f(x) \in U \)且\( f(x) \in V \)，即\( f(x) \in U \cap V \)，即\( x \in f^{-1}(U \cap V) \)。

证毕。

证明\( f^{−1}(U \setminus V) = f^{−1}(U) \setminus f^{−1}(V) \)：

\( \forall x \in f^{-1}(U \setminus V) \)，有\( f(x) \in U \setminus V \)，即\( f(x) \in U \)且\( f(x) \notin V \)，因为\( f(x) \in U \)，故\( x \in f^{-1}(U) \)，因为\( f(x) \notin V \)，故\( x \notin f^{-1}(V) \)，综上，有\( x \in f^{-1}(U) \setminus f^{-1}(V) \)。

反之，\( \forall x \in f^{-1}(U) \setminus f^{-1}(V) \)，有\( x \in f^{-1}(U) \)且\( x \notin f^{-1}(V) \)，即\( f(x) \in U \)且\( f(x) \notin V \)，即\( x \in f^{-1}(U \setminus V) \)。

证毕。

练习3.4.5

题目：

Let \( f: X \to Y \) be a function from one set \( X \) to another set \( Y \). Show that \( f(f^{−1}(S)) = S \) for every \( S \subseteq Y \) if and only if \( f \) is surjective. Show that \( f^{−1}(f(S)) = S \) for every \( S \subseteq X \) if and only if \( f \) is injective.

证明如果\( f \)满射，则\( f(f^{−1}(S)) = S \)：

前面已经证明了\( f(f^{−1}(S)) \subseteq S \)，现在只需要再证明\( S \subseteq f(f^{−1}(S)) \)即可（在\( f \)满射的条件下）。

因为\( f \)满射，有\( \forall y \in S \)，\( \exists x \in X \)，\( f(x) = y \)，结合逆象的定义，可得\( x \in f^{-1}(S) \)，现在我们假设\( y \notin f(f^{-1}(S)) \)，则\( \forall x \in f^{-1}(S) \)，\( f(x) \neq y \)，，这和前面推出的\( \exists x \in f^{-1}(S) \)，\( f(x) = y \)矛盾，故假设不成立，有\( y \in f(f^{-1}(S)) \)。

证毕。

证明如果\( f \)单射，则\( f^{−1}(f(S)) = S \)：

前面已经证明了\( S \subseteq f^{-1}(f(S)) \)，现在只需要再证明\( f^{-1}(f(S)) \subseteq S \)即可（在\( f \)单射的条件下）。

\( \forall x \in f^{-1}(f(S)) \)，有\( f(x) \in f(S) \)，假设\( x \notin S \)，即\( x \notin S \)且\( f(x) \in f(S) \)，根据\( f(S) \)的定义，有\( \forall y \in f(S) \)，\( \exists x_0 \in S \)，\( f(x_0) = y \)，根据这个性质，我们找\( y = f(x) \in f(S) \)对应的\( x_0 \in S \)，记为\( x_1 \)，有\( f(x_1) = f(x) \) 由于\( x \notin S \)，故\( x_1 \neq x_0 \)，即有两个不同的输入值的输出值相同，这和\( f \)单射矛盾，故假设不成立，有\( x \in S \)。

证毕。

练习3.4.6

题目：

Prove Lemma 3.4.9. (Hint: start with the set \( \{ 0, 1 \}^{X} \) and apply the replacement axiom, replacing each function \( f \) with the object \( f^{−1}(\{ 1 \}) \).) See also Exercise 3.5.11.

Lemma 3.4.9的内容：

Let X be a set. Then the set \( \{Y: Y \subseteq X\} \) is a set.

证明：

根据幂集公理，我们能得到集合\( \{ 0, 1 \}^X \)，即所有\( X \to \{ 0, 1 \} \)的函数的集合（注：这里如果\( X \)的某个元素映射到\( 0 \)，代表剔除，如果映射到\( 1 \)，则代表保留），通过替换公理，我们将\( \{ 0, 1 \}^X \)中的所有函数\( f \)都替换成\( f^{-1}(f(\{ 1 \})) \)，从而得到所有要保留的元素，这里最终得到的集合就是所有\( X \)子集组成的集合了，我们下面记为集合\( A \)。

我们现在证明两点：

1. \( X \)的所有子集都在\( A \)中。
2. \( A \)中的所有元素都是\( X \)的子集（没有多出来的奇怪元素）。

首先证明第一点：

\( \forall Y \subseteq X \)，有\( \forall x \in Y \)，\( x \in X \)，我们构造函数\( f: X \to \{ 0, 1 \} \)，映射规则为：如果\( x \in Y \)，则\( f(x) = 1 \)，否则\( f(x) = 0 \)，明显的，函数\( f \in \{ 0, 1 \}^X \)，再根据我们集合\( A \)的构造规则，可以得知元素\( f^{-1}(f(\{ 1 \})) = Y \)有在\( A \)中， 综上，所有子集\( Y \)都在\( A \)中。

再证明第二点：

假设\( \exists Y \in A \)，\( Y \nsubseteq X \)，这意味着\( \exists x \in Y \)，\( x \notin X \)，根据\( A \)的构造规则，可以得知\( \exists f \in \{ 0, 1 \}^X \)，\( x \in f^{-1}(f(\{ 1 \})) \)，然而\( f^{-1}(f(\{ 1 \})) \subseteq X \)，即\( x \in X \)，矛盾，故假设不成立，有\( \forall Y \in A \)，\( Y \subseteq X \)。

证毕。

练习3.4.7

题目：

Let \( X, Y \) be sets. Define a partial function from \( X \) to \( Y \) to be any function \( f: X' \to Y' \) whose domain \( X' \) is a subset of \( X \), and whose range \( Y' \) is a subset of \( Y \). Show that the collection of all partial functions from \( X \) to \( Y \) is itself a set. (Hint: use Exercise 3.4.6, the power set axiom, the replacement axiom, and the union axiom.)

证明：

根据幂集公理，我们能得到\( X \)所有子集组成的集合，记作\( 2^X \)，同理，可以得到\( Y \)所有子集组成的集合，记作\( 2^Y \)。

针对\( 2^X \)使用替换公理和幂集公理，将每个\( X' \in 2^X \)都替换成\( (2^Y)^{\{X'\}} \)，即替换成所有定义域为单例集\( \{ X' \} \)，值域为\( 2^Y \)的函数\( f: \{ X' \} \to 2^Y \) （注意，定义域是单例集\( \{ X' \} \)，不是\( X' \)），即我们得到一个类似这样的集合：\( \{ f_0: \{ X_0 \} \to 2^Y, f_1: \{ X_1 \} \to 2^Y, f_2: \{ X_2 \} \to 2^Y, \dots \} \)，这里\( X_0, X_1, X_2, \dots \)分别是\( X \)的子集，我们记这个集合为\( A \)。

这里说明下，\( A \)中每个函数\( f: \{ X' \} \to 2^Y \)，有\( f(\{ X' \}) \)，即\( \{ X' \} \)的前象为另外一个单例集\( \{ Y' \} \) （因为定义域只有一个元素，故只有一个输出），这个单例集中的\( Y' \)就是分配给该\( X' \)的一个Y的子集。

针对\( A \)使用替换公理和幂集公理，将每个函数\( f: \{ X' \} \to 2^Y \)进行替换，具体的替换方式为：我们知道，每个函数\( f(\{ X' \}) \)为另外一个单例集\( \{ Y' \} \)，这里我们将每个函数\( f \)都替换成\( X^{'^{Y'}} \)，即所有定义域为\( X' \)，值域为\( Y' \)的函数组成的集合，至此，我们得到一个类似这样的集合： \( \{ \{ f_{000}: X_0 \to Y_0, f_{001}: X_0 \to Y_0, \dots , f_{010}: X_0 \to Y_1, f_{011}: X_0 \to Y_1, \dots , f_{020}: X_0 \to Y_2, f_{021}: X_0 \to Y_2, \dots , \dots \}, \{ f_{100}: X_1 \to Y_0, f_{101}: X_1 \to Y_0, \dots , f_{110}: X_1 \to Y_1, f_{111}: X_1 \to Y_1, \dots , f_{120}: X_1 \to Y_2, f_{121}: X_1 \to Y_2, \dots , \dots \}, \dots \} \)，这里多个\( X_k \)和\( Y_k \)分别是\( X \)和\( Y \)的子集（注意，这里以\( f_{000} \)为例，有多个\( f_{000}: X_0 \to Y_0, f_{001}: X_0 \to Y_0, \dots , \)这样定义域和值域都相同的函数，但是它们的映射关系不同），我们记这个得到的集合为\( B \)。

最后，我们对\( B \)使用并集公理，得到的便是所有偏函数的集合了，记为\( C \)。

下面，我们证明\( C \)就是我们要的集合，这需要证明两点：

1. 所有\( X \)和\( Y \)的偏函数都属于\( C \)。
2. \( C \)中所有元素都是\( X \)和\( Y \)的偏函数（没有多余的奇怪元素）。

先证明第一点：

假设存在\( X \)和\( Y \)的偏函数\( f: X' \to Y' \)，\( f \notin C \)，根据\( A \)的构造过程， 我们知道\( \exists (f_0: \{ X' \} \to 2^Y) \in A \)，再根据\( B \)的构造过程，我们知道\( f_0 \)会被替换公理替换成类似这样的集合： \( \{ f_{000}: X' \to Y_0, f_{001}: X' \to Y_0, \dots , f_{010}: X' \to Y_1, f_{011}: X' \to Y_1, \dots , f_{020}: X' \to Y_2, f_{021}: X' \to Y_2, \dots , \dots \} \)，我们记该集合为\( D \)，这里由于\( Y' \in 2^Y \)，故\( f \in D \)，最后根据\( B \)到\( C \)的构造过程（幂集公理），得\( f \in C \)。

再证明第二点：

假设\( \exists f: A \to B \)不是\( X \)和\( Y \)的偏函数，即\( A \nsubseteq X \)或\( B \nsubseteq Y \)，根据C的构造过程，我们知道\( f \)是从\( C \)中的某个类似这样的集合中来的： \( \{ f_{000}: A \to Y_0, f_{001}: A \to Y_0, \dots , f_{010}: A \to Y_1, f_{011}: A \to Y_1, \dots , f_{020}: A \to Y_2, f_{021}: A \to Y_2, \dots , \dots \} \)，我们记该集合为\( E \)，由\( E \)的构造过程知，\( E \)中每个函数的值域均是\( Y \)的子集，\( f \)既然是它们的一员，那\( B \)也不例外，\( B \subseteq Y \)，同理，\( A \)也必须是\( X \)的子集，综上，假设不成立，有\( C \)中所有元素都是\( X \)和\( Y \)的偏函数。

证毕。

练习3.4.8

题目：

Show that Axiom 3.4 can be deduced from Axiom 3.1, Axiom 3.3 and Axiom 3.11.

证明：

令\( A, B \) 为两个集合。

根据公理3.1和公理3.3，可以得到双例集\( \{ A, B \} \)，对该集合使用公理3.11，得集合C：\( \forall x \in C \)，有\( x \in A \)或\( x \in B \)，即公理3.4成立。

证毕。

练习3.4.9

题目：

Show that if \( \beta \) and \( \beta' \) are two elements of a set \( I \), and to each \( \alpha \in I \) we assign a set \( A_{\alpha} \), then \( \{ x \in A_{\beta} : \forall \alpha \in I, x \in A_{\alpha} \} = \{ x \in A_{\beta'} : \forall \alpha \in I, x \in A_{\alpha} \} \)， and so the definition of \( \bigcap_{\alpha \in I} A_{\alpha} \) defined in (3.3) does not depend on \( \beta \). Also explain why (3.4) is true.

证明：

记\( \{ x \in A_{\beta} : \forall \alpha \in I, x \in A_{\alpha} \} \)为\( A \)，记\( \{ x \in A_{\beta'} : \forall \alpha \in I, x \in A_{\alpha} \} \)为\( B \)。

假设\( A \neq B \)，即\( \exists x \in A \)，\( x \notin B \)，或\( \exists x \in B \)，\( x \notin A \)。

1. 如果\( \exists x \in A \)，\( x \notin B \)，因为\( x \in A \)，故\( \forall \alpha \in I, x \in A_{\alpha} \)，又\( \beta' \in I \)，故\( x \in A_{\beta'} \)，综上有\( x \in B \)，即该种情况是不可能的。
2. 如果\( \exists x \in B \)，\( x \notin A \)，因为\( x \in B \)，故\( \forall \alpha \in I, x \in A_{\alpha} \)，又\( \beta \in I \)，故\( x \in A_{\beta} \)，综上有\( x \in A \)，即该种情况是不可能的。

所有不相等的情况都不可能发生，故\( A = B \)。

证毕。

(3.4)的内容：

\( \forall y \in \bigcap_{\alpha \in I} A_{\alpha} \Leftrightarrow (\forall \alpha \in I, y \in A_{\alpha}) \)

解释下为什么(3.4)是对的：

\( \bigcap_{\alpha \in I} A_{\alpha} \)中所有元素都是通过“首先任选一个元素\( \beta \in I \)，再用规范公理在\( A_{\beta} \)元素的基础上，过滤得只剩下满足\( \forall \alpha \in I, y \in A_{\alpha} \)的元素”这样的方式得到的，故自然两者是等价的（说实话，我感觉就是一个意思，除了前者多了一个选择一个元素\( \beta \)这一过程）。

练习3.4.10

题目：

Suppose that \( I \) and \( J \) are two sets, and for all \( \alpha \in I \cup J \) let \( A_{\alpha} \) be a set. Show that \( (\bigcup_{\alpha \in I} A_{\alpha}) \cup (\bigcup_{\alpha \in J} A_{\alpha}) = (\bigcup_{\alpha \in I \cup J} A_{\alpha}) \). If \( I \) and \( J \) are non-empty, show that \( (\bigcap_{\alpha \in I} A_{\alpha}) \cap (\bigcap_{\alpha \in J} A_{\alpha}) = (\bigcap_{\alpha \in I \cup J} A_{\alpha}) \).

证明\( (\bigcup_{\alpha \in I} A_{\alpha}) \cup (\bigcup_{\alpha \in J} A_{\alpha}) = (\bigcup_{\alpha \in I \cup J} A_{\alpha}) \)：

记左边为\( A \)，右边为\( B \)。

\( \forall x \in A \)，有\( x \in \bigcup_{\alpha \in I} A_{\alpha} \)或\( x \in \bigcup_{\alpha \in J} A_{\alpha} \)。

1. 如果\( x \in \bigcup_{\alpha \in I} A_{\alpha} \)，则\( \exists \beta \in I, x \in A_{\beta} \)，因为\( \beta \in I \)，故\( \beta \in I \cup J \)，综上，有\( x \in B \)。
2. 如果\( x \in \bigcup_{\alpha \in J} A_{\alpha} \)，则\( \exists \beta \in J, x \in A_{\beta} \)，因为\( \beta \in J \)，故\( \beta \in I \cup J \)，综上，有\( x \in B \)。

反之，\( \forall x \in B \)，有\( \exists \beta \in I \cup J, x \in A_{\beta} \)，即（\( \exists \beta \in I, x \in A_{\beta} \)）或（\( \exists \beta \in J, x \in A_{\beta} \)）。

1. 如果\( \exists \beta \in I, x \in A_{\beta} \)，则有\( x \in \bigcup_{\alpha \in I} A_{\alpha} \)，进而有\( x \in A \)。
2. 如果\( \exists \beta \in J, x \in A_{\beta} \)，则有\( x \in \bigcup_{\alpha \in J} A_{\alpha} \)，进而有\( x \in A \)。

证毕。

证明\( (\bigcap_{\alpha \in I} A_{\alpha}) \cap (\bigcap_{\alpha \in J} A_{\alpha}) = (\bigcap_{\alpha \in I \cup J} A_{\alpha}) \)：

记左边为\( A \)，右边为\( B \)。

\( \forall x \in A \)，有\( x \in \bigcap_{\alpha \in I} A_{\alpha} \)且\( x \in \bigcap_{\alpha \in J} A_{\alpha} \)，因为\( x \in \bigcap_{\alpha \in I} A_{\alpha} \)，故\( \forall \alpha \in I, x \in A_{\alpha} \)，因为\( x \in \bigcap_{\alpha \in J} A_{\alpha} \)，故\( \forall \alpha \in J, x \in A_{\alpha} \)，综上，有\( \forall \alpha \in I \cup J, x \in A_{\alpha} \)，即\( x \in B \)。

反之，\( \forall x \in B \)，有\( \forall \alpha \in I \cup J, x \in A_{\alpha} \)，即\( \forall \alpha \in I, x \in A_{\alpha} \)且\( \forall \alpha \in J, x \in A_{\alpha} \), 即\( x \in \bigcap_{\alpha \in I} A_{\alpha} \)且\( x \in \bigcap_{\alpha \in J} A_{\alpha} \)，即\( x \in A \)。

证毕。

练习3.4.11

题目：

Let \( X \) be a set, let \( I \) be a non-empty set, and for all \( \alpha \in I \) let \( A_{\alpha} \) be a subset of \( X \). Show that \( X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} = \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha}) \) and \( X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} = \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha}) \), This should be compared with de Morgan’s laws in Proposition 3.1.28 (although one cannot derive the above identities directly from de Morgan’s laws, as I could be infinite).

证明\( X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} = \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)：

\( \forall x \in X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} \)，有\( x \in X \)且（\( \forall \alpha \in I, x \notin A_{\alpha} \)），假设\( x \notin \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)，则\( \exists \beta \in I, x \notin X \setminus A_{\alpha} \)，即\( \exists \beta \in I \)，\( x \notin X \)或\( x \in A_{\beta} \)，这两种情况都不可能，故假设不成立，有\( x \in \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)。

反之，\( \forall x \in \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)，有\( \forall \alpha \in I, x \in X \setminus A_{\alpha} \)，即\( \forall \alpha \in I \)，\( x \in X \)且\( x \notin A_{\alpha} \)，假设\( x \notin X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} \)，则\( x \notin X \)或\( x \in \bigcup\limits_{\alpha \in I} A_{\alpha} \)，前者不可能，后者意味着\( \exists \beta \in I, x \in A_{\beta} \)，这也不可能，故假设不成立，有\( x \in X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} \)。

证毕。

证明\( X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} = \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)：

\( \forall x \in X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} \)，有\( x \in X \)且\( \exists \beta \in I, x \notin A_{\beta} \)，假设\( x \notin \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)，则\( \forall \alpha \in I, x \notin X \setminus A_{\alpha} \)，即\( \forall \alpha \in I \)，\( x \notin X \)或\( x \in A_{\alpha} \)， \( x \notin X \)是不可能的，故只可能\( x \in A_{\alpha} \)，但我们又知道\( \exists \beta \in I, x \notin A_{\beta} \)，故不是所有\( \alpha \in I \)都有\( x \in A_{\alpha} \)，即假设不成立，有\( x \in \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)。

反之，\( \forall x \in \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha}) \)，有\( \exists \beta \in I, x \in X \setminus A_{\beta} \)，即\( x \in X \)且\( x \notin A_{\beta} \)，假设\( x \notin X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} \)，则\( x \notin X \)或\( x \in \bigcap\limits_{\alpha \in I} A_{\alpha} \)， \( x \notin X \)不可能，故只有\( x \in \bigcap\limits_{\alpha \in I} A_{\alpha} \)，这意味着\( \forall \alpha \in I, x \in A_{\alpha} \)，但我们知道， \( \exists \beta \in I, x \notin A_{\beta} \)，故这种情况也不可能，即假设不成立，有\( x \in X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} \)。

证毕。

章节3.5

练习3.5.1

题目：

Suppose we define the ordered pair \( (x, y) \) for any objects \( x \) and \( y \) by the formula \( (x, y) = \{ \{ x \}, \{x, y\} \} \) (thus using several applications of Axiom 3.3). Thus for instance \( (1, 2) \) is the set \( \{ \{ 1 \}, \{ 1, 2 \} \} \), \( (2, 1) \) is the set \( \{ \{ 2 \}, \{ 2, 1 \} \} \), and \( (1, 1) \) is the set \( \{ \{ 1 \} \} \). Show that such a definition indeed obeys the property (3.5), and also whenever \( X \) and \( Y \) are sets, the Cartesian product \( X \times Y \) is also a set. Thus this definition can be validly used as a definition of an ordered pair. For an additional challenge, show that the alternate definition \( (x, y) = \{ x, \{ x, y \} \} \) also verifies (3.5) and is thus also an acceptable definition of ordered pair. (For this latter task one needs the axiom of regularity, and in particular Exercise 3.2.2.)

属性(3.5)的内容：

令\( (x, y), (x', y') \)为两个有序对，则\( (x, y) = (x', y') \Leftrightarrow x = x' 且 y = y' \)。

证明定义\( (x, y) = \{ \{ x \}, \{x, y\} \} \)满足属性(3.5)：

\( (x, y) \)对应的集合为\( \{ \{ x \}, \{ x, y \} \} \)， \( (x', y') \)对应的集合为\( \{ \{ x' \}, \{ x', y' \} \} \)。

必要性：

\( (x, y) = (x', y') \)，即\( \{ \{ x \}, \{ x, y \} \} = \{ \{ x' \}, \{ x', y' \} \} \)，记左边的集合为\( A \)，右边的集合为\( B \)，用反证法来证明，假设\( x \neq x' \)或\( y \neq y' \)，这两种情况分开来讨论：

1. 如果\( x \neq x' \)，因为\( A = B \)，故\( \{ x \} = \{ x', y' \} \)，等号左边只有一个元素，故\( x' = y' \)，此时\( B \)可以简化成\( \{ \{ x' \} \} \)， \( A \)也只能有一个元素，故\( x = y \)，\( A \)简化成\( \{ \{ x \} \} \)，此时得到\( x = x' \)，矛盾，故这种情况不可能。
2. 如果\( y \neq y' \)，因为\( A = B \)，故\( \{ x, y \} \)需要等于\( B \)中两个元素的其中一个，这两种情况分开来讨论：
   1. 如果\( \{ x, y \} = \{ x', y' \} \)，则由于\( y \neq y' \)，故有\( x = y', y = x' \)，利用这个信息可以得到 \( A = \{ \{ y' \}, \{ x', y' \}, \}, B = \{ \{ y \}, \{ x', y' \} \} \)，因为\( A = B \)，故\( \{ y' \} \)，需要等于\( B \)中的其中一个元素，又\( y \neq y' \)，故\( \{ y' \} = \{ x', y' \} \)，得\( \{ x' = y' \} \)，此时\( A \)可以简化成\( \{ \{ y' \} \} \)，\( B \)可以简化成\( \{ \{ y \}, \{ y' \} \} \)，因为\( A = B \)，故B只能有一个元素，得\( y = y' \)，矛盾，故这种情况不可能。
   2. 如果\( \{ x, y \} = \{ x' \} \)，此时\( x = y = x' \)， \( A \)可以简化成\( \{ \{ y \} \} \)，由于\( A = B \)，故\( B \)也只能有一个元素，即\( x' = y' \)，此时\( B \)可以简化成\( \{ \{ y' \} \} \)，又\( A = B \)，故\( y = y' \)，矛盾，故这种情况也不可能。

综上，如果\( (x, y) = (x', y') \)，则\( x = x' \)且\( y = y' \)。

充分性：

\( x = x' 且 y = y' \)，则直接有\( \{ \{ x \}, \{ x, y \} \} = \{ \{ x' \}, \{ x', y' \} \} \)。

证毕。

证明定义\( (x, y) = \{ x, \{x, y\} \} \)满足属性(3.5)：

\( (x, y) \)对应的集合为\( \{ x, \{ x, y \} \} \)， \( (x', y') \)对应的集合为\( \{ x', \{ x', y' \} \} \)。

必要性：

\( (x, y) = (x', y') \)，即\( \{ x, \{ x, y \} \} = \{ x', \{ x', y' \} \} \)，记左边的集合为\( A \)，右边的集合为\( B \)。

由于\( A = B \)，故\( x \)需要等于\( B \)中的某个元素，即\( x = x' \)或\( x = \{ x', y' \} \)，同理，\( \{ x, y \} \)也需要等于\( B \)中的某个元素，即\( \{ x, y \} = x' \)或\( \{ x, y \} = \{ x', y' \} \)，假设\( x = \{ x', y' \} \)，

1. 如果\( \{ x, y \} = x' \)，则\( x \in x' \)，再由\( x = \{ x', y' \} \)，可得\( x' \in x \)，这违反了正则公理，故这种情况是不可能的。
2. 如果\( \{ x, y \} = \{ x', y' \} \)，结合\( x = \{ x', y' \} \)，可得\( \{ x', y' \} \in (\{ x, y \} = \{ x', y' \}) \)，违反了正则公理，故这种情况也是不可能的。

综上，\( x \neq \{ x', y' \} \)，只可能\( x = x' \)。

再次考虑\( \{ x, y \} \)也需要等于\( B \)中的某个元素，即\( \{ x, y \} = x' \)或\( \{ x, y \} = \{ x', y' \} \) （注：这次我们有了额外的信息，即\( x = x' \)），如果\( \{ x, y \} = x' \)，则由\( x = x' \)，可得\( x' \in (\{ x, y \} = x') \)，这违反了正则公理，故\( \{ x, y \} \neq x' \)，只可能\( \{ x, y \} = \{ x', y' \} \)，结合\( x = x' \)，可得\( \{ x, y \} = \{ x, y' \} \)，故\( \{ y \} = \{ x, y \} \setminus \{ x \} = \{ x, y' \} \setminus \{ x \} = \{ y' \} \)，即\( y = y' \)。

综上，我们有\( A = B \)，则\( x = x' \)且\( y = y' \)。

充分性：

\( x = x' 且 y = y' \)，则直接有\( \{ x, \{ x, y \} \} = \{ x', \{ x', y' \} \} \)。

证毕。

证明如果\( X, Y \)是集合，则笛卡尔积\( X \times Y \)也是一个集合：

利用练习3.4.7，我们得到由所有\( X \)和\( Y \)的偏函数组成的集合，记为\( A \)，对\( A \)使用规范公理，得到集合\( \{ f: \{ x \} \to \{ y \} : f \in A, x \in X, y \in Y \} \)，即把\( A \)过滤得仅剩下定义域和值域均为单例集的偏函数，记该集合为\( B \)，对\( B \)使用替换公理，每个偏函数\( f: \{ x \} \to \{ y \} \)都替换成\( (x, y) \)，记该集合为\( C \)，\( C \)就是我们要的\( X \times Y \)。

下面证明\( \forall x \in X, y \in Y \)，\( (x, y) \in C \) （注：根据\( C \)的构造规则，我们已经知道\( C \)中每个元素都是\( X \)和\( Y \)集合的有序对，这点不需要额外证明）：

\( \forall x \in X, y \in Y \)，构造函数\( f: \{ x \} \to \{ y \}, f(x) = y \)，根据\( B \)的构造规则，有\( f \in B \)，再根据\( C \)的构造规则，有\( (x, y) \in C \)。

证毕。

练习3.5.2

题目：

Suppose we define an ordered n-tuple to be a surjective function \( x: \{ i \in \mathbf{N} : 1 \leq i \leq n \} \to X \) whose range is some arbitrary set \( X \) (so different ordered n-tuples are allowed to have different ranges); we then write \( x_i \) for \( x(i) \), and also write \( x \) as \( (x_i)_{1 \leq i \leq n} \) . Using this definition, verify that we have \( (x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n} \) if and only if \( x_i = y_i \) for all \( 1 \leq i \leq n \). Also, show that if \( (X_i)_{1 \leq i \leq n} \) are an ordered n-tuple of sets, then the Cartesian product, as defined in Definition 3.5.7, is indeed a set. (Hint: use Exercise 3.4.7 and the axiom of specification.)

定义3.5.7的内容：

(Ordered n-tuple and n-fold Cartesian product). Let \( n \) be a natural number. An ordered n-tuple \( (x_i)_{1 \leq i \leq n} \) (also denoted \( (x_1, \dots , x_n )) \) is a collection of objects \( x_i \), one for every natural number i between \( 1 \) and \( n \); we refer to \( x_i \) as the \( i^{th} \) component of the ordered n-tuple. Two ordered n-tuples \( (x_i)_{1 \leq i \leq n} \) and \( (y_i)_{1 \leq i \leq n} \) are said to be equal iff \( x_i = y_i \) for all \( 1 \leq i \leq n \). If \( (X_i )_{1 \leq i \leq n} \) is an ordered n-tuple of sets, we define their Cartesian product \( \prod\limits_{1 \leq i \leq n} X_i \) (also denoted \( \prod_{i=1}^{n} X_i \) or \( X_1 \times \dots \times X_n \)) by \( \prod\limits_{1 \leq i \leq n} X_i := \{ (x_i)_{1 \leq i \leq n} : \forall 1 \leq i \leq n, x_i \in X_i \} \).

证明该n元有序对的定义具有题目所描述的属性：

必要性：

\( (x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n} \)，即函数\( x = \)函数\( y \)，两函数相等，有定义域内每个输入值的输出值相等，即\( \forall 1 \leq i \leq n, x(i) = y(i) \)，即\( \forall 1 \leq i \leq n, x_i = y_i \)。

充分性：

\( \forall 1 \leq i \leq n, x_i = y_i \)，即\( \forall 1 \leq i \leq n, x(i) = y(i) \)，函数\( x \)和函数\( y \)的定义域都是\( \{ i : 1 \leq i \leq n \} \)，可得定义域内每个输入值的输出值相等，剩下值域待验证了，假设两函数的值域不相等，我们记\( x \)的值域为\( A \)， \( y \)的值域为\( B \)，则\( \exists a \in A \)，\( a \notin B \)，或\( \exists b \in B \)，\( b \notin A \)，

1. 如果\( \exists a \in A \)，\( a \notin B \)，则根据\( a \in A \)，有 \( \exists i_0 \in \{ i : 1 \leq i \leq n \} \)，\( x(i_0) = y(i_0) = a \)，而\( y(i_0) \in B \)，即\( a \in B \)，矛盾，故该情况是不可能的。
2. 如果\( \exists b \in B \)，\( b \notin A \)，则根据\( b \in B \)，有 \( \exists i_1 \in \{ i : 1 \leq i \leq n \} \)，\( y(i_1) = x(i_1) = b \)，而\( x(i_1) \in A \)，即\( b \in A \)，矛盾，故该情况是不可能的。

综上，定义域、值域、映射关系都相等，故两函数相等。

证毕。

证明定义3.5.7的n重笛卡尔积是一个存在的集合：

令\( U = \bigcup\limits_{1 \leq i \leq n} X_i \)，令\( F \)为所有定义域为\( \{ i : 1 \leq i \leq n \} ) \)的子集，值域为\( U \)的子集的偏函数组成的集合（通过练习3.4.7得到），记为\( B \)，对\( B \)使用规范公理，得到： \( \{ x | (x: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} x(i)) \in B, \forall 1 \leq i \leq n, x(i) \in X_i \} \)，即得到所有定义域为\( \{ i: 1 \leq i \leq n \} \)且\( x(i) \in X_i \)的满射函数，记该集合为C，根据n元有序对的定义，\( C \)的每个元素都是一个n元有序对。

根据C的构造过程，\( \forall (x_i)_{1 \leq i \leq n} \in C \)，有\( \forall 1 \leq i \leq n, x_i \in X_i \)，反之，任意满足\( \forall 1 \leq i \leq n, x_i \in X_i \)的\( (x_i)_{1 \leq i \leq n} \)，有：\( (x_i)_{1 \leq i \leq n} \)是满射函数，故它的值域为\( \bigcup\limits_{1 \leq i \leq n} x(i) \subseteq U \)，故\( (x_i)_{1 \leq i \leq n} \in B \)，进而根据C的构造规则，有\( (x_i)_{1 \leq i \leq n} \in C \)。

证毕。

练习3.5.3

题目：

Show that the definitions of equality for ordered pair and ordered n-tuple obey the reflexivity, symmetry, and transitivity axioms.

证明该n元有序对的定义具有自反性：

\( \forall (x_i)_{1 \leq i \leq n} = (x: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} x(i)) \)，因集合的相等满足自反性，即\( x = x \)，故该n元有序对的定义具有自反性。

证毕。

证明该n元有序对的定义具有对称性：

\( \forall (x_i)_{1 \leq i \leq n} = (x: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} x(i)), (y_i)_{1 \leq i \leq n} = (y: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} y(i)) \)，如果\( x = y \)，则因为集合的相等具有对称性，故\( y = x \)，得该n元有序对的定义具有对称性。

证毕。

证明该n元有序对的定义具有传递性：

\( \forall (x_i)_{1 \leq i \leq n} = (x: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} x(i)), (y_i)_{1 \leq i \leq n} = (y: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} y(i)), (z_i)_{1 \leq i \leq n} = (z: \{ i: 1 \leq i \leq n \} \to \bigcup\limits_{1 \leq i \leq n} z(i)) \)，如果\( x = y, y = z \)，则因为集合的相等具有传递性，故\( x = z \)，得该n元有序对的定义具有传递性。

证毕。

练习3.5.4

题目：

Let \( A, B, C \) be sets. Show that \( A \times (B \cup C) = (A \times B) \cup (A \times C) \), that \( A \times (B \cap C) = (A \times B) \cap (A \times C) \), and that \( A \times (B \setminus C) = (A \times B) \setminus (A \times C) \). (One can of course prove similar identities in which the roles of the left and right factors of the Cartesian product are reversed.)

证明\( A \times (B \cup C) = (A \times B) \cup (A \times C) \)：

\( \forall (x, y) \in A \times (B \cup C) \)，有\( x \in A, y \in B \cup C \)，得\( y \in B \)或\( y \in C \)，

1. 如果\( y \in B \)，则\( (x, y) \in A \times B \)，进而有\( (x, y) \in (A \times B) \cup (A \times C) \)。
2. 如果\( y \in C \)，则\( (x, y) \in A \times C \)，进而有\( (x, y) \in (A \times B) \cup (A \times C) \)。

反之，\( \forall (x, y) \in (A \times B) \cup (A \times C) \)，有\( (x, y) \in A \times B \)或\( (x, y) \in A \times C \)，

1. 如果\( (x, y) \in A \times B \)，则\( x \in A, y \in B \)，故有\( x \in A, y \in B \cup C \)，综合得\( (x, y) \in A \times (B \cup C) \)。
2. 如果\( (x, y) \in A \times C \)，则\( x \in A, y \in C \)，故有\( x \in A, y \in B \cup C \)，综合得\( (x, y) \in A \times (B \cup C) \)。

证毕。

证明\( A \times (B \cap C) = (A \times B) \cap (A \times C) \)：

\( \forall (x, y) \in A \times (B \cap C) \)，有\( x \in A, y \in B \cap C \) ，即\( x \in A \)，\( y \in B \)且\( y \in C \)，因\( x \in A \)，\( y \in B \)，得\( (x, y) \in A \times B \)，因\( x \in A \)，\( y \in C \)，得\( (x, y) \in A \times C \)，综合得，\( (x, y) \in A \times B \)且\( (x, y) \in A \times C \)，即 \( (x, y) \in (A \times B) \cap (A \times C) \)。

反之，\( \forall (x, y) \in (A \times B) \cap (A \times C) \)，有\( (x, y) \in A \times B \)且\( (x, y) \in A \times C \)，即\( x \in A, y \in B \)且\( x \in A, y \in C \)，综合得\( x \in A, y \in B \cap C \)，即\( (x, y) \in A \times (B \cap C) \)。

证毕。

证明\( A \times (B \setminus C) = (A \times B) \setminus (A \times C) \)：

\( \forall (x, y) \in A \times (B \setminus C) \)，有\( x \in A, y \in B \setminus C \)，即\( x \in A, y \in B \)且\( y \notin C \)，因\( x \in A, y \in B \)，故有\( (x, y) \in A \times B \)，因\( y \notin C \)，故有\( (x, y) \notin A \times C \)，综合得，\( (x, y) \in (A \times B) \setminus (A \times C) \)。

反之，\( \forall (x, y) \in (A \times B) \setminus (A \times C) \)，有\( (x, y) \in A \times B \)且\( (x, y) \notin A \times C \)，有\( x \in A, y \in B \)且（\( x \notin A \)或\( y \notin C \)），排除\( x \notin A \)的可能性，得\( x \in A, y \in B, y \notin C \)，即\( x \in A, y \in B \setminus C \)，即\( (x, y) \in A \times (B \setminus C) \)。

证毕。

练习3.5.5

题目：

Let \( A, B, C, D \) be sets. Show that \( (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) \). Is it true that \( (A \times B) \cup (C \times D) = (A \cup C) \times (B \cup D) \)? Is it true that \( (A \times B) \setminus (C \times D) = (A \setminus C) \times (B \setminus D) \)?

证明\( (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) \)：

\( \forall (x, y) \in (A \times B) \cap (C \times D) \)，有\( (x, y) \in A \times B \)且\( (x, y) \in C \times D \)，得\( x \in A, y \in B, x \in C, y \in D \)，即\( x \in A \cap C, y \in B \cap D \)，即\( (x, y) \in (A \cap C) \times (B \cap D) \)。

反之，\( \forall (x, y) \in (A \cap C) \times (B \cap D) \)，有\( x \in A \cap C, y \in B \cap D \)，即\( x \in A, x \in C, y \in B, y \in D \)，由\( x \in A, y \in B \)，得\( (x, y) \in A \times B \)，由\( x \in C, y \in D \)，得\( (x, y) \in C \times D \)，综合得\( (x, y) \in (A \times B) \cap (C \times D) \)。

证毕。

\( (A \times B) \cup (C \times D) \neq (A \cup C) \times (B \cup D) \)，反例：\( A = \{ 1, 2 \}, B = \{ 3, 4 \}, C = \{ 4, 5 \}, D = \{ 5, 6 \} \)。

\( (A \times B) \setminus (C \times D) \neq (A \setminus C) \times (B \setminus D) \)，反例：\( A = \{ 1, 2 \}, B = \{ 3, 4 \}, C = \{ 1, 2 \}, D = \{ 5, 6 \} \)。

练习3.5.6

题目：

Let \( A, B, C, D \) be non-empty sets. Show that \( A \times B \subseteq C \times D \) if and only if \( A \subseteq C \) and \( B \subseteq D \), and that \( A \times B = C \times D \) if and only if \( A = C \) and \( B = D \). What happens if the hypotheses that the \( A, B, C, D \) are all non-empty are removed?

证明：\( (A \times B \subseteq C \times D) \equiv (A \subseteq C 且 B \subseteq D) \)：

必要性：

\( A \times B \subseteq C \times D \)，即\( \forall (x, y) \in A \times B, (x, y) \in C \times D \)，即\( x \in A, x \in C, y \in B, y \in D \)，

1. 假设\( A \nsubseteq C \)，则\( \exists x_0 \in A, x_0 \notin C \)，但因\( x_0 \in A \)，故\( \exists (x_0, y) \in A \times B \)，根据前面得到的，有\( x_0 \in A, x_0 \in C \)，矛盾，故该种情况是不可能的。
2. 假设\( B \nsubseteq D \)，则\( \exists y_0 \in B, y_0 \notin D \)，但因\( y_0 \in B \)，故\( \exists (x, y_0) \in A \times B \)，根据前面得到的，有\( y_0 \in B, y_0 \in D \)，矛盾，故该种情况是不可能的。

综上，有\( A \subseteq C \)且\( B \subseteq D \)。

充分性：

因\( A \subseteq C \)，故\( \forall x \in A, x \in C \)，因\( B \subseteq D \)，故\( \forall y \in B, y \in D \)，所以有\( \forall (x, y) \in A \times B \)， \( x \in A \)，进而有\( x \in C \)，\( y \in B \)，进而有\( y \in D \)，综合得，\( (x, y) \in C \times D \)，即我们有\( A \times B \subseteq C \times D \)。

证毕。

证明：\( (A \times B = C \times D) \equiv (A = C 且 B = D) \)：

必要性：

因为\( A \times B = C \times D \)，故\( A \times B \subseteq C \times D \)且\( C \times D \subseteq A \times B \)，

1. 因为\( A \times B \subseteq C \times D \)，根据前面的证明，有\( A \subseteq C, B \subseteq D \)。
2. 因为\( C \times D \subseteq A \times B \)，根据前面的证明，有\( C \subseteq A, D \subseteq B \)。

综上，得\( A = C, B = D \)。

充分性：

因为\( A = C 且 B = D \)，故\( A \subseteq C, C \subseteq A, B \subseteq D, D \subseteq B \)，

1. 因为\( A \subseteq C, B \subseteq D \)，根据前面的证明，有\( A \times B \subseteq C \times D \)。
2. 因为\( C \subseteq A, D \subseteq B \)，根据前面的证明，有\( C \times D \subseteq A \times B \)。

综上，得\( A \times B = C \times D \)。

证毕。

如果\( A, B, C, D \)为非空集合的前提条件去掉，则\( A \times B \subseteq C \times D \)，不一定有\( A \subseteq C \)且\( B \subseteq D \)，反例：\( A = \emptyset, B = \{ 1, 2 \}, C = \{ 3, 4 \}, D = \emptyset \)。但反之，如果\( A \subseteq C \)且\( B \subseteq D \)，则一定有\( A \times B \subseteq C \times D \)。

如果\( A, B, C, D \)为非空集合的前提条件去掉，则\( A \times B = C \times D \)，不一定有\( A = C \)且\( B = D \)，反例：\( A = \emptyset, B = \{ 1, 2 \}, C = \{ 3, 4 \}, D = \emptyset \)。但反之，如果\( A = C \)且\( B = D \)，则一定有\( A \times B = C \times D \)。

练习3.5.7

题目：

Let \( X, Y \) be sets, and let \( \pi_{X \times Y \to X}: X \times Y \to X \) and \( \pi_{X \times Y \to Y}: X \times Y \to Y \) be the maps \( \pi_{X \times Y \to X }(x, y) := x \) and \( \pi_{X \times Y \to Y}(x, y) := y \); these maps are known as the co-ordinate functions on \( X \times Y \). Show that for any functions \( f: Z \to X \) and \( g: Z \to Y \), there exists a unique function \( h: Z \to X \times Y \) such that \( \pi_{X \times Y \to X} \circ h = f \) and \( \pi_{X \times Y \to Y} \circ h = g \). (Compare this to the last part of Exercise 3.3.8, and to Exercise 3.1.7.) This function \( h \) is known as the direct sum of \( f \) and \( g \) and is denoted \( h = f \oplus g \).

证明：

构造函数\( h: Z \to X \times Y \)，映射规则为：\( \forall z \in Z \)，记\( f(z) = x \)，\( g(z) = y \)，则\( h(z) = (x, y) \)。

先证明\( \pi_{X \times Y \to X} \circ h = f \)。

这两个函数的定义域和值域都是\( Z \to X \)，且 \( \forall z \in Z, \pi_{X \times Y \to X} \circ h(z) = \pi_{X \times Y \to X}(h(z)) = \pi_{X \times Y \to X}((f(z), g(z))) = f(z) \)，故两函数相等。

再证明\( \pi_{X \times Y \to Y} \circ h = g \)。

这两个函数的定义域和值域都是\( Z \to Y \)，且 \( \forall z \in Z, \pi_{X \times Y \to Y} \circ h(z) = \pi_{X \times Y \to Y}(h(z)) = \pi_{X \times Y \to Y}((f(z), g(z))) = g(z) \)，故两函数相等。

最后证明\( h \)是唯一的，假设存在另外一个函数\( h' \)满足要求，则首先\( h, h' \)的定义域和值域相等，都是\( Z \to X \times Y \)，且\( \forall z \in Z, h(z) = (f(z), g(z)) = h'(z) \)，故两函数相等。

证毕。

练习3.5.8

题目：

Let \( X_1, \dots , X_n \) be sets. Show that the Cartesian product \( \prod_{i = 1}^{n} X_i \) is empty if and only if at least one of the \( X_i \) is empty.

证明：

必要性：

假设\( \forall 1 \leq i \leq n, X_i \neq \emptyset \)，则根据引理3.5.12，\( \exists (x_i)_{1 \leq i \leq n}, \forall 1 \leq i \leq n, x_i \in X_i \)，该n元有序对属于\( \prod_{i = 1}^{n} X_i \)，故假设不成立，至少有一个\( X_i \)是空集。

充分性：

至少有一个\( X_i \)为空集，我们记它为\( X_k \)，假设\( \prod_{i = 1}^{n} X_i \neq \emptyset \)，即\( \exists (x_i)_{1 \leq i \leq n}, \forall 1 \leq i \leq n, x_i \in X_i \)，由于\( X_k \)为空集，故不可能有\( x_k \in X_k \)，故假设不成立，即\( \prod_{i = 1}^{n} X_i = \emptyset \)。

证毕。

练习3.5.9

题目：

Suppose that \( I \) and \( J \) are two sets, and for all \( \alpha \in I \) let \( A_{\alpha} \) be a set, and for all \( \beta \in J \) let \( B_{\beta} \) be a set. Show that \( (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha, \beta) \in I \times J} (A_{\alpha} \cap B_{\beta}) \).

证明：

\( \forall x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \)，有\( x \in \bigcup_{\alpha \in I} A_{\alpha} \)且\( x \in \bigcup_{\beta \in J} B_{\beta} \)，因为\( x \in \bigcup_{\alpha \in I} A_{\alpha} \)，故\( \exists \alpha \in I, x \in A_{\alpha} \)，因为\( x \in \bigcup_{\beta \in J} B_{\beta} \)，故\( \exists \beta \in J, x \in B_{\alpha} \)，综合得，\( x \in A_{\alpha} \cap B_{\beta} \)，进而有\( x \in \bigcup_{(\alpha, \beta) \in I \times J} (A_{\alpha} \cap B_{\beta}) \)。

反之，\( \forall x \in \bigcup_{(\alpha, \beta) \in I \times J} (A_{\alpha} \cap B_{\beta}) \)，有\( \exists (\alpha, \beta) \in I \times J, x \in A_{\alpha} \cap B_{\beta} \)，因\( x \in A_{\alpha} \)，故\( x \in \bigcup_{\alpha \in I} A_{\alpha} \)，因\( x \in B_{\beta} \)，故\( x \in \bigcup_{\beta \in J} B_{\beta} \)，综合得，\( x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \)。

证毕。

练习3.5.10

题目：

If \( f: X \to Y \) is a function, define the graph of \( f \) to be the subset of \( X \times Y \) defined by \( \{ (x, f(x)): x \in X \} \). Show that two functions \( f: X \to Y , \tilde{f} : X \to Y \) are equal if and only if they have the same graph. Conversely, if \( G \) is any subset of \( X \times Y \) with the property that for each \( x \in X \), the set \( \{ y \in Y: (x, y) \in G \} \) has exactly one element (or in other words, \( G \) obeys the vertical line test), show that there is exactly one function \( f: X \to Y \) whose graph is equal to \( G \).

证明两函数相等\( \equiv \)它们的图相等：

\( f: X \to Y \)的图为\( \{ (x, f(x)): x \in X \} \)，记为\( A \)， \( \tilde{f}: X \to Y \)的图为\( \{ (x, \tilde{f}(x)): x \in X \} \)，记为\( B \)。

必要性：

假设\( A \neq B \)，即（\( \exists (x_0, f(x_0)) \in A, (x_0, f(x_0)) \notin B \)）或（\( \exists (x_1, \tilde{f}(x_1)) \in B, (x_1, \tilde{f}(x_1)) \notin A \)），

1. 如果\( \exists (x_0, f(x_0)) \in A, (x_0, f(x_0)) \notin B \)，得\( (x_0, \tilde{f}(x_0)) \neq (x_0, f(x_0)) \)，即\( \tilde{f}(x_0) \neq f(x_0) \)，这和\( \tilde{f} = f \)矛盾，故这种情况是不可能的。
2. 如果\( \exists (x_1, \tilde{f}(x_1)) \in B, (x_1, \tilde{f}(x_1)) \notin A \)，得\( (x_1, f(x_1)) \neq (x_1, \tilde{f}(x_1)) \)，即\( f(x_1) \neq \tilde{f}(x_1) \)，这和\( f = \tilde{f} \)矛盾，故这种情况是不可能的。

综上，所有情况都不可能，故假设不成立，有\( A = B \)。

充分性：

假设\( f \neq \tilde{f} \)，即\( \exists x \in X, f(x) \neq \tilde{f}(x) \)，而\( (x, f(x)) \in A \)，再加上\( A = B \)，故\( (x, f(x)) \in B \)，根据\( B \)的构造规则，知\( (x, f(x)) = (x, \tilde{f}(x)) \)，进而有\( f(x) = \tilde{f}(x) \)，矛盾，故假设不成立，\( f = \tilde{f} \)。

证毕。

证明如果\( G \)满足垂直线测试，则它对应一个唯一的函数：

构造函数\( f: X \to Y \)，映射规则为：\( \forall x \in X \)，根据要求，\( \{ y \in Y, (x, y) \in G \} \)为单例集，我们记该集合内的唯一元素为\( y \)，则\( f(x) = y \)。

现在我们证明该函数是唯一的，假设有另外一个函数\( (f': X \to Y) \neq (f: X \to Y) \)， \( f' \)的图\( G' = \{ (x, f'(x)), x \in X \} \)也等于\( G \)，因为\( f' \neq f \)，故\( \exists x \in X, f'(x) \neq f(x) \)，而\( (x, f(x)) \in G \)，进而有\( (x, f(x)) \in G' \)，根据图的构造规则，知\( (x, f(x)) = (x, f'(x)) \)，可得\( f(x) = f'(x) \)，矛盾，故假设不成立，不存在其他函数有相同的图\( G \)。

证毕。

练习3.5.11

题目：

Show that Axiom 3.10 can in fact be deduced from Lemma 3.4.9 and the other axioms of set theory, and thus Lemma 3.4.9 can be used as an alternate formulation of the power set axiom. (Hint: for any two sets \( X \) and \( Y \), use Lemma 3.4.9 and the axiom of specification to construct the set of all subsets of \( X \times Y \) which obey the vertical line test. Then use Exercise 3.5.10 and the axiom of replacement.)

公理3.10即幂集公理。引理3.4.9则是\( 2^X \)存在定理。

证明：

对\( X \times Y \)使用引理3.4.9，得到\( X \times Y \)所有子集组成的集合，记为\( A \)，对\( A \)使用规范公理，限制元素必须满足垂直线测试，即如果记\( X \times Y \)的某个子集为\( X' \times Y' \) ，则它需要满足\( \forall x \in X, \{ y \in Y, (x, y) \in X \times Y \} \)有且仅有一个元素（注意，这里所有\( x \in X \)都得有对应的有序对\( (x, y) \)，不能有某个\( x \)值没有输出），我们记这个这步得到的集合为\( B \)，此时根据练习3.5.10，有\( B \)的每个元素\( G \)都对应一个唯一的函数，该函数的图\( = G \)，故可以对\( B \)使用替换公理，将每个元素\( G \)都替换成对应的函数，我们记最后得到的这个集合为\( C \)。

下面，我们证明\( C \)就是所有定义域为\( X \)，值域为\( Y \)的函数组成的集合。

首先证明，所有定义域为\( X \)，值域为\( Y \)的函数都在\( C \)中：

\( \forall f: X \to Y \)，\( f \)有唯一的图\( G \)，因\( G \subseteq X \times Y \)，故\( G \in A \)，又\( G \)满足垂直线测试，故\( G \in B \)，最后，\( G \)在\( C \)中被替换成其对应的唯一函数，即\( f \)，故有\( f \in C \)。

最后，根据\( C \)的构造过程，有：\( C \)中所有元素都是定义域为\( X \)，值域为\( Y \)的函数，不存在其他类型的元素。

证毕。

练习3.5.12

题目：

This exercise will establish a rigorous version of Proposition 2.1.16. Let \( X \) be an arbitrary non-empty set, Let \( f: \mathbf{N} \times X \to X \) be a function, and let \( c \) be an element of \( X \). Show that there exists a function \( a: \mathbf{N} \to X \) such that \( a(0) = c, a(n+\!+) = f(n, a(n)) \) for all \( n \in \mathbf{N} \), and furthermore that this function is unique. (Hint: first show inductively, by a modification of the proof of Lemma 3.5.12, that for every natural number \( N \in \mathbf{N} \), there exists a unique function \( a_N : \{ n \in \mathbf{N} : n \leq N \} \to X \) such that \( a_N(0) = c \) and \( a_N(n+\!+) = f(n, a_N(n)) \) for all \( n \in \mathbf{N} \) such that \( n < N \).) For an additional challenge, prove this result without using any properties of the natural numbers other than the Peano axioms directly (in particular, without using the ordering of the natural numbers, and without appealing to Proposition 2.1.16). (Hint: first show inductively, using only the Peano axioms and basic set theory, that for every natural number \( N \in \mathbf{N} \), there exists a unique pair \( A_N, B_N \) of subsets of \( \mathbf{N} \) which obeys the following properties:

1. \( A_N \cap B_N = \emptyset \).
2. \( A_N \cup B_N = \mathbf{N} \).
3. \( 0 \in A_N \).
4. \( N+\!+ \in B_N \).
5. Whenever \( n \in B_N \), we have \( n+\!+ \in B_N \).
6. Whenever \( n \in A_N \) and \( n \neq N \), we have \( n+\!+ \in A_N \).

Once one obtains these sets, use \( A_N \) as a substitute for \( \{ n \in \mathbf{N} : n \leq N \} \) in the previous argument.)

说明：

1. 为了辅助3.5.13的证明，这里作者在自己博客的勘误中，将\( f: \mathbf{N} \times \mathbf{N} \to \mathbf{N} \)进一步通用化成 \( f: \mathbf{N} \times X \to X \)，其中\( X \)为任意非空集合。
2. 这里严格应该按照additional challenge那里的要求来证明，即不能用到序相关的东西，因为序是在加法的基础上定义的，而加法用了递归定义，然而递归定义正是我们要证明的，相当于循环依赖了，是非法的，故下面的证明中，我们只按 additional challenge的要求来证明，不证明用到序相关属性的那个版本（用到序的版本的证明还是很简单的，additional challenge的版本则相对更复杂）。

证明：

首先，我们通过手动构造集合的方法+数学归纳法，来证明满足上述6条属性的\( A_N, B_N \)对是存在的。

针对\( N = 0 \)，令\( A_0 = \{ 0 \} \)，\( B_0 = \mathbf{N} \setminus \{ 0 \} \)。

现在证明\( A_0, B_0 \)满足6条属性：

根据\( A_0, B_0 \)的定义，很容易验证\( A_0, B_0 \)是满足属性1、2、3、4的。

针对属性5，根据\( B_0 \)的定义，当\( n \in B_N \)时，有\( n \neq 0 \)，故\( n+\!+ \neq 0 \)，从而有\( n+\!+ \notin A_0 \)，进而有\( n+\!+ \in B_0 \)，即属性5是满足的。

针对属性6，根据\( A_0 \)的定义，我们知道\( \nexists n \in A_0, n \neq 0 \)，该命题直接为真，故属性6也是满足的。

OK，到此，\( N = 0 \)的基础情况证明完毕，现在，归纳假设当\( N = K \)时，满足上述6条属性的\( A_K, B_K \)对是存在的，当\( N = K+\!+ \)时，令\( A_{K+\!+} = A_K \cup \{ K+\!+ \} \)，令\( B_{K+\!+} = B_K \setminus \{ K+\!+ \} \)。

现在证明\( A_{K+\!+}, B_{K+\!+} \)满足6条属性：

针对属性1，\( A_{K+\!+} \cap B_{K+\!+} = (A_K \cup \{ K+\!+ \}) \cap (B_K \setminus \{ K+\!+ \}) = ((B_K \setminus \{ K+\!+ \}) \cap A_K) \cup ((B_K \setminus \{ K+\!+ \}) \cap \{ K+\!+ \}) = \emptyset \cup \emptyset = \emptyset \)，即属性1是满足的。

针对属性2，\( A_{K+\!+} \cup B_{K+\!+} = (A_K \cup \{ K+\!+ \}) \cup (B_K \setminus \{ K+\!+ \}) = A_K \cup (\{ K+\!+ \} \cup (B_K \setminus \{ K+\!+ \})) = A_K \cup B_K = \mathbf{N} \)，即属性2是满足的。

针对属性3，根据归纳假设，\( 0 \in A_K \)，而\( A_K \subseteq A_{K+\!+} \)，故\( 0 \in A_{K+\!+} \)，即属性3是满足的。

针对属性4，根据归纳假设，\( K+\!+ \in B_K \)，根据属性5，有\( (K+\!+)+\!+ \in B_K \)，而\( (K+\!+)+\!+ \neq K+\!+ \)，故在构造\( B_{K+\!+} \)的过程中不会被剔除，即\( (K+\!+)+\!+ in B_{K+\!+} \)，即属性4是满足的。

针对属性5，\( \forall n \in B_{K+\!+} \)，如果\( n \neq K+\!+ \)，则\( n \)不会被剔除，有\( n \in B_{K+\!+} \)，如果\( n = K+\!+ \)，则根据归纳假设，\( n = K+\!+ \in B_K \)，故\( n+\!+ = (K+\!+)+\!+ \in B_K \)，又\( (K+\!+)+\!+ \neq K+\!+ \)，故\( (K+\!+)+\!+ \)不会被剔除，即\( (K+\!+)+\!+ \in B_{K+\!+} \)，综上，有属性5是满足的。

针对属性6，\( \forall n \in A_{K+\!+}, n \neq K+\!+ \)，有\( n \in A_K \)（因为\( A_{K+\!+} \)就是\( A_K \)再加上一个元素\( K+\!+ \)而已，如果\( n \neq K+\!+ \)，那么\( n \)必然早就在\( A_K \)中了），如果此时\( n \neq K \)，根据归纳假设，有\( n+\!+ \in A_K \)，进而有\( n+\!+ \in A_{K+\!+} \)（因为\( A_K \subseteq A_{K+\!+} \)），如果此时\( n = K \)，则\( n+\!+ = K+\!+ \in A_{K+\!+} \)，综上，有属性6是满足的。

故构造的\( A_{K+\!+}, B_{K+\!+J} \)对满足6个属性，归纳完毕，到此，便证明了满足上述6条属性的\( A_N, B_N \)对的存在性。

证明完存在性，接着，我们证明\( A_N, B_N \)对的唯一性。

令\( C, D \)为任意满足上述6条属性的集合，我们证明\( A_N = C \)。

首先证明，\( \forall n \in A_N \)，有\( n \in C \)，用数学归纳法来证明，当\( n = 0 \)时，根据属性3，有\( 0 \in A_N, 0 \in C \)，即\( n = 0 \)时是成立的，假设当\( n = k \)时，成立，即：如果\( k \in A_N \)，则\( k \in C \)。

当\( n = k+\!+ \)时，如果\( k+\!+ \in A_N \)（如果\( k+\!+ \notin A_N \)则命题直接成立，不用管），则我们此时假设\( k = N \)，于是有\( (k+\!+ = N+\!+) \in B_N \)，矛盾，故必有\( k \neq N \)，再假设\( k \notin A_N \)，即\( k \in B_N \)，则根据属性5，有\( k+\!+ \in B_N \)，矛盾，故必有\( k \in A_N \)，根据归纳假设，\( k \in A_N \)可得\( k \in C \)，再加上\( k \neq N \)，根据属性6，有\( k+\!+ \in C \)。

至此，归纳完毕，有\( \forall n \in A_N \)，\( n \in C \)。

接着，需要再证明\( \forall n \in C \)，有\( n \in A_N \)，证明方法和上面是一样的，只要把上面的证明中\( A_N, B_N \)的符号分别和\( C, D \)交换即可，故这里不再重复。

至此，我们证明了\( A_N \)是唯一的，则\( B_N = \mathbf{N} \setminus A_N \)也是唯一的， \( A_N, B_N \)对的唯一性证明完毕。

证明完\( A_N, B_N \)对的存在性及唯一性后，我们就可以证明函数\( a \)的存在性和唯一性了，为了证明\( a \)的存在性和唯一性，我们先证明：\( \forall N \in \mathbf{N} \)，函数\( a_N: A_N \to X, a_N(0) = c \)且\( \forall n \in A_N \setminus \{ N \} \)，有\( a_N(n+\!+) = f(n, a_N(n)) \)是存在且唯一的。

当\( N = 0 \)时，构造函数\( a_0: A_0 \to X \)，令\( a_0(0) = c \)，由于\( A_0 = \{ 0 \} \)，所以\( A_0 \setminus \{ 0 \} = \emptyset \)，故\( \forall n \in A_0 \setminus \{ 0 \}, a_0(n+\!+) = f(n, a_0(n)) \)直接成立。现在证明\( a_0 \)是唯一的， \( \forall \)满足条件的函数\( a'_0: A_0 \to X \)，有：\( \forall n \in A_0 \)， \( a_0(n) = a'(n) = a_0(0) = c \)，即\( a_0 = a'_0 \)，也就是说函数\( a_0 \)是唯一的。

归纳假设当\( N = K \)时成立，即函数\( a_K: A_K \to X, a_K(0) = c \)且\( \forall n \in A_K \setminus \{ K \} \)，有\( a_K(n+\!+) = f(n, a_K(n)) \)是存在且唯一的。

当\( N = K+\!+ \)时，构造函数\( a_{K+\!+}: A_{K+\!+} \to X \)，令\( a_{K+\!+}(0) = c \)， \( \forall n \in A_{K+\!+} \)，如果\( n \in A_{K+\!+} \setminus \{ K+\!+ \} \)，则有\( n \in A_K \)，即\( n \)在函数\( a_K \)的定义域内，此时令\( a_{K+\!+}(n) = a_{K}(n) \)，而当\( n = K+\!+ \)时，则令\( a_{K+\!+}(n) = f(K, a_{K+\!+}(K)) \)。

现在我们需要证明\( a_{K+\!+} \)是满足要求的：首先，\( a_{K+\!+}(0) = c \) 是满足的，我们还需要证明\( \forall n \in A_{K+\!+} \setminus \{ K+\!+ \}, a_{K+\!+}(n+\!+) = f(n, a_{K+\!+}(n)) \)。

\( \forall n \in (A_{K+\!+} \setminus \{ K+\!+ \} = A_K) \)，

1. 如果\( n = K \)，则\( n+\!+ = K+\!+ \)，此时根据\( a_{K+\!+} \)的构造方法，有\( a_{K+\!+}(n+\!+) = f(K, a_{K+\!+}(K)) = f(n, a_{K+\!+}(n)) \)。
2. 如果\( n \neq K \)，则有\( n \in A_K \setminus K \)且\( n+\!+ \in A_{K+\!+} \setminus \{ K+\!+ \} \)，此时根据\( a_{K+\!+} \)的构造方法，有\( a_{K+\!+}(n+\!+) = a_K(n+\!+) \)，又因为\( n \in A_K \setminus K \)，故根据归纳假设，等式右边的\( a_K(n+\!+) = f(n, a_K(n)) \)，而\( n \in A_{K+\!+} \setminus \{ K+\!+ \} \)，故\( a_{K+\!+}(n) = a_K(n) \)，从而得到\( a_{K+\!+}(n+\!+) = f(n, a_K(n)) = f(n, a_{K+\!+}(n)) \)。

至此，我们证明了：\( \forall N \in \mathbf{N} \)，函数\( a_N: A_N \to X, a_N(0) = c \) 且\( \forall n \in A_N \setminus \{ N \} \)，有\( a_N(n+\!+) = f(n, a_N(n)) \)是存在且唯一的，现在，我们去证明函数\( a \)是存在且唯一的。

先证明\( a \)的存在性，构造函数\( a: \mathbf{N} \to X \)， \( \forall n \in \mathbf{N} \)，令\( a(n) = a_{n + 1}(n) \)。

于是，\( a(0) = a_1(0) = c \)，\( \forall n \in \mathbf{N} \)，因为\( n \in A_{n + 1} \setminus \{ n + 1 \} \)，故\( a(n+\!+) = a_{n + 1}(n+\!+) = f(n, a_{n + 1}(n)) = f(n, a(n)) \)。

最后，证明\( a \)的唯一性，令\( a': \mathbf{N} \to X \)为任意满足条件的函数，我们要证明\( a = a' \)，因为它们的定义域和值域已经相等了，故只要证明相同的输入值有相同的输出值即可。

用数学归纳法证明，当\( n = 0 \)时，\( a(0) = a'(0) = c \)，成立。归纳假设当\( n = k \)时成立，即\( a(k) = a'(k) \)。当\( n = k+\!+ \)时，\( a(k+\!+) = f(k, a(k)), a'(k+\!+) = f(k, a'(k)) \)，根据归纳假设，有\( f(k, a(k)) = f(k, a'(k)) \)，进而有\( a(k+\!+) = a'(k+\!+) \)。

至此，我们证明了\( a \)的存在性及唯一性。

证毕。

练习3.5.13

题目：

The purpose of this exercise is to show that there is essentially only one version of the natural number system in set theory (cf. the discussion in Remark 2.1.12). Suppose we have a set \( \mathbf{N'} \) of “alternative natural numbers”, an “alternative zero” \( 0' \), and an “alternative increment operation” which takes any alternative natural number \( n' \in \mathbf{N'} \) and returns another alternative natural number \( n'+\!+' \in \mathbf{N'} \), such that the Peano axioms (Axioms 2.1-2.5) all hold with the natural numbers, zero, and increment replaced by their alternative counterparts. Show that there exists a bijection \( f: \mathbf{N} \to \mathbf{N'} \) from the natural numbers to the alternative natural numbers such that \( f(0) = 0' \), and such that for any \( n \in \mathbf{N} \) and \( n' \in \mathbf{N'} \), we have \( f(n) = n' \) if and only if \( f(n+\!+) = n'+\!+' \). (Hint: use Exercise 3.5.12.)

证明：

构造函数\( a: \mathbf{N} \times \mathbf{N'} \to \mathbf{N'} \)， \( \forall (n, n') \in \mathbf{N} \times \mathbf{N'} \)，令\( a(n, n') = n'+\!+' \)。

（注：根据构造，可知：\( a(0, 0') = 1', a(1, 1') = 2' \)，以此类推， \( a \)在这些第一个参数和第二个参数匹配情况下的输出值才是我们关注的，其他地方的输出值，比如\( a(0, 1') = 2' \)则是我们不在乎的。）

令\( c = 0' \)，根据练习3.5.12， \( \exists \)函数\( f: \mathbf{N} \to \mathbf{N'} \)，满足：\( f(0) = c = 0' \)， \( \forall n \in \mathbf{N}, f(n+\!+) = a(n, f(n)) \)。

现在我们证明该函数\( f \)满足题目的要求。

首先，\( f(0) = 0' \)是满足要求的，下面，我们证明\( \forall n \in \mathbf{N}, n' \in \mathbf{N'} \)，有\( f(n) = n' \)当且仅当\( f(n+\!+) = n'+\!+' \)。

必要性：

用数学归纳法证明。

\( \forall n \in \mathbf{N}, n' \in \mathbf{N'} \)，有：

当\( n = 0 \)时，如果\( f(n) = n' \)，即\( f(0) = 0' \), 则我们有\( f(0+\!+) = a(0, f(0)) = a(0, 0') = 0'+\!+' \)，成立。

归纳假设当\( n = k \)时成立，即：如果\( f(k) = n' \)，则\( f(k+\!+) = n'+\!+' \)。

当\( n = k+\!+ \)时，如果\( f(k+\!+) = n' \)，此时分\( n' = 0' \)以及\( n' \neq 0' \) 两种情况：

1. 如果\( n' = 0' \)，则\( f(k+\!+) = a(k, f(k)) = f(k)+\!+' = 0' \)，但公理2.3，得\( f(k)+\!+' = 0' \)是不可能成立的，得出矛盾，故\( n' = 0' \)是不可能的。
2. 如果\( n' \neq 0' \)，则\( \exists c'+\!+' = n' \)，从而有\( f(k+\!+) = a(k, f(k)) = f(k)+\!+' = n'+\!+' = c'+\!+' \)，根据公理2.4，有\( f(k) = c' \)，再根据归纳假设，有\( f(k+\!+) = c'+\!+' = n'+\!+' \)。

综上，当\( n = k+\!+ \)时，如果\( f(k+\!+) = n' \)，则\( f(k+\!+) = n'+\!+' \)，即\( n = k+\!+ \)时成立，归纳完毕。

充分性：

如果\( f(n+\!+) = n'+\!+' \)，则\( f(n+\!+) = a(n, f(n)) = f(n)+\!+' = n'+\!+' \)，根据公理2.4，有\( f(n) = n' \)。

至此，必要性和充分性都证完了，可得\( f(n) = n' \equiv f(n+\!+) = n'+\!+' \)。

还得证明\( f \)是双射函数。

先证明\( f \)是单射函数，即：\( \forall n, n' \in \mathbf{N} \)，如果\( n \neq n' \)，则\( f(n) \neq f(n') \)。用数学归纳法来证明，对\( n \)进行归纳。

当\( n = 0 \)时，\( f(n) = f(0) = 0' \)，\( \forall n' \neq n \)，因\( n' \neq 0 \)，故\( \exists c'+\!+ = n' \)，从而有\( f(n') = f(c'+\!+) = f(c')+\!+' \neq (0' = f(n)) \)，故\( n = 0 \)时成立。

归纳假设当\( n = k \)时成立，即\( \forall n' \in \mathbf{N} \)，如果\( k \neq n' \)，则\( f(k) \neq f(n') \)。

当\( n = k+\!+ \)时，\( \forall n' \in \mathbf{N} \)，如果\( k+\!+ \neq n' \)，分两种情况进行讨论：

1. 如果\( n' = 0 \)，此时\( f(n') = f(0) = 0' \)，则\( f(k+\!+) = f(k)+\!+' \neq (0' = f(n')) \)，即该种情况下是成立的。
2. 如果\( n' \neq 0 \)，此时\( \exists c'+\!+ = n' \)，故\( f(n') = f(c'+\!+) = f(c')+\!+' \)，由于\( k+\!+ \neq n' \)，可得\( k \neq c' \)，根据归纳假设，得：\( f(k) \neq f(c') \)，有\( f(k)+\!+' \neq f(c')+\!+' \)，又\( f(k+\!+) = f(k)+\!+', f(n') = f(c')+\!+' \)，可得，\( f(k+\!+) \neq f(n') \)，即该种情况下也是成立的。

综上，有\( n = k+\!+ \)时，成立，归纳完毕，\( f \)是单射函数。

现在，最后证明\( f \)是满射函数，即\( \forall n' \in \mathbf{N'}, \exists n \in \mathbf{N}, f(n) = n' \)，对\( n' \)进行归纳( 注：\( \mathbf{N'} \)也满足数学归纳法公理框架 )。

当\( n' = 0' \)时，则\( 0 \in \mathbf{N}, f(0) = 0' \)，成立。

假设当\( n' = k' \)时成立，即\( \exists n \in \mathbf{N}, f(n) = k' \)。

当\( n' = k'+\!+' \)时，根据归纳假设，\( \exists n \in \mathbf{N}, f(n) = k' \)，此时有\( f(n+\!+) = f(n)+\!+' = k'+\!+' \)，即\( n' = k'+\!+' \)时，也是成立的。

归纳完毕，\( f \)是满射函数。

至此，可得\( f \)是双射函数。

证毕。

章节3.6

练习3.6.1

题目：

Prove Proposition 3.6.4.

Proposition 3.6.4的内容：

Let \( X, Y, Z \) be sets. Then \( X \) has equal cardinality with \( X \). If \( X \) has equal cardinality with \( Y \), then \( Y \) has equal cardinality with \( X \). If \( X \) has equal cardinality with \( Y \) and \( Y \) has equal cardinality with \( Z \), then \( X \) has equal cardinality with \( Z \).

证明自反性：

构造函数\( f: X \to X \)，\( \forall x \in X, f(x) := x \)。

下面证明\( f \)是双射函数。

先证明单射：

\( \forall x_0 \neq x_1 \in X, f(x_0) = x_0, f(x_1) \)，有\( f(x_0) \neq f(x_1) \) 即\( f \)单射。

再证明满射：

\( \forall x \in X, \exists x \in X, f(x) = x \)，即\( f \)满射。

因存在\( f: X \to X \)为双射函数，故\( X \)和\( X \)基数相等。

证毕。

证明对称性：

因为\( X \)和\( Y \)基数相等，故存在双射函数\( f: X \to Y \)，此时\( f^{-1}: Y \to X \)是\( Y \)到\( X \)的双射函数，即\( Y \)和\( X \)基数相等。

证毕。

证明传递性：

因为\( X \)和\( Y \)基数相等，故存在双射函数\( f: X \to Y \)，因为\( Y \)和\( Z \)基数相等，故存在双射函数\( g: Y \to Z \)，令函数\( h: X \to Z, h = g \circ f \)，下面证明\( h \)是双射函数。

先证明单射：

\( \forall x_0 \neq x_1 \in X \)，因为\( f \)单射，故\( f(x_0) \neq f(x_1) \)，又\( g \)单射，故\( g(f(x_0)) \neq g(f(x_1)) \)，即\( (g \circ f)(x_0) \neq (g \circ f)(x_1) \)，即\( h \)单射。

再证明满射：

\( \forall z \in Z \)，因为\( g \)满射，故\( \exists y \in Y, g(y) = z \)，又因为\( f \)满射以及\( g(y) \in Y \)，故\( \exists x \in X, f(x) = g(y) \)。

因存在\( h: X \to Z \)为双射函数，故\( X \)和\( Z \)基数相等。

证毕。

练习3.6.2

题目：

Show that a set \( X \) has cardinality \( 0 \) if and only if \( X \) is the empty set.

证明：

必要性：

如果\( X \)有基数\( 0 \)，即存在\( X \to \{ i \in \mathbf{N}, 1 \leq i \leq 0 \} \)的双射函数，记为\( f \)，假设\( X \)不为空集，即\( \exists x \in X \)，则我们有\( f(x) \in (\{ i \in \mathbf{N}, 1 \leq i \leq 0 \} = \emptyset) \)矛盾，故\( X \)为空集。

充分性：

如果\( X \)为空集，则\( f: \emptyset \to \emptyset \)为\( X \to (\{ i \in \mathbf{N}, 1 \leq i \leq 0 \} = \emptyset) \)的双射函数，即\( X \)和\( \{ i \in \mathbf{N}, 1 \leq i \leq 0 \} \)基数相等，即\( X \)的基数为0。

证毕。

练习3.6.3

题目：

Let \( n \) be a natural number, and let \( f: \{ i \in N : 1 \leq i \leq n \} \to N \) be a function. Show that there exists a natural number \( M \) such that \( f(i) \leq M \) for all \( 1 \leq i \leq n \). (Hint: induct on \( n \). You may also want to peek at Lemma 5.1.14.) Thus finite subsets of the natural numbers are bounded.

证明：

当\( n = 0 \)时，因为\( \{ i \in N : 1 \leq i \leq 0 \} = \emptyset \)，故\( \forall M \in \mathbf{N} \), \( \forall 1 \leq i \leq n, f(i) \leq M \)，成立。

归纳假设当\( n = k \)时成立，即\( \exists M \in \mathbf{N} \)，\( \forall 1 \leq i \leq n, f(i) \leq M \)。

当\( n = k+\!+ \)时，构造函数\( g: \{ i \in N : 1 \leq i \leq k \} \to N, \forall 1 \leq i \leq k, g(i) := f(i) \)，根据归纳假设\( \exists M \in \mathbf{N}, \forall 1 \leq i \leq k, (g(i) = f(i)) \leq M \)，令\( M_1 = max(M, f(k+\!+)) \)，则\( \forall 1 \leq i \leq k+\!+, f(i) \leq M_1 \)，成立。

证毕。

练习3.6.4

题目：

Prove Proposition 3.6.14

Proposition 3.6.14的内容：

(Cardinal arithmetic).

1. Let \( X \) be a finite set, and let \( x \) be an object which is not an element of \( X \). Then \( X \cup \{ x \} \) is finite and \( \#(X \cup \{ x \}) = \#(X) + 1 \).
2. Let \( X \) and \( Y \) be finite sets. Then \( X \cup Y \) is finite and \( \#(X \cup Y ) \leq \#(X) + \#(Y) \). If in addition \( X \) and \( Y \) are disjoint (i.e., \( X \cap Y = \emptyset \)), then \( \#(X \cup Y ) = \#(X) + \#(Y) \).
3. Let \( X \) be a finite set, and let \( Y \) be a subset of \( X \). Then \( Y \) is finite, and \( \#(Y) \leq \#(X) \). If in addition \( Y \neq X \) (i.e., \( Y \) is a proper subset of \( X \)), then we have \( \#(Y) < \#(X) \).
4. If \( X \) is a finite set, and \( f: X \to Y \) is a function, then \( f(X) \) is a finite set with \( \#(f(X)) \leq \#(X) \). If in addition \( f \) is one-to-one, then \( \#(f(X)) = \#(X) \).
5. Let \( X \) and \( Y \) be finite sets. Then Cartesian product \( X \times Y \) is finite and \( \#(X \times Y) = \#(X) \times \#(Y) \).
6. Let \( X \) and \( Y \) be finite sets. Then the set Y^X (defined in Axiom 3.10) is finite and \( \#(Y^X) = \#(Y)^{\#(X)} \).

证明命题1：

先证明，\( \forall y \in X \cup \{ x \} \)，如果\( y \notin X \)，则\( y = x \)：由\( y \in X \cup \{ x \} \)，有\( y \in X \)或\( y \in \{ x \} \)，因\( y \notin X \)，故排除前者，继续考虑\( y \in \{ x \} \)，这种情况有\( y = x \)，而\( x \notin X \)，故\( y \notin X \)且\( y = x \)。

下面证明存在我们想要的双射函数。

因为\( X \)有限，故存在双射函数\( f: X \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) \} \)，构造函数\( g: X \cup \{ x \} \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) + 1 \} \)， \( \forall y \in X \cup \{ x \} \)，如果\( y \in X \)，则\( g(y) := f(y) \)，如果\( y \notin X \)，即\( y = x \)，则\( g(y) := g(x) := \#(X) + 1 \)。

现证明\( g \)是双射函数。

先证单射：

\( \forall y_0 \neq y_1 \in X \cup \{ x \} \)，

1. 如果\( y_0, y_1 \in X \)，则\( g(y_0) = f(y_0), g(y_1) = f(y_1) \)，因为\( f \)单射，故\( f(y_0) \neq f(y_1) \)，从而有\( g(y_0) \neq g(y_1) \)。
2. 如果\( y_0, y_1 \)中有且仅有一个\( \notin X \)，不妨设\( y_0 \notin X \)，此时有\( y_0 \notin X, y_1 \in X \)，由\( y_0 \notin X \)，得\( g(y_0) = \#(X) + 1 \)，由\( y_1 \in X \)，得\( g(y_1) = f(y_1) \in \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) \} \)，故有\( g(y_1) \neq \#(X) + 1 \)，即\( g(y_1) \neq g(y_0) \)。
3. 如果\( y_0 \notin X, y_1 \notin X \)，则\( y_0 = y_1 = x \)，矛盾。

再证满射：

\( \forall i \in \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) + 1 \} \)，如果\( i \in \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) \} \)，则因为\( f \)满射，\( \exists y \in X \)，\( f(y) = g(y) = i \)，如果\( i \notin \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) \} \)，即\( i = \#(X) + 1 \)，则有\( g(x) = \#(X) + 1 = i \)。

证毕。

证明命题2：

因为\( X \)有限，记\( X \)的基数为\( n, n \in \mathbf{N} \)，则存在双射函数\( f: X \to \{ i \in \mathbf{N}, 1 \leq i \leq n \} \)，同理，记\( Y \)的基数为\( m, m \in \mathbf{N} \)，则存在双射函数\( g: X \to \{ i \in \mathbf{N}, 1 \leq i \leq m \} \)。

对\( X \)的基数\( n \)进行归纳。

当\( n = 0 \)时，\( X = \emptyset \)，\( X \cup Y = Y \)，故\( (\#(X \cup Y) = \#(Y)) \leq (\#(X) + \#(Y) = \#(Y)) \)，此时，\( X \cap Y = \emptyset \)，且有：\( \#(X \cup Y) = 0 + \#(Y) = \#(X) + \#(Y) \)。

归纳假设当\( n = k \)时成立。当\( n = k+\!+ \)时，因为\( X \)非空集，故\( \exists x \in X \)。此时，令\( C = X \setminus \{ x \} \)，则\( X \cup Y = C \cup \{ x \} \cup Y \)，且根据引理3.6.9，有\( C \)的基数为\( k \)。

因为\( C \)的基数为\( k \)，根据归纳假设，有：\( C \cup Y \)有限，\( \#(C \cup Y) \leq \#( C) + \#(Y) \)，且如果\( C \cap Y = \emptyset \)，则\( \#(C \cup Y) = \#( C) + \#(Y) \)。

因为\( C \cup Y \)有限，记它的基数为\( c \)，则存在双射函数\( a: C \cup Y \to \{ i \in \mathbf{N}, 1 \leq i \leq c \} \)，此时构造函数\( b: X \cup Y \to \{ i \in \mathbf{N}, 1 \leq i \leq c + 1 \} \)， \( \forall y \in X \cup Y \)，如果\( y \in C \cup Y \)，则\( b(y) := a(y) \)，如果\( y \notin C \cup Y \)，即\( y = x \)，则\( b(y) := b(x) := c + 1 \)。

现在证明\( b \)是双射函数。

先证单射：

\( \forall y_0 \neq y_1 \in X \cup Y \)，

1. 如果\( y_0, y_1 \in C \cup Y \)，则\( b(y_0) = a(y_0), b(y_1) = a(y_1) \)，因为\( a \)单射，故\( a(y_0) \neq a(y_1) \)，从而有\( b(y_0) \neq b(y_1) \)。
2. 如果\( y_0, y_1 \)中有且仅有一个\( \notin C \cup Y \)，不妨设\( y_0 \notin C \cup Y \)，此时有\( y_0 \notin C \cup Y, y_1 \in C \cup Y \)，由\( y_0 \notin C \cup Y \)，得\( y_0 = x \)，从而有\( b(y_0) = b(x) = c + 1 \)，由\( y_1 \in C \cup Y \)，得\( b(y_1) = a(y_1) \in \{ i \in \mathbf{N}, 1 \leq i \leq c \} \)，故有\( b(y_1) \neq c + 1 \)，即\( b(y_1) \neq b(y_0) \)。
3. 如果\( y_0 \notin C \cup Y, y_1 \notin C \cup Y \)，则\( y_0 = y_1 = x \)，矛盾。

再证满射：

\( \forall i \in \{ i \in \mathbf{N}, 1 \leq i \leq c + 1 \} \)，如果\( i \in \{ i \in \mathbf{N}, 1 \leq i \leq c \} \)，则因为\( a \)满射，\( \exists y \in X \)，\( a(y) = b(y) = i \)，如果\( i \notin \{ i \in \mathbf{N}, 1 \leq i \leq c \} \)，即\( i = c + 1 \)，则有\( b(x) = c + 1 = i \)。

证明完\( b \)是双射函数，接着证明：如果\( X \cap Y = \emptyset \)，则\( \#(X \cup Y) = \#(X) + \#(Y) \)。

如果\( X \cap Y = \emptyset \)，则\( C \cap Y = \emptyset \)，根据归纳假设，有\( \#(C \cup Y) = \#( C) + \#(Y) = k + \#(Y) = c \)，进而得\( \#(X \cup Y) = c + 1 = k + \#(Y) + 1 = (k+\!+) + \#(Y) = \#(X) + \#(Y) \)。

证毕。

证明命题3：

因为\( X \)有限，记\( X \)的基数为\( n, n \in \mathbf{N} \)，则存在双射函数\( f: X \to \{ i \in \mathbf{N}, 1 \leq i \leq n \} \)。

对\( X \)的基数\( n \)进行归纳。

当\( n = 0 \)时，\( X = \emptyset \)，\( \forall Y \subseteq X \)，有\( Y = \emptyset = X \)，从而有\( (\#(Y) = 0) \leq (\#(X) = 0) \)。

归纳假设当\( n = k \)时，命题成立，即\( \forall Y \subseteq X \)，\( Y \)有限且\( \#(Y) \leq \#(X) \)，且如果\( Y \neq X \)，则\( \#(Y) < \#(X) \)。

当\( n = k+\!+ \)时，因为\( X \)非空，故\( \exists x \in X \)，令\( C = X \setminus \{ x \} \)，则根据引理3.6.9，有\( C \)的基数为\( k \)。

\( \forall Y \subseteq X \)，要么\( x \in Y \)，要么\( x \notin Y \)。

如果\( x \notin Y \)，则\( Y \subseteq C \)，根据归纳假设，有：

1. \( Y \)有限且\( \#(Y) \leq (\#( C) = k) \leq (k+\!+ = \#(X)) \)。
2. 如果\( Y \neq C \)，则有\( Y \neq X \)（否则如果\( Y = X \)，则\( Y \)不可能是\( C \)的子集，产生矛盾），且\( \#(Y) < \#( C) < \#(X) \)。

如果\( x \in Y \)，则令\( D = Y \setminus \{ x \} \)，此时有\( x \notin D \)，进而有\( D \subseteq C \)，根据归纳假设，有：

1. \( D \)有限且\( \#(D) \leq \#( C) \)，此时根据命题1，有\( Y = D \cup \{ x \} \)也是有限的，且\( (\#(Y) = \#(D) + 1) \leq (\#( C) + 1 = \#(X)) \)。
2. 如果\( D \neq C \)，则有\( D \neq X \)（否则如果\( D = X \)，则\( D \)不可能是\( C \)的子集，产生矛盾），且有\( \#(D) < \#( C) \)，进而得到\( \#(Y) = \#(D) + 1 \leq \#( C) < \#(X) \)。

综上，当\( n = k+\!+ \)时成立。

证毕。

证明命题4：

因为\( X \)有限，记\( X \)的基数为\( n, n \in \mathbf{N} \)，则存在双射函数\( f: X \to \{ i \in \mathbf{N}, 1 \leq i \leq n \} \)。

对\( X \)的基数\( n \)进行归纳。

当\( n = 0 \)时，\( X = \emptyset, f(X) = \emptyset, (\#(f(X)) = 0) \leq (\#(X) = 0) \)，除此之外，如果\( f \)单射（虽然不单射也行），则\( \#(f(X)) = \#(X) = 0 \)，即\( n = 0 \)时命题成立。

归纳假设当\( n = k \)时成立，即：\( f(X) \)有限且\( \#(f(X)) \leq \#(X) \)，除此之外，如果\( f \)单射，则\( \#(f(X)) = \#(X) \)。

当\( n = k+\!+ \)时，因为\( X \)非空，故\( \exists x \in X \)，我们令\( C = X \setminus \{ x \} \)，根据引理3.6.9，\( C \)的基数为\( k \)，构造函数\( f': C \to Y, \forall c \in C, f'( c) = f( c) \)，此时根据归纳假设，有：

1. \( f'( C) \)有限且\( \#(f'( C)) \leq \#( C) \)。
2. 如果\( f' \)单射，则\( \#(f'( C)) = \#( C) \)

顺着第一点，\( f(X) = f( C) \cup f(\{ x \}) \)，根据\( f' \)的构造方法，有\( f'( C) = f( C) \)，故\( f( C) \)和\( f(\{ x \}) \)都是有限的，根据命题2，它们的并集\( f(X) \)也是有限的，且\( \#(f(X)) \leq (\#(f( C)) + \#(f(\{ x \})) = \#(f( C)) + 1) \)，又\( (\#(f'( C)) = \#(f( C))) \leq \#( C) \)，得\( \#(f(X)) \leq \#(f( C)) + 1 \leq (\#( C) + 1 = \#(X)) \)。

顺着第二点，如果\( f \)单射，则\( f' \)也单射，此时\( \#(f'( C)) = \#( C) \)，从而得到\( \#(f'( C)) + 1 = \#( C) + 1 \)，即\( \#(f(X)) = \#(X) \)。

综上，即\( n = k+\!+ \)时，命题也成立，归纳完毕。

证毕。

证明命题5：

因为\( X \)有限，记\( X \)的基数为\( n, n \in \mathbf{N} \)，则存在双射函数\( f: X \to \{ i \in \mathbf{N}, 1 \leq i \leq n \} \)，同理，记\( Y \)的基数为\( m, m \in \mathbf{N} \)，则存在双射函数\( g: X \to \{ i \in \mathbf{N}, 1 \leq i \leq m \} \)。

对\( X \)的基数\( n \)进行归纳。

当\( n = 0 \)时，\( X \times Y = \emptyset \)是有限的，且\( \#(X \times Y) = \#(\emptyset) = \#(X) \times \#(Y) = 0 \)，即\( n = 0 \)时成立。

归纳假设当\( n = k \)时成立，即：\( \#(X \times Y) \)有限，且\( \#(X \times Y) = \#(X) \times \#(Y) \)。

当\( n = k+\!+ \)时，因为\( X \)非空集，故\( \exists x \in X \)，此时，令\( C = X \setminus \{ x \} \)，根据引理3.6.9，\( C \)的基数为\( k \)，再根据归纳假设，有：\( C \times Y \)有限，且\( \#(C \times Y) = \#( C) \times \#(Y) \)。

因为\( C \times Y \)有限，记它的基数为\( d \)，则存在双射函数\( h: C \times Y \to \{ i \in \mathbf{N}, 1 \leq i \leq d \} \)，构造函数\( u: X \times Y \to \{ i \in \mathbf{N}, 1 \leq i \leq (\#( C) \times \#(Y) + \#(Y) = d + m) \} \)， \( \forall (a, b) \in X \times Y \)，当\( a \in C \)时，即\( (a, b) \in C \times Y \)时，令\( u(a, b) = h(a, b) \)，当\( a \notin C \)即\( a = x \)时，令\( u(a, b) = u(x, b) = d + g(b) \)。

下面证明\( u \)是双射函数。

先证单射：

\( \forall (a_0, b_0) \neq (a_1, b_1) \in X \times Y \)。

如果\( a_0, a_1 \)均\( \in C \)，则\( (a_0, b_0), (a_1, b_1) \in C \times Y \)，此时由于\( h \)单射，故\( h(a_0, b_0) \neq h(a_1, b_1) \)，而\( u(a_0, b_0) = h(a_0, b_0), u(a_1, b_1) = h(a_1, b_1) \)，故\( u(a_0, b_0) \neq u(a_1, b_1) \)。

如果\( a_0, a_1 \)有且仅有一个\( \notin C \)，不妨设\( a_0 \notin C, a_1 \in C \)，此时\( u(a_0, b_0) = d + g(b_0) > d \)，而\( u(a_1, b_1) = h(a, b) \leq d \)，故\( u(a_0, b_0) \neq u(a_1, b_1) \)。

如果\( a_0, a_1 \)均\( \notin C \)，即\( a_0 = a_1 = x \)，又\( (a_0, b_0) \neq (a_1, b_1) \)，可得\( b_0 \neq b_1 \)，此时\( u(a_0, b_0) = u(x, b_0) = d + g(b_0), u(a_1, b_1) = u(x, b_1) = d + g(b_1) \)，因为\( g \)单射，故\( g(b_0) \neq g(b_1) \)，从而有\( u(a_0, b_0) \neq u(a_1, b_1) \)。

综上，有\( u \)单射。

再证满射：

\( \forall i \in \{ i \in \mathbf{N}, 1 \leq i \leq d + m \} \)，

如果\( 1 \leq i \leq d \)，则\( i \in \{ i \in \mathbf{N}, 1 \leq i \leq d \} \)，又因为\( h \)满射，故\( \exists (a, b) \in C \times Y \)，使得\( h(a, b) = i \)，而\( (a, b) \in C \times Y \)，有\( a \in C \)，故\( u(a, b) = h(a, b) = i \)。

如果\( d < i \leq d + m \)，则令\( i1 = i - d \)，有\( i1 \in \{ i \in \mathbf{N}, 1 \leq i \leq m \} \)，又因为\( g \)满射，故\( \exists b \in Y \)，使得\( g(b) = i1 \)，此时有：\( i = d + i1 = d + g(b) \)，且\( u(x, b) = d + g(b) \)。

综上，有\( u \)满射。

再加上\( d + m = \#( C) \times \#(Y) + \#(Y) = (\#( C) + 1) \times \#(Y) = \#(X) \times \#(Y) \)，可得命题成立。

证毕。

证明命题6：

因为\( X \)有限，故存在双射函数\( f: X \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(X) \} \)，因为\( Y \)有限，存在双射函数\( g: X \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(Y) \} \)。

记\( X \)的基数为\( n \)，对\( X \)的基数\( n \)进行归纳。

当\( n = 0 \)，\( X = \emptyset \)，此时\( Y^X \)有且仅有一个函数，即\( \#(Y^X) = 1 = \#(Y)^0 = \#(Y)^{\#(X)} \)，故\( n = 0 \)时成立。

归纳假设当\( n = k \)时成立，即\( Y^X \)有限，且\( \#(Y^X) = \#(Y)^{\#(X)} \)。

当\( n = k+\!+ \)时，因为\( X \)非空集，故\( \exists x \in X \)，此时令\( C = X \setminus C \)，根据引理3.6.9，\( C \)的基数为\( k \)，再根据归纳假设，有\( Y^C \)有限，且\( \#(Y^C) = \#(Y)^{\#( C)} \)。

构造函数\( p: Y^{\{ x \}} \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(Y) \} \)， \( \forall (q: \{ x \} \to Y) \in Y^{\{ x \}} \)，令\( p(q) = g(x) \)，易证\( p \)双射，有\( \#(Y^{\{ x \}}) = \#(Y) \)。

\( \forall q \in Y^X \)，\( \forall X' \subseteq X \)，定义\( q \)在\( Y^{X'} \)中的对应函数为： \( (q_{X'}: X' \to Y) \in Y^{X'}, \forall x \in X', q_{X'}(x) = q(x) \) （该函数一定存在，因为\( Y^{X'} \)包含所有\( X' \to Y \)的函数）。

构造函数\( h: Y^X \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(Y)^{\#( C)} \times \#(Y) \} \)， \( \forall q \in Y^X \)，记其在\( Y^C \)中的对应函数为\( q_C: C \to Y \)，在\( Y^{\{ x \}} \)中对应的函数为\( q_{\{ x \}}: \{ x \} \to Y \)，因为\( Y^C \)有限，故存在双射函数\( a: Y^C \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(Y)^{\#( C)} \} \)，使得\( 1 \leq a(q_C) \leq \#(Y)^{\#( C)} \)，令\( h(q) = \#(Y)^{\#( C)} \times (p(q_{\{ x \}}) - 1) + (a(q_C) - 1) \) （注：想象将\( q \)映射到一个矩阵中的某个数中，每行有\( \#(Y)^{\#( C)} \)个元素， \( p(q_{\{ x \}}) - 1 \)决定行，\( a(q_C) - 1 \)决定列，也就是说行列是0-based的）。

证明\( h \)双射。

先证单射：

\( \forall q \neq w \in Y^X \)，记\( q \)在\( Y^C \)中的对应函数为\( q_C: C \to Y \)，在\( Y^{\{ x \}} \)中对应的函数为\( q_{\{ x \}}: \{ x \} \to Y \)，记\( w \)在\( Y^C \)中的对应函数为\( w_C: C \to Y \)，在\( Y^{\{ x \}} \)中对应的函数为\( w_{\{ x \}}: \{ x \} \to Y \)，分两种情况考虑：

如果\( p(q_{\{ x \}}) \neq p(w_{\{ x \}}) \)（注：即映射到矩阵的不同行），则\( h(q) = \#(Y)^{\#( C)} \times (p(q_{\{ x \}}) - 1) + (a(q_C) - 1) \)， \( h(w) = \#(Y)^{\#( C)} \times (p(w_{\{ x \}}) - 1) + (a(w_C) - 1) \)，再加上\( 1 \leq a(q_C) \leq \#(Y)^{\#( C)}, 1 \leq a(w_C) \leq \#(Y)^{\#( C)} \)，可得\( h(q) \neq h(w) \)。

如果\( p(q_{\{ x \}}) = p(w_{\{ x \}}) \)（注：即映射到矩阵的相同行，此时我们的目标是证明它们映射到不同列），此时因为\( p \)单射，故\( q_{\{ x \}} = w_{\{ x \}} \)，从而有\( \forall c \in \{ x \} \)，有\( c = x \)且\( q( c) = q_{\{ x \}}( c) = w_{\{ x \}}( c) = w( c) ) \)，但是既然\( p \neq w \)，则在它们的定义域\( X = C \cup \{ x \} \)中一定存在一个\( c_0 \in X, p(c_0) \neq w(c_0) \)，既然\( c_0 \notin \{ x \} \)，则\( c_0 \)一定\( \in C \)，这意味着\( \exists c_0 \in C, p_C(c_0) \neq w_C(c_0) \)，即\( p_C \neq w_C \)，再加上\( a \)单射，故\( a(q_C) \neq a(w_C) \)，从而有\( h(q) \neq h(w) \)。

综上，有\( h \)单射。

再证满射：

\( \forall i \in \{ i \in \mathbf{N}, 1 \leq i \leq \#(Y)^{\#( C)} \times \#(Y) \} \)，根据定理2.3.9，有\( m_0, r_0 \in \mathbf{N}, 0 \leq r_0 < \#(Y)^{\#( C)}, i = m_0 \times \#(Y)^{\#( C)} + r_0 \)，令\( m = m_0 + 1, r = r_0 + 1 \)。

因为\( 1 \leq r \leq \#(Y)^{\#( C)} \)，再加上\( a \)满射，故\( \exists f_0 \in Y^C, a(f_0) = r \)。

因为\( 1 \leq m \leq \#(Y) \)（否则如果\( m > \#(Y) \)，则\( i > \#(Y)^{\#( C)} \times \#(Y) \)，矛盾），再加上\( p \)满射，故\( \exists f_1 \in Y^{\{ x \}}, p(f_1) = m \)。

构造函数\( f_2: X \to Y \)，\( \forall c \in X \)，如果\( c \in C \)，则令\( f_2( c) = f_0( c) \)，如果\( c \notin C \)，即\( c = x \)，则令\( f_2( c) = f_1(x) = m \)。

可得\( f_0 \)是\( f_2 \)在\( Y^C \)的对应函数，\( f_1 \)是\( f_2 \)在\( Y^{\{ x \}} \)的对应函数，故\( h(f_2) = \#(Y)^{\#( C)} \times (p(f_1) - 1) + (a(f_0) - 1) = \#(Y)^{\#( C)} \times m_0 + r_0 = i \)。

综上，有\( h \)满射。

最后，\( \#(Y)^{\#( C)} \times \#(Y) = \#(Y)^{\#( C) + 1} = \#(Y)^{\#(X)} \)。

证毕。

练习3.6.5

题目：

Let \( A \) and \( B \) be sets. Show that \( A \times B \) and \( B \times A \) have equal cardinality by constructing an explicit bijection between the two sets. Then use Proposition 3.6.14 to conclude an alternate proof of Lemma 2.3.2.

引理2.3.2的内容：

(Multiplication is commutative). Let \( n, m \) be natural numbers. Then \( n \times m = m \times n \).

证明\( A \times B \)和\( B \times A \)基数相等：

构造函数\( f: A \times B \to B \times A, \forall (a, b) \in A \times B, f(a, b) = (b, a) \)。

现证明\( f \)双射。

先证单射：

\( \forall (a_0, b_0) \neq (a_1, b_1) \neq A \times B \)，有\( a_0 \neq a_1 \)或\( b_0 \neq b_1 \)，而\( f(a_0, b_0) = (b_0, a_0), f(a_1, b_1) = (b_1, a_1) \)，可得\( f(a_0, b_0) \neq f(a_1, b_1) \)。

再证满射：

\( \forall (b, a) \in B \times A \)，有\( (a, b) \in A \times B, f(a, b) = (b, a) \)。

综上，\( f \)双射，两者基数相等。

证毕。

使用定理3.6.14证明引理2.3.2：

令\( X \)为任意基数为\( n \)的集合，\( Y \)为任意基数为\( m \)的集合，根据定理3.6.14的命题5，有：

1. \( X \times Y \)有限， 且\( \#(X \times Y) = \#(X) \times \#(Y) = n \times m \)。
2. \( Y \times X \)有限， 且\( \#(Y \times X) = \#(Y) \times \#(X) = m \times n \)。

根据前面的证明，\( X \times Y \)和\( Y \times X \)基数相等，即\( n \times m = m \times n \)。

证毕。

练习3.6.6

题目：

Let \( A, B, C \) be sets. Show that the sets \( (A^B)^C \) and \( A^{B \times C} \) have equal cardinality by constructing an explicit bijection between the two sets. Conclude that \( (a^b)^c = a^{bc} \) for any natural numbers \( a, b, c \). Use a similar argument to also conclude \( a^b \times a^c = a^{b + c} \).

证明\( (A^B)^C \)和\( A^{B \times C} \)基数相等：

构造函数\( h: (A^B)^C \to A^{B \times C}, \forall (f: C \to A^B) \in (A^B)^C \)，构造函数\( (g: (B \times C) \to A) \in A^{B \times C} \)，\( \forall (b, c) \in B \times C \)，令\( g((b, c)) = (f( c))(b) \)，构造完函数\( g \)后，我们令\( h(f) = g \)。

现证明\( h \)双射。

先证明单射：

\( \forall f_0 \neq f_1 \in C \to A^B \)，有

1. 构造函数\( g_0: (B \times C) \to A \)，\( \forall (b, c) \in B \times C \)，令\( g_0((b, c)) = (f_0( c))(b) \)，此时根据\( h \)的构造方法，有：\( h(f_0) = g_0 \)。
2. 构造函数\( g_1: (B \times C) \to A \)，\( \forall (b, c) \in B \times C \)，令\( g_1((b, c)) = (f_1( c))(b) \)，此时根据\( h \)的构造方法，有：\( h(f_1) = g_1 \)。

假设\( g_0 = g_1 \)，则有\( \forall (b, c) \in B \times C, g_0((b, c)) = g_1((b, c)) \)，即\( (f_0( c))(b) = (f_1( c))(b) \)，这意味着：\( \forall c \in C \)，\( f_0( c) = f_1( c) ) \)，和\( f_0 \neq f_1 \)矛盾，故假设不成立，有\( g_0 \neq g_1 \)，即\( h \)单射。

再证明满射：

\( \forall g \in A^{B \times C} \)，构造函数\( (f: C \to A^B) \in (A^B)^C \)， \( \forall b \in B, \forall c \in C \)（即\( \forall (b, c) \in B \times C \)），令\( (f( c))(b) = g((b, c)) \)，此时，根据\( h \)的构造方法，有\( h(f) = g \)。

证毕。

证明\( (a^b)^c = a^{bc} \)：

令\( A \)为任意基数为\( a \)的集合，\( B \)为任意基数为\( b \)的集合， \( C \)为任意基数为\( c \)的集合。

根据定理3.6.14的命题6，有\( (A^B)^C \)有限，基数为\( (a^b)^c \)。

根据定理3.6.14的命题5，有\( B \times C \)有限，基数为\( b \times c \)。

再根据定理3.6.14的命题6，有\( A^{B \times C} \)有限，基数为\( a^{b \times c} \)。

根据前面的证明，有\( (A^B)^C \)和\( A^{B \times C} \)基数相等，即\( (a^b)^c = a^{b \times c} \)。

证毕。

证明如果\( B \cap C = \emptyset \)，则\( A^B \times A^C \)和\( A^{B \cup C} \)基数相等：

构造函数\( h: (A^B \times A^C) \to A^{B \cup C}, \forall (f_0, f_1) \in (A^B \times A^C) \)，构造函数\( (g: (B \cup C) \to A) \in A^{B \cup C} \)，\( \forall x \in B \cup C \)，要么\( x \in B \)或\( x \in C \)，不可能两者同时成立，因为\( B \cap C = \emptyset \)，此时，如果\( x \in B \)，则令\( g(x) = f_0(x) \) ，如果\( x \in C \)，则令\( g( c) = f_1( c) \)，构造完\( g \)后，我们令\( h((f_0, f_1)) = g \)。

现证\( h \)双射。

先证\( h \)单射：

\( \forall (f_0, f_1) \neq (f_2, f_3) \in (A^B \times A^C) \)，有\( f_0 \neq f_2 \)或\( f_1 \neq f_3 \)。

1. 构造函数\( (g_0: (B \cup C) \to A) \in A^{B \cup C} \)，\( \forall x \in B \cup C \)，如果\( x \in B \)，则令\( g_0(x) = f_0(x) \)，如果\( x \in C \)，则令\( g_0( c) = f_1( c) \)，根据\( h \)的构造方法，有\( h((f_0, f_1)) = g_0 \)。
2. 构造函数\( (g_1: (B \cup C) \to A) \in A^{B \cup C} \)，\( \forall x \in B \cup C \)，如果\( x \in B \)，则令\( g_1(x) = f_2(x) \)，如果\( x \in C \)，则令\( g_1( c) = f_3( c) \)，根据\( h \)的构造方法，有\( h((f_2, f_3)) = g_1 \)。

假设\( g_0 = g_1 \)，则有：

1. \( \forall b \in B \)，有\( g_0(b) = g_1(b) \)，即\( f_0 = f_2 \)。
2. \( \forall c \in C \)，有\( g_0( c) = g_1( c) \)，即\( f_1 = f_3 \)。

此时有\( f_0 = f_2 \)且\( f_1 = f_3 \)，这和\( f_0 \neq f_2 \)或\( f_1 \neq f_3 \)矛盾，故假设不成立，有\( g_0 \neq g_1 \)，即\( h((f_0, f_1)) \neq h((f_2, f_3)) \)，也就说\( h \)单射。

再证\( h \) 满射：

\( \forall g \in A^{B \cup C} \)：

1. 构造函数\( f_0: B \to A \)，\( \forall b \in B \)，令\( f_0(b) = g(b) \)。
2. 构造函数\( f_1: C \to A \)，\( \forall c \in C \)，令\( f_1( c) = g( c) \)。

根据\( h \)的构造方法，有\( h(f_0, f_1) = g \)。

综上，可得\( h \)满射。

证毕。

证明\( a^b \times a^c = a^{b + c} \)：

令\( A \)为任意基数为\( a \)的集合，\( B \)为任意基数为\( b \)的集合， \( C \)为任意基数为\( c \)的集合，要求\( B \cap C = \emptyset \)。

根据定理3.6.14的命题6，有\( A^B, A^C \)均有限，基数分别为\( a^b, a^c \)。

根据定理3.6.14的命题5，有\( A^B \times A^C \)有限，基数为\( a^b \times a^c \)。

根据定理3.6.14的命题2，有\( B \cup C \)有限，基数为\( b + c \)。

再根据定理3.6.14的命题5，有\( A^{B \cup C} \)有限，基数为\( a^{b + c} \)

根据前面的证明，有\( A^B \times A^C \)和\( A^{B \cup C} \)基数相等，即\( a^b \times a^c = a^{b + c} \)。

证毕。

练习3.6.7

题目：

Let \( A \) and \( B \) be sets. Let us say that \( A \) has lesser or equal cardinality to \( B \) if there exists an injection \( f: A \to B \) from \( A \) to \( B \). Show that if \( A \) and \( B \) are finite sets, then \( A \) has lesser or equal cardinality to \( B \) if and only if \( \#(A) \leq \#(B) \).

注：这是两个不同的对“基数小于或等于”的定义，一个适用于所有集合，一个仅适用于有限集合，该定理目的是检测两个定义是否兼容。

证明：

因为\( A \)有限，故存在双射函数\( f: A \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \} \)。因为\( B \)有限，故存在双射函数\( g: B \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(B) \} \)。

必要性：

如果\( A \)的基数小于或等于\( B \)的基数，则存在单射函数\( h: A \to B \)，此时假设\( \#(A) > \#(B) \)，我们要推出矛盾，从而否定假设：

令函数\( d_0: \{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \} \to B = h \circ f^{-1} \)，因为\( f^{-1}, h \)都是单射函数，根据练习3.3.2有\( d_0 \)也是单射函数。令函数\( d_1: \{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \} \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(B) \} = g \circ d_0 \)，因为\( d_0, g \)都是单射函数，根据练习3.3.2有\( d_1 \)也是单射函数。

\( d_1 \)单射，根据定理3.6.14的命题4，有\( \#(d_1(\{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \})) = \#(\{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \}) = \#(A) \)，然而\( d_1(\{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \}) \subseteq \{ i \in \mathbf{N}, 1 \leq i \leq \#(B) \} \)，根据定理3.6.14的命题3，有\( \#(d_1(\{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \})) \leq \#(B) \)，然而\( \#(A) > \#(B) \)，故\( d_1(\{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \}) = \#(A) \) 和\( d_1(\{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \}) \leq \#(B) \)是不可能同时成立的，矛盾，假设不成立，有\( \#(A) \leq \#(B) \)。

充分性：

如果\( \#(A) \leq \#(B) \)，我们的目标是证明存在\( A \)到\( B \)的单射函数。

构造函数\( d_0: \{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \} \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(B) \} \)， \( \forall i \in \{ i \in \mathbf{N}, 1 \leq i \leq \#(A) \} \)，令\( d_0(i) = i \)，易证\( d_0 \)是单射函数。

令函数\( d_1: A \to \{ i \in \mathbf{N}, 1 \leq i \leq \#(B) \} = d_0 \circ f \)，因为\( d_0, f \)都是单射函数，故根据练习3.3.2，有d_1为单射函数。令函数\( d_2: A \to B = g^{-1} \circ d_1 \)，因为\( g^{-1}, d_1 \)都是单射函数，故根据练习3.3.2，有\( d_2 \)为\( A \)到\( B \)的单射函数，即\( A \)的基数小于或等于\( B \)的基数。

证毕。

练习3.6.8

题目：

Let \( A \) and \( B \) be sets such that there exists an injection \( f: A \to B \) from \( A \) to \( B \) (i.e., \( A \) has lesser or equal cardinality to \( B \)). Show that there then exists a surjection \( g: B \to A \) from \( B \) to \( A \). (The converse to this statement requires the axiom of choice; see Exercise 8.4.3.)

证明：

如果\( A \)为空集，则有且仅有一个函数\( g: B \to A \)且\( g \)满射。

如果\( A \)不为空集，则\( \exists x \in A \)，此时，我们构造函数\( g: B \to A, \forall b \in B \)，如果\( \exists a \in A \)，使得\( f(a) = b \)，则令\( g(b) = a \)，如果\( \nexists a \in A \)，使得\( f(a) = b \)，则令\( g(b) = x \)。现在证明\( g \)满射：\( \forall a \in A \)，有\( f(a) \ in B \)，根据\( g \)的构造方法，有\( g(f(a)) = a \)，即\( g \)满射。

证毕。

练习3.6.9

题目：

Let \( A \) and \( B \) be finite sets. Show that \( A \cup B \) and \( A \cap B \) are also finite sets, and that \( \#(A) + \#(B) = \#(A \cup B) + \#(A \cap B) \).

证明：

\( A \cup B \)有限在练习3.6.4已经证明过了。

而\( (A \cap B) \subseteq A \)，根据定理3.6.14的命题3，有\( A \cap B \)有限。

下面证明\( \#(A) + \#(B) = \#(A \cup B) + \#(A \cap B) \)：

对\( A \cap B \)的基数进行数学归纳。

当\( n = 0 \)时，即\( A \cap B = \emptyset \)，此时根据定理3.6.14的命题2，有\( \#(A \cup B) = \#(A) + \#(B) \)，整理一下，有\( \#(A) + \#(B) = \#(A \cup B) + 0 = \#(A \cup B) + \#(A \cap B) \)，也就说\( n = 0 \)时成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，因为\( A \cap B \)非空，故\( \exists x \in A \cap B \)，此时令\( C = (A \cap B) \setminus \{ x \}, A' = A \setminus \{ x \}, B' = B \setminus \{ x \} \)，可得\( C, A, B \)的基数分别为\( k, \#(A) - 1 \#(B) - 1 \) 以及\( C = A' \cap B', A' \cup B' = (A \cup B) \setminus \{ x \} \)，根据归纳假设，有： \( \#(A') + \#(B') = \#(A' \cup B') + \#(A' \cap B') = \#((A \cup B) \setminus \{ x \}) + \#( C) = \#(A \cup B) - 1 + k \)，进一步可得\( \#(A) + \#(B) = \#(A') + 1 + \#(B') + 1 = \#(A \cup B) + k + 1 = \#(A \cup B) + \#(A \cap B) \)。

综上，有\( n = k+\!+ \)时，成立，归纳完毕。

证毕。

练习3.6.10

题目：

Let \( A_1 , \dots , A_n \) be finite sets such that \( \#(\bigcup_{i \in \{ 1 , \dots , n \}} A_i) > n \). Show that there exists \( i \in \{ 1, \dots , n \} \) such that \( \#(A_i) \geq 2 \). (This is known as the pigeonhole principle.)

证明：

对\( n \)进行数学归纳。

当\( n = 0 \)时，\( \bigcup_{i \in \{ 1 , \dots , n \}} A_i = \emptyset \)，故前提条件\( \#(\bigcup_{i \in \{ 1 , \dots , n \}} A_i) = 0 > 0 \)不成立，命题直接成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，如果\( \#(\bigcup_{i \in \{ 1 , \dots , n \}} A_i) > n \)，此时假设\( \forall 1 \leq i \leq n \)，有\( A_i < 2 \)，可得\( \#(\bigcup_{i \in \{ 1 , \dots , k \}} A_i) > k \)，根据归纳假设，有\( \exists i_0 \in \{ 1, \dots, k \} \)，使得\( \#(A_{i_0}) \geq 2 \)，然而这与“\( \forall 1 \leq i \leq n \)，有\( A_i < 2 \)”是矛盾的，故假设不成立，有\( \exists i_1 \in \{ 1, \dots, n \} \)，使得\( \#(A_{i_1}) \geq 2 \)。

综上，当\( n = k+\!+ \)时成立，归纳完毕。

证毕。

参考文章

ANALYSIS I EXERCISES