查看“︁序数”︁的源代码

'''序数'''是自然数的推广。

=== 直观理解 ===
[[文件:Omega4.jpg|缩略图|仅供参考]]
顾名思义，序数是用来排序的号码。最小的序数是 0，因而我们从 0 开始排序。这只是一个很简单的排序，还没有超过自然数的范畴。

现在考虑对这个集合 <math>\{ 1/2,3/4,7/8,\ldots \} \cup \{1\}</math>，按照＜来排序：
{| class="wikitable"
|+
!号码
!元素
|-
|1/2
|0
|-
|3/4
|1
|-
|7/8
|2
|-
|……
|……
|-
|1
|？
|}
注意到当我们为 1/2,3/4,7/8,…… 这些元素排序时，已经用尽了全部的自然数。但我们又要为 1 编号。1 大于前面的所有元素，因此，1 的号码需要是一个大于全体自然数的东西。它依然是序数（因为我们定义序数就是为了处理这种情况），我们给它命名为 ω。

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

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

<math>0=\varnothing=\{\}</math>

<math>1=\{ 0\}</math>

<math>2=\{0,1\}</math>

<math>3=\{0,1,2\}</math>

<math>1048576=\{0,1,2,3,...,1048575\}</math>

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

如 <math>2+1=2\cup\{2\}=\{0,1\}\cup\{2\}=\{0,1,2\}=3</math>，<math>n+1=n\cup\{n\}=\{0,1,2,3,...,n\}</math>。

==== 有限序数与超限序数 ====
所有自然数都是'''<span id="有限序数">有限序数</span>'''。

大于任意有限序数的序数称作'''<span id="超限序数">超限序数</span>'''（或无限序数）。

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

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

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

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

==== 基本列 ====
如果序数 <math>\alpha</math> 是一个极限序数，则它的基本列 <math>\langle \alpha[n] \rangle </math> 是一个递增的序数列，并且满足其上确界为 <math>\alpha</math>。即 <math>\alpha={\rm sup}\{\alpha[n]|n\in \mathbb{N}\}={\rm sup}\{\alpha[0],\alpha[1],\alpha[2],...\}</math>。

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

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

==== 递归序数与非递归序数 ====

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

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

所有递归序数的集合也是一个序数，记为 <math>\omega_1^{\rm CK}</math>（又作 <math>\Omega</math>，[[CKO]]）

<math>\omega_1^{\rm CK}=\{0,1,...,\omega,...,\omega^2,...,\omega^\omega,...,\varepsilon_0,...,\varphi(1,0,0),...,\psi(\Omega_{\omega}),...\}</math>

由于图灵机的总数是可数无穷多的，因此 <math>\Omega</math> 依然是一个可数序数。

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

最小的非递归序数就是所有递归序数的集合 <math>\omega_1^{\rm CK}</math>。

==== 可数序数与不可数序数 ====
如果一个序数与有限基数或 <math>\aleph_0</math> 等势，则它是可数序数。如 <math>0,1,2,\omega,\varepsilon_0,\psi(\Omega_{\omega}),Y(1,3),\Omega,I,\psi_{\alpha}(\alpha_{\omega}),\omega_1^L</math> 等等都是可数序数。

不是可数序数的序数是不可数序数，如 <math>\omega_1</math>。

=== 序数的运算 ===

==== 序数加法 ====
<math>\alpha+0=\alpha</math>

<math>\alpha+(\beta+1)=(\alpha+\beta)+1</math>

<math>\alpha+\beta=\bigcup_{\gamma <\beta}(\alpha +\gamma)</math>，如果 <math>\beta</math> 是极限序数。

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

<math>\alpha+\beta\ne\beta+\alpha,(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)</math>

例：<math>1+\omega=\bigcup_{\gamma <\omega}(1 +\gamma)=\{1+0,1+1,1+2,...\}={\rm sup}\{1,2,3,...\}=\omega\ne \omega+1</math>

==== 序数乘法 ====
<math>\alpha\times0=0</math>

<math>\alpha\times(\beta+1)=(\alpha\times\beta)+\alpha</math>

<math>\alpha\times\beta=\bigcup_{\gamma <\beta}(\alpha \times\gamma)</math>，如果 <math>\beta</math> 是极限序数。

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

