序数：修订间差异

2026年3月2日 (一) 20:47的最新版本

序数是自然数的推广。

直观理解

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

$1 = {0}$

$2 = {0, 1}$

$3 = {0, 1, 2}$

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

序数的后继

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

如 $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 有时也被视为极限序数）

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

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

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

基本列

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

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

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

递归序数与非递归序数

递归序数

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

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

所有递归序数的集合也是一个序数，记为 $ω_{1}^{C K}$ （又作 $Ω$ ，CKO）

$ω_{1}^{C K} = {0, 1, . . ., ω, . . ., ω^{2}, . . ., ω^{ω}, . . ., ε_{0}, . . ., φ (1, 0, 0), . . ., ψ (Ω_{ω}), . . .}$

由于图灵机的总数是可数无穷多的，因此 $Ω$ 依然是一个可数序数。

非递归序数

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

最小的非递归序数就是所有递归序数的集合 $ω_{1}^{C K}$ 。

可数序数与不可数序数

如果一个序数与有限基数或 $ℵ_{0}$ 等势，则它是可数序数。如 $0, 1, 2, ω, ε_{0}, ψ (Ω_{ω}), Y (1, 3), Ω, I, ψ_{α} (α_{ω}), ω_{1}^{L}$ 等等都是可数序数。

不是可数序数的序数是不可数序数，如 $ω_{1}$ 。

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

不可数极限序数也可以有ω长的基本列，例如 $ω_{1} + ω^{2}$ ， $ω_{1} + ε_{0}$ 。它们的共尾度是ω。

序数的运算

序数加法

$α + 0 = α$

$α + (β + 1) = (α + β) + 1$

$α + β = ⋃_{γ < β} (α + γ)$ ，如果 $β$ 是极限序数。

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

$α + β \neq β + α, (α + β) + γ = α + (β + γ)$

例： $1 + ω = ⋃_{γ < ω} (1 + γ) = {1 + 0, 1 + 1, 1 + 2, . . .} = s u p {1, 2, 3, . . .} = ω \neq ω + 1$

序数乘法

$α \times 0 = 0$

$α \times (β + 1) = (α \times β) + α$

$α \times β = ⋃_{γ < β} (α \times γ)$ ，如果 $β$ 是极限序数。

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

$1 . α \times β \neq β \times α, (α \times β) \times γ = α \times (β \times γ)$

$2 . (α + β) \times γ \neq (α \times γ) + (β \times γ), α \times (β + γ) = (α \times β) + (α \times γ)$

例：

$\begin{aligned} (ω + 1) \times ω & = ⋃_{γ < ω} ((ω + 1) \times γ) \\ = {(ω + 1) \times 0, (ω + 1) \times 1, (ω + 1) \times 2, . . .} \\ = {0, ω + 1, ω + (1 + ω) + 1, ω + (1 + ω) + (1 + ω) + 1, . . .} \\ = s u p {0, ω + 1, ω \times 2 + 1, ω \times 3 + 1, . . .} = ω^{2} \\ \neq ω \times (ω + 1) = ω^{2} + ω \end{aligned}$

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

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

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

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

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

序数的指数运算

$α^{0} = 1$

$α^{β + 1} = α^{β} \times α$

$α^{β} = ⋃_{γ < β} (α^{γ})$ ，如果 $β$ 是极限序数。

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

$(α \times β)^{γ} \neq α^{γ} \times β^{γ}, α^{β + γ} = α^{β} \times α^{γ}$

例：

$\begin{aligned} (2 \times 3)^{ω} & = 6^{ω} = ⋃_{γ < ω} (6^{γ}) = {6^{0}, 6^{1}, 6^{2}, . . .} = s u p {1, 6, 36, . . .} = ω \\ \neq 2^{ω} \times 3^{ω} = ⋃_{γ < ω} (2^{γ}) \times ⋃_{γ < ω} (3^{γ}) = ω \times ω = ω^{2} \end{aligned}$

$ε_{0}$ 是第一个满足 $ω^{α} = α$ 的不动点。

$ω^{ε_{0}} = ⋃_{γ < ε_{0}} (ω^{γ}) = s u p {1, ω, ω^{2}, . . ., ω^{ω}, . . ., ω^{ω^{ω}}, . . .} = ε_{0}$

$ε_{0} \times ω = ω^{ε_{0}} \times ω = ω^{ε_{0} + 1}$

@@ 第2行： / 第2行： @@
 === 直观理解 ===
