數學歸納法是科學的嗎，嚴謹嗎？我怎麼覺得不嚴謹？

01-03

#2017-5-31補充：
從歸納法證明的過程來看的話，第一步是一個確定的結論，比如當n=1是，1和2存在關係A，這個可直接驗證，沒問題。問題出在第二步的假設，第二步做了兩件事，一是假設，假設n=任意自然數m時，m和m+1也存在關係A，二是通過演繹演繹出n=m+1時，m+1和m+2也存在關係A，才說明這種關係具有延續性；
問題是
如果第二步推出的關係正確，則結合第一步結論，可推出整個結論正確。
那麼如何檢驗假設前提的有效性？可驗證嗎？要驗證在一個假設下推理出來的關係（m+1和m+2）正確，我們能夠採用的科學嚴謹方法是什麼？之所以你可以往後面的自然數繼續推，是因為你假設它針對任意的自然數成立。

為何不直接假設「如果今天周三，則結論正確」，結果一看日期，果然今天周三，所以結論正確。關鍵在於周三和結論正確之間的邏輯關係怎麼就可靠了？
#########以下是問題原文#######
很奇怪。第二步中通常是假設n等於一個數m時結論成立，然後推演出等於m+1時成立，然後就直接說整個結論成立了，那麼，如果第二步假設不成立呢？整個結論是不是就不成立了？為何最終的結論建立在第二步的一個假設上？另外，反證法是不是比歸納法要強有力？至少反正法是假設它是錯的然後推出矛盾從而證明結論是對的，

簡短的回答：

不是。數學歸納法是數學的，或者邏輯的，而絕非科學的。說起歸納總是讓人想到經驗觀察式的歸納，然而數學歸納法本質上是演繹的。物理世界裡面有沒有無窮個對象都是難說的。（有沒有無窮種看待對象的方式和有沒有無窮個對象是兩個問題。）
單個命題（比如作為公理的數學歸納法）沒有嚴謹不嚴謹的問題，只有對或者錯的問題，並且這種對錯也不是絕對的，而是相對於系統而言的。人有嚴謹不嚴謹的問題，文章有嚴謹不嚴謹的問題。而單獨的一個論斷拿出來看都是不嚴謹的，每篇論文，刪掉論證只留下結論，那麼這個結論就是不嚴謹的。
作為推理規則的數學歸納法也沒有嚴謹不嚴謹的問題，只有在對應的系統內是否保真的問題。一個人可以嚴謹地使用規則，即檢查了規則的所有前提是否被滿足後才使用規則，也可以不嚴謹地使用規則，比如說在使用全稱替換規則的時候有一個條件是替換要滿足替換自由，如果一個人不嚴謹地使用這條規則，忽略了這個條件，那他就會從 $forall xexists y (x<y)$ 得到 $exists y(y<y)$ 。
對於作為規則或者作為公理的數學歸納法的表述自然可以是不嚴謹的，比如說你的表述，比如說某些垃圾教材上的表述，比如說某些老師課堂上的表述——但是這些都和數學歸納法本身沒有關係。

長回答：

這裡的問題並不是數學歸納法的問題，而是如下幾個邏輯或者元數學問題的混雜：

什麼是一個假言命題？
什麼是一個推理，更進一步，推理的原子部分——推理規則——是個什麼東西？
什麼是假設（令……/假定……/考慮……），什麼是定理，為什麼從假設可以得到（假言命題形式的）定理？
推理規則和公理有什麼區別？
數的結構是什麼？有別的可能性么？不同的結構之間的關係是什麼？

粗糙地看，假言命題有兩種比較重要的理解：

第一種是將其理解為經典邏輯中的等價形式：前假或者後真，也就是「並非（前真且後假）」，然後用關於否定的和析取/合取的推理規則來進行推理。（諷刺的是，很多邏輯裡面是用蘊涵（和 $ot$ ）來定義否定 $egphi := (phi o ot )$ ）
第二種是將其理解為樸素的直覺主義邏輯自然演繹系統規則所陳述的那樣：首先我們假設某個公式，比如 $phi$ ，然後利用系統內的規則得到比如說 $psi$ ，到了這一步，我們就可以撤銷前提 $phi$ ，而將上面的一切視作是對於 $phi o psi$ 的證明。（當然這個時候可能我們只撤銷了一個前提，這個證明本身依舊處於一個更大的假設下，只有當所有假設都確實被撤銷了，這才真的是一個系統內定理的證明，否則僅僅是在特定條件/假設下的推理罷了）

第二種理解或許是比較符合直觀的，而第一種理解本身也有自己的好處，就是可以計算真值。事實上這兩種東西對應了兩種不同的語言直觀——條件命令和條件賭注的情況：

