5. 序数

5.1序数与势

这一节简单地介绍序数与势的理论. 更深入的理论通常在集合论专著中加以发挥, 其中的许多问题甚至至今仍待解决.

我们已经见识过归纳集 $\mathbb{N}$ 和里面的自然数 $n$ 了. 我们要概括出 $n$ 的以下性质, 因为它和数数关系最大.

定义 5.1.1 (序数). 对 $\in$ 成良序集的传递集称作序数, 其中传递指的是以下性质:

$\mathrm{isTransitive}(x):\forall y(y\in x\to y\subseteq x)$

可以看出, 每个 $n\in \mathbb{N}$ 都是传递集, 而且 $\mathbb{N}$ 自己也是个传递集. 在强调序数的身份时, 自然数又称有限序数, $\mathbb{N}$ 又记为 $\omega$.

这个记号自然让我们想问是不是总有更大的序数, 答案是肯定的, 灵感来源正是 $\mathbb{N}$ 中的后继函数.

定理 5.1.2. 对任何序数 $\alpha$, 总有 $\beta =\alpha \cup \{\alpha \}$ 仍为序数, 且显然 $\alpha$ 同构于 $\beta$ 的真前段 $\beta [\alpha ]$.

证明. 显然.

$\square$

我们还可以用更豪迈的方式构造远远大的序数.

定理 5.1.3 (上界序数). 一集序数 $\{{\alpha }_i|i\in I\}$ 的并 ${\bigcup }_{i\in I}{\alpha }_i$ 还是个序数. 我们称这序数为这集序数的上确界, 记为 ${\sup }_{i\in I}{\alpha }_i$.

证明. $\forall y(y\in {\bigcup }_{i\in I}{\alpha }_i\leftrightarrow \exists i\in I(y\in {\alpha }_i)\to \exists i\in I(y\subseteq {\alpha }_i)\to y\subseteq {\bigcup }_{i\in I}{\alpha }_i)$

$\square$

我们记全体序数组成的类为 $\mathbf{Ord}$.

定理 5.1.4. $\mathbf{Ord}$ 上的 $\in$ 仍为良序, 换言之记序数 $\beta <\alpha$ 当且仅当 $\beta \in \alpha$ 是合理的.

证明. 只需要注意一族序数的交还是序数, 且仍在这个序数族内.

$\square$

定理 5.1.5 (序数的结构). $\forall alpha\in \mathbf{Ord}(\alpha =\{\beta \in \mathbf{Ord}|\beta <\alpha \})$

证明. 这就是说序数就是比它小的全体序数组成的集. 证明是轻松的, 只要注意 $\alpha [\beta ]=\beta$ 即可.

$\square$

定义 5.1.6 (序型). 由良序集比较定理不难得知, 每个良序集都唯一确定地序同构于某个序数. 我们称良序集 $(X,\le )$ 同构的序数为这良序集的序型, 记为 $\mathrm{Type}(X,\le )$, 在不引起矛盾的时候也记为 $\mathrm{Type}(X)$.

不过, 很显然 $\mathbb{N}$ 并不是按照后继的方式得来的序数. 因此, 我们也可以对序数做以下区分:

定理 5.1.7 (后继序数与极限序数). 称 $\alpha$ 是个后继序数, 若有一个序数 $\beta$ 使得 $\alpha =\beta \cup \{\beta \}$.

称 $\alpha$ 是个极限序数, 若 $\alpha =\cup \{\beta |\beta \in \alpha \}$, 这里的 $\beta$ 取遍 $\alpha$ 中的所有序数.

这个定理宣称, 序数总是后继序数与极限序数中的一种.

证明. 注意上面对极限序数其实可以有别的写法, 例如我们称 ${\lim }_{\beta <\alpha }\beta =\cup \alpha$, 则极限序数无非是 $\alpha ={\lim }_{\beta <\alpha }\beta$.

我们考虑不是后继序数的序数 $\alpha$. $\forall \beta \in \alpha (\beta \cup \{\beta \}\subseteq \alpha )$, 而 $\alpha$ 不是后继序数指出 $\alpha <\beta \cup \{\beta \}\vee \beta \cup \{\beta \}<\alpha$, 因此 $\beta \cup \{\beta \}<\alpha$.

更简单的, 根据序数结构我们可以轻松断言 $\forall \beta \cup \{\beta \}\in \alpha (\beta \in \alpha )$, 于是 $\forall \beta \in \mathbf{Ord}(\beta \in \alpha \leftrightarrow \beta \cup \{\beta \}\in \alpha )$.

