數學歸納法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數學歸納法(英語:Mathematical Induction,縮寫:MI)是一種數學證明方法,通常被用於證明某個給定命題在整個或者局部自然數範圍內成立。除了自然數以外,廣義上的數學歸納法也可以用於證明一般良基結構,例如:集合論中的。這種廣義的數學歸納法應用於數學邏輯計算機科學領域,稱作結構歸納法

雖然數學歸納法名字中有「歸納」,但是數學歸納法並非邏輯不嚴謹歸納推理法,它屬於完全嚴謹演繹推理法[1]事實上,所有數學證明都屬於演繹推理方法

定義[編輯]

最簡單和常見的數學歸納法是證明當等於任意一個自然數時某命題成立。證明分下面兩步:

骨牌一個接一個倒下,就如同一個值到下一個值的過程
  1. 證明 「當時命題成立。」(選擇數字1因其作為自然數集合中的最小值)
  2. 證明 「若假設時命題成立,可推導出在時命題成立。(代表任意自然數)」

這種方法的原理在於:首先證明在某個起點值時命題成立,然後證明從一個值到下一個值的過程有效。當這兩點都已經證明,那麼任意值都可以通過反覆使用這個方法推導出來。把這個方法想成多米諾骨牌效應也許更容易理解一些。[2][3]例如:你有一列很長的直立着的多米諾骨牌,如果你可以:

  1. 證明 「第一張骨牌會倒。」
  2. 證明 「只要任意一張骨牌倒了,其下一張骨牌也會因為前面的骨牌倒而跟着倒。」

則可下結論:所有的骨牌都會倒下。

例子[編輯]

例子1[編輯]

證明下面這個給定公式命題為真

其中為任意自然數。這是用於計算前n個自然數的和的簡單公式。

證明[編輯]

第一步-起始步驟[編輯]

第一步是驗證這個公式在時成立。左邊,而右邊,所以這個公式在時成立。第一步完成。

第二步-推遞步驟[編輯]

第二步證明假設時公式成立,則可推理公式也成立。 證明步驟如下。

假設時公式成立。即

【等式

然後在等式等號兩邊分別加上得到 【等式】 這就是時的等式。

現在需要根據等式等式演繹出等式符號形式。(需要注意的是如果給定公式不為真,則做不到)通過因式分解合併(形式轉換/字符操縱),等式的右手邊

也就是說

這樣便證明了從等式成立可推理出等式也成立。證明至此完成,結論:對於任意自然數均成立。

解釋[編輯]

在這個證明中,推理的過程如下:

  1. 首先證明命題成立,即公式時成立。
  2. 然後證明從命題成立可以推演出命題也成立。【此部實際屬於演繹推理法。技術方法是基於命題符號形式轉換出命題的符號形式】
  3. 根據上兩條從命題成立可以推理命題,也就是命題成立。
  4. 繼續推理,可以知道命題成立。
  5. 命題成立可以推導出命題也成立。
  6. 不斷的重複推導下一命題成立的步驟。(這就是所謂「歸納」推理的地方)
  7. 我們便可以下結論:對於任意自然數命題 成立。

例子2[編輯]

證明對於Fibonacci數列,定義,且,則

證明[編輯]

首先,我們先使得的情況成立, 然後,我們假定的情況下的成立的, 然後我們使得的情況也成立,(這是為了表明,如果有任意數k使得其成立,則有其+1也成立) 於是我們得證,即從,到到所有正實數都成立,就像多米諾骨牌的第一塊成立而且每一塊的下一塊都成立()

數學歸納法的變體[編輯]

在應用中,數學歸納法常常需要採取一些變化來適應實際的需求。下面介紹一些常見的數學歸納法變體。

從0以外的自然數開始[編輯]

第一種情況: 如果欲證明的命題並不是針對全部自然數,而只是針對所有大於等於某個數字b的自然數,那麼證明的步驟需要做如下修改:

  1. 第一步,證明當時命題成立。
  2. 第二步,證明如果) 成立,那麼可以推導出也成立。

用這個方法可以證明諸如「當時,這一類命題。

第二種情況: 如果欲證明的命題針對全部自然數,但僅當大於等於某個數字b時比較容易證明,則可參考如下步驟:

  1. 第一步,證明當時命題成立。
  2. 第二步,證明如果)成立,那麼可以推導出也成立。

用這種方法可以證明一些需要通過放縮來證明的不等式。

只針對偶數或只針對奇數[編輯]

如果我們想證明的命題並不是針對全部自然數,而只是針對所有奇數偶數,那麼證明的步驟需要做如下修改:

奇數方面:

  1. 第一步,證明當時命題成立。
  2. 第二步,證明如果成立,那麼可以推導出也成立。

偶數方面:

  1. 第一步,證明當或2時命題成立。
  2. 第二步,證明如果成立,那麼可以推導出也成立。

或調整命題表述,使之變為對所有正整數成立,例如

證明「對所有正奇數成立」等價於證明「對所有正整數成立」。

遞歸歸納法[編輯]