條件命令：如果你要做 A，那麼你要做 B。這對應的是經典邏輯的模型，如果你要遵守規定，同時發現你做不了 B，那麼你只能選擇不做 A。而如果你根本不想做 A，你也遵守了這條規定。
條件賭註：如果條件 A 成立，那麼我們對 B 是否發生進行賭注。（比如說 B 本身預設了 A：「如果中國隊進入了世界盃決賽，那麼我賭中國隊贏得大力神杯」）如果條件 A 不成立，則賭注本身無從談起。這對應的是某種直覺主義式的理解：我們只關心 A 成立的時候會得到什麼，而不關心 A 不成立的情況。

所以，這裡的第一個問題是關於一般形式的（有窮形式的）『歸納法』，我們不對所有自然數進行歸納，而只考慮如下有窮形式的推理：

$A_0$ 是真的；
如果 $A_0$ 是真的，那麼 $A_1$ 是真的；（在推理中，這兩條放在一起立刻會得到結論 $A_1$ ）
如果 $A_1$ 是真的，那麼 $A_2$ 是真的；（這三條放在一起會立刻得到 $A_2$ ）
……
如果 $A_{n-1}$ 是真的，那麼 $A_n$ 是真的。

結論： $A_0,A_1,ldots,A_n$ 都是真的。

無論採取上述哪種解讀方式，這個推理都是沒有問題的，因為它只用到了一條關於蘊涵的推理規則（MP）。除非你面對的是堆垛悖論那樣的困境，那就是另一個問題了，見：如何解答堆垛悖論？

也就是說，在面對有窮多個對象的時候，我們根本不需要這一條公理，用普通的推理形式就足夠了。

另一方面，直觀上來說，自然數理應具有某種意義上的緊緻性：如果你要說「一個東西對於自然數全體（這是一個無窮集合）成立」這一點是錯的，那麼你至少要找到一個反例。而這個反例必定要落在某個具體的 n 上面。因此如果你要否定這個推理的話，矛盾的點很容易會落到一個和數學歸納法無關的地方上。既然你要說這個東西對於 n 不成立，那麼我只需要 1 個前提和 n 個假言條件句，連續使用 n 次 MP 規則，就能證明你說的是錯的。

（當然我這裡玩了一點把戲，畢竟這個地方依賴於某種選擇公理式的東西，如果沒有選擇公理的話， $eg( forall x,Px)$ 無法讓我們知道到底是哪個自然數 n 使得它不成立，而直覺主義邏輯中這也推不出 $exists x, eg Px$ ——數學歸納法實際上也變相充當了選擇公理的角色，因為任何一個自然數的非空子集都有最小元，我們總是可以把這個最小元選出來作為我們的替罪羊。然而在沒有歸納法也沒有選擇公理的情況下，如果我們同時還使用直覺主義邏輯，嘛……好慘啊23333 ）

這個地方有一個額外的問題，是一個關於斷定（assertion）和陳述（statement）的問題。

我們上面使用到了這樣一個推理模式，或者說，推理規則（MP）：

如果 p 是真的，那麼 q 是真的；（或者說，「如果 p，那麼 q」）
p 是真的。（或者說，「p」，但是這樣寫果然很奇怪吧）

結論：q 是真的。

Lewis Carroll 寫過一篇文章來吐槽這個東西，他的意思是，我們可以構建出某種芝諾悖論式的無窮結構：

我們的起點是：(A0) p 是真的；(A1) 如果 p 那麼 q；結論 (C) q 是真的。

但是如果我拒絕這個推理本身，你要怎麼辦呢？即，我接受 (A0) 和 (A1) ，但卻拒絕 (C)。你或許會選擇加上一條：

(A2) 如果你接受了 (A0) 和 (A1)，那麼你就要接受 (C)。

於是我們的論證就變成了這樣的形式：前提：(A0)，(A1)，(A2)；結論：(C)。

但是如果我依舊拒絕這個推理那要怎麼辦呢？你或許會再加上一條：

(A3) 如果你接受了 (A0)、(A1) 和 (A2)，那麼你就要接受 (C)。

於是我們的論證就變成了：前提：(A0)，(A1)，(A2)，(A3)；結論：(C)。

……

無窮無盡。

這裡的問題是這樣的：就命題本身而言，它們沒有斷定效力，當然，加上一個「是真的」也不增加斷定效力。最簡單的例子就是看假言命題：當我說「如果 p，那麼 q」（也就是「如果 p 是真的，那麼 q 是真的」）的時候，我沒有斷定 p 是真的，也沒有斷定 q 是真的。重複：作為命題的陳述沒有斷定效力。因此推理規則不是關於命題的規則，如果是關於命題本身的規則的話，那麼我們永遠都只能在相同的層面上不斷打轉。推理規則是關於我們應該如何斷定的規則。推理規則是關於斷定的規則是什麼意思呢？

推理（或者說推理模式）「如果 p，那麼 q，但是 p；因此 q。」中，三個東西依次被斷定了：「如果 p，那麼 q」、「p」、「q」。

