超限递归

设 $(W, \preceq )$ 是良序集。

① 造出函数。 由递归定理（取 $G(f) = \operatorname{ran}\, f$，即「前面全部取值的值域」）得到唯一的 $F$ 定义在 $W$ 上，使

每个 $F(w)$ 都是集合 —— 由替换公理模式，$\{ F(v) : v \prec w \}$ 是某个集合的像。

② $F$ 保序。 若 $v \prec w$，则 $F(v) \in \{ F(u) : u \prec w \} = F(w)$。反过来若 $F(v) \in F(w)$，则 $F(v) = F(u)$ 对某个 $u \prec w$；再由 ③ 的单射性得 $v = u \prec w$。

③ $F$ 是单射。 反设存在 $v \ne w$ 使 $F(v) = F(w)$；由于 $\preceq$ 是全序，不妨 $v \prec w$。由 ② 得 $F(v) \in F(w) = F(v)$，即 $F(v) \in F(v)$ —— 与「任何集合都不属于自身」（正则公理的推论）矛盾。（这一步是真正用到正则公理的地方。）

④ $\alpha := \operatorname{ran}\, F$ 是序数。 由替换公理模式，$\alpha = \{ F(w) : w \in W \}$ 是集合。传递性：若 $x \in F(w)$，则 $x = F(v)$ 对某个 $v \prec w$，故 $x \in \alpha$。$\in$ 良序：$\alpha$ 上的 $\in$ 经 ②③ 就是 $(W, \prec)$ 的序（$x \in y \iff F^{-1}(x) \prec F^{-1}(y)$），良序性原样搬过来。

⑤ 于是 $F$ 是 $(W, \preceq ) \to (\alpha, \in)$ 的序同构，故 $W$ 的序型 $\alpha$ 存在。

⑥ 唯一性。 设 $\alpha, \beta$ 都是 $W$ 的序型，则 $(\alpha, \in) \cong (\beta, \in)$。由三歧性，$\alpha \in \beta$、$\alpha = \beta$、$\beta \in \alpha$ 恰有一个成立。若 $\alpha \in \beta$：由 $\beta$ 传递得 $\alpha \subseteq \beta$，且 $\alpha = \{ x \in \beta : x \in \alpha \}$ 是 $\beta$ 的真初始段。把两个序同构接起来，得到 $(\alpha, \in)$ 与自己的真初始段序同构 —— 而良序集不能与自己的真初始段序同构（见下），矛盾。故 $\alpha \notin \beta$；交换 $\alpha, \beta$ 同理得 $\beta \notin \alpha$。于是只能 $\alpha = \beta$。

引理（上一步用到）：良序集 $(L, \prec)$ 不可能与它的真初始段 $L_{< a} = \{ x \in L : x \prec a \}$ 序同构。 证：设 $h : L \to L_{< a}$ 是序同构。对 $x \prec a$ 用超限归纳：若 $\forall y \prec x,\ h(y) = y$，则 $h(x)$ 是 $L_{< a}$ 中大于一切 $h(y) = y\ (y \prec x)$ 的最小元，也就是「大于一切 $y \prec x$ 的最小元」，即 $h(x) = x$（序同构把「小于 $x$ 的全部元素」映成「小于 $h(x)$ 的全部元素」）。故 $h$ 在 $L_{< a}$ 上恒等；于是 $h(a)$ 是 $L_{< a}$ 中大于一切 $y \prec a$ 的最小元，即 $h(a) = a$ —— 但 $h(a) \in L_{< a}$ 意为 $h(a) \prec a$，矛盾。∎

设 $(W, \preceq )$ 是良序集，$G$ 任给。记 $W_{< w} = \{ v \in W : v \prec w \}$。

① 初始段上的解至多一个。 设 $w \in W$，$f, g$ 都是 $W_{< w}$ 上满足递归式的函数。反设 $f \ne g$，取最小的 $v \prec w$ 使 $f(v) \ne g(v)$（这一步用的是良序性：$\{ u \prec w : f(u) \ne g(u) \}$ 非空故有最小元）。于是在 $W_{< v}$ 上 $f$ 与 $g$ 相同，从而

矛盾。故 $W_{< w}$ 上至多一个解，且这个解唯一确定。

② 构造候选关系的集合。 令

它是集合：候选的 $f$ 都是 $W_{< w} \times V$ 的子集，先由幂集公理拿到 $\mathcal{P}(W \times V)$，再用分离公理模式从里面筛出满足条件的那些（$V$ 取一个足够大的集合即可，例如 $G$ 的值域之并的幂集的幂集）。由 ①，对每个 $w$ 至多一个 $y$，所以 $R$ 是单值的，即 $R$ 是一个函数。

③ $R$ 的定义域是整个 $W$。 反设不然，取最小的 $w \notin \operatorname{dom}\, R$。则 $W_{< w} \subseteq \operatorname{dom}\, R$，于是 $f := R \upharpoonright W_{< w}$ 是 $W_{< w}$ 上满足递归式的函数（若 $v \prec w$，由 $v \in \operatorname{dom}\, R$ 及单值性得 $f(v) = G(f \upharpoonright W_{< v})$）。于是 $(w, G(f)) \in R$，与 $w \notin \operatorname{dom}\, R$ 矛盾。

故 $R$ 就是所求的函数 $F$，由 ① 唯一。

④ 超限归纳。 设 $W \setminus S$ 非空，取它的最小元 $w$。则 $W_{< w} \subseteq S$，由假设 $w \in S$，矛盾。故 $S = W$。∎