超限歸納法

超限歸納法

超限歸納法又稱超窮歸納法、超限歸納證法,數學中用來證明某種類型命題的重要方法。

基本介紹

  • 中文名:超限歸納法
  • 外文名:transfinite induction
  • 別稱:超窮歸納法、超限歸納證法
  • 學科:數理科學
介紹,超限歸納,超限遞歸,同選擇公理的聯繫,套用,

介紹

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

超限歸納

假設只要對於所有的 β < α,P(β) 為真,則 P(α) 也為真。那么超限歸納告訴我們 P 對於所有序數為真。
就是說,如果 P(α) 為真只要 P(β) 對於所有 β < α 為真,則 P(α) 對於所有 α 為真。或者更實用的說:若要證明所有序數 α 都符合性質 P,你可以假定它對於所有更小的 β < α 已經是成立的。
通常證明被分為三種情況:
  • 零情況:證明 P(0) 為真。
  • 後繼情況:證明對於任何後繼序數β+1, P(β+1) 得出自 P(β)(如果需要的話,也假定對於所有 α < β 有 P(α))。
  • 極限情況:證明對於任何極限序數λ, P(λ) 得出自 [P(α) 對於所有 α < λ]。
留意,以上三種情況(證明方法)都是相同的,只是所考慮的序數類型不同。正式來說不用分開考慮它們,但在實踐時,因為它們的證明過程通常相差很大,所以需要分別表述。在一些情況下,“零情況”會被視為一種“極限情況”,因此可以使用極限序數來證明。

超限遞歸

超限遞歸是一種構造或定義某種對象的方法,它與超限歸納的概念密切相關。例如,可以定義以序數為下標的集合序列Aα,只要指定三個事項:
  • A0是什麼
  • 如何確定Aα+1Aα(又或者是從A0Aα的部分)
  • 對於極限序數 λ,如何確定AλAα的對於 α < λ 的序列。
更形式的說,我們陳述超限遞歸定理如下。給定函式類G1,G2,G3,存在一個唯一的超限序列F帶有
是所有序數的真類),使得
,對於所有
,對於所有極限序數
。這裡的
是指F
上的限制。
注意我們要求G1,G2,G3的定義域足夠廣闊來使上述性質有意義。所以滿足這些性質的序列的唯一性可以使用超限歸納證明。
更一般的說,你可以在任何良基關係R上通過超限遞歸定義對象。(R甚至不需要是集合;它可以是真類,只要它是類似集合的關係便可,也就是說:對於任何x,使得yRx的所有y的蒐集必定是集合。)

同選擇公理的聯繫

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

套用

超限歸納法是數學歸納法的形式之一,可以套用於(大的)良序集,比如說套用到序數或基數,甚至於所有有序的集。
超限歸納法可用於證明一個命題P在所有序數中成立:
基礎:證明P(0)成立;
歸納:證明對於任何一個序數b,如果P(a)在所有序數a<b中成立,那么P(b)也將成立。
後面一步常常分解為兩種情況:
能套用和一般的歸納法相似的方法的後繼序數(有直接前驅的序數),(P(a)蘊涵P(a+1)),
沒有前驅的極限序數,因此不能用這種方法。
顯然,極限序數可以通過將極限序數b看成所有小於b的序數的極限來處理:假定在所有的a<b中P(a)成立,取所有這些情況的極限(通常通過並集公理實現),則證明了P(b)。

相關詞條

熱門詞條

聯絡我們