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

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

=== 直观理解 ===
顾名思义，序数是用来排序的号码。比方说，我们想要按照好吃程度从小到大来排序{树叶，屎，蛋糕}这个集合，我们就可以用到序数。
{| class="wikitable"
|+
!号码
!元素
|-
|0
|屎
|-
|1
|树叶
|-
|2
|蛋糕
|}
最小的序数是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>。

==== 有限序数与超限序数 ====
所有自然数都是有限序数。

大于任意有限序数的序数称作'''超限序数'''(或无限序数)

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

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

如果<math>\lambda</math>是极限序数，那么<math>\lambda={\rm sup}\{\alpha|\alpha < \lambda\}</math>。("<math>\rm sup</math>"为"上确界"，一般可以省略不写)


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

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

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

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

所有递归序数的集合也是一个序数，记为<math>\omega_1^{\rm CK}</math>（为了方便，通常写作<math>\Omega</math>）

<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>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>.

=== 序数的运算 ===

==== 1.序数加法 ====
<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>

==== 2.序数乘法 ====
<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>。

==== 3.序数的指数运算 ====
<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>
[[分类:入门]]