又名遞降歸納法。數學歸納法並不是只能應用於形如「對任意的」這樣的命題。對於形如「對任意的」這樣的命題,如果對一般的比較複雜,而比較容易驗證,並且我們可以實現從的遞推,的話,我們就能應用歸納法得到對於任意的,原命題均成立。

完整歸納法[編輯]

另一個一般化的方法叫完整歸納法(也稱第二數學歸納法或強歸納法),在第二步中我們假定式子不僅當時成立,當小於或等於時也成立。這樣可以設計出這樣兩步:

  1. 證明當時式子成立.
  2. 證明當時成立,那麼當時式子也成立.

例如,這種方法被用來證明:

其中 是第斐波納契數(即黃金分割)。如果我們可以假設式子已經在當時成立,從之後可以直截了當地證明當時式子成立.

這種方法也是第一種形式的特殊化:

  1. 定義是我們將證的式子,
  2. 成立
  3. 成立時成立。

結論:對一切自然數成立。

超限歸納法[編輯]

最後兩步可以用這樣一步表示:

證明如果式子在所有的成立,那麼式子在當時也成立。

實際上這是數學歸納法的大多數通式,可以知道他不僅對表達自然數的式子有效,而且對於任何在良基集(也就是一個偏序的集合,包括有限降鏈)中元素的式子也有效(這裏""被定義為 當且僅當)。

這種形式的歸納法當運用到序數(以有序的和一些的良基類的形式)時被稱為超限歸納法,它在集合論拓撲學和其他領域是一種重要的方法。

要區別用超限歸納法證明的命題的三種情況:

  1. 是一個極小元素,也就是沒有一個元素小於
  2. 有一個直接的前輩,比小的元素有一個大的元素
  3. 沒有任何前輩,也就是是一個界限序數.

參見數學歸納法的三種形式

形式寫法[編輯]

使用二階邏輯[編輯]

二階邏輯可捕捉數學歸納法這概念,表達成如下邏輯式:

是容納一自然數的述詞變元,遍歷所有述詞而非個別數字,為二階量詞(是故此式與二階邏輯有關),則是自然數變元,遍歷所有自然數。

白話解釋此式,此式說:起始步驟與推遞步驟(即歸納假設,蘊涵 ) 兩步成立會導出對任一自然數成立之結論。通常,我們為了證明第二步,會假設成立(歸納假設),再進一步證明。此牽涉到條件證法,將條件句之前件作為假設,假定其正確以便於證明。

使用一階邏輯[編輯]

若用一階邏輯將數學歸納法公設化,則須採用公設模式,替每一個可能存在的述詞設下針對其的獨立公設。舉例而言,我們僅允許三個一階述詞存在,分別名為 ,則原先以二階邏輯描述的公設可改寫為:

。然而其強度與以二階邏輯描述之邏輯式不同,前者較後者弱。理由為一階邏輯述詞之數量為可數,而二階邏輯量限所迭代的集合為不可數。

此外,二階邏輯所表示的歸納公設綜合其它皮亞諾公設同疇(categorical),且所得之自然數模型無限大。根據勒文海姆-斯科倫定理,用一階邏輯表達的理論若有可數無限大的模型,則其有不可數大的模型,是故無法前頭將所述的模型公設化[4]。亦即,用二階邏輯表達的公設僅允許一群模型彼此同構,而一階邏輯模型則因前述定理,並非每個模型都同構。

使用一階ZFC集合論[編輯]

一階ZFC集合論不允許述詞被遍歷, 但我們可以藉由遍歷集合,繞過一階邏輯之限制,描述歸納法:

本身是集合,但可視作命題——只要命題在這數下成立,數字就會收入集合。別於皮亞諾公設,將數學歸納法定為公設,ZFC集合論直接定義自然數,使得歸納法本身是定理而非公設。

數學歸納法的合理性[編輯]

皮亞諾公理視數學歸納法不證自明,設作公理,而於策梅洛-弗蘭克爾集合論,數學歸納法可從良序定理推導出來。[5] 需要注意的是數學歸納法只能判定給定命題的,而不能證偽,因為在形式轉換這一過程需要一定技巧與靈感抽象概念自然數,可通過抽象的工具去處理。通過有限的步驟處理無限物件如證明質數的無窮。

參見[編輯]

參考文獻[編輯]

  1. ^ Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26]. (原始內容存檔於2011-05-24) (英語). 
  2. ^ Matt DeVos. Mathematical Induction (PDF). 西門菲莎大學 (英語). 
  3. ^ Gerardo con Diaz. Mathematical Induction (PDF). 哈佛大學. [2019-02-10]. (原始內容 (PDF)存檔於2013-05-02) (英語). 
  4. ^ Derek Goldrei. Propositional and predicate calculus: a model of argument. Springer-Verlag London. 2005: 286-287. ISBN 1-85233-921-7 (英語). 
  5. ^ Well Ordering Principle and the Principle of Mathematical Induction (PDF). [2019-02-03]. (原始內容 (PDF)存檔於2017-11-19) (英語). 

外部連結[編輯]