鸭梨公共文档

主题

序数与良序 ​

1. 良序集 ​

在之前的章节中，我们已经讨论了 偏序集 (Partially Ordered Set) 和 全序集 (Totally Ordered Set)。在全序集中，集合内的任意两个元素都是可以比较的。然而，即便是在全序集中，有些集合的结构仍然比其他集合更为“整齐”。例如，自然数集 N\mathbb{N} 具有一个非常特殊的性质：任何一个非空的自然数子集，都一定存在一个最小的元素。这种性质在实数集 R\mathbb{R} 中并不成立，例如开区间 (0, 1)(0,\, 1) 就没有最小元。这种“每个子集都有最小元”的性质，正是我们本章讨论的核心——良序。

1.1 良序的定义 ​

定义 良序集 (Well-Ordered Set)：一个全序集 (W, ⩽)(W,\, \leqslant) 被称为良序集，如果 WW 的每一个非空子集 S⊆WS \subseteq W 都有一个关于关系 ⩽\leqslant 的最小元。也就是说，存在 m∈Sm \in S，使得对于所有的 x∈Sx \in S，都有 m⩽xm \leqslant x。

这个定义初看起来可能有些抽象，但它实际上是对“递归”和“归纳”思想的终极推广。如果一个集合是良序的，我们总能找到一个“起始点”（整个集合的最小元），并且对于任何一个部分，我们总能找到它的“紧接着的下一个部分”（通过取剩余部分的最小元）。

良序性有一个非常有用的等价描述：一个全序集是良序的，当且仅当它不存在无限递降链。

@theorem-1 良序的等价性：全序集 (W, ⩽)(W,\, \leqslant) 是良序的，当且仅当不存在 WW 中的无限序列 x0>x1>x2>⋯x_0 > x_1 > x_2 > \cdots。

证明： (1) 必要性：若 WW 是良序的，假设存在无限递降链 S={x0, x1, x2, ⋯ }S = \left\{x_0,\, x_1,\, x_2,\, \cdots\right\}。由于 SS 是 WW 的非空子集，它必然有最小元 xkx_k。但根据递降链的定义，xk+1<xkx_{k+1} < x_k，这与 xkx_k 是最小元矛盾。 (2) 充分性：若不存在无限递降链，假设 WW 的某个非空子集 SS 没有最小元。我们可以任取 x0∈Sx_0 \in S。因为 x0x_0 不是最小元，必然存在 x1∈Sx_1 \in S 使得 x1<x0x_1 < x_0。同理，存在 x2∈Sx_2 \in S 使得 x2<x1x_2 < x_1。如此下去，我们构造了一条无限递降链，矛盾。

例 1.1 自然数集 (N, ⩽)(\mathbb{N},\, \leqslant) 是良序集。这是皮亚诺公理的基础，也是数学归纳法之所以有效的深层原因。

例 1.2 整数集 (Z, ⩽)(\mathbb{Z},\, \leqslant) 不是良序集。考虑负整数子集 S={−1, −2, −3, ⋯ }S = \left\{-1,\, -2,\, -3,\, \cdots\right\}，它没有最小元（你可以一直往负无穷方向找更小的数）。

例 1.3 有理数集在 [0, 1][0,\, 1] 上的交集 (Q∩[0, 1], ⩽)(\mathbb{Q} \cap [0,\, 1],\, \leqslant) 不是良序集。例如，子集 S={x∈Q∣0<x⩽1}S = \left\{x \in \mathbb{Q} \mid 0 < x \leqslant 1\right\} 没有最小元，因为对于任何 x∈Sx \in S，都有 x/2∈Sx / 2 \in S 且 x/2<xx / 2 < x。

1.2 良序集的性质 ​

良序集具有非常优良的遗传性质。

@theorem-2 良序集的每个子集在继承原有的序关系下，仍然是一个良序集。

证明：设 (W, ⩽)(W,\, \leqslant) 是良序集，A⊆WA \subseteq W。对于 AA 的任何非空子集 S⊆AS \subseteq A，显然 SS 也是 WW 的非空子集。因为 WW 是良序的，所以 SS 在 WW 中有最小元 mm。由于 m∈Sm \in S 且 S⊆AS \subseteq A，这个 mm 也就是 SS 在 AA 中的最小元。

良序集最重要的应用之一是 超限归纳法 (Transfinite Induction)，它是对数学归纳法的自然推广。

