超限归纳法

超限归纳法（Template:Lang-en）是数学归纳法向（大）良序集合比如基數或序数的集合的扩展。

超限归纳

假设只要对于所有的$\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}}_{\mathrm{1}}$, ${\mathrm{G}}_{\mathrm{2}}$, ${\mathrm{G}}_{\mathrm{3}}$，存在一个唯一的超限序列$\mathrm{F}$带有$\mathrm{d}\mathrm{o}\mathrm{m}(\mathrm{F})=Ord$（$Ord$ 是所有序数的真类），使得

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

注意我们要求${\mathrm{G}}_{\mathrm{1}}$, ${\mathrm{G}}_{\mathrm{2}}$, ${\mathrm{G}}_{\mathrm{3}}$的定义域足够广阔来使上述性质有意义。所以满足这些性质的序列的唯一性可以使用超限归纳证明。

更一般的说，你可以在任何良基关系$R$上通过超限递归定义對象。（$R$甚至不需要是集合；它可以是真类，只要它是类似集合的关系便可，也就是说：对于任何 $x$，使得$yRx$的所有$y$的搜集必定是集合。）

同选择公理的联系

有一个常见的误解是超限归纳法或超限递归法要求选择公理。其實超限归纳可以应用于任何良序集合。但是常见的情况是使用选择公理来良序排序一个集合，使其適用超限归纳法。

参见

• 数学归纳法
• 结构归纳法
• ε歸納法
• 首個不可數序數