\[ \def\ran{\text{ran}} \def\FUN{\mathsf{FUN}} \]
讲义 0.2.18 数学归纳法
习题 1：证明设 \(A\) 为传递集合，则 \(A^+\) 也是传递集合。
证明：由 \(A\) 的传递性可知，\(\forall a \in A, a \subseteq A\)。取任意 \(b \in A^+\)，只要证明 \(b \subseteq A^+\)。
\(A^+\) 是 \(A\) 的后继（此处右上角的 \(+\) 并不是传递闭包），即 \(A^+ = A \cup \set{A}\)。
- 若 \(b \in A\) 则 \(b \subseteq A \subseteq A^+\)；
- 若 \(b \notin A\) 则 \(b = A\)，此时 \(b \subseteq A^+\) 成立。
\(Q.E.D.\)
习题 2：证明对任意自然数 \(n\)，都有 \(0 = n\) 或 \(0 \in n\)。
证明：对 \(n\) 使用数学归纳法。
- 若 \(n = 0\)，显然命题 \(0 = n\) 成立；
- 若 \(n = 1\)，即 \(n = \set{\emptyset, \set{\emptyset}}\)，显然命题 \(0 \in n\) 成立；
- 若 \(n = k(k > 1)\) 时命题 \(0 \in n\) 成立，则 \(n = k + 1\) 时，\(n = k \cup \set{k}\)，显然命题 \(0 \in n\) 成立。
因此，对任意自然数 \(n\)，都有 \(0 = n\) 或 \(0 \in n\)。
\(Q.E.D.\)
讲义 0.2.19 有穷集合和无穷集合
习题 1: 证明 \(\omega^{++}\) 与 \(\omega\) 等势。
证明：构造 \(f: \omega^{++} \to \omega\)，其中 \(f(n) = n - 2\)。显然 \(f\) 是双射，因此 \(\omega^{++}\) 与 \(\omega\) 等势。
\(Q.E.D.\)
习题 2：假设 \(A, B, A_1, B_1\) 为满足如下条件的集合：
- \(A \cap A_1 = \emptyset, B \cap B_1 = \emptyset\)；
- \(A \sim B, A_1 \sim B_1\)；
证明：\(A \cup A_1 \sim B \cup B_1\)。
证明：由题意得，\(\exists f: A \to B, g: A_1 \to B_1\)，\(f,g\) 为双射。
构造 \(h: A \cup A_1 \to B \cup B_1\)：
\[ h(x) = \left\{\begin{matrix} f(x) & \text{if } x \in A \\ g(x) & \text{if } x \in A_1\\ \end{matrix}\right. \]
显然，\(h\) 为双射。因此 \(A \cup A_1 \sim B \cup B_1\)。
\(Q.E.D.\)
习题 3：设 \(A, B\) 为两个集合，证明：
- \(A \preceq B\) 当且仅当 \(A\) 与 \(B\) 的某个子集等势。
证明：先证充分性。若 \(A \preceq B\)，则 \(\exists f : A \to B\) 是一个单射。令 \(C = \ran(f) \subseteq B\)，则 \(f: A \to C\) 是双射，因此 \(A \sim C\)。
再证必要性。若 \(\exists D \subseteq B. A \sim D\)，则 \(\exists g: A \to D\) 为双射。因此 \(g: A \to B\) 是单射，故 \(A \preceq B\)。
\(Q.E.D.\)
讲义 0.2.21 有穷集合
习题：设 \(A, B\) 为两个集合，试证明：
- 如果 \(A\) 有穷，\(B \preceq A\)，则 \(B\) 也是有穷集合。
证明：\(A\) 是有穷集合
\(\Rightarrow \exists n \in \mathbb{N}. A \preceq n\)
\(\Rightarrow B \preceq n\)
\(\Rightarrow B\) 是有穷集合。
\(Q.E.D.\)
讲义 0.2.22 可数集合
习题 1：设 \(A, B\) 为两个可数集合，且 \(A, B\) 不相交，即 \(A \cap B = \emptyset\)。证明：\(A \cup B\) 也是可数的。
证明：\(A, B\) 可数意味着 \(\exists f: \omega \to A, g: \omega \to B\)，\(f, g\) 为满射。构造
\[ h(n) = \left\{\begin{matrix} f(\frac{n}{2}) & \text{if } n \text{ 为偶数} \\ g(\frac{n-1}{2}) & \text{if } n \text{ 为奇数} \\ \end{matrix}\right. \]
显然 \(h: \omega \to A \cup B\) 为满射。因此 \(A \cup B\) 可数。
\(Q.E.D.\)
习题 2：证明：
对任意 \(k \in \omega\) 有，\(\omega^k\) 都是可数集合（约定 \(\omega^0 = \set{\emptyset}, \omega^1 = \omega\)）；
集合 \(\bigcup \set{\omega^k | k \in \omega}\) 是可数的。
- 证明：\(k = 0\) 时，\(\omega^0 = \set{\emptyset}\) 显然是可数集合。
\(k = 1\) 时，构造 \(f_1: \omega \to \omega\)，\(f_1(x) = x\) 为双射，可知 \(\omega^1\) 为可数集合。
对 \(k \in \omega\) 归纳。若 \(k = n(n \ge 1)\) 时，命题成立，即 \(\exists f_n: \omega^n \to \omega\) 为双射，则当 \(k = n + 1\) 时，\(\omega^k = \omega^n \times \omega\)，构造 \(f_{n + 1}(x, y) = \frac{1}{2}((f_n(x)+y)^2 + f_n(x) + 3y)\)，显然 \(f_{n+1}: \omega^{n+1} \to \omega\) 为双射，因此 \(\omega^{n+1}\) 也可数，命题成立。
因此，对任意 \(k \in \omega\) 有，\(\omega^k\) 都是可数集合。
\(Q.E.D.\)
- 证明：令 \(T = \bigcup\set{\omega^k | k \in \omega}\)。构造
\[ g(t) = \left\{\begin{matrix} 0 & \text{if } t \in \omega^0 \\ kf_1(t) + 1 & \text{if } t \in \omega^1 \\ \dots \\ kf_n(t) + k & \text{if } t \in \omega^k \\ \dots \end{matrix}\right. \]
显然 \(g: T \to \omega\) 为双射，即 \(T\) 和 \(\omega\) 等价。
\(Q.E.D.\)
讲义 0.2.24 不可数集合
习题 1：令 \(\FUN(\omega, \omega)\) 表示所有从 \(\omega\) 到 \(\omega\) 的映射组成的集合，即 \(\FUN(\omega, \omega) = \set{f|f: \omega \to \omega 为映射}\)，用对角线方法证明 \(\FUN(\omega, \omega)\) 是不可数的。
证明：使用反证法。假设 \(\FUN(\omega, \omega)\) 可数，不妨设 \(\FUN(\omega, \omega) = \set{f_0, f_1, f_2, \dots}\)。
构造新映射 \(f: \omega \to \omega\)，\(f(n) = f_n(n) + 1\)。
- 若 \(f \notin \FUN(\omega, \omega)\)，与 \(\FUN(\omega, \omega)\) 的定义相矛盾；
- 若 \(f \in \FUN(\omega, \omega)\)，但 \(\forall n \in \mathbb{N}. f(n) \ne f_n(n)\)，矛盾。
假设不成立。原命题成立。
\(Q.E.D.\)
讲义 0.2.25 序数
习题：设 \(S\) 为序数集合，证明：
如果 \(\alpha\) 是 \(S\) 的最大元，则 \(\alpha = \bigcup S\)；
如果 \(S\) 中无最大元，则对任何的 \(\beta\) 属于 \(S\)，有 \(\beta < \bigcup S\)。
- 证明：\(\alpha\) 是 \(S\) 的最大元，由三岐性得，\(\forall \beta \in S. \beta = \alpha \vee \beta \in \alpha\)。
由 \(S\) 是传递集合，\(\forall \beta \in S. \beta \subseteq \alpha\)，即 \(S\) 中任意元素都是 \(\alpha\) 的子集，因此 \(\bigcup S \subseteq \alpha\)。
由 \(\alpha \in S\) 得，\(\alpha \subseteq \bigcup S\)。
因此 \(\alpha= \bigcup S\)。
\(Q.E.D.\)
- 证明：由传递集合得，\(\forall \beta \in S. \beta \subseteq \bigcup S\)。
\(S\) 中没有最大元，即 \(\forall \beta \in S. \exists \gamma \in S. \beta < \gamma\)，因此 \(\beta \ne \bigcup S\)。
因此，\(\beta < \bigcup S\)。
\(Q.E.D.\)
讲义 0.2.26 超穷归纳法
习题：设 \(\alpha, \beta\) 为序数，且 \(\alpha \ne 0\)。
\(\alpha\) 是极限序数，当且仅当 \(\bigcup \alpha = \alpha\)；
如果 \(\beta \in \alpha\)，且 \(\beta\) 是 \(\alpha\) 的最大元，则 \(\alpha = \beta^+\)。
- 证明：
先证必要性（\(\alpha\) 是极限序数 \(\Rightarrow \bigcup \alpha = \alpha\)）：如果 \(\alpha\) 是极限序数，那么 \(\forall \beta \in \alpha. \beta < \alpha\)，并且 \(\alpha\) 中没有最大元。由 \(\alpha\) 的传递性可知，\(\alpha\) 中任意元素都是其子集，因此 \(\bigcup \alpha \subseteq \alpha\)。
\(\forall \beta \in \alpha. \beta \subseteq \alpha\)，因此 \(\beta \in \bigcup \alpha\)。因此 \(\alpha \subseteq \bigcup \alpha\)。
因此 \(\bigcup \alpha = \alpha\)。
再证充分性（\(\bigcup \alpha = \alpha \Rightarrow \alpha\) 是极限序数）：假设 \(\bigcup \alpha = \alpha\)。这意味着 \(\alpha\) 是由它自身的所有元素组成的，并且对于每个 \(\beta \in \alpha\)，都有 \(\beta \subset \alpha\)。
如果 \(\alpha\) 不是极限序数，则 \(\alpha\) 中应有一个最大元 \(\gamma\)，使得 \(\alpha = \gamma^+\)。由上一题结论，\(\bigcup \alpha = \gamma\)，但这与假设 \(\bigcup \alpha = \alpha\) 矛盾。因此，\(\alpha\) 不能有最大元。
因此，\(\alpha\) 必须是极限序数。
\(Q.E.D.\)
- 证明：由 \(\beta\) 是 \(\alpha\) 中最大元，\(\forall \gamma \in \alpha. \gamma \le \beta\)，且 \(\alpha\) 为后继序数。设 \(\alpha = \beta_0^+ = \beta_0 \cup \set {\beta_0}\)，只要证明 \(\beta = \beta_0\)。
若 \(\beta < \beta_0\)，与 \(\beta\) 是 \(\alpha\) 中最大元矛盾；
若 \(\beta_0 < \beta\)，则 \(\alpha = \beta_0 \le \beta\)，与 \(\beta \in \alpha\) 矛盾。
因此，\(\beta = \beta_0\)。
\(Q.E.D.\)