@theorem-3 超限归纳法：设 (W, ⩽)(W,\, \leqslant) 是一个良序集，P(x)P(x) 是关于 WW 中元素的性质。如果对于任何 a∈Wa \in W，只要对于所有 x<ax < a 都有 P(x)P(x) 成立，就能推导出 P(a)P(a) 成立，那么对于所有的 x∈Wx \in W，P(x)P(x) 都成立。

证明：假设集合 S={x∈W∣¬P(x)}S = \left\{x \in W \mid \neg P(x)\right\} 非空。由于 WW 是良序的，SS 必然有一个最小元 mm。因为 mm 是 SS 的最小元，所以对于所有 x<mx < m，都有 x∉Sx \notin S，即 P(x)P(x) 成立。根据定理的假设，由“所有 x<mx < m 都有 P(x)P(x) 成立”可以推导出 P(m)P(m) 成立。这与 m∈Sm \in S（即 ¬P(m)\neg P(m)）矛盾。因此 SS 必须为空集。

NOTE

注意超限归纳法不需要显式地证明“基础情况” P(min⁡W)P(\min W)。因为当 aa 是最小元时，满足 x<ax < a 的 xx 不存在，前提条件“对于所有 x<ax < a 都有 P(x)P(x) 成立”是平凡真 (Vacuously True) 的。

2. 序数 ​

在之前的章节中，我们讨论了基数，它用来衡量集合的“大小”。而 序数 (Ordinal Number) 则是用来衡量良序集的“排队方式”或者说“序类型”。

2.1 序数的动机 ​

如果我们有两个良序集，我们如何判断它们的排列方式是否“一样”？在数学上，我们使用 序同构 (Order Isomorphism) 来定义。如果两个良序集之间存在一个保持顺序的双射，我们就说它们具有相同的序类型。

冯·诺依曼 (John von Neumann) 提出了一种极其天才的方法：我们不需要寻找一个抽象的“序类型”概念，我们可以直接构造出一系列标准的集合，每一个集合本身就是一个良序集，并且代表了一种唯一的序类型。这些标准的集合就是序数。

在第 5 章中，我们已经看到了自然数的冯·诺依曼构造：

  • 0=∅0 = \emptyset
  • 1={0}={∅}1 = \left\{0\right\} = \left\{\emptyset\right\}
  • 2={0, 1}={∅, {∅}}2 = \left\{0,\, 1\right\} = \left\{\emptyset,\, \left\{\emptyset\right\}\right\}
  • n={0, 1, ⋯ , n−1}n = \left\{0,\, 1,\, \cdots,\, n-1\right\}

每一个自然数都是它前面所有自然数组成的集合。序数理论就是将这种“包含前面所有成员”的想法推广到无穷远方。

2.2 序数的定义 ​

为了定义序数，我们需要先理解什么是传递集。

定义 传递集 (Transitive Set)：一个集合 AA 被称为传递集，如果 AA 的每一个元素同时也是 AA 的子集。即：若 x∈Ax \in A，则 x⊆Ax \subseteq A。

例 2.1 集合 2={0, 1}={∅, {∅}}2 = \left\{0,\, 1\right\} = \left\{\emptyset,\, \left\{\emptyset\right\}\right\} 是传递集。它的元素是 00 和 11。我们知道 0=∅⊆20 = \emptyset \subseteq 2 总是成立的，而 1={∅}1 = \left\{\emptyset\right\} 也是 22 的子集，因为它的唯一元素 ∅\emptyset 属于 22。

例 2.2 集合 {1}={{∅}}\left\{1\right\} = \left\{\left\{\emptyset\right\}\right\} 不是传递集。它的元素是 11，但 11 不是 {1}\left\{1\right\} 的子集，因为 0∈10 \in 1 但是 0∉{1}0 \notin \left\{1\right\}。

有了传递集的概念，我们就可以给出序数的正式定义：

定义 序数 (Ordinal Number)：一个集合 α\alpha 被称为序数，如果：

  1. α\alpha 是一个传递集。
  2. α\alpha 中的元素关于属于关系 ∈\in 构成良序。

通常我们用小写希腊字母 α, β, γ,⋯\alpha,\, \beta,\, \gamma, \cdots 来表示序数。

在序数的世界里，属于关系 ∈\in 就是它们的排序关系。我们定义 α<β\alpha < \beta 当且仅当 α∈β\alpha \in \beta。由于序数的定义要求元素被 ∈\in 良序排列，这意味着对于任何序数 α\alpha，其内部的结构就是 (α, ∈)\left(\alpha,\, \in\right) 是一个良序集。

