2. 序数

本节介绍序数的构造及性质, 并证明超限归纳法.

2.1偏序、全序与良序

定义 2.1.1 (偏序与全序). 集合 $P$ 上的二元关系 $<$ 称为偏序 (partial order), 如果满足:

1.	$x\nless x$
2.	$x<y\wedge y<z⟹x<z$ 如果进一步有:
3.	$\forall x,y(x<y\vee x=y\vee x>y)$

就称 $<$ 是 $P$ 上的全序或线性序 (linear order).

注 2.1.2. 这些定义可以不加修改地推广为类上的序关系.

定义 2.1.3. 如果 $X$ 是偏序集 $(P,<)$ 的非空子集, $P$ 的元素 $x$ 称为 $X$ 的$$\begin{array}{rlrl}& \text{极小元，}& & \text{如果 }x\in X\wedge (\forall y\in X)y\nless x;\\ & \text{最小元，}& & \text{如果 }x\in X\wedge (\forall y\in X)y\ge x;\\ & \text{上界，}& & \text{如果 }(\forall y\in X)y<x\text{，记作 }x=\sup X;\\ & \text{上确界，}& & \text{如果 }x\text{是最小的上界}.\end{array}$$极大元、最大元、下界、下确界的定义是类似的.

定义 2.1.4 (保序映射). 如果 $P,Q$ 是偏序集, 那么 $f:P\to Q$ 称为是保序的或单调的, 如果$$x<y⟹f(x)<f(y).$$$f:P\to Q$ 称为 (偏序集间的) 同构, 如果 $f$ 是双射, 并且 $f$ 和 $f^{-1}$ 都是保序映射.

定义 2.1.5 (良序). $P$ 是全序集, 如果 $P$ 的每个子集都有最小元, 就称 $P$ 是良序集 (well-ordered set).

引理 2.1.6. 良序集之间保序的双射是同构.

引理 2.1.7. 如果 $f:W\to W$ 是良序集上的保序映射, 那么 $\forall x\in W,f(x)\ge x$.

证明. 反设 $X=\left\{x\in W:f(x)<x\right\}$ 非空, 令 $z$ 是 $X$ 的最小元, $w=f(z)$, 那么 $w=f(z)<z$, 于是 $w\notin X$. 另一方面, 因为 $f$ 保序, $w<z⟹f(w)<f(z)=w$, 于是 $w\in X$, 矛盾.

$\square$

推论 2.1.8. 良序集的自同构只有恒等.

证明. 设 $f$ 是自同构, 根据引理 2.1.7, $f(x)\ge x$ 并且 $f^{-1}(x)\ge x$, 于是 $f(x)=x$.

$\square$

推论 2.1.9. 两个良序集间的同构映射是唯一的.

定义 2.1.10 (前段). 良序集 $W$ 的由 $u$ 给出的前段 (initial segment) 定义为$$W(u)=\left\{x\in W:x<u\right\}$$

引理 2.1.11. 良序集不能同构于自身的前段.

证明. 设 $f:W\to W(u)$ 是同构, 那么 $f(u)\in W(u)⟹f(u)<u$, 与 2.1.7 矛盾

$\square$

定理 2.1.12. $V,W$ 是良序集, 那么如下情况恰有一种成立:

1.	$V$ 与 $W$ 同构;
2.	$V$ 同构于 $W$ 的一个前段;
3.	$W$ 同构于 $V$ 的一个前段.

