集合论/序数

有限和超限序数

序数的标准表示

序数的定义很少能揭示其本质。在这种情况中，纯数学家会创建他们想要研究的对象的表示。这些表示是基于熟悉的数学结构构建的，并且等价于那些难以理解的对象。通过操作表示中的熟悉的数学结构，纯数学家就可以研究那些神秘的抽象实体的结构。

序数最常见的表示法，由冯·诺依曼提出，如下所示。序数 0 被定义为空集 $\emptyset$；序数 1 被定义为集合 $\{0\}$，当然等于 $\{\emptyset \}$。类似地，序数 2 是集合 $\{0,1\}$；序数 3 是集合 $\{0,1,2\}$；序数 4 是集合 $\{0,1,2,3\}$。任何有限序数 $n$ 被定义为集合 $\{0,1,2,\ldots ,n-1\}$（或者，在严格的表示法中，序数 α 的后继被定义为集合 $s(\alpha )=\alpha \cup \{\alpha \}\,$）。

事实上，这个定义可以自然地扩展到超限序数。序数 $\omega$ 是一个集合，它包含所有有限序数 $\{0,1,2,3,\ldots \}$。同样，$\omega +1$ 是集合 $\{0,1,2,3,\ldots ,\omega \}$；$\omega +2$ 是集合 $\{0,1,2,3,\ldots ,\omega ,\omega +1\}$；等等。

序数 $\omega +\omega$ （或 $\omega *2$）是包含所有有限序数和形式为 $\omega +n$ 的序数的集合，其中 $n$ 是一个有限序数。因此 $\omega +\omega =\{0,1,2,\ldots ;\omega ,\omega +1,\omega +2,\ldots \}$.

序数 $\omega _{1}$ 是第一个不可数序数，它是所有可数序数的集合。

良序关系

序数的基本性质是良序性。这将使上述非正式讨论能够得到正式定义，并允许我们证明一些必要的基本事实。

定义：集合 P 的全序关系是一个 P 的良序关系，如果每个非空子集都有一个最小元素。定义：良序集合 W 的初始段是形如 {w∈W|w<v} 的集合，其中 v∈W。

良序关系是一种“通用顺序”，在某种意义上，给定任意两个良序集合，一个良序集合是另一个良序集合的序同构，或者是另一个良序集合的初始段。这将在以下几个定理中得到证明。

定理：从良序集合到自身的任何增函数都是上升的：如果 (W, <) 是一个良序集合，而 f: W→W 是一个函数，使得 x>y→f(x)>f(y)，那么对于所有 w∈W，都有 f(w)≥w。

• 证明：如果 {w∈W: f(w)<w} 非空，令 v=min {w∈W: f(w)<w}。则 f(v)<v，因为 f 是增函数，所以 f(f(v)) < f(v)，所以 f(v)∈{w∈W: f(w)<w}。则 f(v)≥v，因为 v 是该集合的最小元素，这与 f(v)<v 矛盾。因此，{w∈W: f(w)<w} 必须为空。

定理：良序集合上的任何序自同构都是恒等变换。

• 证明：给定任何自同构 f: W→W，该函数及其逆函数都必须是增函数。根据上述定理，我们可以得出结论
• f(x) ≥ x
• 以及 f^-1(x) ≥ x
• f 是增函数，所以 f(f^-1(x)) ≥ f(x)
• 简化后，x ≥ f(x)。
• f(x) = x

定理：如果 *f* 和 *g* 都是良序集合 V 和 W 的序同构，则 f=g。

• 证明：g^-1∘f 和 f∘g^-1 分别是 V 和 W 上的自同构，因此它们都等于恒等函数。

定理：良序集合不存在到其任何自身初始段的序同构。

• 证明：令 (W, <) 为良序关系，令 S_v = {w∈W|w<v} 为初始段。如果 f: W→S_v 是序同构，则将 f 的范围扩展到 W，f 是一个到自身的增函数，因此 f(v)≥v。但 f(v)∈{w∈W|w<v}，因此 f(v)<v。因此，这样的 f 不存在。

定理：序同构 f: W→V 对 W 的初始段 S_w 的限制是该初始段到 V 的初始段 S_f(w) 的序同构。

