序数

序数是自然数的推广。

直观理解

仅供参考

顾名思义，序数是用来排序的号码。最小的序数是 0，因而我们从 0 开始排序。这只是一个很简单的排序，还没有超过自然数的范畴。

现在考虑对这个集合 $\{1/2,3/4,7/8,\dots \}\cup \{1\}$，按照＜来排序：

号码	元素
1/2	0
3/4	1
7/8	2
……	……
1	？

注意到当我们为 1/2,3/4,7/8,…… 这些元素排序时，已经用尽了全部的自然数。但我们又要为 1 编号。1 大于前面的所有元素，因此，1 的号码需要是一个大于全体自然数的东西。它依然是序数（因为我们定义序数就是为了处理这种情况），我们给它命名为 ω。

想象一下我们在此基础上又要给 $\{3/2,7/4,15/8,\dots \}\cup \{2\}$ 编号。因此我们还需要越来越多的大于ω的序数。随着“编号游戏”的对象愈发复杂，我们所需要的序数也愈发庞大，复杂，单纯靠直观理解已经难以为继，因此我们需要看以下的内容。

数学定义

序数是在∈序上良序的传递集（传递集即满足每个元素都是自身的子集）。如：

$0=\varnothing =\{\}$

$1=\{0\}$

$2=\{0,1\}$

$3=\{0,1,2\}$

$1048576=\{0,1,2,3,...,1048575\}$

序数的后继

序数 $\alpha$ 的后继被定义为 $\alpha +1=\alpha \cup \{\alpha \}$。它也是所有序数运算的基础。

如 $2+1=2\cup \{2\}=\{0,1\}\cup \{2\}=\{0,1,2\}=3$，$n+1=n\cup \{n\}=\{0,1,2,3,...,n\}$。

有限序数与超限序数

所有自然数都是有限序数。

大于任意有限序数的序数称作超限序数（或无限序数）。

极限序数

不是 0 且不是任何序数的后继的序数被称为极限序数。（0 有时也被视为极限序数）

即序数 $\lambda$ 是极限序数要满足“不存在某个序数 $\alpha$ 使得 $\lambda =\alpha +1$”。

如果 $\lambda$ 是极限序数，那么 $\lambda =\sup \{\alpha |\alpha <\lambda \}$。

$\omega$ 被定义为全体自然数的集合，$\omega =\mathbb{\mathbb{N}}=\{0,1,2,3,...\}$ 既是第一个超限序数，也是第一个极限序数。

基本列

如果序数 $\alpha$ 是一个极限序数，则它的基本列 $⟨\alpha [n]⟩$ 是一个递增的序数列，并且满足其上确界为 $\alpha$。即 $\alpha =\mathrm{s}\mathrm{u}\mathrm{p}\{\alpha [n]|n\in \mathbb{\mathbb{N}}\}=\mathrm{s}\mathrm{u}\mathrm{p}\{\alpha [0],\alpha [1],\alpha [2],...\}$。

注意到一个极限序数具有多种基本列。因此为了方便运用和理解，我们需要一套标准基本列系统来给极限序数一个唯一的基本列。

很遗憾的是，不存在一个通用的基本列系统来为所有序数指定标准基本列。因此，我们只能借助序数记号来为它极限之下的极限序数指定标准基本列。

递归序数与非递归序数

递归序数

一个序数 $\alpha$ 被称为递归序数，当且仅当存在一个图灵机（或等效的可计算函数，或图灵完备的计算机语言），它能计算出一个良序关系 $\prec$，使得这个良序关系的序型与 $\alpha$ 同构。

直观来讲，递归序数都是可以“自下而上”得到的序数。

所有递归序数的集合也是一个序数，记为 ${\omega }_1^{\mathrm{C}\mathrm{K}}$（又作 $\mathrm{\Omega }$，CKO）

${\omega }_1^{\mathrm{C}\mathrm{K}}=\{0,1,...,\omega ,...,{\omega }^2,...,{\omega }^{\omega },...,{\epsilon }_0,...,\phi (1,0,0),...,\psi ({\mathrm{\Omega }}_{\omega }),...\}$

由于图灵机的总数是可数无穷多的，因此 $\mathrm{\Omega }$ 依然是一个可数序数。

非递归序数

不是递归序数的序数被称为非递归序数。

最小的非递归序数就是所有递归序数的集合 ${\omega }_1^{\mathrm{C}\mathrm{K}}$。

可数序数与不可数序数

