良序定理

设 $A$、$B$ 是任意两个集合。

① 良序化。 由良序定理，$A$ 上有一个良序 $\preceq_A$、$B$ 上有一个良序 $\preceq_B$。

② 换成序数。 每个良序集序同构于唯一的一个序数，记作 $\alpha$、$\beta$。于是只需比较两个序数。

③ 序数可比。 对任意两个序数 $\alpha$、$\beta$，总有 $\alpha \in \beta$、$\alpha = \beta$、$\beta \in \alpha$ 三者之一成立（这一步是序数理论的基本事实，用的是良序性）。

• 若 $\alpha \subseteq \beta$：序同构给出单射 $A \to B$，于是 $|A| \le |B|$；
• 若 $\beta \subseteq \alpha$：同理 $|B| \le |A|$。

所以必有 $|A| \le |B|$ 或 $|B| \le |A|$。$\blacksquare$

反过来说：基数可比定理 $\implies$ 良序定理（取 $A$、$B$ 中能单射进另一个的那个方向，可以良序化较小的集合，再把良序搬到较大集合上）。所以它与 AC、良序定理、佐恩引理是同一件事。

设 $(P, \preceq )$ 是非空偏序集，且 $P$ 的每个链都有上界。由良序定理，取 $P$ 上的一个良序 $\le$（与 $\preceq$ 无关）。

用超限递归沿 $\le$ 构造 $P$ 的一个 $\preceq$链 $C$：

• 记 $U(C) = \{ u \in P : u$ 是 $C$ 的 $\preceq$上界 }。
• 若 U(C) 中存在元素有 $\preceq$严格上界，就取其中 $\le$最小的那个 $v$，令 $C \leftarrow C \cup \{v\}$；
• 否则停止。

为什么必停：每步都往 $C$ 里加入一个不属于 $C$ 的元素，所以若在任意序数处都不停，就会得到从「全体序数」到 $P$ 的单射。由替换公理模式，全体序数会是一个集合的像，即序数全体构成集合——这与 Burali-Forti 悖论矛盾。故递归在某个序数 $\beta$ 处停止。

停止时 $C$ 有上界：$C$ 是 $\preceq$链，由题设 $U(C) \ne \emptyset$，取 $u \in U(C)$。

$u$ 是极大元：若存在 $w \in P$ 使 $u \prec w$，则 $w \succ u \succeq c$（$\forall c \in C$），故 $w \in U(C)$ 是有严格上界的元素，与「停止条件」矛盾。

故 $u$ 是 $P$ 的 $\preceq$极大元。∎

设 $X$ 是集合。考虑「$X$ 的部分良序」全体：

按初始段延拓排序：

$(W_{1}, \preceq _{1}) \le (W_{2}, \preceq _{2}) \iff W_{1} \subseteq W_{2}$，$\preceq _{1} = \preceq _{2}|W_{1}$，且 $W_{1}$ 是 $(W_{2}, \preceq _{2})$ 的一个前段。

1. $(\mathcal{W}, \le )$ 是偏序集（三条性质直接验证）。
2. 每个链有上界：设 $\mathcal{D} \subseteq \mathcal{W}$ 是链。令 $W^{$} = \bigcup \{ W : (W, \preceq ) \in \mathcal{D} \}W∗=⋃{W:(W,⪯)∈D}，在 $W^{$} 上定义

因 $\mathcal{D}$ 是链，这些良序彼此兼容，$\preceq_$⪯∗​ 是 $W^{$} 上的良序，且 $(W^{$}, \preceq_)\in \mathcal{W} 是 $\mathcal{D}$ 的上界。

1. 由佐恩引理，取极大元 $(W, \preceq )$。
2. 若 $W \ne X$，取 $x \in X \setminus W$，在 $W \cup \{x\}$ 上定义序：保留 $W$ 上的 $\preceq$，并令所有 $w \in W$ 都 $\preceq x$（把 $x$ 放在最顶端）。这仍是良序，而且是 $(W, \preceq )$ 的严格延拓，与极大性矛盾。故 $W = X$，即 $X$ 被良序化。∎

设 $X$ 是集合。$X = \emptyset$ 时平凡，以下设 $X \ne \emptyset$。

1. 由 AC，非空子集族 $\mathcal{P}(X) \setminus \{\emptyset \}$ 上有选择函数 $\varphi$，即 $\varphi (A) \in A$ 对每个非空 $A \subseteq X$ 成立。
2. 用超限递归往下取元素：对序数 $\alpha$，只要余集非空就令

一旦余集为空就停止。

1. 过程一定会停：取 $X$ 的 Hartogs 数 $\aleph (X)$，即最小的不能单射进 $X$ 的序数（见「Hartogs 定理」——它在 ZF 里就能证，不需要 AC）。若对一切 $\alpha < \aleph (X)$ 过程都没停，则 $\alpha \mapsto x(\alpha )$ 就是 $\aleph (X)$ 到 $X$ 的单射，与 $\aleph (X)$ 的定义矛盾。故存在序数 $\gamma$ 使 $x : \gamma \to X$ 是双射。
2. 把 $\gamma$ 上的序经 $x$ 搬到 $X$ 上：

因为序数在 $\in$／$\le$ 下是良序的，$X$ 上这个序也是良序。∎

设 $F$ 是一族非空集合（即 $\emptyset \notin F$）。

1. 由良序定理，取 $U = \bigcup F$ 的一个良序 $\preceq$。
2. 对每个 $X \in F$：$X \ne \emptyset$ 且 $X \subseteq U$，所以 $X$ 是 $U$ 的非空子集，有 $\preceq$最小元 m(X)。
3. 定义 $f(X) = m(X)$（$X$ 唯一确定 m(X)，故这是一个函数）。则 $\operatorname{dom} f = F$ 且 $f(X) \in X$ 对一切 $X \in F$ 成立，即 $f$ 是 $F$ 的选择函数。

由 $F$ 的任意性，AC 成立。∎