超限歸納法

超限歸納法（transfinite induction）是數學歸納法向（大）良序集合比如基數或序數的集合的擴展。

假設只要對於所有的 β < α，P(β) 為真，則 P(α) 也為真。那麼超限歸納告訴我們 P 對於所有序數為真。

就是説，如果 P(α) 為真只要 P(β) 對於所有 β < α 為真，則 P(α) 對於所有 α 為真。或者更實用的説：若要證明所有序數 α 都符合性質 P，你可以假定它對於所有更小的 β < α 已經是成立的。

通常證明被分為三種情況：

留意，以上三種情況(證明方法)都是相同的，只是所考慮的序數類型不同。正式來説不用分開考慮它們，但在實踐時，因為它們的證明過程通常相差很大，所以需要分別表述。在一些情況下，“零情況”會被視為一種“極限情況”，因此可以使用極限序數來證明 ^[1]  。

超限遞歸是一種構造或定義某種對象的方法，它與超限歸納的概念密切相關。例如，可以定義以序數為下標的集合序列A_α，只要指定三個事項：

更形式的説，我們陳述超限遞歸定理如下。給定函數類G₁,G₂,G₃，存在一個唯一的超限序列F帶有

（

是所有序數的真類），使得

，對於所有

，對於所有極限序數

。這裏的

是指F在

上的限制。

注意我們要求G₁,G₂,G₃的定義域足夠廣闊來使上述性質有意義。所以滿足這些性質的序列的唯一性可以使用超限歸納證明。

更一般的説，你可以在任何良基關係R上通過超限遞歸定義對象。（R甚至不需要是集合；它可以是真類，只要它是類似集合的關係便可，也就是説：對於任何x，使得yRx的所有y的蒐集必定是集合。） ^[2] 

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

超限歸納法是數學歸納法的形式之一，可以應用於（大的）良序集，比如説應用到序數或基數，甚至於所有有序的集。

超限歸納法可用於證明一個命題P在所有序數中成立：

基礎：證明P(0)成立；

歸納：證明對於任何一個序數b，如果P(a)在所有序數a<b中成立，那麼P(b)也將成立。

後面一步常常分解為兩種情況：

能應用和一般的歸納法相似的方法的後繼序數（有直接前驅的序數），（P(a)藴涵P(a+1)），

沒有前驅的極限序數，因此不能用這種方法。

顯然，極限序數可以通過將極限序數b看成所有小於b的序數的極限來處理：假定在所有的a<b中P(a)成立，取所有這些情況的極限（通常通過並集公理實現），則證明了P(b)。