证明. 设二元关系$$f=\left\{(x,y)\in V\times W:V(x)\text{同构于 }W(y)\right\}.$$使用引理 2.1.11 容易说明 $f$ 是函数并且是单射. 如果 $s$ 是 $V(x)$ 和 $W(y)$ 之间的同构且 $x^{\prime }<x$, 那么 $V(x^{\prime })$ 和 $W(s(x^{\prime }))$ 也同构 (经由 $s$), 因此 $f$ 是保序的.
如果 $\text{dom}f=V$ 且 $\text{ran}f=W$, 那么情形 1 成立.
如果 $y_1<y_2$ 且 $y_2\in \text{ran}f$ 那么显然有 $y_1\in \text{ran}f$. 于是如果 $\text{ran}f\ne W$, 设 $y_0$ 是 $W\setminus \text{ran}f$ 的最小元, 就有 $\text{ran}f=W(y_0)$. 此时 $f$ 的定义域一定是整个 $V$, 否则可以同样构造 $x_0$ 为 $V\setminus \text{dom}f$ 的最小元, 那么 $f:V(x_0)\to W(y_0)$ 是同构, 于是 $(x_0,y_0)\in f$, 矛盾. 此时情况 2 成立.
同理可以证明如果 $\text{dom}f\ne V$, 那么情况 3 成立.
引理 2.1.11 保证了三种情况只能有一种成立.

$\square$

如果两个良序集同构, 就称他们有相同的序型, 良序集之间同构的唯一性以及包含关系提示我们, 不严格的讲, 将序数定义为良序集的序型.

2.2序数

我们在上一节的习题中已经给出如下定义:

定义 2.2.1 (传递集). 集合 $T$ 称为传递 (transitive) 的, 如果 $x\in T⟹x\subset T$.

在此基础上我们定义序数为:

定义 2.2.2 (序数). 集合 $\alpha$ 被称为序数 (ordinal number), 如果它是传递的并且关于 $\in$ 是良序集.

我们一般用小写希腊字母 ($\alpha ,\beta ,\gamma ,\dots$) 表示序数. 全体序数的类记为 $Ord$.
在 $Ord$ 上我们定义序关系 $\alpha <\beta ⟺\alpha \in \beta$.

引理 2.2.3.
(1) $0=\varnothing$ 是序数.
(2) 如果 $\alpha$ 是序数且 $\beta \in \alpha$, 那么 $\beta$ 是序数.
(3) 如果 $\alpha ,\beta$ 是序数且 $\alpha \ne \beta$, 那么 $\alpha \subset \beta ⟹\alpha \in \beta$.
(4) 如果 $\alpha ,\beta$ 是序数, 那么 $\alpha \subset \beta$ 或者 $\beta \subset \alpha$.

证明. (1): 直接验证定义.
(2): 只需证明 $\beta$ 是传递集. 设 $b\in \beta$, 那么 $\forall x\in b$, $x<b<\beta ⟹x<\beta$, 即 $x\in \beta$, 于是 $b\subset \beta$ .
(3): 如果 $\alpha \subset \beta$, 令 $\gamma$ 是 $\beta \setminus \alpha$ 的最小元, 如果 $a\in \alpha ,a>\gamma$, 那么 $\gamma \in a\subset \alpha$, 矛盾, 于是 $\alpha \subset \beta (\gamma )$. 再由 $\alpha$ 的最小性, 实际上有 $\alpha =\left\{\xi \in \beta :\xi <\gamma \right\}=\gamma \in \beta$.
(4): 容易说明 $\gamma =\alpha \cap \beta$ 是序数, 我们断言 $\gamma =\alpha$ 或 $\gamma =\beta$, 否则根据 (3) $\gamma \in \alpha$ 且 $\gamma \in \beta$, 于是 $\gamma \in \gamma$, 这与 $\in$ 是严格序关系矛盾 (也与正规公理矛盾).

$\square$

使用引理 2.2.3 可以证明如下关于序数的结论:

命题 2.2.4.
(1) $<$ 是 $Ord$ 上的全序.
(2) 对任意的 $\alpha$, $\alpha =\left\{\beta :\beta <\alpha \right\}$.
(3) 如果 $C$ 是序数的非空类, 那么 $\bigcap C\in C$ 且 $\bigcap C=\inf C$.
(4) 如果 $X$ 是序数的非空集合, 那么 $\bigcup X$ 是序数且 $\bigcup X=\sup X$.
(5) 对任意的 $\alpha$, $\alpha$ 的后继 ${\alpha }^{\ast }=\alpha \cup \left\{\alpha \right\}$ 是序数, 且 ${\alpha }^{\ast }=\inf \left\{\beta :\beta >\alpha \right\}$