我们反证. 如果存在既非后继序数也非极限序数的序数, 由于 $\mathbf{Ord}$ 是良序集, 总能选出最小的满足此条件的序数 $\alpha$. 不难注意到最小性指出 $\alpha =\{\beta \in \mathbf{Ord}|\beta =\gamma \cup \{\gamma \}\wedge \beta \in \alpha \}\cup \{\beta \in \mathbf{Ord}|\cup \beta =\beta \wedge \beta \in \alpha \}$

因此, $\cup \alpha =\{\gamma \cup \{\gamma \}|\gamma \in \alpha \}\cup \{\beta \in \mathbf{Ord}|\cup \beta =\beta \wedge \beta \in \alpha \}=\alpha$, 这指出 $\alpha$ 是个极限序数, 与假设矛盾.

$\square$

自然数有加法和乘法, 如果读者上过初中说不定还会算自然数的幂或指数, 我们希望给数大小用的序数也定义这样的计算方法.

定义 5.1.8 (序数算术). 我们递归地定义对 $\alpha$ 的序数加法如下:

1.	$\alpha +\varnothing =\alpha$
2.	$\alpha +\beta \cup \{\beta \}=(\alpha +\beta )\cup \{\alpha +\beta \}$
3.	$\alpha +{\lim }_{\gamma <\beta }\gamma ={\lim }_{\gamma <\beta }(\alpha +\gamma )$

我们递归地定义对 $\alpha$ 的序数乘法如下:

1.	$\alpha \cdot \varnothing =\varnothing$
2.	$\alpha \cdot \beta \cup \{\beta \}=(\alpha \cdot \beta )+\alpha$
3.	$\alpha \cdot {\lim }_{\gamma <\beta }\gamma ={\lim }_{\gamma <\beta }(\alpha \cdot \gamma )$

我们递归地定义对 $\alpha$ 的序数指数如下:

1.	${\alpha }^{\varnothing }=\{\varnothing \}$
2.	${\alpha }^{\beta \cup \{\beta \}}={\alpha }^{\beta }\cdot \alpha$
3.	${\alpha }^{{\lim }_{\gamma <\beta }\gamma }={\lim }_{\gamma <\beta }{\alpha }^{\gamma }$

注意我们并未像自然数里面一样证明递归定义原理, 读者可以自行解决.

序数算术在自然数上面显然和我们熟知的东西是一样的, 但是对于那些无穷序数 (即包含 $\omega$ 的序数) 而言, 这些序数算术可能会有些奇怪.

命题 5.1.9. 以下都是序数算术的性质. 为了美观, 我们将 $\in$ 换成 $<$.

1.	结合律 $\alpha +(\beta +\gamma )=(\alpha +\beta )+\gamma$, $\alpha \cdot (\beta \cdot \gamma )=(\alpha \cdot \beta )\cdot \gamma$
2.	加法单调 $\beta <\gamma \to \alpha +\beta <\alpha +\gamma \wedge \beta +\alpha \le \gamma +\alpha$
3.	乘法单调 $\beta <\gamma \wedge \varnothing <\alpha \to \alpha \cdot \beta <\alpha \cdot \gamma \wedge \beta \cdot \alpha \le \gamma \cdot \alpha$
4.	右减法 $\alpha <\beta \to \exists !\delta (\alpha +\delta =\beta )$
5.	右带余除法 $\forall \alpha (\varnothing <\alpha \to \forall \beta \exists !\gamma \exists !\rho (\beta =\alpha \cdot \gamma +\rho \wedge \rho <\alpha ))$
6.	乘法分配右加法 $\alpha \cdot (\beta +\gamma )=\alpha \cdot \beta +\alpha \cdot \gamma$
7.	幂单调 $\beta <\gamma \wedge \{\varnothing \}<\alpha \to {\alpha }^{\beta }<{\alpha }^{\gamma }\wedge {\beta }^{\alpha }\le {\gamma }^{\alpha }$
8.	幂改写右运算 ${\alpha }^{\beta +\gamma }={\alpha }^{\beta }\cdot {\alpha }^{\gamma }$, ${\alpha }^{\beta \cdot \gamma }=({\alpha }^{\beta }{)}^{\gamma }$

注 5.1.10. 这里左右是非常重要的, 读者不难举出左单调不严格, 左分配不成立, 左减法不唯一等等的各种例子.

我们在序数算术中有一个最重要的定理, 它许诺每个序数都可以写成一个漂亮的形式.