2.3 后继序数与极限序数 ​

序数可以分为三类：

  1. 零：空集 ∅\emptyset 是最小的序数，记作 00。
  2. 定义 后继序数 (Successor Ordinal)：如果一个序数 α\alpha 可以表示为 α=β∪{β}\alpha = \beta \cup \left\{\beta\right\} 的形式，其中 β\beta 也是一个序数，那么 α\alpha 称为 β\beta 的后继，记作 S(β)S(\beta) 或 β+1\beta + 1。
  3. 定义 极限序数 (Limit Ordinal)：如果一个序数 λ\lambda 既不是 00，也不是任何序数的后继，那么 λ\lambda 称为极限序数。

第一个极限序数是所有自然数的集合：

ω=N={0, 1, 2, 3, ⋯ }\omega = \mathbb{N} = \left\{0,\, 1,\, 2,\, 3,\, \cdots\right\}

ω\omega 是第一个无穷序数。在 ω\omega 之后，我们可以继续应用后继运算：

ω+1=ω∪{ω}={0, 1, 2, ⋯ , ω}\omega + 1 = \omega \cup \left\{\omega\right\} = \left\{0,\, 1,\, 2,\, \cdots,\, \omega\right\}

ω+2=(ω+1)∪{ω+1}={0, 1, 2, ⋯ , ω, ω+1}\omega + 2 = (\omega + 1) \cup \left\{\omega + 1\right\} = \left\{0,\, 1,\, 2,\, \cdots,\, \omega,\, \omega + 1\right\}

如果我们把所有的 ω+n\omega + n 收集起来，我们又会得到一个新的极限序数，我们称之为 ω⋅2\omega \cdot 2（或者是 ω+ω\omega + \omega）。

2.4 序数的比较 ​

序数之间有一种非常完美的线性结构。

@theorem-4 对于任意两个序数 α\alpha 和 β\beta，恰好满足以下三种关系之一：

  1. α∈β\alpha \in \beta （即 α<β\alpha < \beta）
  2. α=β\alpha = \beta
  3. β∈α\beta \in \alpha （即 β<α\beta < \alpha）

这个定理告诉我们序数全体在 ∈\in 关系下是全序的。更进一步：

@theorem-5 序数的全体按 ∈\in 排列构成良序。

TIP

Burali-Forti 悖论：尽管序数全体的表现非常像一个良序集，但序数的全体并不能构成一个集合。如果存在一个“所有序数的集合” Ω\Omega，那么根据序数的性质，Ω\Omega 本身也会是一个序数。于是会有 Ω∈Ω\Omega \in \Omega，这意味着 Ω<Ω\Omega < \Omega，这在良序中是不可能的。因此，序数的全体是一个 真类 (Proper Class)。

3. 超限递归 ​

既然良序集可以进行归纳证明，自然也可以进行递归定义。

@theorem-6 超限递归定理 (Transfinite Recursion Theorem)：设 GG 是一个定义在全体集合上的操作（类函数），则存在唯一的类函数 FF，使得对于每一个序数 α\alpha，都有：

F(α)=G(F↾α)F(\alpha) = G(F \upharpoonright \alpha)

其中 F↾αF \upharpoonright \alpha 表示 FF 在所有小于 α\alpha 的序数上的取值。

直觉解释：这个定理告诉我们，只要我们知道如何根据“之前所有的结果”来确定“当前的结果”，我们就可以沿着序数轴一直定义下去。

一个著名的应用是 冯·诺依曼宇宙 (Von Neumann Universe) VV 的构造，它定义了集合论的累积层次：

  • V0=∅V_0 = \emptyset
  • Vα+1=P(Vα)V_{\alpha + 1} = \mathcal{P}(V_\alpha) （幂集运算）
  • Vλ=⋃β<λVβV_\lambda = \bigcup_{\beta < \lambda} V_{\beta} （对于极限序数 λ\lambda）

通过这种方式，我们可以给每一个集合分配一个“秩” (Rank)，即它第一次出现在哪个 VαV_\alpha 中。

4. 序数的算术 ​

序数的运算是自然数算术的直接推广，但由于序数涉及到无限的次序，一些我们熟悉的性质（如交换律）将会失效。

4.1 序数的加法 ​