<math>1.\alpha\times\beta\ne\beta\times\alpha,(\alpha\times\beta)\times\gamma=\alpha\times(\beta\times\gamma)</math>

<math>2.(\alpha+\beta)\times\gamma\ne (\alpha\times\gamma)+(\beta\times\gamma), \alpha\times(\beta+\gamma)=(\alpha\times\beta)+(\alpha\times\gamma)</math>

例：

<math>\begin{align} (\omega+1)\times\omega&=\bigcup_{\gamma <\omega}((\omega+1) \times\gamma)\\&=\{(\omega+1)\times0,(\omega+1)\times1,(\omega+1)\times2,...\}\\&=\{0,\omega+1,\omega+(1+\omega)+1,\omega+(1+\omega)+(1+\omega)+1,...\}\\&={\rm sup}\{ 0,\omega+1,\omega\times2+1,\omega\times3+1,...\}=\omega^2 \\&\ne\omega\times(\omega+1)=\omega^2+\omega \end{align}</math>

'''Q:'''为什么不是<math>\omega^2+1</math>？

A: 我们知道<math>\omega^2+1=\omega^2\cup\{\omega^2\}=\{0,1,2,...,\omega,\omega+1,...,\omega\times2,...,\omega\times3,...,\omega^2\}</math>

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

其实也可以换一个方向思考：既然 <math>{\rm sup}\{ \omega,\omega\times2,\omega\times3,...\}=\omega^2</math>

而 <math>{\rm sup}\{ 0,\omega+1,\omega\times2+1,\omega\times3+1,...\}</math> 中从小到大排列的每一项都比前者小，因此也不会超过 <math>\omega^2</math>。

==== 序数的指数运算 ====
<math>\alpha^0=1</math>

<math>\alpha^{\beta+1}=\alpha^\beta\times\alpha</math>

<math>\alpha^\beta=\bigcup_{\gamma <\beta}(\alpha^\gamma)</math>，如果 <math>\beta</math> 是极限序数。

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

<math>(\alpha\times\beta)^\gamma\ne\alpha^\gamma\times\beta^\gamma,\alpha^{\beta+\gamma}=\alpha^\beta\times\alpha^\gamma</math>

例：

<math>\begin{align} (2\times3)^\omega &=6^\omega=\bigcup_{\gamma <\omega}(6^\gamma)=\{6^0,6^1,6^2,... \}={\rm sup}\{1,6,36,... \}=\omega \\&\ne 2^\omega\times3^\omega=\bigcup_{\gamma <\omega}(2^\gamma)\times\bigcup_{\gamma <\omega}(3^\gamma)=\omega\times\omega=\omega^2 \end{align}</math>

<math>\varepsilon_0</math> 是第一个满足 <math>\omega^\alpha=\alpha</math> 的不动点。

<math>\omega^{\varepsilon_0}=\bigcup_{\gamma <\varepsilon_0}(\omega^\gamma)={\rm sup}\{1,\omega,\omega^2,...,\omega^\omega,...,\omega^{\omega^\omega},...\}=\varepsilon_0</math>

<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>\varphi(x)</math> 是一个性质。如果对所有序数 <math>\alpha</math> ，以下都成立：

* 如果对所有的 <math>\beta<\alpha</math> 都有 <math>\varphi(\beta)</math> 成立，那么 <math>\varphi(\alpha)</math> 成立

那么 <math>\varphi(\alpha)</math> 对所有序数 <math>\alpha</math> 成立。

等价地，设 <math>\varphi(x)</math> 是一个性质。如果以下都成立：

* <math>\varphi(0)</math> 成立
* 对于后继序数 <math>\alpha+1</math> ，若 <math>\varphi(\alpha)</math> 成立，则 <math>\varphi(\alpha+1)</math> 成立
* 对于极限序数 <math>\alpha</math> ，若对于所有 <math>\beta<\alpha</math> 有 <math>\varphi(\beta)</math> 成立，则 <math>\varphi(\alpha)</math> 成立

那么 <math>\varphi(\alpha)</math> 对所有序数 <math>\alpha</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>。

[[分类:入门]]

[[分类:集合论相关]]
[[分类:重要概念]]