如果一个序数与有限基数或 ${\mathrm{\aleph }}_0$ 等势，则它是可数序数。如 $0,1,2,\omega ,{\epsilon }_0,\psi ({\mathrm{\Omega }}_{\omega }),Y(1,3),\mathrm{\Omega },I,{\psi }_{\alpha }({\alpha }_{\omega }),{\omega }_1^L$ 等等都是可数序数。

不是可数序数的序数是不可数序数，如 ${\omega }_1$。

序数的运算

序数加法

$\alpha +0=\alpha$

$\alpha +(\beta +1)=(\alpha +\beta )+1$

$\alpha +\beta =\bigcup _{\gamma <\beta }(\alpha +\gamma )$，如果 $\beta$ 是极限序数。

序数加法不具有交换律，但具有结合律。即

$\alpha +\beta \ne \beta +\alpha ,(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$

例：$1+\omega =\bigcup _{\gamma <\omega }(1+\gamma )=\{1+0,1+1,1+2,...\}=\mathrm{s}\mathrm{u}\mathrm{p}\{1,2,3,...\}=\omega \ne \omega +1$

序数乘法

$\alpha \times 0=0$

$\alpha \times (\beta +1)=(\alpha \times \beta )+\alpha$

$\alpha \times \beta =\bigcup _{\gamma <\beta }(\alpha \times \gamma )$，如果 $\beta$ 是极限序数。

序数乘法不具有交换律和右分配律，但具有结合律和左分配律。即

$1.\alpha \times \beta \ne \beta \times \alpha ,(\alpha \times \beta )\times \gamma =\alpha \times (\beta \times \gamma )$

$2.(\alpha +\beta )\times \gamma \ne (\alpha \times \gamma )+(\beta \times \gamma ),\alpha \times (\beta +\gamma )=(\alpha \times \beta )+(\alpha \times \gamma )$

例：

$\begin{array}{rl}(\omega +1)\times \omega & =\bigcup _{\gamma <\omega }((\omega +1)\times \gamma )\\ & =\{(\omega +1)\times 0,(\omega +1)\times 1,(\omega +1)\times 2,...\}\\ & =\{0,\omega +1,\omega +(1+\omega )+1,\omega +(1+\omega )+(1+\omega )+1,...\}\\ & =\mathrm{s}\mathrm{u}\mathrm{p}\{0,\omega +1,\omega \times 2+1,\omega \times 3+1,...\}={\omega }^2\\ & \ne \omega \times (\omega +1)={\omega }^2+\omega \end{array}$

Q:为什么不是${\omega }^2+1$？

A: 我们知道${\omega }^2+1={\omega }^2\cup \{{\omega }^2\}=\{0,1,2,...,\omega ,\omega +1,...,\omega \times 2,...,\omega \times 3,...,{\omega }^2\}$

而 $\bigcup _{\gamma <\omega }(\omega \times \gamma +1)$ 中显然没有任何一个元素能够达到或是超过 ${\omega }^2$，因此它们的上确界也不会超过 ${\omega }^2$。

其实也可以换一个方向思考：既然 $\mathrm{s}\mathrm{u}\mathrm{p}\{\omega ,\omega \times 2,\omega \times 3,...\}={\omega }^2$

而 $\mathrm{s}\mathrm{u}\mathrm{p}\{0,\omega +1,\omega \times 2+1,\omega \times 3+1,...\}$ 中从小到大排列的每一项都比前者小，因此也不会超过 ${\omega }^2$。

序数的指数运算

${\alpha }^0=1$

${\alpha }^{\beta +1}={\alpha }^{\beta }\times \alpha$

${\alpha }^{\beta }=\bigcup _{\gamma <\beta }({\alpha }^{\gamma })$，如果 $\beta$ 是极限序数。

序数的指数不具有对底数乘法的分配律，但指数加法具有对底数的分配律。即

$(\alpha \times \beta {)}^{\gamma }\ne {\alpha }^{\gamma }\times {\beta }^{\gamma },{\alpha }^{\beta +\gamma }={\alpha }^{\beta }\times {\alpha }^{\gamma }$

例：

$\begin{array}{rl}(2\times 3{)}^{\omega }& =6^{\omega }=\bigcup _{\gamma <\omega }(6^{\gamma })=\{6^0,6^1,6^2,...\}=\mathrm{s}\mathrm{u}\mathrm{p}\{1,6,36,...\}=\omega \\ & \ne 2^{\omega }\times 3^{\omega }=\bigcup _{\gamma <\omega }(2^{\gamma })\times \bigcup _{\gamma <\omega }(3^{\gamma })=\omega \times \omega ={\omega }^2\end{array}$

${\epsilon }_0$ 是第一个满足 ${\omega }^{\alpha }=\alpha$ 的不动点。

${\omega }^{{\epsilon }_0}=\bigcup _{\gamma <{\epsilon }_0}({\omega }^{\gamma })=\mathrm{s}\mathrm{u}\mathrm{p}\{1,\omega ,{\omega }^2,...,{\omega }^{\omega },...,{\omega }^{{\omega }^{\omega }},...\}={\epsilon }_0$

${\epsilon }_0\times \omega ={\omega }^{{\epsilon }_0}\times \omega ={\omega }^{{\epsilon }_0+1}$

形式化定义

序数和序数类

一个集合 $\alpha$ 称为序数，当且仅当它满足以下条件：

• 传递性： $\alpha$ 的每个元素都是其子集（$\mathrm{\forall }\beta \in \alpha ,\beta \subseteq \alpha$）
• 全序性：$\alpha$ 上的关系 $\in$ 是全序关系（$\mathrm{\forall }\beta ,\gamma \in \alpha ,(\beta \in \gamma )\vee (\beta =\gamma )\vee (\beta \ni \gamma )$）
• 良基性：每个非空子集 $S\subseteq \alpha$ 有最小元（$\mathrm{\exists }\beta \in S(\mathrm{\forall }\gamma \in S,\beta \notin \gamma )$）

等价地，序数可定义为良序集的序型，即与某个良序集同构的最小序数。

序数类是所有序数的总体，是一个真类，即：$\mathbf{𝐎}\mathbf{𝐧}\equiv \{\alpha |\alpha \text{ 是序数}\}$

其中，序数的成员关系满足以下性质：

• 三歧性：$\mathrm{\forall }\alpha ,\beta \in \mathbf{𝐎}\mathbf{𝐧},(\alpha \in \beta )\vee (\alpha =\beta )\vee (\alpha \ni \beta )$
• 传递性：$((\alpha \in \mathbf{𝐎}\mathbf{𝐧})\wedge (\beta \in \alpha ))\to (\beta \in \mathbf{𝐎}\mathbf{𝐧})$
• 良序性：On 上的关系 ∈ 是良序的，即每个非空子类有最小元

后继序数和极限序数

一个序数 $\alpha$ 称为后继序数，当且仅当存在序数 $\beta$ 使得 $\alpha =\beta +1$（$\alpha \text{ 是后继序数}⟺\mathrm{\exists }\beta \in \mathbf{𝐎}\mathbf{𝐧}(\alpha =\beta +1)$）

一个序数 $\alpha$ 称为后继序数，当且仅当不存在序数 $\beta$ 使得 $\alpha =\beta +1$（$\alpha \text{ 是极限序数}⟺\mathrm{\neg }\mathrm{\exists }\beta \in \mathbf{𝐎}\mathbf{𝐧}(\alpha =\beta +1)$）

递归函数

一个部分函数 $f:\omega \to \omega$ 称为递归函数，当且仅当存在图灵机 $M$ 满足：对任意 $n\in \omega$，

• 若 $n\in \text{dom}(f)$，则 $M$ 在输入 $n$ 时会在有限步内停机，并输出 $f(n)$；
• 若 $n\notin \text{dom}(f)$，则 $M$ 在输入 $n$ 时永不停机。

定义所有递归函数的类为 ${\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}}_{\text{f}}$。

