超限归纳法

超限归纳法（英語：Transfinite Induction）是数学归纳法向（大）良序集合比如基數或序数的集合的扩展。

超限归纳编辑

假设只要对于所有的 $\beta <\alpha$ ， $P(\beta )$ 为真，则 $P(\alpha )$ 也为真。那么超限归纳告诉我们 $P$ 对于所有序数为真。

就是说，如果 $P(\alpha )$ 为真只要 $P(\beta )$ 对于所有 $\beta <\alpha$ 为真，则 $P(\alpha )$ 对于所有 $\alpha$ 为真。或者更实用的说：若要证明所有序数 $\alpha$ 都符合性质 $P$ ，你可以假定它对于所有更小的 $\beta <\alpha$ 已经是成立的。

通常证明被分为三种情况：

零情况： 证明 $P(0)$ 为真。

后继情况： 证明对于任何后继序数 $\beta +1$ ， $P(\beta +1)$ 得出自 $P(\beta )$ （如果需要的话，也假定对于所有 $\alpha <\beta$ 有 $P(\alpha )$ ）。

极限情况： 证明对于任何极限序数 $\lambda$ ， $P(\lambda )$ 得出自 [ $P(\alpha )$ 对于所有 $\alpha <\lambda$ ]。

留意，以上三種情況(證明方法)都是相同的，只是所考虑的序数类型不同。正式來說不用分开考慮它们，但在实践時，因為它们的证明過程通常相差很大，所以需要分别表述。在一些情況下，「零情況」會被視為一種「極限情況」，因此可以使用極限序數來證明。

超限递归编辑

超限递归是一種构造或定义某种對象的方法，它與超限归纳的概念密切相關。例如，可以定義以序數為下標的集合序列 A_α ，只要指定三个事項：

$A_{0}$ 是什么
如何确定 $A_{\alpha +1}$ 自 $A_{\alpha }$ （又或者是從 $A_{0}$ 到 $A_{\alpha }$ 的部分）
对于极限序数 $\lambda$ ，如何确定 $A_{\lambda }$ 自 $A_{\alpha }$ 的对于 $\alpha <\lambda$ 的序列。

更形式的说，我们陈述超限递归定理如下。给定函数类 $\mathrm {G_{1}}$ , $\mathrm {G_{2}}$ , $\mathrm {G_{3}}$ ，存在一个唯一的超限序列 $\mathrm {F}$ 带有 $\mathrm {dom} (\mathrm {F} )=Ord$ （ $Ord$ 是所有序数的真类），使得

$\mathrm {F} (0)=\mathrm {G_{1}} (\varnothing )$
$\mathrm {F} (\alpha +1)=\mathrm {G_{2}} (\mathrm {F} (\alpha ))$ ，对于所有 $\alpha \in Ord$
$\mathrm {F} (\alpha )=\mathrm {G_{3}} (\mathrm {F} \upharpoonright \alpha )$ ，对于所有极限序數 $\alpha \neq 0$ 。這裡的 $\mathrm {F} \upharpoonright \alpha$ 是指 $\mathrm {F}$ 在 $\{\beta \in Ord:\beta <\alpha \}$ 上的限制。