证明. 这里只证 (3), 记 $\alpha =\bigcap C$, $\alpha$ 是序数的证明是容易的. 如果 $\alpha \notin C$, 那么 $\forall \beta \in C,\alpha <\beta$, 于是 $\alpha \in \bigcap C=\alpha$, 矛盾.

$\square$

注 2.2.5. (3) 实际上说明了 $\in$ 是 $Ord$ 上的良序.

我们看到 $Ord$ 是真类, 否则 $(\sup Ord{)}^{\ast }$ 将是一个序数但是不属于 $Ord$.

现在我们可以证明良序集的序型和序数的关系:

定理 2.2.6. 每个良序集同构于唯一一个序数.

证明. 唯一性由引理 2.1.11 保证. 设 $W$ 是良序集, 定义函数 $F(x)=\alpha$, 如果 $W(x)\simeq \alpha$. 如果对 $\forall x\in W$, 这样的 $\alpha$ 都存在:
设 $\gamma$ 是最小的序数使得 $\gamma \notin \text{ran}F$, 假设存在 $\beta >\gamma$ 使得 $\beta \in \text{ran}F$, 由于 $\gamma$ 是 $\beta$ 的前段, 存在 $\gamma$ 到 $W$ 的某个前段的同构, 这表明 $\gamma \in \text{ran}F$, 矛盾, 因此 $\text{ran}F\subset \gamma$. 根据 $\gamma$ 的定义 $F$ 是满射, 于是由引理 2.1.6 , $F$ 是同构.
否则, 设 $x_0$ 是最小的使得 $F(x)$ 不存在的元素, 对 $W(x_0)$ 应用已证部分的定理, 我们得到 $W(x_0)$ 与某个 $\alpha$ 同构, 矛盾.

$\square$

如果存在 $\beta$ 使得 $\alpha ={\beta }^{\ast }$, 那么 $\alpha$ 称为后继序数, 如果 $\alpha$ 不是后继序数, 那么 $\alpha =\sup \left\{\beta :\beta <\alpha \right\}=\bigcup \alpha$, 此时 $\alpha$ 称为极限序数. 我们把 0 也视作极限序数, $0=\sup \varnothing$.
无穷公理保证了除了 0 之外的极限序数存在.

定义 2.2.7 (自然数). 定义自然数集 $\mathbb{N}$ 为最小的非 0 极限序数 $\omega$, 小于 $\omega$ 的序数称为有限序数, 或自然数. 集合 $X$ 称为有限的, 如果存在 $X$ 到某个自然数 $n$ 的单射, 反之称为无穷的.

可以验证 $\omega$ 是最小的归纳集, 于是这个定义和第一节习题中对自然数的定义是相同的.

2.3归纳与递归

如同对于自然数集我们有数学归纳法, 在 $Ord$ 上如下的推广定理成立.

定理 2.3.1 (超限归纳). 设 $C$ 是序数的类, 如果

1.	$0\in C$;
2.	$\alpha \in C⟹{\alpha }^{\ast }\in C$;
3.	$\alpha$ 是非零极限序数且 $\alpha \subset C⟹\alpha \in C$.

那么 $C=Ord$.

归纳法将成为我们证明各种与序数有关的命题的强大工具.

定义 2.3.2 (序列). 一个 $\mathbf{\alpha }$-序列是序数 $\alpha$ 上的函数 $\xi \mapsto {\alpha }_{\xi }$, 记作 $⟨a_{\xi }:\xi <\alpha ⟩$, $\alpha$ 称为序列的长度. 如果 $\alpha <\omega$, 就称为有限序列, 如果 $\alpha =\omega$, 就称为可数序列.
有时也将定义在 $Ord$ 上的函数称为一个 “序列”.