這看上去平平無奇，但是這是很關鍵的事情，如果我們將 MP 規則理解為下面這樣，那麼立刻就完蛋了：

如果（斷定 p），那麼（斷定 q）；
斷定 p；
因此，斷定 q。

「斷定」被拉回到了和構成命題相同的層次上，「如果斷定 p，那麼斷定 q」僅僅是一個命題，而沒有提供任何關於我們應該如何使用斷定的規範，最簡單的一點就是將上述的「斷定 p」和「斷定 q」替換成「A」和「B」，然後我們就可以重複 Lewis Carroll 的無窮鏈條了：是啊，我接受「如果 A，那麼 B」，也接受「A」，但是為什麼我要接受「B」呢？

這裡也大概就是題主的問題了。題主混淆了斷定和命題的層面，所有他的陳述，在命題層面上大概是上述悖論的類似物，而在斷定層面上則是荒謬的。

那要如何解決這種悖論呢？其實也不難，不採用那種回應方式就可以了，不說「那麼我們再加上一條……」，而要說，比如：

你說你接受「如果 A 那麼 B」和「A」，但卻不接受「B」——要不然是你根本就沒有理解「我接受」是什麼意思，要不然是你沒有理解「如果……那麼……」是什麼意思，要不然你不理解「不」是什麼意思。如果你拒絕接受這種基本的思維規範，那麼對不起，我沒法和你對話。

數學證明裡面我們經常會引入一些變數，邏輯也是一樣。比如說我們會假設「p 為真」，然後得到一系列結論，比如說通過析取引入規則得到「p 或者 q」。最後我們就得到了，也就是斷定了一個邏輯定理「如果 p，那麼 p 或者 q」。

這個操作神奇的地方是，我們從頭到尾都沒有斷定 p，當然也沒有斷定「p 或者 q」——但是我們最後卻得到了一個斷定，雖然不是關於 p 的斷定，但是這本身也是很神奇的事情：斷定竟然能無中生有。Out of nothing! （其實不神奇啦……畢竟每個公理都可以不依賴任何前提和之前的公理而直接斷定）

這裡或許會有些東西令人不悅，但是我們先將其中一些沒什麼爭議的事實陳述出來：

任何一個數學定理都是一個斷定，任何一個邏輯定理也都是一個斷定。如果他們都僅僅是未被斷定的命題那就完蛋了——「根據定理 7，你這裡有一個矛盾。」「對啊，因此定理 7 是錯的。」寫這種論文可以說是迫真司馬。
作為假定的內容，以及從假定的內容得到的結論（在假定沒有被撤銷之前），多半不是定理。比如說「x 是一個奇數」（如果這是一個定理，那麼按照一階邏輯的全稱量化規則，就會得到「對於任意的 x，x 都是一個奇數」）以及從之得到的結論「 $x^2 > 0$ 」；再比如上面的的「p（為真）」，以及從之得到的結論「p 或者 q（為真）」。

也就是說假定和斷定顯然是不同的。但是問題在於，如果不同到一個非常極端的地步，那麼從假定出發做的任何事情也都是可以的了——因此基於假定的推理就完全沒有價值了。然而我們並不希望如此極端，我們希望假定和斷定遵循相同的推理規則，因此我們才能通過「假定……得到……」的方式證明「如果……那麼……」。

對於絕大多數好的邏輯來說，演繹定理（ $A,Gammavdash B iffGammavdash A o B$ ）都是至關重要的。

當 $Gamma$ 是有窮集合的時候我們可以將所有東西都移到右邊去，得到 $vdash (igwedge_{Xin Gamma}X) o (A o B )$

（然而不是有窮的情況下就沒辦法了，畢竟一般情況下我們只支持有窮長的語句。就算我們支持無窮長的語句，這個語句一般情況下也沒有有窮長的證明呀……然而我們只接受有窮長的證明）

這大概體現出來了某種假定式的推理和定理之間的關係。

數學歸納法本身有很多種等價的表述，但是任何錶述都有兩個選擇，一個是將其作為公理，一個是將其作為一種推理規則。作為公理的情況下，數學歸納法的使用本質上就是在使用 MP 規則，或者說，通過 MP 規則，我們將數學歸納法拆解為了一般的形式：先證明對於 0 的情況成立，然後證明對於任意的 n，如果 n 的情況下成立那麼 n+1 的情況下也成立。——完成這兩步之後自動得到了原來那個全稱命題的證明。數學歸納法真正的價值，在於它允許我們使用有限的語言來做一個關於無窮對象的論斷：如果……那麼對於所有自然數都……。而這種無窮性本身並不是憑空產生的，而產生於歸納法第二個條件的無窮性：當我們對於任意一個自然數 n 做假言論斷的時候，實際上我們已經在使用（思考）自然數全體了。雖然這是一種假定式的使用，但是假定式的使用和斷定式的使用在規則上並無太大區別，並且事實上我們最後得到的「對於任意的 n，如果 n 具有 P 性質，那麼 n+1 也具有 P 性質」是一個斷定式的使用。

