超限递归定理

普通递归也可以读取整段历史；超限递归的新问题是索引越过全部有限阶段后还要继续。后继序数 $\alpha +1$ 有紧邻前驱，而非零极限序数 $\lambda$ 没有“上一项”，所以仅写一个从前项更新的公式不够，必须说明极限处如何使用整个初段。

常见定义分成初值、后继和极限三种情况，但这只是组织规则 $G$ 的方便形式。极限规则可以是取并、取上确界，也可以是另一种集合值操作；递归定理本身不要求单调性或连续性，只要求规则对每个历史给出唯一合法值。

累积层级的第一批值 ​

von Neumann 层级定义为

其中 $\lambda$ 为非零极限序数。于是 $V_1=\{\varnothing \}$，$V_2=\{\varnothing ,\{\varnothing \}\}$，$V_3$ 有四个元素。到 $\omega$ 时没有 $V_{\omega -1}$ 可取；$V_{\omega }$ 是所有有限层的并，恰好由遗传有限集组成。每个有限序数都属于某个有限层，所以 $\omega \subseteq V_{\omega }$；但 $\omega$ 不是遗传有限集，故 $\omega \notin V_{\omega }$。下一步取幂集才有 $\omega \in V_{\omega +1}$。这区分了极限处收集旧层的元素，与后继处加入这些元素的新子集。

固定序数 $\alpha$，序数加法理路序数算术Ordinal arithmetic以良序拼接和按序复制解释序数加、乘、幂，明确零底数约定、单侧分配律与 Cantor 标准形。也在右参数上递归：$\alpha +0=\alpha$，$\alpha +(\beta +1)=(\alpha +\beta )+1$，极限处取此前值的上确界。因此 $1+\omega =\underset{n<\omega }{sup}(1+n)=\omega$，而 $\omega +1>\omega$。递归的方向解释了加法不交换。

为什么不会发生冲突 ​

若 $F,H$ 都满足规则而不相同，取它们最早不同的索引 $\alpha$。此前完全相同意味着 $F\upharpoonright \alpha =H\upharpoonright \alpha$，把同一输入交给单值规则 $G$，便得到 $F(\alpha )=H(\alpha )$，矛盾。这是超限归纳理路超限归纳法Transfinite induction若性质在每个序数处由所有更小序数上的成立推出，则它对全部序数成立。中最小反例论证的具体使用。

存在性则组织成相容的局部解：后继处添加唯一新值，极限处将此前的局部解取并。唯一性保证该并仍是函数，替代公理保证固定序数长度内所需的值和初段能收集成集合。若漏写极限规则，$F(\omega )$ 尚未确定；若规则允许多个输出，就不能据此保证唯一；若要求某一步输出“所有集合”，则已经超出集合值定理的适用范围。读取当前或未来值的循环方程也不自动受此定理保障。

超限递归负责对象的存在唯一性，超限归纳负责它们的性质，两者在层级构造中配合使用。可构造宇宙、Borel 层级与反复取导集的序列，都须明确后继和极限操作；基数枚举、规范选择过程也可用序数组织阶段，但选择规则所需的额外公理不能由递归定理代替。

集合大小的良基关系也有相应版本。设 $E$ 是集合 $A$ 上的良基关系，${\mathrm{pred}}_E(a)=\{b\in A:bEa\}$；若一条可定义规则 $H(a,s)$ 对每个定义在 ${\mathrm{pred}}_E(a)$ 上的函数 $s$ 指定唯一集合值，则存在唯一函数 $F$ 满足

唯一性由最小反例法得到，存在性则把相容的向下封闭局部解拼合；替换保证结果仍是集合函数。这一良基递归版本可构造关系秩与 Mostowski 坍缩，不要求 $E$ 本身是全序。不过索引允许超限不意味着计算机能在有限时间执行全部步骤：此处首先是数学存在性定理。