• 证明：对于任何 w'∈S_w，都有 f(w')<f(w)，因此 f(w')∈S_f(w)，f 将 S_w 映射到 S_f(w) 中。此外，对于任何 v∈S_f(w)，都有 v<f(w)，因此 f^-1(v)<f^-1f(w)) = w，因此 f^-1(v) 在受限函数的域中，其中 f(f^-1(v)) = v，这意味着受限函数 f 也映射到 S_f(w) 上。因此，将 f 的域限制到 S_w，就可以将它的范围缩减到 S_f(w)，使其成为双射。

我们现在终于来到了良序关系背后的主要思想。

定理：给定任意两个良序集合，一个集合是另一个集合的序同构，或者是另一个集合的初始段。

• 证明：令 (V, <) 和 (W, <) 为两个良序集合。首先，我们使用前一个定理来建立以下事实：W 中所有 w 的集合，使得 W 中的初始段 S_w 与 V 中某个 v 的初始段 S_v 同构，是*向下闭合的*。给定任何 w∈W，如果 S_w 存在这样的同构，那么给定任何 w'<w，也存在 v'∈V 使得 S_w' 与 S_v' 序同构。

这是因为根据上述定理，将同构限制到 S_v 中 w' 的初始段，也是该段到 S_w 中 f(w') 的初始段的序同构，其中 f 是序同构。但 S_v 中的初始段也是 V 中的初始段，因为顺序是传递的，W 中的初始段也是如此。

假设存在 v∈V，其中 S_v 与 W 中任何 w 的 S_w 都不序同构。则 v 属于上述集合的补集，因此该补集非空：令 v₀ 为最小的 v。则任何 v>v₀ 也将属于该补集：如果 S_v 与某个 S_w 同构，则 v₀<v 意味着 v 也必须如此，但事实并非如此。

对于任何 v∈S_v0，都有 v<v₀，并且鉴于 v₀ 是不存在这样的同构的最小元素，所以 S_v 必须与 W 中某个 w 的 S_w 同构。此外，这样的 w 必须是唯一的，因为如果 S_v 也与 W 中某个 w' 的 S_w' 同构，则不失一般性，假设 w'<w，并令 f 和 g 分别是到 S_w 和 S_w' 的同构。则 g∘f^-1: S_w→S_w' 是一个良序集合到其自身初始段的同构，这被证明是不可能的。

这建立了一个由以下定义的函数 f: S_v0→W

f(v) = S__v 与 S__w 序同构的唯一 w∈W

我们证明了 f 的范围也是向下闭合的，这意味着如果 w∈f(V) 且 w'<w，则 w'∈f(V)。如果 w∈f(V)，则存在 v∈V 使得 f(v) = w，因此存在一个从 S__v 到 S_w 的序同构 g。对于任何 w'<w，f^-1 对 S_v 中 w' 的初始段的限制也是一个到 S_v 中 g^-1(w') 的初始段的序同构。如前所述，初始段中的初始段也是整个集合的初始段，这是由于传递性。因此，S_g^-1(w') 与 S_w' 序同构，这意味着 f(g^-1(w')) = w'。因此，w'∈f(V)。

现在要证明 f 是一个满射函数。注意，如果它不是，则像集的补集 W-f(V) 非空，因此令 w₀=min W-f(V)。w₀ 是最小值意味着对于任何 w<w₀，都有 w∈f(V)，因此 S_w0⊆f(V)。反之，如果 w∈f(V)，则 w≠w₀，因为 w₀∉f(V)。第二，如果 w>w₀，则因为范围是向下闭合的，所以 w₀∈f(V)，这是错误的。因此，w<w₀，所以 w∈S_w0，所以 f(V)=S_w0。但这意味着 f 是 S_v0 到 S_w0 的序同构，这与 v₀ 被定义为不存在这样的同构的 V 中的最小元素相矛盾。因此，W-f(V) 必须为空，而 f 是满射的。

有了所有这些，f 因此是 S_v0 和 W 之间的序同构。

这处理了存在 v∈V 的情况，其中 S_v 与 W 中任何 w 的 S_w 都不序同构。同样的论点适用于存在 w∈V 的情况，其中 S_w 与 V 中任何 v 的 S_v 都不序同构，方法是应用相同的结果，交换 V 和 W，并在 V 和 W 的初始段之间找到一个同构。

最后，假设两者都不存在，并且对于每个 v∈V，S_v 与某个 w∈W 的 S_w 序同构，并且每个 S_w 与某个 v∈V 的 S_v 序同构。则定义的函数，这次是 f: V→W，其域为整个 V，将是 V 和 W 之间的序同构。

注意，这三种情况中只有一种可能成立，这是因为良序集合与自身初始段的序同构是不可能的。

传递集和序数

序数的基本排序是集合包含关系 ∈。我们建立一个集合类，使得 a<b 当且仅当 a∈b。成为序数的基本要求是传递性。

定义：如果 S∈T 则 S⊆T，则集合 T 是传递的。扩展子集的定义：如果对于所有 S∈T 和 R∈S，都有 R∈T，则集合 T 是传递的。

在某种意义上，传递集是“向下闭合的”，这是通过 ∈ 关系实现的。

定义：序数是通过 ∈ 关系良序的传递集。

请记住，良序也意味着线性排序。因此，符号 ∈ 和 < 将在序数的元素中可互换使用。