+[[文件:Omega4.jpg|缩略图|仅供参考]]
 顾名思义，序数是用来排序的号码。最小的序数是 0，因而我们从 0 开始排序。这只是一个很简单的排序，还没有超过自然数的范畴。
@@ 第48行： / 第49行： @@
 ==== 有限序数与超限序数 ====
-所有自然数都是有限序数。
+所有自然数都是'''<span id="有限序数">有限序数</span>'''。
-大于任意有限序数的序数称作'''超限序数'''（或无限序数）。
+大于任意有限序数的序数称作'''<span id="超限序数">超限序数</span>'''（或无限序数）。
 ==== 极限序数 ====
@@ 第90行： / 第91行： @@
 不是可数序数的序数是不可数序数，如 <math>\omega_1</math>。
+除0以外，所有可数极限序数都有ω长的基本列。
+不可数极限序数也可以有ω长的基本列，例如<math>\omega_1+\omega^2</math>，<math>\omega_1+\varepsilon_0</math>。它们的'''共尾度'''是ω。
 === 序数的运算 ===
@@ 第153行： / 第158行： @@
 <math>\varepsilon_0\times\omega=\omega^{\varepsilon_0}\times\omega=\omega^{\varepsilon_0+1}</math>
-=== 形式化定义 ===
-'''序数和序数类'''
-一个集合 <math>\alpha</math> 称为序数，当且仅当它满足以下条件：
-* 传递性： <math>\alpha</math> 的每个元素都是其子集（<math>\forall\beta\in\alpha,\beta\subseteq\alpha</math>）
-* 全序性：<math>\alpha</math> 上的关系 <math>\in</math> 是全序关系（<math>\forall\beta,\gamma\in\alpha,(\beta\in\gamma)\lor(\beta=\gamma)\lor(\beta\ni\gamma)</math>）
-* 良基性：每个非空子集 <math>S\subseteq\alpha</math> 有最小元（<math>\exists\beta\in S(\forall\gamma\in S,\beta\notin\gamma)</math>）
-等价地，序数可定义为良序集的序型，即与某个良序集同构的最小序数。
-序数类是所有序数的总体，是一个真类，即：<math>\bold{On}\equiv\{\alpha|\alpha\text{ 是序数}\}</math>
-其中，序数的成员关系满足以下性质：
-* 三歧性：<math>\forall\alpha,\beta\in\bold{On},(\alpha\in\beta)\lor(\alpha=\beta)\lor(\alpha\ni\beta)</math>
-* 传递性：<math>((\alpha\in\bold{On})\land(\beta\in\alpha))\rightarrow(\beta\in\bold{On})</math>
-* 良序性：On 上的关系 ∈ 是良序的，即每个非空子类有最小元
-'''后继序数和极限序数'''
-一个序数 <math>\alpha</math> 称为后继序数，当且仅当存在序数 <math>\beta</math> 使得 <math>\alpha=\beta+1</math>（<math>\alpha\text{ 是后继序数}\Longleftrightarrow\exists\beta\in\bold{On}(\alpha=\beta+1)</math>）
-一个序数 <math>\alpha</math> 称为后继序数，当且仅当不存在序数 <math>\beta</math> 使得 <math>\alpha=\beta+1</math>（<math>\alpha\text{ 是极限序数}\Longleftrightarrow\neg\exists\beta\in\bold{On}(\alpha=\beta+1)</math>）
-'''递归函数'''
-一个部分函数 <math>f:\omega\rightarrow\omega</math> 称为递归函数，当且仅当存在图灵机 <math>M</math> 满足：对任意 <math>n\in\omega</math>，
-* 若 <math>n\in\text{dom}(f)</math>，则 <math>M</math> 在输入 <math>n</math> 时会在有限步内停机，并输出 <math>f(n)</math>；
-* 若 <math>n\notin\text{dom}(f)</math>，则 <math>M</math> 在输入 <math>n</math> 时永不停机。
-定义所有递归函数的类为 <math>\bold{Rec}_\text{f}</math>。
-'''超限递归'''
-设 <math>\beta</math> 是一个序数，<math>f:\omega\rightarrow\omega</math> 是一个递归函数。通过超限递归定义一个函数 <math>F:\bold{On}\rightarrow\bold{On}</math>，满足：
-* 对后继序数 <math>\alpha=\gamma+1</math>，定义 <math>F(\alpha)=f(\langle\gamma,F(\gamma)\rangle)</math>；
-* 对极限序数 <math>\alpha</math>，定义 <math>F(\alpha)=\sup\{F(\gamma)|\gamma<\alpha\}</math>。
-定义 <math>F_f</math> 是由 <math>f</math> 定义的超限递归函数。
-称 <math>\alpha</math> 是 <math>f</math> 相对于 <math>\beta</math> 的序数，当且仅当存在递归函数 <math>f\in\bold{Rec}_\text{f}</math>，使得 <math>\alpha=F(\beta)</math>（即 <math>\alpha</math> 是通过 <math>f</math> 在 <math>b</math> 处的超限递归生成的序数），其中 <math>F</math> 是通过 <math>f</math> 定义的超限递归函数。
-称 <math>\alpha</math> 是递归在 <math>\beta</math> 上的序数，当且仅当存在递归函数 <math>f\in\bold{Rec}_\text{f}</math> 和序数 <math>\gamma<\beta</math>，使得 <math>\alpha=F_f(\gamma)</math>。
-'''递归序数和非递归序数'''
-一个序数 <math>\alpha</math> 称为递归序数，当且仅当存在递归函数 <math>f\in\bold{Rec}_\text{f}</math> 和序数 <math>\beta</math>，使得 <math>\alpha</math> 是 <math>f</math> 相对于 <math>\beta</math> 的序数（<math>\alpha\text{ 是递归序数}\Longleftrightarrow\exists f\in\bold{Rec}_\text{f}\ \exists\beta\in\bold{On}(\alpha=F_f(\beta))</math>）
-递归序数类是所有递归序数的总体：<math>\bold{Rec}\equiv\{\alpha|\alpha\text{ 是递归序数}\}</math>
-一个序数 <math>\alpha</math> 称为非递归序数，当且仅当它不是递归序数，即 <math>\alpha\text{ 是非递归序数}\Longleftrightarrow\alpha\in\bold{On}\land\alpha\notin\bold{Rec}</math>（<math>\alpha\text{ 是非递归序数}\Longleftrightarrow\neg\exists f\in\bold{Rec}_\text{f}\ \exists\beta\in\bold{On}(\alpha=F_f(\beta))</math>）
-'''容许序数'''
-一个序数 <math>\alpha</math> 称为容许序数，当且仅当构造宇宙 <math>L_\alpha</math> 满足 Kripke-Platek 集合论的公理。等价地，<math>\alpha</math> 是容许的当且仅当对任何递归在 <math>\alpha</math> 上的函数 <math>F:L_\alpha\rightarrow L_\alpha</math>，其定义域和值域都属于 <math>L_\alpha</math>（即 <math>\alpha</math> 对递归封闭）。
-<math>\alpha\text{ 是容许序数}\Longleftrightarrow L_\alpha\vDash\bold{KP}</math>
-'''Church-Kleene 序数（[[CKO]]）'''
-<math>\omega_\alpha^\text{CK}</math> 序数通过超限递归定义：
-* <math>\omega_0^\text{CK}=\omega</math>
-* 对后继序数 <math>\alpha=\beta+1</math>，<math>\omega_\alpha^\text{CK}=\sup\{\alpha\in\bold{On}|\alpha\text{ 是递归在 }\omega_\beta^\text{CK}\text{ 上的序数}\}</math>
-* 对极限序数 <math>\alpha</math>，<math>\omega_\alpha^\text{CK}=\sup\{\omega_\beta^\text{CK}|\beta<\alpha\}</math>
-第一个非递归序数 <math>\omega_1^\text{CK}</math> 是所有递归序数的最小上界（即上确界），即：<math>\omega_1^\text{CK}=\sup\{\alpha\in\bold{On}|\alpha\in\bold{Rec}\}</math>，它是可数的最小非递归序数。
-'''序数的基本列'''
-对极限序数 <math>\lambda</math>，其基本列定义为递增序列 <math>\langle\lambda[\xi]\rangle_{\xi<\mu}</math>（<math>\mu</math> 为序数），满足： <math>\forall\xi<\mu,\lambda[\xi]<\lambda</math> 且 <math>\sup\{\lambda[\xi]|\xi<\mu\}=\lambda</math>。
-若 <math>\lambda</math> 是正则序数（<math>\text{cf}(\lambda)=\lambda</math>），则 <math>\mu=\lambda</math>；若 <math>\lambda</math> 是奇异序数（<math>\text{cf}(\lambda)<\lambda</math>），则 <math>\mu=\text{cf}(\lambda)</math>。
 [[分类:入门]]
 [[分类:集合论相关]]
+[[分类:重要概念]]