前序知识

[B2-1] 二元关系

[B3] 自然数

回顾

在冯·诺依曼自然数定义中，我们知道 $0 = \varnothing$ 并通过后继运算 $A ^+ := A \cup \{ A \}$ 得到 $1, 2, \dots$ 等自然数。

（引用）

后继 (successor) 的定义：对于集合 $A$，$A$ 的后继为：$A^+ = A \cup \{ A \}$。

这样，有 $A \sube A^+$ 和 $A \in A^+$。

其实就是套娃。比如：

$$ \begin{align*}

\empty^+ &= \{ \empty \} \\

\empty^{++} &= \{ \empty, \{ \empty \} \} \\

\empty^{+++} &= \{ \empty, \{ \empty \}, \{ \empty, \{ \empty \} \} \} \\

\empty^{++++} &= \{ \empty, \{ \empty \}, \{ \empty, \{ \empty \} \}, \{ \empty, \{ \empty \}, \{ \empty, \{ \empty \} \} \} \} \\

& \ \ \vdots

\end{align*} $$

也把求后继的操作记为 $\sigma$。

$\forall x \in A^+$，一定有 $x \in A$ 或者 $x = A$。

这个定理是关于自然数重要的分类讨论基础。

证明：因为 $A^+ = A \cup \{ A \}$，一个可能是 $x$ 来源于 $A$ 的部分也就是 $x \in A$，否则 $x$ 来源于 $\{ A \}$ 的部分也就是 $x = A$。

自然数的定义：把这些记号定义为自然数：

$$ \begin{align*}

0 &= \empty \\

1 &= 0^+ = \empty^{+} = \{ 0 \} \\

2 &= 1^+ = \empty^{++} = \{ 0, 1 \} \\

3 &= 2^+ = \empty^{+++} = \{ 0, 1, 2 \} \\

& \ \ \vdots \\

n &= \{ 0, 1, 2, \cdots, n-1\}

\end{align*} $$

其中 $\emptyset$ 是空集。

具体而言如图。

可以知道，如果 $n$ 是自然数，$\forall x \in n$，$x$ 也是自然数。

证明：归纳法，$n = 0$ 时空真命题成立；假设 $n \in \N$ 时假设成立想要证 $n^+$ 也成立：$\forall x \in n^+$，因 $n^+ = n \cup \{ n \}$ 分类讨论 $x$ 来源：①$x \in n$，那么根据归纳假设有 $x$ 是自然数；② $x = n$，根据 $n$ 是自然数 $x$ 是自然数。

记录 $\N = \{ 0, 1, 2, \dots \}$。

一、序数的定义

1. 传递集的定义

【传递集的定义】一个集合 $X$ 是传递集，当且仅当：$\forall x \in X$，$\forall y \in x$ 都有 $y \in X$。
【所有自然数都是传递集】如题。
证：归纳法。
- $n = 0$ 当然是传递的（空真命题）。
- 假设 $n \in \N$ 是传递的，只需要证 $n^+$ 是传递的。根据 $n^+ = n \cup \{ n \}$，对于 $\forall x \in n^+$，可分类讨论 $x$ 的来源，下面两者一定至少有一者为真：$x \in n$ 和 $x = n$。
  1. 如果 $x \in n$，根据 $n$ 是传递的有 $\forall y \in x$ 都有 $y \in n$。又 $n \subseteq n^+$，得到 $y \in n^+$。
  2. 如果 $x = n$，那么 $\forall y \in x$ 即 $y \in n$，根据 $n \subseteq n^+$ 都有 $y \in n^+$。
  - 因而 $\forall y \in x$ 都有 $y \in n^+$。即 $n^+$ 是传递的。

2. 序数的定义

【序数的集合论定义】一个集合 $\alpha$ 是序数，当且仅当：
1. $\alpha$ 是传递集。
2. $\in$ 关系在 $\alpha$ 上构成严格良序。
【所有自然数都是序数】如题。
证：我们已经知道自然数都是传递的，只需证 $\in$ 关系对任何 $n \in \N$ 构成严格良序。这需要证明 $\in$ 符合严格良序的定义：①反自反性；②传递性；③严格全序；④严格良序。
1. 反自反性（$\forall x \in n$，$\neg (x\in x)$ ）。其实根据 ZFC 公理可以排除，不过我们还是用上面定义直接证。数学归纳法。
  1. 当 $n = 0$，空真命题成立。
  2. 假设 $n \in \N$ 上有 $\forall x \in n$，$\neg (x\in x)$ ，想要证 $\forall x \in n^+$，$\neg (x\in x)$ 。反证法假设 $x \in x$。由于 $n^+ = n \cup \{ n \}$，分类讨论 $x$ 的来源。
    1. 如果 $x \in n$，根据归纳假设有 $\neg (x\in x)$ 。发生矛盾。
    2. 如果 $x = n$，代入 $x \in x$ 的后者得到 $x \in n$，根据归纳假设有 $\neg (x\in x)$ 。发生矛盾。
    - 分类讨论结束，都有矛盾。反证法结束得到 $\neg (x\in x)$ 。
  - 归纳假设结束。