一個麻煩的地方是變數和常量的理解，當我們在數學歸納法第二部分，即歸納步驟的證明的開頭說「考慮任意自然數 n，如果 n 時……，則要證明 n+1 時……」，或者「當 n&>0 時，如果對於任意 m& 都成立，要證明當 $phi(n)$ 也成立」之類的表述的時候，我們看上去是在一個局部進行推理，沒有真正『延拓』到全局上。要看清楚這一點是如何做到的，最簡單的方式是看這裡的 n——一般來說這需要是一個新的名字，它不能是一個常量的名字，因為我們沒有辦法對於常量進行量化，但是同時它也不能和別的變數重名。雖然一下子想不到什麼特別好的例子，但是毫無疑問，混亂的變數命名會在某些情況下導致不合邏輯的結論出現，尤其是當我們在此之後進一步對變數進行全稱概括的時候。（一個可能的例子是我們在證明一個形如 $forall mforall n, phi(m,n)$ 形式的命題的時候，如果草率使用名稱，可能最後證明的僅僅是對角線的情況： $forall n,phi(n,n)$ ）這種『全新性』保證了任意性。

（說起來，之前上課的時候有人糾結過 n 到底是不是自然數的問題，這裡有一個對象語言和元語言的區分，具體見：命題變元是什麼？ - 知乎）

最後一個問題是，為什麼我們非得這樣規定自然數。

其實如果我們僅僅是要前4條公理的話，我們已經能表述可列無窮的結構了。參見：Peano公理第五條是否多餘？或者說它是可以被證明的 - 知乎

數學歸納法的作用是，限制我們只表達這種結構——我們要表達的是自然數，不是自然數尾巴後面多一份自然數的 copy，或者跟著一大團東西，我們就是要自然數本身，不多不少，而且結構一定要是這樣的序列結構。（在所有的自然數後面跟一份自然數的 copy 本身實際上並沒有改變論域的大小，兩者都是可數無窮大，但是這種得到的東西和原來的東西在後繼函數關係上和序關係上是不同構的）當然這種限制至少在一階的情況下是失敗的。因為依然有一些不是自然數的結構滿足 PA 的五條一階表述（第五條準確來說不是一條公理，而是一個公理模式，但是這是技術細節了）。然後我不確定二階邏輯是如何解決這個問題的，所以略過不談。

這裡就有一個 alternative mathematics 的問題了——如果我不用這第五條，用別的東西，會怎麼樣呢？然而實際上不可能存在 alternative mathematics，尤其是當我們習慣了公理化的表述之後，任何一個所謂的和別的數學不同的，能夠刻畫出不同模型類的東西（比如某個公理系統），都是一個標本一樣的新系統（或者舊系統的片段/擴充/改頭換面）。你造出來的東西沒有辦法去替換別的東西，而僅僅是在收藏架上面新放了一個東西罷了。這裡的操作永遠只有增加，沒有替換。就算是不一致的系統，也不會因為系統內部的矛盾而炸開到別的地方去。

當然，這並不是說這些系統是零散的，沒有結構的——我們還是可以研究不同公理化得到的結構之間的關係，比如說是不是有一個 isomorphism，比如說是不是有一個 embedding 之類的。然而……嘛沒什麼。

以上。

關鍵在於皮亞諾公理，公理可以不太嚴謹地描述成以下的幾條：

0是自然數
每個自然數都有且僅有一個後繼，不同自然數的後繼不同；
沒有任何自然數的後繼為0
如果一個自然數的子集滿足：0在集合內；任何集合內數的後繼都在集合內；則這個子集就是所有自然數

可以看到最後一條直接導致了第一數學歸納法的成立。這是皮亞諾公理的一部分，意味著數學歸納法的有效性不可以通過任何其他公理來推導得到。

還有第二數學歸納法，第二數學歸納法可以通過構造命題列 $Q_n = cap_{k=1}^n P_k$ 來轉換為第一數學歸納法，所以也是直接依賴於皮亞諾公理的。

其實題主這個問題很好，數學歸納法從原理上來說並沒有那麼顯然，過去我們可以證明的命題都是有固定數量的步驟的，已知有限多個命題，然後通過固定的步驟證明其中某個命題；而數學歸納法則一次證明了無限多個命題。這其中靠的就是皮亞諾公理。所以覺得不是很嚴謹其實說明你的直覺是很敏銳的。

有些人認為數學歸納法可以靠構造一步一步遞增的證明過程（n=1，n=2，n=3……）來完成，這件事本身需要可計算性相關的理論，而這個理論是直接依賴於數學歸納法的。

引入歸納法可以讓人們在數學中完成一次證明無窮多個命題這件事，但它也是雙刃劍，根據哥德爾不完備定理，引入皮亞諾公理會導致數學體系中出現既不能被證明、也不能被證否的命題，這也側面說明了數學歸納法其實是很不平凡的工具。