定义 序数加法：对于序数 α\alpha，我们通过对 β\beta 的超限递归来定义 α+β\alpha + \beta：

  1. α+0=α\alpha + 0 = \alpha
  2. α+S(β)=S(α+β)\alpha + S(\beta) = S(\alpha + \beta)
  3. α+λ=sup⁡{α+β∣β<λ}\alpha + \lambda = \sup \left\{\alpha + \beta \mid \beta < \lambda\right\} （λ\lambda 为极限序数）

序数加法的直觉含义是：先排好一个序类型为 α\alpha 的队伍，紧接着后面再排一个序类型为 β\beta 的队伍。

IMPORTANT

警告：序数加法不满足交换律！

例 4.1 考虑 1+ω1 + \omega 和 ω+1\omega + 1。

  • 根据定义，1+ω=sup⁡{1+n∣n<ω}1 + \omega = \sup \left\{1 + n \mid n < \omega\right\}。因为 1+n1 + n 只是有限的自然数，其上确界仍然是 ω\omega。所以 1+ω=ω1 + \omega = \omega。
  • 而 ω+1=S(ω)\omega + 1 = S(\omega)，它包含 ω\omega 作为一个元素。在序结构上，ω+1\omega + 1 是在所有自然数 0,1,2,⋯0, 1, 2, \cdots 之后又增加了一个新元素（我们称之为“无穷远点”）。
  • 显然，ω\omega 的结构里没有最大元，而 ω+1\omega + 1 有最大元（即 ω\omega）。两个序结构不同，因此 ω≠ω+1\omega \neq \omega + 1。由此可见 1+ω≠ω+11 + \omega \neq \omega + 1。

4.2 序数的乘法 ​

定义 序数乘法：对于序数 α\alpha，通过对 β\beta 的递归定义 α⋅β\alpha \cdot \beta：

  1. α⋅0=0\alpha \cdot 0 = 0
  2. α⋅S(β)=(α⋅β)+α\alpha \cdot S(\beta) = (\alpha \cdot \beta) + \alpha
  3. α⋅λ=sup⁡{α⋅β∣β<λ}\alpha \cdot \lambda = \sup \left\{\alpha \cdot \beta \mid \beta < \lambda\right\} （λ\lambda 为极限序数）

乘法 α⋅β\alpha \cdot \beta 的直觉是：有 β\beta 份长度为 α\alpha 的排列连在一起。

同样地，序数乘法不满足交换律。 例 4.2 考虑 2⋅ω2 \cdot \omega 和 ω⋅2\omega \cdot 2。

  • 2⋅ω=sup⁡{2⋅n∣n<ω}=ω2 \cdot \omega = \sup \left\{2 \cdot n \mid n < \omega\right\} = \omega。这可以理解为将无数个“一对”并排，结果还是一个简单的无限序列。
  • ω⋅2=ω⋅1+ω=ω+ω\omega \cdot 2 = \omega \cdot 1 + \omega = \omega + \omega。这是两个 ω\omega 连在一起，形成了一个更复杂的结构（有两个互不连通的无限部分）。
  • 因此 2⋅ω≠ω⋅22 \cdot \omega \neq \omega \cdot 2。

此外，序数乘法满足左分配律 α⋅(β+γ)=α⋅β+α⋅γ\alpha \cdot (\beta + \gamma) = \alpha \cdot \beta + \alpha \cdot \gamma，但不满足右分配律。例如 (1+1)⋅ω=2⋅ω=ω(1+1) \cdot \omega = 2 \cdot \omega = \omega，而 1⋅ω+1⋅ω=ω+ω≠ω1 \cdot \omega + 1 \cdot \omega = \omega + \omega \neq \omega。

4.3 序数的幂 ​

定义 序数幂运算：通过递归定义 αβ\alpha^\beta：

  1. α0=1\alpha^0 = 1
  2. αS(β)=αβ⋅α\alpha^{S(\beta)} = \alpha^\beta \cdot \alpha
  3. αλ=sup⁡{αβ∣β<λ}\alpha^\lambda = \sup \left\{\alpha^\beta \mid \beta < \lambda\right\} （对于 α>0\alpha > 0）

利用幂运算，我们可以构造出巨大的序数，例如 ωω\omega^\omega 是所有多项式级别增长的序数极限。甚至可以定义更复杂的 ϵ0\epsilon_0，它是满足 ωϵ=ϵ\omega^\epsilon = \epsilon 的最小序数：

ϵ0=sup⁡{ω, ωω, ωωω, ⋯ }\epsilon_0 = \sup \left\{\omega,\, \omega^\omega,\, \omega^{\omega^\omega},\, \cdots\right\}