我们时常用如下方法来定义一个序列:
给定一个 (定义在全体序列上的) 函数 $G$, 那么对每个 $\theta$ 都存在唯一一个 $\theta$-序列$$⟨a_{\xi }:\xi <\theta ⟩$$使得$$a_{\alpha }=G(⟨a_{\xi }:\xi <\alpha ⟩)$$对每个 $\alpha <\theta$ 成立.

对于这种方法我们给出一个一般性的定理:

定理 2.3.3 (递归构造). 记 $V$ 是全体序列的类, $G$ 是 $V$ 上的函数, 那么 2.2 唯一地定义了 $Ord$ 上的函数 $F$ 使得$$F(\alpha )=G(F\upharpoonright \alpha )$$(2.1)对每个序数 $\alpha$ 成立.
(注意根据替换公理, $F$ 在 $\alpha$ 上的限制 $F\upharpoonright \alpha$ 是集合)

证明. 令$$\begin{array}{rl}F(\alpha )=a⟺& \text{存在序列 }⟨a_{\xi }:\xi <\alpha ⟩\text{使得}\\ & (1)(\forall \xi <\alpha )a_{\xi }=G(⟨a_{\eta }:\eta <\xi ⟩);\\ & (2)a=G(⟨a_{\xi }:\xi <\alpha ⟩).\end{array}$$(2.2)对任意的 $\alpha$, 如果存在 $\alpha$-序列满足 (1), 那么它是唯一的, 否则如果存在两个满足条件的序列 $⟨a_{\xi }:\xi <\alpha ⟩$ 和 $⟨b_{\xi }:\xi <\alpha ⟩$, 对 $\xi$ 归纳就说明 $a_{\xi }=b_{\xi }$. 进一步, 对 $\alpha$ 归纳可以说明对任意的 $\alpha$, 满足 (1) 的序列存在 (在极限序数的步骤将 $\alpha$-序列构造为 $\xi$-序列的并, $\xi <\alpha$), 因此 $F$ 对每个 $\alpha \in Ord$ 有定义. 显然 $F$ 满足 2.1, 再次使用归纳法可以说明 $F$ 的唯一性.

$\square$

推论 2.3.4. 设 $X$ 是集合, $\theta$ 是序数, 那么对任意定义在全体长度小于 $\theta$ 的序列上, 取值在 $X$ 中的函数 $G$, 存在唯一的 $X$ 中的 $\theta$-序列 $⟨a_{\alpha }:\alpha <\theta ⟩$ 使得 $a_{\alpha }=G(⟨a_{\xi }:\xi <\alpha ⟩)$.

2.4序数算术

有了递归定义法, 我们就可以在 $Ord$ 上定义加法、乘法和幂运算. 作为准备, 我们先定义序数的 “极限” 运算:

定义 2.4.1 (极限). 设 $\alpha$ 是极限序数, $⟨{\gamma }_{\xi }:\xi <\alpha ⟩$ 是不减的序数序列, 定义它的极限为$$\underset{\xi \to \alpha }{\lim }{\gamma }_{\xi }=\sup \left\{{\gamma }_{\xi }:\xi <\alpha \right\}$$

定义 2.4.2 (正规列). 序数列 $⟨{\gamma }_{\xi }:\xi \in Ord⟩$ 称为正规的, 如果它递增并且连续, 即对每个极限序数 $\alpha$, ${\gamma }_{\alpha }=\underset{\xi \to \alpha }{\lim }{\gamma }_{\xi }$.

接下来定义基本的三种运算:

定义 2.4.3 (加法). 对全体序数 $\alpha$,

1.	$\alpha +0=\alpha$;
2.	$\alpha +{\beta }^{\ast }=(\alpha +\beta {)}^{\ast },\forall \beta$;
3.	$\alpha +\beta =\underset{\xi \to \beta }{\lim }(\alpha +\xi ),\forall \text{极限序数 }\beta >0$.

定义 2.4.4 (乘法). 对全体序数 $\alpha$,

1.	$\alpha \cdot 0=0$;
2.	$\alpha \cdot {\beta }^{\ast }=\alpha \cdot \beta +\alpha ,\forall \beta$;
3.	$\alpha \cdot \beta =\underset{\xi \to \beta }{\lim }\alpha \cdot \xi ,\forall \text{极限序数 }\beta >0$.