超限归纳

设 $\phi (x)$ 是一个性质。如果对所有序数 $\alpha$ ，以下都成立：

• 如果对所有的 $\beta <\alpha$ 都有 $\phi (\beta )$ 成立，那么 $\phi (\alpha )$ 成立

那么 $\phi (\alpha )$ 对所有序数 $\alpha$ 成立。

等价地，设 $\phi (x)$ 是一个性质。如果以下都成立：

• $\phi (0)$ 成立
• 对于后继序数 $\alpha +1$ ，若 $\phi (\alpha )$ 成立，则 $\phi (\alpha +1)$ 成立
• 对于极限序数 $\alpha$ ，若对于所有 $\beta <\alpha$ 有 $\phi (\beta )$ 成立，则 $\phi (\alpha )$ 成立

那么 $\phi (\alpha )$ 对所有序数 $\alpha$ 成立。

超限递归

设 $\beta$ 是一个序数，$f:\omega \to \omega$ 是一个递归函数。通过超限递归定义一个函数 $F:\mathbf{𝐎}\mathbf{𝐧}\to \mathbf{𝐎}\mathbf{𝐧}$，满足：

• 对后继序数 $\alpha =\gamma +1$，定义 $F(\alpha )=f(⟨\gamma ,F(\gamma )⟩)$；
• 对极限序数 $\alpha$，定义 $F(\alpha )=\sup \{F(\gamma )|\gamma <\alpha \}$。