數學歸納法來源於公理。關於這個前面高票答案說的差不多了，這裡看到題主是高中生，我突然想到我高中對歸納法的錯誤理解，所以提醒一下，大學生們就不用看了。。

我想強調的是通過數學歸納法我們可以證明命題對任意大的N成立，但是不能說明對可數無窮成立。

高中時我大概沒有好好理解無窮的概念，大概高中接觸的無窮概念比較少。用數學歸納法，你給我一個任意大的數，我都可以證明命題成立，但是無窮就不一定了。我舉個經典例子說明一下。

證明開集的交是開集。（這裡的開集是 $mathbb{R}^n$ 中的經典定義，可以理解成實數軸上的開區間）

通過定義容易證明對開集A,B， $A cap B$ 是開集。

假設n個開集的交是開集，那麼對於n+1個開集A_i的交 $igcap_{i=1}^{n+1}A_i$ ，由歸納假設，前n個集合的交是開集。再根據第一步兩個開集交是開集，我們得到 $igcap_{i=1}^{n+1}A_i$ 是開集。qed

這裡我們得到的結果是對任意大的M，M個開集的交是開集。但是這個結論對無窮不成立，因為

$igcap_{i=1}^infty(0,1+frac{1}{i})=(0,1]$ 不是開集。

對於無窮情況一般用Zorn引理代替歸納法。

一個陳述句P可以作為一個條件，一個「若P則Q」也可以作為命題、作為條件。

歸納法的第二句就是一個若P則Q的條件。

若「命題對n=m成立」則「命題對n=m+1成立」。

用簡單的命題類比一下，你的問題就好像在說：

書上說，如果一個四邊形是平行四邊形，那麼它的對邊相等。

可是為什麼這個四邊形是平行四邊形呢？要不是呢？

---------

至於為什麼

若「命題對n=m成立」則「命題對n=m+1成立」再且上「命題對n=1成立」，

就能推出命題對任何自然數都成立，那就得看其他答主從自然數公理說的了。很不嚴格地講，我們定義自然數的時候，就是用1定義的2，用2定義的3（所謂後繼），故而歸納法就有這樣的結論。然而沒有哪條自然原理保證今天是星期三能蘊含歸納法的原理，因為自1582年新曆法確定以來每天的星期幾都是確定的，而最初星期幾的定義與結論毫無關係。

數學歸納法是一個數學結論，

科學性與否，取決於我們是否堅持用實踐標準來檢驗它。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

事實上，數學歸納法與自然數集 $N$ 的性質有關，

對於 $a,bin N$ 來說，小於關係 $a < b$ ，定義了自然數集上的一個良基關係（well-founded relation），即，對於 $N$ 的任意非空子集都有最小元。

這種良基性質，導致了數學歸納法成立。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

下面我們用反證法來證明一下，

首先需要明確，數學歸納法說的是，如果，

（1）命題 $P(n)$ 對於 $n=1$ 成立，

（2）假設 $P(k)$ 成立可以推出 $P(k+1)$ 成立，

那麼 $forall nin N$ ， $P(n)$ 都成立。

現在我們來證明：

1. 假設命題 $P(n)$ 滿足（1）和（2）兩個條件但是卻 $exists min N$ ，使得 $P(m)$ 不成立。

那麼，集合 $A = {m | min M, eg P(m)}$ 非空，

2. 由於 $A$ 是 $N$ 的非空子集，所以，根據小於關係 $<$ 的良基性質， $A$ 必有最小元，

3. 如果 $A$ 的最小元為 $1$ ，那麼與前提（1）矛盾，

4. 假設 $A$ 的最小元為 $k$ （且 $k eq 1$ ），那麼根據 $A$ 的定義， $P(k)$ 一定不成立。又根據條件（2）， $P(k)$ 不成立必有 $P(k-1)$ 也不成立。因為 $k-1<k$ ，所以與 $k$ 是最小元矛盾。

因此，只要小於關係 $<$ 滿足良基性質——任意非空子集都有最小元，

那麼，就必有數學歸納法成立。

證畢。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

數學歸納法有一種更普遍的形式，稱為良基歸納法，

設 $prec$ 為集合 $A$ 上的良基關係， $P$ 為關於 $A$ 中元素的某個命題，

如果 $P(k)$ 對於所有的 $kprec a$ 成立，就必然有 $P(a)$ 成立，

那麼 $forall ain A$ ， $P(a)$ 都成立。

可以看到，良基歸納法與數學歸納法的另一種表述很相似，即，如果，

如果對於任意 $k 的自然數 <img src=$ 成立，必有 $P(a)$ 也成立，

那麼， $forall nin N$ ， $P(n)$ 都成立。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

補充：2017.07.29

看了評論區中的評論，我覺得有必要寫一下良基歸納法的證明。