定义 2.4.5 (幂). 对全体序数 $\alpha$,

1.	${\alpha }^0=1$;
2.	${\alpha }^{{\beta }^{\ast }}={\alpha }^{\beta }\cdot \alpha ,\forall \beta$;
3.	${\alpha }^{\beta }=\underset{\xi \to \beta }{\lim }{\alpha }^{\xi },\forall \text{极限序数 }\beta >0$.

加法和乘法具有结合律:

命题 2.4.6. 对任意的序数 $\alpha ,\beta \text{和 }\gamma$,
(1) $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$;
(2) $(\alpha \cdot \beta )\cdot \gamma =\alpha \cdot (\beta \cdot \gamma )$.

证明. 对 $\gamma$ 归纳.

$\square$

高级运算对低级运算有左分配律:

命题 2.4.7. 对任意的序数 $\alpha ,\beta \text{和 }\gamma$,
(1) $\alpha \cdot (\beta +\gamma )=\alpha \cdot \beta +\alpha \cdot \gamma$;
(2) $({\alpha }^{\beta }{)}^{\gamma }={\alpha }^{\beta \cdot \gamma }$;
(3) ${\alpha }^{\beta }\cdot {\alpha }^{\gamma }={\alpha }^{\beta +\gamma }$.

证明. 证明及反例待补充, 参见 维基百科: 序数算数.

$\square$

对所有序数 $n<\omega$, 即全体自然数, 以上运算的定义与我们熟知的运算是相同的. 但是一般来说, 交换律对加法与乘法都不成立: $$1+\omega =\omega \ne \omega +1,2\cdot \omega =\omega \ne \omega \cdot 2=\omega +\omega .$$从上面的例子也可以看到, 加法和乘法的右消去律也不成立.

序数的和与乘积也可以几何地定义, 实际上我们可以对全序集定义和与乘积:

定义 2.4.8 (和). 设 $(A,{<}_A)$ 和 $(B,{<}_B)$ 是全序集, 它们的和定义为全序集 $A\bigsqcup B$, 其中序关系定义为 $x<y$ 当且仅当如下某一条成立:
(1) $x,y\in A\wedge x{<}_{A}y$;
(2) $x,y\in B\wedge x{<}_{B}y$;
(3) $x\in A,y\in B$.
其中 $\bigsqcup$ 表示不交并.

定义 2.4.9 (积). 设 $(A,{<}_A)$ 和 $(B,{<}_B)$ 是全序集, 它们的积定义为全序集 $A\times B$, 其中序关系定义为 $(a_1,b_1)<(a_2,b_2)$ 当且仅当 $b_1<b_2$ 或 $b_1=b_2\wedge a_1<a_2$.

引理 2.4.10. 对任意的序数 $\alpha$ 和 $\beta$, 它们作为序数的和与积分别同构于作为全序集的和与积.

证明. 对 $\beta$ 归纳. 注意, 全序集的乘积中序关系的非对称定义是重要的.

$\square$

序数的算数有一一部分和自然数算数相同的性质:

命题 2.4.11 (右保序). 设 $\alpha ,\beta ,\gamma$ 是序数, $\beta <\gamma$, 那么
(1.1) $\alpha +\beta <\alpha +\gamma$;
(1.2) 如果 $\alpha >0$, 那么 $\alpha \cdot \beta <\alpha \cdot \gamma$;
(1.3) 如果 $\alpha >1$, 那么 ${\alpha }^{\beta }<{\alpha }^{\gamma }$.

注 2.4.12. 右保序说明了左消去律成立.

命题 2.4.13 (半左保序). 设 $\alpha ,\beta ,\gamma$ 是序数, $\beta <\gamma$, 那么
(2.1) $\beta +\alpha \le \gamma +\alpha$,
(2.2) $\beta \cdot \alpha \le \gamma \cdot \alpha$,
(2.3) ${\beta }^{\alpha }\le {\gamma }^{\alpha }$.
注: 这三个命题中的等号都有可能成立.

