「數學歸納法」為什麼會對？

「數學歸納法」為什麼會對？(Why does “Mathematical Induction” work?)
中央研究院數學所李國偉研究員/中央研究院數學所李國偉研究員責任編輯

給定一個關於正整數 $${n}$$ 的敘述 $${P(n)}$$，數學歸納法用下面兩個步驟證明 $${P(n)}$$ 對於所有正整數 $${n}$$ 都成立：

１、（歸納基礎）證明 $$n=1$$ 時，$${P(1)}$$ 成立。
２、（歸納步驟）假設 $$n=k$$ 時 $${P(k)}$$ 成立，證明當 $$n=k+1$$ 時 $$P(k+1)$$ 成立。

在一般教科書裡，有時會給出其他形式的數學歸納法。譬如，給定一個正整數 $$m$$，下面這種形式的數學歸納法，可以在兩步內證明 $${P(n)}$$ 對於所有不小於 $$m$$ 的正整數 $$n$$ 都成立：

１’、（歸納基礎）證明 $$n=m$$ 時，$${P(m)}$$ 成立。
２’、（歸納步驟）假設 $${n=k}\geq{m}$$ 時 $${P(k)}$$ 成立，證明當 $$n=k+1$$ 時 $${P(k+1)}$$ 成立。

還有一種方式稱為「完全數學歸納法」，它的兩個步驟如下：

１”、（歸納基礎）證明 $${P(n)}$$ 成立。
２”、（歸納步驟）假設 $$n=k$$ 時，對於所有 $${0<m}\leq{k}$$ 而言 $${P(m)}$$ 都成立，證明當 $$n=k+1$$ 時 $${P(k+1)}$$ 成立。

如此也就證明了$${P(n)}$$ 對於所有正整數 $$n$$ 都成立。

各種形式的數學歸納法所以都對的理由，其實奠基於下面的這條原則，它陳述了一項關於正整數非常根本的性質：

（最小元素原則）^１每一個非空的正整數集合，都擁有一個最小的元素。

我們用第一種數學歸納法為例，說明所謂奠基於以此原則的意義。我們先假設最小原則為真，再假設數學歸納法的歸納基礎與歸納步驟都完成了，就應該會推導出 $${P(n)}$$ 對於所有正整數 $$n$$ 成立的結論。如若不然，令 $$A$$ 是所有使 $${P(n)}$$ 不成立的 $$n$$ 所構成的集合，那麼 $$A$$ 就是一個非空集合。根據最小元素原則，$$A$$ 有一個最小元素 $$a$$。這個元素 $$a$$ 不會是 $$1$$，因為歸納基礎保證 $$1$$ 不屬於 $$A$$。於是 $$a-1$$ 會是不屬於 $$A$$ 的正整數，所以 $${P(a-1)}$$ 成立，再經由歸納步驟便推得 $${P(a)}$$ 成立，也就是說 $$a$$ 不屬於 $$A$$，我們於是得到一個矛盾。另外兩種數學歸納法也可類似地得到驗證。

我們為什麼會接受最小元素原則呢？假設 $$A$$ 是任何一個由正整數構成的集合，它裡面可能有無窮多個元素，也可能只有有限個元素。我們現在拿出一個元素 $$\chi_1$$，如果 $$\chi_1$$ 不是 $$A$$ 裡最小的元素，那麼便可在 $$A$$ 裡找到另一個元素 $$\chi_2$$，而且 $${\chi_2}<{\chi_1}$$。如果 $$\chi_2$$ 還不是 $$A$$ 裡最小的元素，那麼又可以再找一個更小的元素 $$\chi_3$$。如此繼續下去，勢必要找到 $$A$$ 裡最小的元素，否則 $$A$$ 裡面就會包含無窮多個嚴格遞減的元素。然而 $$A$$ 裡比 $$\chi_1$$ 小的元素最多也只有 $${\chi_1}-1$$ 個，不可能包含無窮多個嚴格遞減的元素，我們因而得到一個矛盾。

其實前面這一段說明裡，也有數學歸納法的風味。如果要明顯地運用數學歸納法，我們可以如下論證。令 $$A$$ 是一個非空的正整數集合，假設 $$A$$ 沒有最小元素，我們準備用數學歸納法證明 $$A$$ 必須是空集合，因此就得到一個矛盾，所以所以可以結論 $$A$$ 必須擁有一個最小元素。因為沒有明顯的方式描述 $$A$$ 的元素，所以歸納的對象敘述 $${P(n)}$$ 的選擇有些巧妙。我們令 $${P(n)}$$ 表示：「所有小於 $$n$$ 的正整數 $$m$$ 都不屬於 $$A$$。」

歸納基礎：因為沒有任何正整數會小於 $$1$$，所以 $${P(1)}$$ 成立。

歸納步驟：依據歸納法假設，當 $$n=k$$ 時 $${P(k)}$$ 成立。

現在令 $$n=k+1$$，我們需要證明所有小於 $$k+1$$ 的正整數 $$m$$ 都不屬於 $$A$$。我們可以分為兩種情形來討論。

第一種情形是 $$m<k$$。根據歸納法假設 $${P(k)}$$ 成立，也就是說當 $$m<k$$ 時 $$m$$ 不屬於 $$A$$。

第二種情形是 $$m=k$$。因為比 $$k$$ 小的正整數已經都不屬於 $$A$$了，如果 $$k$$ 屬於 $$A$$，$$k$$ 變成 $$A$$ 裡最小的元素，這與我們的假設 $$A$$ 沒有最小元素矛盾，所以 $$k$$ 也不屬於 $$A$$。

根據數學歸納法，已經證明了 $${P(n)}$$ 對於所有正整數 $$n$$ 都成立。那麼 $$A$$ 就必須是空集合了，否則如果正整數 $$\chi$$ 是 $$A$$ 的元素，但是因為 $${P(\chi+1)}$$ 成立，$$\chi$$ 又不能多於 $$A$$，就得到一個矛盾了。

總而言之，前面的討論顯示數學歸納法與最小元素原則在邏輯上是彼此可以互相推導的，也可以說力量相當。我們所以能接受它們，根本是人類對於數有一種原始的直觀，不論我們嘗試用什麼面貌相異的話來講，最終在邏輯上還是等價的。

參考資料

1. 「最小元素原則」是本文中暫訂的名稱，比較正式的名稱是 Well-founded Principle。