2. 传递性（$\forall x, y, z \in n$，$(x \in y) \wedge (y \in z) \rightarrow (x \in z)$）。对于任意自然数 $\forall n \in \N$，根据传递性性质可得「$\forall x \in n$，$\forall x' \in x$ 都有 $x' \in n$」。那么 $\forall x, y, z \in n$ 且 $x \in y$ 和 $y \in z$ 成立，根据「如果 $n$ 是自然数，$\forall x \in n$，$x$ 也是自然数」，$z$ 是自然数，根据传递性性质从 $y \in z$ 和 $x \in y$ 得到 $x \in z$。
3. 严格全序（$\forall x, y \in n$，$(x \neq y) \rightarrow (x \in y \vee y \in x)$）。数学归纳法。
  1. 当 $n = 0$，空真命题成立。
  2. 假设 $n \in \N$ 上有 $\forall x, y \in n$，$(x \neq y) \rightarrow (x \in y \vee y \in x)$，想要证 $\forall x, y \in n^+$，$(x \neq y) \rightarrow (x \in y \vee y \in x)$。分类讨论 $x, y$ 的来源。
    1. 如果 $x, y \in n$，根据归纳假设立即得到目标。
    2. 如果 $x \in n$ 且 $y = n$，马上得到 $x \in y$ 得到目标。
    3. 如果 $x = n$ 且 $y \in n$，马上得到 $y \in x$ 得到目标。
    4. 如果 $x = y = n$，前件为假得到目标。
    - 分类讨论结束，都得到目标。
  - 归纳假设结束。
4. 根据有限全序集是良序集，严格良序成立。也可以手动证明：严格良序（$\forall S \subseteq n$ 使得 $S \neq \varnothing$，都有 $\exists m \in S$ 使得 $\forall s \in S, \, m \neq s \to m \in s$）。数学归纳法。
  1. 当 $n = 0$，空真命题成立。
  2. 假设 $n \in \N$ 上有 $\forall S \subseteq n$ 使得 $S \neq \varnothing$，都有 $\exists m \in S$ 使得 $\forall s \in S, \, m \neq s \to m \in s$。想要证 $\forall S \subseteq n^+$ 使得 $S \neq \varnothing$，都有 $\exists m \in S$ 使得 $\forall s \in S, \, m \neq s \to m \in s$。分类讨论 $S \cap n$ 是否等于 $\varnothing$。
    1. 如果 $S \cap n = \varnothing$，根据 $n^+ = n \cup \{ n \}$，只能有 $S = \{ n \}$。当然 $n$ 就是这个最小元。
    2. 如果 $S \cap n \neq \varnothing$，我们记 $S' = S \cap n \subseteq n$，根据归纳假设取 $m \in S'$ 使得 $\forall s' \in S', m \neq s' \to m \in s'$。对 $\forall s \in S$，记得 $S \subseteq n^+$ 有 $s \in n^+$，因而可以分类讨论 $s$ 来源：
      
      如果 $s \in n$，那么 $s \in S \cap n = S'$，直接导出 $m \neq s \to m \in s$。
      
      如果 $s = n$，那么 $m \in S' \subseteq n = s$ 得到 $m \in s$ 即后件为真。
      
      分类讨论 $s$ 来源结束，都得到 $m \neq s \to m \in s$，因而 $m$ 就是最小元。
    - 分类讨论 $S \cap n$ 结束，都得到 $S$ 存在最小元。
  - 归纳假设结束。

二、序数的性质 [🚧]

TODO:

来看看这段聊天

【序数的元素仍然是序数】如果 $\alpha$ 是序数，并且 $\beta \in \alpha$，那么 $\beta$ 也是序数。证略。
【序数不属于自身】如果 $\alpha$ 是序数，那么 $\alpha \notin \alpha$。
【序数的性质①引理】对于序数 $\alpha$ 及一个传递集 $T$，如果 $T \subseteq \alpha$，那么 $T \in \alpha \vee T = \alpha$。
证明
- $\Rightarrow$：
【序数的性质①】对于序数 $\alpha$ 和序数 $\beta$，有三岐性，下面三者必定成立且仅成立一者：① $\alpha = \beta$；② $\alpha \in \beta$；③ $\beta \in \alpha$。
证明
【序数集合的上确界】对于序数 $\alpha$，有：$\sup \alpha = \bigcup \alpha$。这里的 $\sup$ 是对于良序 $\in$ 而言的。
证明：需要证明 $\bigcup \alpha$ 是唯一的最小上界。具体而言，需要证明：①上界性；②最小性。
1. 上界性即 $\forall x \in \alpha, x \in \bigcup \alpha$。我们想先证明 $\bigcup \alpha$ 也是序数。
【极限序数的定义】对于序数 $\lambda$ 且 $\lambda \neq 0$，如果不存在使得 $\lambda = \alpha^+$ 的序数 $\alpha$，那么称 $\lambda$ 为极限序数；否则称 $\lambda$ 为后继序数。
- 【极限序数的充要条件】对于序数 $\lambda$ 且 $\lambda \neq 0$，$\lambda$ 为极限序数的充要条件为 $\lambda = \bigcup \lambda$。