\[ \def\ran{\text{ran}} \def\FUN{\mathsf{FUN}} \]
本节知识点
良序：设 \((A, \le)\) 为全序集，如果任意 \(A\) 的非空子集都有 \(\le\)-极小元，则称 \((A, \le)\) 为良序集。
设 \(A\) 为任意的集合，我们称 \(A^+ = A \cup \set{A}\) 为 \(A\) 的后继，\(A\) 为 \(A^+\) 的前趋。
自然数的定义：\(0 = \emptyset, 1 = 0^+\)。
无穷公理：所有自然数组成的整体是集合，记为 \(\omega\)。
传递集合：设 \(A\) 是一个集合，如果 \(A\) 的任意元素都是 \(A\) 的子集，则称 \(A\) 是传递集合。
三歧性：\(\forall x, y \in A. x \in y \lor x = y \lor y \in x\)。
具有三歧性的传递集合叫做序数。每个自然数都是序数，\(\omega\) 是序数。
如果 \(\alpha\) 存在前趋，称 \(\alpha\) 为后继序数。不是后继序数的非零序数称为极限序数。
讲义 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 \mapsto \omega^{++}\)，其中 \(f(0) = \omega, f(1) = \omega^{+}, f(n) = n - 2(n \ge 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\) 为两个集合，试证明：
（1）如果 \(A\) 有穷，\(B \preceq A\)，则 \(B\) 也是有穷集合。
证明：\(A\) 是有穷集合
\(\Rightarrow \exists n \in \omega. 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}\) 是可数的。
TODO：这道题用到了构造 \(A \times B \mapsto \omega\) 的函数，需要记住。
- 证明：引理：两个可数集合的笛卡尔积是可数集合。对于可数集合 \(A, B\)，\(f: A \mapsto \omega, g: B \mapsto \omega\) 为单射。构造 \(h(x, y) = \frac{(f(x)+g(y))\times(f(x)+g(y)+1)}{2} + g(y)\) ，则 \(h:A\times B \mapsto \omega\) 为单射。因此 \(A \times B\) 可数。
下面进行归纳：
\(k = 0\) 时，\(\omega^0 = \set{\emptyset}\) 显然是可数集合。
\(k = 1\) 时，构造 \(f_1: \omega \to \omega\)，\(f_1(x) = x\) 为双射，可知 \(\omega^1\) 为可数集合。
由 \(\omega^k\) 为可数集合和引理可知，\(\omega^{k+1}=\omega^k \times \omega\) 为可数集合。
因此，对任意 \(k \in \omega\) 有，\(\omega^k\) 都是可数集合。
\(Q.E.D.\)
- 证明：由定理 0.2.7，可数多个可数集合的并仍然是可数集合，因此 \(\bigcup \set{\omega^k | k \in \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\) 为序数集合，证明：
（1）如果 \(\alpha\) 是 \(S\) 的最大元，则 \(\alpha = \bigcup S\)；
（2）如果 \(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\)。
（1）\(\alpha\) 是极限序数，当且仅当 \(\bigcup \alpha = \alpha\)；
（2）如果 \(\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. \forall x \in \beta. x \in \bigcup \alpha\) 因此 \(\beta \subseteq \bigcup \alpha\)。又由传递性，\(\beta \subseteq \alpha\)，因此 \(\beta \in \bigcup \alpha\)。因此 \(\alpha \subseteq \bigcup \alpha\)。（TODO：这一步有点问题）
因此 \(\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\) 为后继序数（TODO：这一步怎么来的？）。设 \(\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.\)
