超限歸納法

超限歸納法（英語：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 \}$ 上的限制。