定理 5.1.11 (Cantor 正则形式). 任何序数 $\alpha$ 都可以以唯一的形式写成 $\alpha ={\omega }^{{\beta }_1}\cdot k_1+...+{\omega }^{{\beta }_n}\cdot k_n$, 其中 $\alpha \ge {\beta }_1>{\beta }_2>...>{\beta }_n$, 而 $k_1,...,k_n,n$ 都是自然数.

证明. 归纳. 注意 ${\omega }^{\alpha }\ge \alpha$, 我们反复对 $\alpha$ 用最大的 ${\omega }^{\beta }<\alpha$ 做带余除法即可.

$\square$

不难发现这里 ${\beta }_1$ 是可以等于 $\alpha$ 的, 这其实是 $ϵ$ 数的来源. 这些用不动点来定义的大序数最后会和一些数学公理系统的证明论强度排序扯在一起, 不得不说是很奇妙的事情, 读者若有兴趣可以自行研读后续相关章节和相关书目.

实数理论中, 我们不会用到不可数的序数. 不过, 我们还得先定义不可数, 这需要引入朴素的势的概念.

定义 5.1.12 (势). 称集合 $A$ 的势不大于 $B$, 记为 $|A|\le |B|$, 若存在从 $A$ 到 $B$ 的单射.

称集合 $A$ 与集合 $B$ 等势, 记为 $|A|=|B|$, 若存在 $A$ 与 $B$ 之间的双射.

简记 $|A|\le |B|\wedge \neg (|A|=|B|)$ 为 $|A|<|B|$.

很显然, 单射的复合还是单射使得这个 $|-|\le |-|$ 具备传递性. 恒等映射是单射使得它具备自反性, 而它的 " 反对称性 "(从而它是个 " 偏序 ") 则由以下著名定理给出.

定理 5.1.13 (Cantor-Bernstein). $|A|\le |B|\to |B|\le |A|\to |A|=|B|$

证明. 这是一个非常精彩的构造.

首先设有 $f:A\hookrightarrow B$ 与 $g:B\hookrightarrow A$ 见证两个比较. 假定 $B^{\prime }=g(B)$, 又作 $h=g\circ f:A\hookrightarrow A$, 记 $A_1=h(A)$, 则 $A_1\subseteq B^{\prime }\subseteq A$ 且 $|A|=|A_1|$, 于是不妨设 $A_1\subseteq B\subseteq A$, 且已知一个双射 $f:A\hookrightarrow A_1$, 来找 $|A|=|B|$ 的证据.

轮流定义 $A_0=A,A_{n+1}=f(A_n)$ 和 $B_0=B,B_{n+1}=f(B_n)$, 则 $A_0\supseteq B_0\supseteq A_1\supseteq B_1\supseteq ...$, 于是令 $C_n=A_n\backslash B_n,D_n=B_n\backslash A_{n+1}$, 有 $A_n=({\bigcup }_{m\ge n}{C}_m)\cup ({\bigcup }_{m\ge n}{D}_m)$ 和 $B_n=({\bigcup }_{m>n}{C}_m)\cup ({\bigcup }_{m\ge n}{D}_m)$.

注意 $f_n=f{|}_{C_n}$ 是 $C_n$ 到 $C_{n+1}$ 的双射, 令 $F=({\bigcup }_{n\in \mathbb{N}}{f}_n)\cup ({\bigcup }_{n\in \mathbb{N}}i{d}_{D_n})$, 它就是一个 $A=A_0$ 到 $B=B_0$ 的双射.

$\square$

对于势的比较, 我们有最经典的对角线论证法, 它指出幂集的势总是严格的更大.

定理 5.1.14 (Cantor). $|A|<|\mathcal{P}A|$

证明. 显然 $x\mapsto \{x\}$ 给出了 $|A|\le |\mathcal{P}A|$ 的证据. 反证, 设有 $f:\mathcal{P}A\hookrightarrow A$ 同时是个满射.

考虑 $B=\{x\in A|x\notin f(x)\}$, 则 $\exists a\in A(f(a)=B)$ 将导出 $a\in B\leftrightarrow a\notin B$, 显然矛盾.

$\square$

我们还有一个更精巧的结构, 它给出了一个最小的势严格大于给定集的序数.

定理 5.1.15 (Hartogs). 对任意集合 $A$, 定义 $\aleph (A)=\{\mathrm{Type}(S,R)|S\subseteq A,R\subseteq S^2,isWellOrder(R)\}$, 这是个序数, 且有 $\neg (|\aleph (A)|\ge |A|)$.

此外, 对任何序数 $\alpha$, $\neg (|\alpha |\le |A|)\to |\aleph (A)|\le |\alpha |$.

