选择公理

它指向谁（出边）

推出 1

• 本页 ⟹ 佐恩引理推出
  选择公理 + Hartogs 定理 $\implies$ 佐恩引理（路线 $1\implies2$）

  设 $(P, \preceq )$ 是非空偏序集，且 $P$ 的每个链都有上界。目标是造出一个极大元。

  ① 一个选择函数：由 AC，$\mathcal{P}(P) \setminus \{\emptyset \}$ 上有选择函数 $\varphi$，即 $\varphi (A) \in A$ 对每个非空 $A \subseteq P$ 成立。整段证明只挑这一次。

  ② 链的严格上界：对链 $C \subseteq P$ 记

  $$S(C) = \{ p \in P : \forall c \in C, p \succ c \}$$

  （约定 $S(\emptyset ) = P$。）注意「$C$ 有上界」与「$S(C) \ne \emptyset$」不是一回事：$S$ 要的是严格上界。

  ③ 超限递归：只要 $S$ 非空就往下走 ——

  $$p(\alpha) = \varphi( S(\{ p(\beta) : \beta < \alpha \}) )\quad \text{ 只要} S(\{ p(\beta) : \beta < \alpha \}) \ne \emptyset;\text{ 一旦} S\text{ 为空就停}$$

  于是得到一列严格递增的 $p(0) \prec p(1) \prec p(2) \prec \cdots$。第 0 步用 $S(\emptyset ) = P \ne \emptyset$，所以 $p(0) = \varphi (P)$ 有定义。

  ④ 必停：由 Hartogs 定理，$\aleph (P)$ 是不能单射进 $P$ 的最小序数。把递归的上限取到 $\aleph (P)$ 就够 —— 若对一切 $\alpha < \aleph (P)$ 都不停，则 $\alpha \mapsto p(\alpha )$ 就是一个单射 $\aleph (P) \to P$，与 $\aleph (P)$ 的定义矛盾。故存在 $\alpha _{0} < \aleph (P)$ 使 $S(\{ p(\beta ) : \beta < \alpha _{0} \}) = \emptyset$。（这一步只用到 ZF，不用 AC。）

  ⑤ 停下来就给极大元：令 $C = \{ p(\beta ) : \beta < \alpha _{0} \}$，它是 $P$ 的一个链（而且是严格递增的），由题设存在上界 $u \in P$。

  ⑥ $u$ 是极大元：若存在 $v \in P$ 使 $u \prec v$，则由 $u \succeq c$（$\forall c \in C$）与传递性得 $v \succ c$（$\forall c \in C$），即 $v \in S(C)$ —— 与 $S(C) = \emptyset$ 矛盾。故 $u$ 是 $P$ 的极大元。∎

  $>$ 这一路线的分工很干净：AC 负责「挑」，Hartogs 负责「停」。对比之下，经由良序定理的证法（见「良序定理 $\iff$ 佐恩引理」那条黑线）是把「停」交给 Burali–Forti 悖论。

  比走良序定理更直：整段只挑一次元素，终止性由 Hartogs 定理（ZF 可证）兜底。

等价 1

• 本页 ⟺ 良序定理等价
  选择公理 $\iff$ 良序定理
  选择公理 ⇒ 良序定理（路线 1⟹4）

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

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

  $$x(\alpha) = \varphi( X \setminus \{ x(\beta) : \beta < \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$ 上：

  $$a \preceq b :\iff x^{-1}(a) \le x^{-1}(b)$$

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

  良序定理 ⇒ 选择公理（路线 4⟹1）

  设 $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 成立。∎

  这是整张星图里最关键的一条等价链的起点：AC 给「挑选」，良序给「最小」，两者互为表里。

定义引用 1

• 基数可比定理 用到 本页定义引用

  基数可比定理的前提里点名了选择公理：没有它，两个基数未必比得出大小。

谁指向它（入边）

推出 1

• 佐恩引理 ⟹ 本页推出
  佐恩引理 $\implies$ 选择公理（路线 $2\implies1$）

  设 $\{A_i\}_\{i \in I\}$ 是一族非空集合。要对它造出一个选择函数。

  ① 舞台：部分选择函数全体。令

  $$\mathcal{F} = \{ f : f\text{ 是函数}, \operatorname{dom} f \subseteq I,\text{ 且} \forall i \in \operatorname{dom} f, f(i) \in A_i \}$$

  按包含关系 $\subseteq$ 排序。$\mathcal{F} \ne \emptyset$（空函数在 $\mathcal{F}$ 中），且 $(\mathcal{F}, \subseteq )$ 是偏序集。

  ② 每个链有上界：设 $\mathcal{D} \subseteq \mathcal{F}$ 是 $\subseteq$链，令 $f = \bigcup \mathcal{D}$。

  $f$ 是函数：若 $(i, a), (i, a') \in f$，则它们分别属于某个 $f_{1}, f_{2} \in \mathcal{D}$；$\mathcal{D}$ 是链，不妨设 $f_{1} \subseteq f_{2}$，于是 $(i, a), (i, a') \in f_{2}$，而 $f_{2}$ 是函数，故 $a = a'$。 $f \in \mathcal{F}$：$\operatorname{dom} f = \bigcup _\{g \in \mathcal{D}\} \operatorname{dom} g \subseteq I$，且对 $i \in \operatorname{dom} f$ 有 $f(i) \in A_i$。 $f$ 是 $\mathcal{D}$ 的上界：$f \supseteq g$ 对一切 $g \in \mathcal{D}$ 成立。

  ③ 用佐恩引理，取 $(\mathcal{F}, \subseteq )$ 的极大元 $f$。

  ④ 极大元必须「定义在全体 $I$ 上」：若存在 $i_{0} \in I \setminus \operatorname{dom} f$，由 $A_\{i_{0}\} \ne \emptyset$ 取 $a \in A_\{i_{0}\}$，则

  $$f' = f \cup \{ (i_0, a) \}$$

  仍是 $\mathcal{F}$ 中的元素（$i_{0} \notin \operatorname{dom} f$，不破坏函数性），且 $f \subset f'$ —— 与 $f$ 的极大性矛盾。故 $\operatorname{dom} f = I$。

  ⑤ 于是 $f : I \to \bigcup _\{i \in I\} A_i$ 且 $f(i) \in A_i$ 对一切 $i$ 成立，即 $f$ 是这族集合的选择函数。由族的任意性，AC 成立。∎

  「按包含序取极大元，再证明它已经没法再大」—— 这是用佐恩引理造存在性对象的典型手法。

定义引用 1

• 选择函数 → 本页定义引用

  选择公理的陈述直接使用了「选择函数」这个词：每个 $\emptyset \notin F$ 的集合族都有选择函数。