我们现在为使用序数建立一些基本事实。

• 定理：∅ 是一个序数。
• 证明：它是通过 ∈ 在空虚意义上传递的且良序的。

• 定理：如果 β∈α 且 α 是一个序数，则 β 是一个序数。
• 证明：α 是传递的，所以 β⊆α，因此 β 也通过 ∈ 良序。如果 γ∈β，则 γ∈α，因为 β⊆α，而且 γ⊆α，因为 α 是传递的。那么，如果 δ∈γ，则 δ∈α。因此，δ、γ 和 β 都是 α 的元素，且 δ∈γ∈β，所以 δ∈β，因为 ∈ 是 α 中的传递关系。

• 定理：如果 β⊆α 且 β≠α，且 α 和 β 都是序数，则 β∈α。
• 证明：α-β 非空且是 α 的子集，令 γ = min(α-β)。

如果 δ∈γ，则 δ<γ=min(α-β)，所以 δ∉α-β，这意味着 δ∈β。反之，如果 δ∈β，则 δ∉α-β，而且 δ∈α，因为 β⊆α，且 α 是全序的，因此 δ>γ 或 δ<γ，因为它们都是 α 的元素。第一种情况实际上是不可能的：γ<δ（或 γ∈δ）与 δ∈β 一起意味着 γ∈β，因为 β 是一个传递集，但 γ 应该是一个 α-β 的元素。因此，δ<γ 或 δ∈γ。

因此，γ=β，且 γ∈α-β，所以 γ∈α。

• 定理：如果 α 和 β 是序数，则其中一个必须是另一个的子集。
• 证明：交集 α∩β 也是一个序数：作为 α 的子集，它通过 ∈ 良序。它是传递的，因为如果 γ∈α∩β，则 γ⊆α 且 γ⊆β，所以 γ⊆α∩β。

α∩β 必须等于 α 或 β。假设情况并非如此：那么 α∩β⊆α 但 α∩β≠α，所以根据前面的定理 α∩β∈α。类似地，α∩β⊆β 但 α∩β≠β，所以 α∩β∈β。但 α∩β∈α∩β，与 α 通过 ∈ 良序（特别是，∈ 必须是一个严格排序，因此它具有反自反性）相矛盾。

然后可以很容易地建立以下推论。

• 定理：如果 α 和 β 是序数且 α≠β，则 α∈β 或 β∈α。从这里开始，将 α∈β 也表示为 α<β。因此，∈ 是所有序数类的全排序。

证明：首先，验证 ∈ 是否满足传递性和反自反性。如果 α 是一个序数且 α∈α，则 α 的元素需要良序，特别是通过 ∈ 反自反的，这被 α∈α 违反。因此，对于所有序数，α∉α。其次，如果 α、β 和 γ 是序数且 α<β，β<γ，则 β∈γ 且 α∈β，因此 α∈γ，因为 γ 是一个传递集。

∈ 是一个全排序是上述定理的结果。

现在验证良序性。如果 C 是一个非空的序数类，令 α∈C。如果 α 是 C 的最小值，则 C 有一个最小值。否则，存在一个 β<α 其中 β∈C。然后 α∩C 是 α 的一个非空子集，并且有一个最小元素，所以令 γ=min α∩C。然后对于所有 δ∈C，根据刚才证明的，要么 δ=α，δ<α，要么 δ>α。在第一种情况下，γ∈α，所以 γ<α=δ。在第二种情况下，δ∈α，所以 δ∈α∩C，所以 γ≤δ。在第三种情况下，γ<α 且 α<δ，所以 γ<δ。在所有三种情况下，γ≤δ。

• 定理：如果 α 是一个序数，则 α = {β | β < α}

证明：根据序数之间 < 的定义，即 ∈。

• 定理：一个非空的序数类的交集是另一个序数，实际上是该类的最大上界（inf）。此后，它将表示为 inf。

证明：令 C 为一个序数类。假设 β∈∩C。那么对于任何 γ∈β 和 δ∈C，β∈δ 且 δ 是一个序数，所以 γ∈δ。因此，γ∈∩C，所以 ∩C 是传递的。此外，∩C 是一个序数的子集，因此通过 ∈ 良序。

• 定理：一个序数集的并集是另一个序数，实际上是该集的最小上界（sup）。此后，任何序数集的并集将表示为 sup。

证明：令 S 为一个序数集，令 α∈∪S。那么存在 β∈S，α∈β。β 是一个序数，并且是传递的，因此对于任何 γ∈α，γ∈β，因此 γ∈∪S。因此，α⊆∪S，所以 ∪S 是传递的。此外，∪S 的所有元素都是序数，并且因为所有序数在 < 下都是良序的（意味着 ∈），任何序数集，特别是 ∪S 在 < 下都是良序的。