证明. 首先要验证 $\aleph (A)$ 是个序数, 这是因为它是一集序数, 而且向下封闭 (即比其中某序数小的序数一定也在其中).

这两个命题都采取反证. 第一个, 如果存在这样的单射, 那么 $\aleph (A)$ 及其良序结构将被同构地投射到一个 $A$ 的子集上, 从而得到 $\aleph (A)\in \aleph (A)$ 引发矛盾. 第二个, 由于 $\aleph (A)$ 与 $\alpha$ 都是序数, 反证的假设就给出 $\alpha <\aleph (A)$, 从而由定义可以找到一个 $A$ 的良序子集与 $\alpha$ 同构, 这给出 $\alpha$ 到 $A$ 的单射, 矛盾.

$\square$

这样, 如果 $\mathcal{P}A$ 上面有良序, 我们就有推论: $|\aleph (A)|\le |\mathcal{P}A|$. 但是这两位究竟是相等还是严格小, 就是集合论中的的经久难题了.

5.2良基关系与正则公理

我们先来重温一下三个重要的定义.

定义 5.2.1. 称 $X$ 是传递的, 若 $x\in X\to y\in x\to y\in X$.

称 $X$ 上的关系 $E$ 为良基关系, 若对任意满足 $\exists z\in X(\phi (z))$ 的性质 $\phi$ 均有 $\exists x\in X\forall y\in X(\phi (x)\wedge (\phi (y)\to \neg yEx))$

称 $X$ 上的关系 $E$ 为外延关系, 若 $\forall x\in X\forall y\in X(\forall z\in X(zEx\leftrightarrow zEy)\to x=y)$

注 5.2.2. 传递集因此也可以理解为使得 $\in \cap X^2$ 成为一个 $X$ 上传递关系的集.

注 5.2.3. 注意, 这两个句子既可以理解为 ZFC 的, 也可以理解为 BGC 的. 在前一个情况下, $x\in X$ 也将被理解为某个性质 $inX(x)$; 在后一个情况下, 我们总是默认加入类集 (set-like) 的要求: $\forall x\in X\exists y=\{z\in X|zEx\}$, 换言之要求写出来的这东西是个集. 我们将简记之为 $ex{t}_E(x)$.

在这里, 我们总是恪守 ZF 的本分, 而不去细细检讨 BG 里面可能出现的东西.

定理 5.2.4 (良基归纳法). 假定 $X$ 上有一良基关系 $E$, 又有一个性质 $\Phi$ 满足 $\forall x\in X(\forall y\in X(yEx\to \Phi (y))\to \Phi (x))$, 则有 $\forall x\in X(\Phi (x))$.

证明. 反证, 若 $\exists x\in X(\neg \Phi (x))$, 则考虑性质 $\neg \Phi (x)$, 由良基的定义知 $\exists x\in X\forall y\in X(\neg \Phi (x)\wedge (\neg \Phi (y)\to \neg yEx))$, 换言之 $\exists x\in X(\neg \Phi (x)\wedge \forall y\in X(yEx\to \Phi (y)))$, 这与第二假定产生矛盾.

$\square$

定理 5.2.5 (递归定义原理). 假定 $X$ 上有一良基关系 $E$, 又有一个函数 $G:V\to V$, 则存在唯一的函数 $F:X\to X$ 满足 $\forall x\in X(F(x)=G(x,F{|}_{ex{t}_E(x)}))$

证明. $F(x)=y\leftrightarrow \exists t\subseteq X(x\in t\wedge {\mathrm{isTransitive}}_E(t)\wedge \exists f:t\to X(f(x)=y\wedge \forall z\in X(z\in t\to f(z)=G(z,F{|}_{ex{t}_E(z)}))))$, 其中 ${\mathrm{isTransitive}}_E(t)$ 指的是 $\forall x\in t\forall y\in X(yEx\to y\in t)$, 这里 ${\mathrm{isTransitive}}_E(t)$ 指的是 $xEy\to yEt\to xEt$.

$\square$

注 5.2.6. 采取 "BG 包装的 ZF" 有一个好处, 类上的关系/函数其实就是一个公式, 所以只要验证这个公式满足条件, 这是一阶逻辑的搬砖工作. 虽然这样写比较抽象, 但是看起来很短.

定理 5.2.7 (Mostowski). $(X,E)$ 中 $E$ 是 $X$ 上的良基外延关系, 则存在唯一一个传递的 $M$ 和函数 $\pi :X\to M$ 使得 $(X,E)$ 与 $(M,\in )$ 在 $\pi$ 的见证下同构.