1. 良基關係

設 $prec$ 是集合 $A$ 上的二元關係，如果不存在由 $A$ 中的元素構成的無窮下降鏈，

$cdotsprec a_ipreccdotsprec a_1prec a_0$

則稱 $prec$ 為良基關係，若 $aprec b$ 則稱 $a$ 是 $b$ 的前趨。

2. 極小元

有時還可以用極小元的概念來定義良基關係。

設 $prec$ 是集合 $A$ 上的二元關係，稱關係 $prec$ 是良基的，

當且僅當 $A$ 的所有非空子集 $Q$ 都含有一個極小元 $min Q$ ，即 $forall bprec m,b otin Q$ 。

註：對於自然數集來說，小於關係 $<$ 是良基的，且自然數子集上的極小元就是它的最小元。

3. 良基歸納法

設 $prec$ 是集合 $A$ 上的良基關係， $P$ 是某一性質，

則 $forall ain A. P(a)$ ，當且僅當， $forall xin A. ([forall yprec x. P(y)]Rightarrow P(x))$ 。

良基歸納法說的是，要證明集合上的所有元素都滿足某一性質，只要證明，

對於任意元素 $x$ ，如果它的所有前趨該性質都成立，必有對 $x$ 來說該性質也成立。

4. 良基歸納法的證明：程序設計語言的形式語義 - 第25頁

（1）充分性

如果 $forall ain A. P(a)$ ，則 $forall xin A. (forall yprec x. P(y))$ ，且 $forall xin A. P(x)$ ，

因此， $forall xin A. ([forall yprec x. P(y)]Rightarrow P(x))$ 。

（2）必要性

假設 $forall xin A. ([forall yprec x. P(y)]Rightarrow P(x))$ ，但存在某個 $zin A$ 使得 $eg P(z)$ ，

這樣，我們就可以構造出一個集合 $Q={zin A| eg P(z)}$ ，且 $Qsubseteq A$ ， $Q eqvarnothing$ ，

則它必有極小元 $min Q$ ， $eg P(m)$ 為真，

但是根據前提， $forall xin A. ([forall yprec x. P(y)]Rightarrow P(x))$ ，有 $forall yprec m. P(y)Rightarrow P(m)$ ，

因此， $exists yprec m. eg P(y)$ ，與 $m$ 是 $Q$ 的最小元矛盾，

所以，不存在 $zin A$ ，使得 $eg P(z)$ ，即 $forall ain A. P(a)$ 。

證畢。

5. 數學歸納法

（自然數集上的）數學歸納法，只是良基歸納法的一種特例，

正是因為小於關係 $<$ 是良基的，所以才有（自然數集上的）數學歸納法成立，

而那些非自然數集上的歸納法，例如結構歸納法，可以使用良基性質統一考慮。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

參考：

良基關係

數學歸納法

程序設計語言的形式語義 (豆瓣)

那麼，如果第二步假設不成立呢？整個結論是不是就不成立了？

是的。本來就是這樣的啊，這有什麼值得奇怪的？

我猜你大概是奇怪：「為什麼我在教課書上看到的那些使用了數學歸納法的東西，第二步假設全都成立？」

因為你是在看教科書啊！！！！！人家寫的就是已經證明了的定理的推導過程。這和問「為什麼隕石總是掉到坑裡」有什麼區別？？

另外，反證法是不是比歸納法要強有力？至少反正法是假設它是錯的然後推出矛盾從而證明結論是對的。

數學歸納法已經在有限域上保證了整個鏈的正確性，堵住了你舉出反例的任何途徑。說白了，這些證明方式是等價的，並不會說一個比另一個更有效力。

至於為什麼這個定理用歸納法，那個定理用反證法，這是因為這樣恰好方便證明，或者方便理解。

華羅庚的《數學歸納法》這本小冊子相當不錯，建議你看看，然後可能就會略懂一二。

證明取自

A.Shen, N.K.Vereschagin 集合論基礎

由於對自然數命題a) 成立，

故對自然數命題c)成立，即自然歸納法成立。

看下《邏輯學導論》，了解一下什麼叫假設演繹法。科學只是認識世界的一種方式，不是正確的代名詞。

數學歸納法的正確性是皮亞諾公理的一部分

公理不需要也無法證明，所以沒有為什麼

拒絕皮亞諾公理就是拒絕自然數，以及由自然數衍生的一切數學

這應該是公理集合論吧，

公理集合論（axiomatic set theory）用形式化公理化方法研究集合論的一個學科。數理邏輯的主要分支之一。

題主如果是高中階段，不必去考慮這個問題。你只需要知道數學充滿了產生式系統，滿足條件產生結果，一個步驟的結果觸發下一個步驟。

利益相關：文科生。看到描述里是似乎想搞清楚數學語言的元語言，借用教育心理學回答一下。

問題的關鍵是，第二步證明的是，對於任意的m，從n=m時命題成立可以推出n=m+1時命題成立。

