序数

序数是自然数的推广。

直观理解

仅供参考

顾名思义，序数是用来排序的号码。最小的序数是 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$。

除0以外，所有可数极限序数都有ω长的基本列。

不可数极限序数也可以有ω长的基本列，例如${\omega }_1+{\omega }^2$，${\omega }_1+{\epsilon }_0$。它们的共尾度是ω。

序数的运算

序数加法

$\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}$