证明. 首先证明存在性. 利用递归定义, 我们作 $\pi (x)=\{\pi (y)|yEx\}$, 然后直接让 $M=\pi (X)$, 不难验证它确实是传递的. 我们来验证 $\pi$ 确实见证同构. 它显然保持关系且满, 所以只要验证它单, 这只要对命题 "$\pi$ 在 $ex{t}_E(x)$ 上是单的 " 运用良基归纳法即可.

接着证明唯一性, 换言之只要证明若有传递的 $M_1$ 与 $M_2$ 之间的 $\in -$ 同构 $\pi$, 则 $M_1=M_2$ 且 $\pi =id$. 这是通过在 $(M_1,\in )$ 上面归纳命题 $\pi (x)=x$ 得到的.

$\square$

这样, 良基关系的主要成果就介绍完了. 我们来回顾一下正则公理.

定义 5.2.8 (正则公理). $\mathbf{V}=\mathbf{WF}$

它现在看起来有点奇怪, 因为我们还没有定义良基集.

定义 5.2.9 (积累层级). 作以下集合.

1.	$W{F}_{\varnothing }=\varnothing$
2.	$W{F}_{\alpha \cup \{\alpha \}}=\mathcal{P}(W{F}_{\alpha })$
3.	$W{F}_{{\lim }_{\beta <\alpha }\beta }={\bigcup }_{\beta <\alpha }W{F}_{\beta }$

我们收集它们, 得到 $\mathbf{WF}={\bigcup }_{\alpha \in \mathbf{Ord}}W{F}_{\alpha }$. 它称作积累层级.

注 5.2.10. 换言之, 良基公理现在是 $\forall x\exists \alpha \in \mathbf{Ord}(x\in W{F}_{\alpha })$.

定理 5.2.11. 这个定义与原来的定义在 $ZF-Fund$ 中等价.

证明. 显然用这个定义来推 $(Fund)$ 很简单 (反证得到序数无穷降链), 而用 $(Fund)$ 推 $\mathbf{V}=\mathbf{WF}$ 只需要反证.

$\square$

推论 5.2.12. 我们有 $\mathrm{rank}:\mathbf{V}\to \mathbf{Ord}$, 它将集合 $x$ 投到最小满足 $x\in W{F}_{\alpha \cup \{\alpha \}}$ 的 $\alpha$ 上.

这里下标是 $\alpha \cup \{\alpha \}$ 是因为在积累层级的最底部有 $\varnothing \notin \varnothing$.

定理 5.2.13 (收集原理模式). 任给 $\varphi$, 均有 $\forall X\exists Y\forall u\in X(\exists v(\varphi (u,v))\to \exists v\in Y(\varphi (u,v)))$

证明. 提取 $\mathrm{rank}$ 最小的那些证据.

$\square$

注 5.2.14. 可以证明, 它与替换公理模式等价.

正常的基数理论需要用到选择公理 (见下). 然而, $\mathbf{V}=\mathbf{WF}$ 给了我们另一个机会, 我们由此可以在 ZF 中定义一个基数的类似物, 它同样可以代替势的概念.

定义 5.2.15 (无选择基数). 我们将集合 $A$ 的无选择基数 $\mathrm{card}(A)$ 定义为全体和 $A$ 等势, 且具有最小的 $\mathrm{rank}$ 的那些集构成的集. 无选择指的是没有选择公理.

定理 5.2.16. $|A|=|B|\leftrightarrow \mathrm{card}(A)=\mathrm{card}(B)$

注 5.2.17. 然而, 这个 $\mathrm{card}$ 并不能给出 $\mathrm{card}(X)=\mathrm{card}(\mathrm{card}(X))$, 这是一个重要的缺憾.

定义 5.2.18 (无选择基数的比较). 定义 $\mathrm{card}(A)\le \mathrm{card}(B)$ 当且仅当 $\exists X\in \mathrm{card}(A)\exists Y\in \mathrm{card}(B)\exists f:X\hookrightarrow Y$, 换言之 $|A|\le |B|$.

注 5.2.19. 这个定义非常不直观, 因为我们并没有给出 $\mathrm{card}(A)$ 这个集合本身怎么用来比较, 这是另一个重要的缺憾. 由于此时没有 AC, 也就没有 CC(见下节), 我们不能断言两个 $\mathrm{card}$ 一定是可比较的.

由于不一定可比较, 无选择基数的算术比有选择的正常基数的算术还要复杂, 牵涉的问题也多得多, 我们放在后面继续介绍.