超限递归定理 | Codeboy's Blog

形式陈述

超限递归定理允许当前值依赖此前全部值。典型类版本为：给定一个适当的函数型类运算 $G$ ，存在唯一类函数 $F$ 定义在 $\mathrm{Ord}$ 上，使

F(\alpha)=G(F\mathbin{\upharpoonright}\alpha)

对每个序数 $\alpha$ 成立。固定长度版本则说，对任意序数 $\gamma$ ，可唯一构造 $F:\gamma\to V$ 满足同一递归式。存在性由逐段构造并在相容初段之间取并得到，唯一性由超限归纳证明。精确集合论表述要求 $G$ 对每个已有函数给出唯一集合，并使用替代等公理保证各阶段结果仍为集合。

直觉

自然数递归通常只读取上一项，超限递归则允许在阶段 $\alpha$ 使用所有更早阶段的完整结果定义 $F(\alpha)$ 。后继阶段常从前一对象更新，极限阶段则对整段早期历史取并、上确界或其他汇总。良序保证到达每个阶段时此前部分已经确定，递归定理则保证定义存在且唯一。

例子与边界

von Neumann 累积层级由

V_0=\varnothing,\quad V_{\alpha+1}=\mathcal P(V_\alpha),\quad V_\lambda=\bigcup_{\beta<\lambda}V_\beta

定义。序数加法也由固定左参数后、在右参数上递归得到。若极限阶段规则缺失，仅给后继公式便不能定义 $F(\omega)$ 之后的值；若同一段历史可能给出多个值，唯一性前提便失效；若规则声称产生“所有集合”之类的真类，固定长度的集合值函数也可能不存在。递归定理不是循环定义许可证： $F(\alpha)$ 只能依赖 $F\upharpoonright\alpha$ ，不能依赖自身或未来值。

推论与应用

超限递归把序数长度的无限阶段定义从直觉描述提升为有存在性与唯一性保证的可复用定理，超限归纳则证明递归对象的唯一性与性质。序数算术、累积宇宙、可构造宇宙、Borel 层级、导出列、基数枚举、规范选择过程和良基算法中的秩构造，都是它的直接应用。

参考资料

Thomas Jech, Set Theory, 3rd millennium ed., Springer, 2003，Ch. 2, transfinite recursion theorem and applications。
Kenneth Kunen, Set Theory, College Publications, 2011，Ch. I, recursion on ordinals。

形式陈述 ​

反向链接

形式陈述