超限归纳法

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

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

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

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

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

• 极限情况： 证明对于任何极限序数 λ, P(λ) 得出自 [P(α) 对于所有 α < λ]。

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

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

• A₀ 是什么
• 如何确定 A_α+1 自 A_α（又或者是從A₀到 A_α的部分）
• 对于极限序数 λ，如何确定 A_λ 自 A_α 的对于 α < λ 的序列。

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

• F(0) = G₁(${\displaystyle \emptyset }$)
• F(${\displaystyle \alpha +1}$) = G₂(F(${\displaystyle \alpha }$))，对于所有 ${\displaystyle \alpha \in Ord}$
• F(${\displaystyle \alpha }$) = G₃(F ${\displaystyle \upharpoonright \alpha }$)，对于所有极限序數 ${\displaystyle \alpha \neq 0}$。這裡的F ${\displaystyle \upharpoonright \alpha }$是指F 在 ${\displaystyle \{\beta \in Ord:\beta <\alpha \}}$上的限制。

注意我们要求 G₁, G₂, G₃ 的定义域足够广阔来使上述性质有意义。所以满足这些性质的序列的唯一性可以使用超限归纳证明。

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

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

• 数学归纳法
• 结构归纳法
• epsilon-归纳
• 首個不可數序數