========================================================================

- 為什麼證明了這兩條就能說明命題對全體自然數成立了呢？

- 我就是證明了啊，不信你拿一個n我來試試。

- 那你證明一下命題對n=4875894174成立？

- 你看，首先第一條我證明了n=1時候命題成立對吧？

- 嗯。

- 然後根據第二條，因為n=1的時候成立，所以n=2的時候成立。

- 嗯。

- 然後根據第二條，因為n=2的時候成立，所以n=3的時候成立。

- 嗯。

……

（十年後）

……

- 然後根據第二條，因為n=4875894172的時候成立，所以n=4875894173的時候成立。

- 嗯…………

- 然後根據第二條，因為n=4875894173的時候成立，所以n=4875894174的時候成立。

- ……………（此處表情可以參考我頭像）

等你學的多了你就會發現更多的不嚴謹，然後等你學的久了你就會發現原來都很嚴謹。

數學歸納法主要還是建立在自然數體系下，邏輯上你如果承認你可以從0，1，2...往後一直數，那麼這歸納法的第二步就是邏輯上通的。也就是你從首位成立以及遞推然後可以推得整體成立，你可以一步一步推的。

實際上皮亞諾公理體系所說的也是這個事，這套公理用數學歸納法的形式來定義自然數。這兩個從邏輯上可以歸為一個事。

公理有可能會讓你覺得違和感，但是你一旦承認它，那麼就會很通順明白，很多事情迎刃而解。

數學歸納法的過程和你數數的過程在邏輯上是等價的，你要從第一位開始數，並且要一個一個往後數，你也數不到頭，但是你本能的覺得可以一直數下去，並且你覺得這些數還可以組成一個整體，叫自然數。就是這麼個過程。

tldr：『若P則Q』這個命題本身的正確性並不依賴於P的正確性。

有這種問題很好啊，有什麼可嘲諷的。誰學數學都會有這種困惑的時候。

學了很多數學的各位，我就問問：你們第一次學選擇公理的時候能接受嗎？（好的我知道你們有很多人能接受得了，那麼Zorn引理和良序定理呢？[手動滑稽]）（好了我知道你們連良序定理都能輕輕鬆鬆接受，我蠢行了吧）

回到問題本身，樓上有很多人說得很好了。問題就在於高中階段沒有徹底說明白自然數集到底是什麼，而且題主似乎對基本的邏輯命題不太熟悉（例如當我們說「p=&>q」的時候我們究竟在說什麼），這沒什麼大不了的。當然這不能怪高中課本：把集合論公理講清楚對高中生，甚至不關心這方面內容的多數本科生來說既繁瑣又不必要。而當你徹底搞清楚自然數集的嚴格定義以後，你就知道為什麼會有數學歸納法了。

最後多嘴幾句，給題主一個小建議：看得出你對數學的思考還是挺深入的，這非常好，但是請一定記住思而不學則殆。高中階段沒必要追求這麼嚴格的數學體系，好好掌握最基本的概念、性質、例子和定理就夠了。當你想真正進入這個學科時，會有更為嚴格的體系來供你學習的，別急。實在好奇的話可以看看GTM系列第一本，Introduction to Axiomatic Set Theory。希望對你有幫助。

我完全同意 @羅心澄的答案。我的這個答案實際上是偏題的，只是補充了一個不涉及序關係的數學歸納法證明。

要證明的命題——數學歸納法——是：

對任意關於自然數的性質 P，若 a) P(0) 成立，b) 對任意自然數 n, P(n) =&> P(n+1)，則對任意自然數 n, P(n) 成立。

首先自然是要定義自然數。自然數被定義為所有歸納集的交。所以要先定義歸納集：

集合 Ω 是歸納集當且僅當 a) {}∈Ω，b) S∈Ω ? S∪{S}∈Ω。

歸納集的存在性由無窮公理保證。

然後自然數集是所有歸納集的交，記為 ?，不難證明 ? 也是一個歸納集。

自然數集中的元素是 {}、{{}}、{{},{{}}}、{{},{{}},{{},{{}}}}、{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}、etc。

為簡化記號，自然數集中的元素 {} 用記號 0 表示，{{}} 用記號 1 表示，{{},{{}}} 用記號 2 表示，etc。同時 S∪{S} 被稱作 S 的後繼，對應自然數中加一的概念。同樣為了簡化記號，用 S+1 表示 S∪{S}。

使用簡化記號後，集合 Ω 是歸納集當且僅當 a) 0∈Ω，b) n∈Ω ? n+1∈Ω。

定義好了自然數集，證明歸納法就很容易了。假設自然數上的性質 P 滿足：

1) P(0) 成立

2) 對任意 n∈?, P(n) =&> P(n+1)

不妨定義集合 Σ 為所有滿足 P 的自然數，即 Σ = {n∈S | P(n)}。（Σ 的存在性依賴分離公理）

