Loading AI tools
来自维基百科,自由的百科全书
數學歸納法(英語:Mathematical Induction,縮寫:MI)是一種數學證明方法,通常被用於證明某個給定命題在整個或者局部自然數範圍內成立。除了自然數以外,廣義上的數學歸納法也可以用於證明一般良基結構,例如:集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域,稱作結構歸納法。
此條目需要擴充。 (2013年10月18日) |
雖然數學歸納法名字中有「歸納」,但是數學歸納法並非邏輯上不嚴謹的歸納推理法,它屬於完全嚴謹的演繹推理法。[1]事實上,所有數學證明都屬於演繹推理方法。
最簡單和常見的數學歸納法是證明當等於任意一個自然數時某命題成立。證明分下面兩步:
這種方法的原理在於:首先證明在某個起點值時命題成立,然後證明從一個值到下一個值的過程有效。當這兩點都已經證明,那麼任意值都可以通過反覆使用這個方法推導出來。把這個方法想成多米諾骨牌效應也許更容易理解一些。[2][3]例如:你有一列很長的直立著的多米諾骨牌,如果你可以:
則可下結論:所有的骨牌都會倒下。
其中為任意自然數。這是用於計算前n個自然數的和的簡單公式。
第一步是驗證這個公式在時成立。左邊,而右邊,所以這個公式在時成立。第一步完成。
第二步證明假設時公式成立,則可推理出時公式也成立。 證明步驟如下。
假設時公式成立。即
【等式】
現在需要根據等式等式演繹出等式的符號形式。(需要注意的是如果給定公式不為真,則做不到)通過因式分解合併(形式轉換/字符操縱),等式的右手邊
也就是說
這樣便證明了從等式成立可推理出等式也成立。證明至此完成,結論:對於任意自然數,均成立。
證明對於Fibonacci數列,定義,且,則。
首先,我們先使得的情況成立, 然後,我們假定的情況下的成立的, 然後我們使得的情況也成立,(這是為了表明,如果有任意數k使得其成立,則有其+1也成立) 於是我們得證,即從,到到所有正實數都成立,就像多米諾骨牌的第一塊成立而且每一塊的下一塊都成立()
在應用中,數學歸納法常常需要採取一些變化來適應實際的需求。下面介紹一些常見的數學歸納法變體。
第一種情況: 如果欲證明的命題並不是針對全部自然數,而只是針對所有大於等於某個數字b的自然數,那麼證明的步驟需要做如下修改:
用這個方法可以證明諸如「當時,這一類命題。
第二種情況: 如果欲證明的命題針對全部自然數,但唯若大於等於某個數字b時比較容易證明,則可參考如下步驟:
用這種方法可以證明一些需要通過放縮來證明的不等式。
如果我們想證明的命題並不是針對全部自然數,而只是針對所有奇數或偶數,那麼證明的步驟需要做如下修改:
奇數方面:
偶數方面:
或調整命題表述,使之變為對所有正整數成立,例如
又名遞降歸納法。數學歸納法並不是只能應用於形如「對任意的」這樣的命題。對於形如「對任意的」這樣的命題,如果對一般的比較複雜,而比較容易驗證,並且我們可以實現從到的遞推,的話,我們就能應用歸納法得到對於任意的,原命題均成立。
另一個一般化的方法叫完整歸納法(也稱第二數學歸納法或強歸納法),在第二步中我們假定式子不僅當時成立,當小於或等於時也成立。這樣可以設計出這樣兩步:
例如,這種方法被用來證明:
其中 是第個費波納契數和(即黃金分割)。如果我們可以假設式子已經在當和時成立,從之後可以直截了當地證明當時式子成立.
這種方法也是第一種形式的特殊化:
結論:對一切自然數成立。
最後兩步可以用這樣一步表示:
實際上這是數學歸納法的大多數通式,可以知道他不僅對表達自然數的式子有效,而且對於任何在良基集(也就是一個偏序的集合,包括有限降鏈)中元素的式子也有效(這裡""被定義為 若且唯若和)。
這種形式的歸納法當運用到序數(以良序的和一些的良基類的形式)時被稱為超限歸納法,它在集合論、拓撲學和其他領域是一種重要的方法。
要區別用超限歸納法證明的命題的三種情況:
參見數學歸納法的三種形式。
二階邏輯可捕捉數學歸納法這概念,表達成如下邏輯式:
是容納一自然數的述詞變元,遍歷所有述詞而非個別數字,為二階量詞(是故此式與二階邏輯有關),與則是自然數變元,遍歷所有自然數。
白話解釋此式,此式說:起始步驟與推遞步驟(即歸納假設,蘊涵 ) 兩步成立會導出對任一自然數, 成立之結論。通常,我們為了證明第二步,會假設成立(歸納假設),再進一步證明。此牽涉到條件證法,將條件句之前件作為假設,假定其正確以便於證明。
若用一階邏輯將數學歸納法公設化,則須採用公設模式,替每一個可能存在的述詞設下針對其的獨立公設。舉例而言,我們僅允許三個一階述詞存在,分別名為、、 ,則原先以二階邏輯描述的公設可改寫為:
。然而其強度與以二階邏輯描述之邏輯式不同,前者較後者弱。理由為一階邏輯述詞之數量為可數,而二階邏輯量限所迭代的集合為不可數。
此外,二階邏輯所表示的歸納公設綜合其它皮亞諾公設為同疇(categorical),且所得之自然數模型無限大。根據勒文海姆-斯科倫定理,用一階邏輯表達的理論若有可數無限大的模型,則其有不可數大的模型,是故無法前頭將所述的模型公設化[4]。亦即,用二階邏輯表達的公設僅允許一群模型彼此同構,而一階邏輯模型則因前述定理,並非每個模型都同構。
一階ZFC集合論不允許述詞被遍歷, 但我們可以藉由遍歷集合,繞過一階邏輯之限制,描述歸納法:
本身是集合,但可視作命題——只要命題在這數下成立,數字就會收入集合。別於皮亞諾公設,將數學歸納法定為公設,ZFC集合論直接定義自然數,使得歸納法本身是定理而非公設。
皮亞諾公理視數學歸納法不證自明,設作公理,而於策梅洛-弗蘭克爾集合論,數學歸納法可從良序定理推導出來。[5] 需要注意的是數學歸納法只能判定給定命題的真,而不能證偽,因為在形式轉換這一過程需要一定技巧與靈感。抽象的概念如自然數,可通過抽象的工具去處理。通過有限的步驟處理無限的物件如證明質數的無窮。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.