超限歸納法

超限歸納法（英語：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}$的搜集必定是集合。）

同選擇公理的聯繫

有一個常見的誤解是超限歸納法或超限遞歸法要求選擇公理。其實超限歸納可以應用於任何良序集合。但是常見的情況是使用選擇公理來良序排序一個集合，使其適用超限歸納法。

參見

• 數學歸納法
• 結構歸納法
• ε歸納法
• 首個不可數序數