普通歸納法只由 推出 。很多自然的命題並不是這樣運作:合數可以分解為兩個較小的數,但它們不一定是 ;遞歸定義的序列可能依賴前面兩項或更多項。本單元由良序原理證明強歸納法,並說明它的用法,以及與之等價的最小反例方法。內容建立在單元 1.2 對證明結構與普通歸納法的討論之上。
良序原理
定義 1.4.1
(良序原理)
令 。良序原理指出: 的每個非空子集 都有最小元素,即存在 ,對所有 有 。經平移後,同一結論對每個有下界的非空整數集合也成立。
這個原理對 失效( 本身沒有最小元素),對正實數也失效(集合 沒有最小元素)。
反例模式
離開自然數,良序性便失效
命題:每個非空的正有理數集合都有最小元素。取 。它非空,而對任何成員 ,成員 嚴格較小,因為 給出 。所以 沒有最小成員。命題對 不成立;補救是保留「集合由有下界的整數組成」這個假設,那正是原理所要求的。
強歸納法
定理 1.4.2
(強歸納法)
設 為整數,對每個整數 給定命題 。假設對每個整數 ,下列蘊含成立:
則 對每個整數 都成立。
證明
(取最小的失敗者)
假設不然。集合 非空且有下界,所以有最小元素 。由 的最小性,對每個滿足 的 , 成立。於是定理的假設給出 ,與 矛盾。
證明透視
為何不需要單獨的基礎情形
證明只用了一次良序原理,即在失敗集中取最小元素;也只用了一次歸納假設,即在那個最小元素處。最小性一次提供了整個前提:每個較小的指標都不在 中,所以 對它們全部成立。這就是強歸納法不需要明確基礎情形的原因。對 ,前提「對所有 有 」不涉及任何指標,是空泛地成立,所以 處的蘊含直接斷言 。證明沒有說明怎樣證明這個蘊含,實際工作和實際的基礎情形正是出現在那裏。有下界是必要的:否則 未必有最小元素,論證便無從選取。
兩點說明。第一,實際操作時會先單獨證明最初的幾個情形,因為一般步驟通常至少要引用一個更早的情形。第二,普通歸納法是步驟只用 的特例。
因此強歸納法的證明形式如下:固定 ,假設對所有更早的 有 ,再證明 。當論證引用具體的更早情形,如 或 時,必須檢查這些指標不小於 ,這就是需要幾個基礎情形的原因。
最小反例方法
強歸納法的證明可以直接使用。要證明 ,假設反例集合非空,取其最小元素 ,並由每個較小指標都滿足 這一事實導出矛盾。這在邏輯上與強歸納法相同;選擇讀起來較清楚的一種即可。
例題
例題 1.4.3
(質因數分解存在)
每個整數 都是一個或多個質數的乘積。 用 的強歸納法。設 ,並假設結論對所有滿足 的 成立。若 是質數,它就是一個質數的乘積。否則 ,其中 。由假設, 與 都是質數的乘積,所以 也是。
注意論證對兩個不同的更早數值 和 使用了假設,而它們都不是預先確定為 。
例題 1.4.4
(面值為四和五的郵票)
每個整數 都可寫成 ,其中 為整數。 步驟引用 ,只有當 時 才不小於 ,所以要證明四個基礎情形:,,,。現設 ,並假設結論對所有滿足 的 成立。由於 且 ,有 ,,所以 。
例題 1.4.5
(二進制表示存在)
每個整數 都是若干個互不相同的 的冪之和。 取 ,並假設結論對所有 成立。若 ,則 。若 ,令 是不超過 的最大的 的冪,即 。若 ,已完成。否則 滿足 ,因為 。由假設, 是互不相同的 的冪之和,其中每項至多為 ,所以沒有一項等於 。加上 便得到 的所求表示。
例題 1.4.6
(遞歸序列)
定義 、,並對 令 。最初幾項是 。斷言:對所有 ,。 需要兩個基礎情形: 和 。設 ,並假設公式對 與 成立。利用 與 ,
邊界情形是第一個指標 ,此時步驟同時回到兩個基礎情形。
常見錯誤與細節
常見錯誤
(基礎情形太少)
若步驟引用 ,則 已經引用到 ,它在範圍之外。 與 都必須單獨證明。在郵票的例子中,步驟引用 ,因此需要四個基礎情形。
常見錯誤
(在 n 處或範圍外使用假設)
在歸納步驟中,只可對 使用 ,絕不能使用 本身。指標也必須落在容許的範圍內:在分解的例子中,分解 必須滿足 ,假設才能同時用於兩個因數。
常見錯誤
(在非良序集合上用最小反例)
最小反例的論證適用於 或有下界的整數集合的子集,不適用於 的子集:像 這樣的反例集合沒有最小元素。若步驟只需要 ,普通歸納法更清楚。
練習
快速檢查
(由序列例題中的遞推式,證明對每個 , 都是整數。)
用強歸納法證明遞推式產生的都是整數。
解答 · 引導解答
由遞推式 、、 定義 。對 用強歸納法證明 :基礎情形 與 都是整數;對 ,整數 給出整數 。由於閉式等於 (見序列例題),所以對每個 , 都是整數。(例如 給出 。)
快速檢查
(證明每個整數 都可寫成 ,其中 為整數。)
步驟回溯 格,先決定需要多少個基礎情形。
解答 · 引導解答
基礎情形:,,。設 ,並假設結論對所有滿足 的 成立。由於 且 ,有 ,,所以 。因為步驟回溯 格,所以需要三個基礎情形。
快速檢查
(設 ,且對 有 。證明對所有 有 。)
兩個基礎情形,再用前兩個界估計 。
解答 · 引導解答
基礎情形: 與 。設 ,並假設對所有 有 。則
快速檢查
(利用良序原理證明不存在整數 使 。)
假設這種整數的集合非空,考慮它的最小元素 。
解答 · 引導解答
假設滿足 的整數 所成的集合 非空。則 ,有最小元素 。由於 ,把不等式 乘以正數 得 ,且 。又 。所以 是整數且 ,即 ,而 與 的最小性矛盾。因此 為空集。