不難證明 Σ 也是歸納集。因為 ? 是所有歸納集之交，所以 ? 是 Σ 的子集。同時由定義，Σ 是 ? 的子集。這樣可以證明 ? 和 Σ 就是同一個集合。這說明性質 P 被所有自然數滿足。

題主先說了，「當n=1時，1與2存在對應關係，沒問題。」

第二步，假設n=m時，存在對應關係。接下來推演出n=m+1時，對應關係也成立。

題主的疑惑應該就是假設的「n=m時，對應關係成立」不嚴謹，但數學歸納法是兩步結合得出結論。第二步的重點不在假設n=m時成立，而在於n=m成立能否推出n=m+1成立。假如能推出，那麼代入第一步，n=1時（此時第二步的m即為1）已證成立，即可推出n=2，3，4，···時也成立。

既然題主覺得反證法更有力，那我就用反證法證明數學歸納法沒問題。

假定存在m，使得f(k)成立，使得命題f(k+1)不成立。

由數學歸納法假設，當對於任意的n，有當f(n)成立時，f(n+1)必成立，那麼f(m)不成立（否則f(m+1)成立），與f(m)成立矛盾，原假設不成立。

其實歸根到底，題主提出這個問題就是無窮的概念學的不好罷了，多看看數分和實變會有不小的幫助。

分兩塊來解釋下。

一，題主對歸納法的理解

根本就錯了啊！錯了啊錯了啊！！ (拎耳朵！)

你如果用你描述的歸納法去解題，完全要被老師打屁股啊！同學！

誰說歸納法第二步是：「設n=任意自然數m時，m和m+1也存在關係A 」然後「是通過演繹演繹出n=m+1時，m+1和m+2也存在關係A，才說明這種關係具有延續性」

這麼玩的話都假設對任意m有m+1成立了，還要什麼演繹出對m+1有m+2？關演繹證明什麼事??這樣的「數學歸納法」必須不科學啊，簡直扯屁。。。。

這就是你產生問題的原因。

然而，歸納法第二步是，你假設n=任意自然數k時候，關於n的命題是成立的，然後你要做的事情是證明n=k+1的時候，命題成立。也就是整個證明過程的精髓在於你怎麼去證明n=k+1的時候命題成立。

所以不用管假設「n=k時命題成立」是否合情靠譜，只要你成立，我就推出後面一個n=k+1時成立，這樣的「延續性」才是重要的。

至於前面的「n=k命題成立"的假設是否靠譜，我們第一步裡面就用了1去驗證了下，這個第一步，叫「歸納奠基」，來說明「n=k命題成立「的確是可以存在的。

二,舉個例子解釋思想。

很多地方喜歡用多米諾骨牌去類比數學歸納法，其實並不好。具體不表

這裡舉另一個。

秦始皇想保證他們家世世代代有嫡系男丁繼承王位。他命人造出了一種葯，這個葯作用就是男人服下後必然能生出一個兒子來。

這樣江山不愁後繼無人啊！

是不是有這個葯問題就解決了呢，，，不是的，，，

你得保證，你始皇帝嬴政是個男人。。。。。

數學歸納法：

一：已經有一個男人嬴政是秦國的統治者了！

二：假設：不管哪朝哪代什麼年代，秦國王室都有個男人，他可以繼承王位成為統治者

演繹證明（就是吃藥）：這個男人吃藥後就能生出個男人來繼承自己的王位成統治者

我大秦（清？）萬世一系的千古江上吶~~~

這裡面這個假設可以是不成立的，也就是說有那麼一個時代，秦國王室沒有男人了。。。那麼想要一直讓男人統治的夢想就破滅了啊！但是，一旦始皇帝是個男人，那有了這個葯，以後必然是男人統治天下。。。

所謂「延續性」，所謂在無窮遠的地方還保證命題的成立，精髓在此。在「吃藥」上面！

不知說透了沒，反正大秦（清）都亡了

（此回答僅供幫助理解，可能有些不夠數學）

在知道皮亞諾公理前，我自己的理解是，數學歸納法可以構造一個證明生成器，然後證明「給它輸入自然數n，它一定能輸出 $P_n$ 的合法證明，然後停機」。

這個機器可以這麼輸出：

&<你手寫的 $P_0$ 的證明&>...1

&<你手寫的 $forall k in mathbb N. P_k o P_{k+1}$ 的證明&>...2

∵由1得， $P_0$ 成立，

由2得， $P_0 o P_1$ 成立，……， $P_{n-1} o P_n$ 成立（此處循環輸出，共n條）

∴ $P_n$ 成立。證畢

對於不同的n，得到的證明是不同的（長度和n有關），但單獨看每個證明都是有限且合法的。

有了這個生成器，我們就可以做到「對於給定的n，總能寫出合法的證明」（證明存在，但不必實實在在寫出來）。

既然一定存在證明，原命題當然就為真了。