• 定理：如果 α 是一个序数，则 α∪{α} 是一个序数。如果 β>α 是大于 α 的一个序数，则 β≥α∪{α}。

证明：α∪{α} 是一个序数集，因此在 < 下是良序的。它是传递的：如果 β∈α∪{α}，要么 β∈α 要么 β=α。在第一种情况下，如果 γ∈β，则 γ∈α 且 γα∪{α}，所以 β⊆α∪{α}。在第二种情况下，β=α⊆α∪{α}。

用 S(α)=α∪{α} 表示。S(α) 被称为 α 的后继，因为根据上面的说法，它们之间没有序数：没有序数 β 对于任何序数 α 满足 α<β<S(α)。对于任何 α，如果存在一个序数 β 使得 α=S(β)，则 α 被称为 **后继序数**。否则，α 被称为 **极限序数**。

所有序数类 *Ord* 不是一个集合。如果它是一个集合，则 sup Ord 是一个序数，并且对于任何序数，sup Ord≥α。但 S(sup Ord) 也是一个序数，并且 S(sup Ord)>sup Ord，这是一个矛盾。

我们终于来到了序数的主要意义：作为“通用的良序函数”。

• 定理：每个良序集都与唯一的序数同构。

证明：令 W 为一个良序集。考虑公式“当 S_w（W 中由 w 确定的初始段）与序数 α 同构时，F(w) = α”。

首先，注意对于给定的 w∈W，如果这样的序数存在，它是唯一的（否则，一个序数将与它自己的初始段同构），并且它也存在于所有 w'<w，实际上，S_w 上的同构等于 F，限制在 S_w 上。这是因为如果 o 是 S_w 和 α 之间的同构，则对于任何 w'<w，o 对 S_w' 的限制是 S_w' 和 o(w')<α 之间的同构。所以 F(w') = o(w') < F(w)。这也表明当 F 被定义时，F（以及 F^-1）是单调的。

反之亦然：如果 α=F(w) 对于某些 w∈W 且 β<α，则存在一个 w'<w 使得 β=F(w')。这是因为正如前面所述，F 限制在 S_w 上是 S_w 和 α 之间的同构，特别是它是满射的。此外，注意对于任何 w∈W，如果 F 为所有 w'<w 定义，则它在 w 上定义，实际上等于 F(S_w)。首先，F 是单调的，所以它是其域和像之间的同构，因此只需要证明 F(S_w) 是一个序数。它是序数的集合，因此通过 ∈ 良序。此外，如果 α ∈ F(S_w) 且 β<α，则根据刚才证明的内容，β ∈ F(S_w)，因此 F(S_w) 是一个传递集。因此，F(S_w) 是一个序数。

这表明实际上 F 在整个 W 上都定义：否则，令 v = min { w∈W | S_w 不与任何序数同构 }。然后 F 在所有 v'<v 上定义，因此根据上一段，它在 v 上定义，这是一个矛盾。

现在在 W 中添加一个大于 W 中所有元素的元素，将其称为 m。结果集仍然是一个良序集。那么上述陈述也适用于这个新的良序集，因此 F(m) 在其中定义，这意味着 S_m 与序数 F(m) 同构。但 W=S(m)。

前几个序数

定义 0 = ∅。然后定义 0 的后继

1 = S(0)，2 = S(1)，3 = S(2)，等等。

0 是一个极限序数。用 ω 表示第一个非零极限序数。ω 的存在来自无穷公理。小于 ω 的序数被称为 **有限** 或 **自然数**。自然数集有时用 N 表示，它也等于 ω。

归纳法，递归

良序性允许“向上计数”。这在归纳原理中给出

如果一个类 C 满足 3 个属性

1. 0∈C 2. α∈C → S(α)∈C 3. α 是极限序数，并且 (β<α→β∈C) 一起意味着 α∈C

那么 C 包含所有序数。这来自良序性：如果 Ord-C 非空，则 min(Ord-C) 要么是 0，要么是一个后继序数，要么是一个非零极限序数。那么要么 0∉C（违反 1），对于某个 α，S(α)=min(Ord-C) 意味着 α∈ 且 S(α)∉C（违反 2），要么 min(Ord-C) 是一个极限序数，并且所有 β<min(Ord-C) 都是 C 的元素，根据最小性，违反 3。

归纳法的一个主要目的是定义递归函数，即证明这样的递归函数存在。当递归在序数上进行时，它通常被称为“超限递归”。主要思想是，给定一个“类函数”G，它接收域为序数的函数，存在一个唯一的类函数 F，使得 F(α)=G(F 限制在 α 上) 对于所有序数 α。注意“限制在 α 上”意味着一个域限制在 α 的所有元素上，意味着所有小于 α 的序数。

超限递归的证明

序数算术

加法、乘法和乘方现在可以使用超限递归定义。