5. 良序定理 ​

我们在这一章讨论了许多关于良序集的优美性质。但一个关键的问题是：哪些集合可以被良序化？自然数集可以，实数集呢？

@theorem-7 良序定理 (Well-Ordering Theorem)：每一个集合都可以被良序化。也就是说，对于任何集合 XX，都存在一个关系 ⩽⊆X×X\leqslant \subseteq X \times X，使得 (X, ⩽)(X,\, \leqslant) 是一个良序集。

这个定理是由策梅洛 (Ernst Zermelo) 在 1904 年证明的。这个结论在当时引起了巨大的震动，因为对于像实数集 R\mathbb{R} 这样的集合，尽管定理断言它存在良序，但直到今天，没有人能够显式地写出一个具体的实数良序关系。良序定理的存在性证明高度依赖于 选择公理 (Axiom of Choice)。

6. Zorn 引理 ​

在数学证明中，我们经常需要寻找某种“极大”的对象（例如极大理想、基、极大一致集等）。Zorn 引理是处理这类问题的利器。

@theorem-8 Zorn 引理 (Zorn's Lemma)：设 (P, ⩽)(P,\, \leqslant) 是一个非空的偏序集。如果 PP 中的每一个 链 (Chain，即全序子集) 在 PP 中都有上界，那么 PP 至少存在一个极大元。

TIP

极大元 mm 的意思是：在 PP 中不存在 xx 使得 x>mx > m。注意这不代表 mm 比 PP 中所有元素都大（那是最大元），只是没人比它更大。

例 6.1 向量空间的基： 我们要证明每个向量空间 VV 都有基。 证明：

  1. 令 PP 为 VV 中所有线性无关子集构成的集合，序关系为集合包含关系 ⊆\subseteq。
  2. PP 非空，因为空集（或任一非零向量组成的集合）是线性无关的。
  3. 设 CC 是 PP 中的一条链。考虑 U=⋃S∈CSU = \bigcup_{S \in C} S。
  4. 我们可以证明 UU 也是线性无关的：若 UU 中有限个向量线性相关，因为 CC 是链，这些向量必然全部属于 CC 中的某个成员 SS，这与 SS 线性无关矛盾。
  5. 因此 U∈PU \in P，且 UU 是 CC 的上界。
  6. 根据 Zorn 引理，PP 存在极大元 BB。
  7. 这个极大线性无关集 BB 必然张成整个空间 VV（否则可以添加向量使其更大），因此 BB 是 VV 的一个基。

7. 选择公理的三大等价形式 ​

本章讨论的良序定理、Zorn 引理以及我们在第 2 章提到的选择公理，实际上在逻辑上是完全等价的。

@theorem-9 在 ZF 集合论公理体系下，以下命题是等价的：

  1. 选择公理 (AC)：任意非空集合族都有选择函数。
  2. 良序定理 (WO)：每个集合都可以被良序化。
  3. Zorn 引理 (ZL)：每条链都有上界的偏序集必有极大元。

证明思路：

  • AC ⇒\Rightarrow WO：给定集合 XX，利用选择函数从剩余元素中不断选出“下一个”元素。通过超限递归，我们可以将 XX 的元素与序数一一对应，从而诱导出良序。
  • WO ⇒\Rightarrow ZL：如果集合已经可以良序化，我们可以沿着这个良序进行构造。假设不存在极大元，我们可以构造出一条穿过整个偏序集的长链，最终导致矛盾。
  • ZL ⇒\Rightarrow AC：考虑所有部分选择函数构成的偏序集。利用 Zorn 引理找到一个极大元。这个极大元必须是一个定义在整个族上的全选择函数，否则它就不是极大的。

数学家杰里·波拿巴 (Jerry Bona) 曾有一句著名的俏皮话：

“选择公理显然是对的，良序定理显然是错的，而 Zorn 引理则没人搞得懂。”

这句话形象地说明了虽然这三者逻辑等价，但它们带给人的直觉感受却完全不同。选择公理听起来非常自然，而良序定理（实数可以排好队且每个子集有最小项）则显得极其不可思议。

参考文献 ​

  1. Jech, T. (2003). Set Theory. Springer Monographs in Mathematics.
  2. Halmos, P. R. (1960). Naive Set Theory. Van Nostrand.
  3. Kunen, K. (1980). Set Theory: An Introduction to Independence Proofs. Elsevier.