超限归纳法

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

超限归纳

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

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

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

• 零情况： 证明${\displaystyle P(0)}$为真。
• 后继情况： 证明对于任何后继序数${\displaystyle \beta +1}$， ${\displaystyle P(\beta +1)}$得出自${\displaystyle P(\beta )}$（如果需要的话，也假定对于所有 ${\displaystyle \alpha <\beta }$ 有${\displaystyle P(\alpha )}$）。
• 极限情况： 证明对于任何极限序数${\displaystyle \lambda }$，${\displaystyle P(\lambda )}$得出自 [${\displaystyle P(\alpha )}$对于所有${\displaystyle \alpha <\lambda }$]。

留意，以上三种情况(证明方法)都是相同的，只是所考虑的序数类型不同。正式来说不用分开考虑它们，但在实践时，因为它们的证明过程通常相差很大，所以需要分别表述。在一些情况下，“零情况”会被视为一种“极限情况”，因此可以使用极限序数来证明。

超限递归

超限递归是一种构造或定义某种对象的方法，它与超限归纳的概念密切相关。例如，可以定义以序数为下标的集合序列 A_α ，只要指定三个事项：

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

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

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

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

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

同选择公理的联系

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

参见

• 数学归纳法
• 结构归纳法
• ε归纳法
• 首个不可数序数