证明. 对 $\gamma$ 归纳.

$\square$

命题 2.4.14. 设 $\alpha ,\beta$ 是序数, 那么
(3.1) 如果 $\alpha <\beta$, 那么存在唯一的 $\delta$ 使得 $\beta =\alpha +\delta$;
(3.2) 如果 $\alpha >0$, 那么存在唯一的 $\delta$ 和唯一的 $\rho <\alpha$ 使得 $\beta =\alpha \cdot \delta +\rho$.

证明.
(3.1) 取 $\delta$ 为 $\left\{\xi :\alpha <\xi <\beta \right\}$ 的序型, $\delta$ 的唯一性由上个命题的 (2.1) 保证.
(3.2) 取 $\delta$ 为使得 $\alpha \cdot \delta \le \beta$ 的最大序数, $\delta =\bigcup \left\{\xi :\alpha \cdot \xi \le \beta \right\}$.

$\square$

作为本小节的结束, 我们证明 Cantor 正规形式定理:

定理 2.4.15. 每个非零序数 $\alpha$ 可以唯一地表示为$$\alpha ={\omega }^{{\beta }_0}\cdot c_0+\cdots +{\omega }^{{\beta }_n}\cdot c_n,$$其中自然数 $n\ge 1$, $\alpha \ge {\beta }_0>{\beta }_1>\cdots >{\beta }_n$, $c_0,\dots ,c_n$ 是非零自然数.

证明. 对 $\alpha$ 归纳, $\alpha =1$ 时有 $1={\omega }^0\cdot 1$; 对任意的 $\alpha >0$, 令 $\beta$ 为最大的使 ${\omega }^{\beta }\le \alpha$ 的序数, 那么存在唯一的 $\delta$ 和 $\rho <{\omega }^{\beta }$ 使得 $\alpha ={\omega }^{\beta }\cdot \delta +\rho$. 一定有 $\delta <\omega$, 否则与 $\beta$ 的最大性矛盾. 根据归纳假设, $\rho$ 可以表示为正规形式, 因此 $\alpha$ 也可以表示为正规形式. 对 $\alpha$ 归纳可以证明正规形式的唯一性 (待补充).

$\square$

注 2.4.16. 在 $\alpha$ 正规形式分解中, ${\beta }_0$ 称为 $\alpha$ 的次数, 记作 $\mathrm{deg}\alpha$, 存在 $\alpha$ 使得 $\mathrm{deg}\alpha =\alpha$, 这时 $\alpha$ 的正规形式无法用小于 $\alpha$ 的序数表达, 满足这个性质的最小的序数记为 ${\epsilon }_0$.

命题 2.4.17. 设 $a_0=0,a_{n+1}={\omega }^{a_n}$, 那么 ${\epsilon }_0=\underset{n\to \omega }{\lim }{a}_n$.

命题 2.4.18. $\mathrm{deg}\alpha =\alpha ⟺\alpha ={\omega }^{\alpha }$.

2.5推广: 扎实关系

在这一小节中, 我们将良序的概念推广到一般的二元关系上.

定义 2.5.1 (扎实关系). 集合 $P$ 上的二元关系 $E$ 称为扎实的, 如果任意的 $X\subset P$ 都含有 $E$-极小的元素. $x\in X$ 称为 $E$-极小的, 如果不存在 $y\in X$ 使得 $yEx$.

显然良序是扎实关系.

给定 $P$ 上的扎实关系 $E$, 我们可以定义 $E$ 的高, 并且为每个 $x\in P$ 定义一个序数—— $x$ 的代.

定理 2.5.2. 设 $E$ 是集合 $P$ 上的扎实关系, 那么存在唯一的函数 $\rho :P\to Ord$ 使得$$\rho (x)=\sup \left\{\rho (y)+1:yEx\right\}$$且 $\text{ran}\rho$ 是序数, 这个序数被称为 $E$ 的高.

证明. 待补充.

$\square$

2.6习题