定义 $F_f$ 是由 $f$ 定义的超限递归函数。

称 $\alpha$ 是 $f$ 相对于 $\beta$ 的序数，当且仅当存在递归函数 $f\in {\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}}_{\text{f}}$，使得 $\alpha =F(\beta )$（即 $\alpha$ 是通过 $f$ 在 $b$ 处的超限递归生成的序数），其中 $F$ 是通过 $f$ 定义的超限递归函数。

称 $\alpha$ 是递归在 $\beta$​ 上的序数，当且仅当存在递归函数 $f\in {\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}}_{\text{f}}$ 和序数 ​$\gamma <\beta$，使得 $\alpha =F_f(\gamma )$。

递归序数和非递归序数

一个序数 $\alpha$ 称为递归序数，当且仅当存在递归函数 $f\in {\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}}_{\text{f}}$ 和序数 $\beta$，使得 $\alpha$ 是 $f$ 相对于 $\beta$ 的序数（$\alpha \text{ 是递归序数}⟺\mathrm{\exists }f\in {\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}}_{\text{f}}\mathrm{\exists }\beta \in \mathbf{𝐎}\mathbf{𝐧}(\alpha =F_f(\beta ))$）

递归序数类是所有递归序数的总体：$\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}\equiv \{\alpha |\alpha \text{ 是递归序数}\}$

一个序数 $\alpha$ 称为非递归序数，当且仅当它不是递归序数，即 $\alpha \text{ 是非递归序数}⟺\alpha \in \mathbf{𝐎}\mathbf{𝐧}\wedge \alpha \notin \mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}$（$\alpha \text{ 是非递归序数}⟺\mathrm{\neg }\mathrm{\exists }f\in {\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}}_{\text{f}}\mathrm{\exists }\beta \in \mathbf{𝐎}\mathbf{𝐧}(\alpha =F_f(\beta ))$）

容许序数

一个序数 $\alpha$ 称为容许序数，当且仅当构造宇宙 $L_{\alpha }$ 满足 Kripke-Platek 集合论的公理。等价地，$\alpha$ 是容许的当且仅当对任何递归在 $\alpha$ 上的函数 $F:L_{\alpha }\to L_{\alpha }$​，其定义域和值域都属于 $L_{\alpha }$​（即 $\alpha$ 对递归封闭）。

$\alpha \text{ 是容许序数}⟺L_{\alpha }\models \mathbf{𝐊}\mathbf{𝐏}$

Church-Kleene 序数（CKO）

${\omega }_{\alpha }^{\text{CK}}$​ 序数通过超限递归定义：

• ${\omega }_0^{\text{CK}}=\omega$
• 对后继序数 $\alpha =\beta +1$，${\omega }_{\alpha }^{\text{CK}}=\sup \{\alpha \in \mathbf{𝐎}\mathbf{𝐧}|\alpha \text{ 是递归在 }{\omega }_{\beta }^{\text{CK}}\text{ 上的序数}\}$
• 对极限序数 $\alpha$，${\omega }_{\alpha }^{\text{CK}}=\sup \{{\omega }_{\beta }^{\text{CK}}|\beta <\alpha \}$

第一个非递归序数 ​${\omega }_1^{\text{CK}}$ 是所有递归序数的最小上界（即上确界），即：${\omega }_1^{\text{CK}}=\sup \{\alpha \in \mathbf{𝐎}\mathbf{𝐧}|\alpha \in \mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐜}\}$，它是可数的最小非递归序数。

序数的基本列

对极限序数 $\lambda$，其基本列定义为递增序列 $⟨\lambda [\xi ]{⟩}_{\xi <\mu }$（$\mu$ 为序数），满足： $\mathrm{\forall }\xi <\mu ,\lambda [\xi ]<\lambda$ 且 $\sup \{\lambda [\xi ]|\xi <\mu \}=\lambda$。

若 $\lambda$ 是正则序数（$\text{cf}(\lambda )=\lambda$），则 $\mu =\lambda$；若 $\lambda$ 是奇异序数（$\text{cf}(\lambda )<\lambda$），则 $\mu =\text{cf}(\lambda )$。