動機
離散數學中的證明必須解釋:為甚麼由有限多個步驟可以推出無窮多個情況。僅僅檢驗例子做不到這一點;缺少有效起點的歸納步驟同樣做不到。在討論歸納法之前,我們必須準確說明一個命題對甚麼對象加了量詞,以及哪些選擇可以依賴於先前的選擇。
定義
定義 1.1.1
(謂詞、量詞與依賴關係)
謂詞 在給定 的值,或在指定論域上對 加量詞後,便成為命題。命題 要求 中每個 都滿足 ; 則要求至少有一個見證元。在 中,見證元 可以依賴於 ;在 中,則必須有單一的見證元對所有 都成立。
概念視角結構
把依賴的見證元看作函數
命題 斷言可以為每個 選出一個見證元,亦即存在函數 ,使每個 都有 。當 由明確的規則給出時,例如對「每個整數都有更大的整數」取 ,這個函數本身就是證明;對任意的無窮論域,從命題過渡到這樣的函數需要用到選擇公理。反過來的命題 要求的是一個常值函數。用這種語言,兩種量詞次序的差別就是函數與常數的差別;而否定 則指出一個輸入,在那裏不存在任何見證元,因此不可能有這樣的函數。
我們取 。蘊涵式 僅當 為真而 為假時才為假。它的逆否命題 與它等價,但它的逆命題 則不一定等價。全稱命題的反例必須滿足其假設並違反其結論;無關的例子並不能反駁它。
定理/命題
定理 1.1.2
(量詞的否定)
對任意指定論域上的謂詞,
因此 即 ,各論域保持不變。
定理 1.1.3
(普通歸納法與強歸納法)
設對每個 , 都是一個命題。若 成立,且對每個 都有 成立,則所有 都成立。由 以及假設更強的歸納步驟亦可得到同樣的結論:對每個 , 合起來蘊涵 。
證明思路
證明
(否定律)
全稱命題恰好在至少有一個元素不滿足謂詞時不成立;這證明了第一條否定律。存在命題恰好在沒有元素滿足謂詞時不成立,等價於每個元素都不滿足謂詞,這證明了第二條。這兩條定律在空論域上依然成立:此時全稱命題為真,存在命題為假。由外向內逐層應用這些定律,可以保持依賴關係的次序。
證明
(經由最小不成立指標的歸納法)
對於歸納法,設某個 為假,並取最小的不成立指標 。基礎情況排除了 。在普通歸納法中,由最小性可知 為真,於是歸納步驟使 為真,矛盾。在強歸納法中,每個更早的 都為真,於是假設更強的歸納步驟給出同樣的矛盾。
強歸納法亦可由普通歸納法推出:令 表示對所有 , 均成立。強歸納步驟證明了 。這說明「強」指的是可用的歸納假設,而不是另一種真值原理。
證明透視
最小不成立指標提供了甚麼
論證用到 的一個性質,而定理本身並沒有寫出它:非負整數的每個非空集合都有最小元。基礎情況只用了一次,用來說明 ,這樣 才是一個指標;缺少它,論證便失效,而事實上即使每個 都為假,步驟 也可以對每個 成立。最小性負責保證歸納步驟的前提:普通歸納法只需要 ,強歸納法需要 全部,而兩者成立的理由相同。然後歸納步驟恰好在 處使用一次,與 的選取矛盾。由普通歸納法推出強歸納法,也證實了兩者的分別只在於步驟可以假設甚麼: 把全部歷史打包成一個命題。
歸納證明必須保持所歸納的命題固定不變。如果歸納步驟需要比所述假設更強的事實,便應當加強命題並證明新的基礎情況;不可以暗中假定缺少的事實。
例題詳解
例題 1.1.4
(一個見證元,還是一族見證元?)
在整數範圍內, 為真:取 即可。但 為假:對任何給定的 ,取 即可。其否定為 ,同樣的取法可以驗證。僅僅調換量詞的次序,就改變了數學問題。
例題 1.1.5
(代數過程清晰可見的歸納法)
對 ,有 ,其中 時的空和為 。若公式在 時成立,則加上下一項得 。基礎情況與這一計算證明了所有情況。該論證恰好使用了前一個等式,而沒有在 處假定所要證明的等式。
例題 1.1.6
(為甚麼強歸納法與因數分解相配合)
每個整數 都是若干質數的乘積。 時成立。假設命題對從 到 的所有整數都成立,則 要麼是質數,要麼 且 。在後一種情況,歸納假設分別適用於 ,把它們的分解相乘便證明了命題。若只知道 的情況,則無法直接掌握這兩個因數。
陳述的論域是其內容的一部分
僅有一個公式還不是數學斷言。論域決定了哪些對象可以充當例子、見證元和反例。關於整數平方的陳述可能為真,而同樣的文字用於任意實數則可能為假。例如,「平方不小於原數」這一斷言對非負整數成立,但對嚴格介乎零與一之間的實數不成立。去掉論域限制會改變定理,即使代數表達式完全相同。
當證明引入一個任意對象時,必須尊重該論域,並且只使用所述的假設。「任意」一詞並不表示隨手挑選一個方便的測試例子。在全稱命題的證明中,論證必須對每個容許的對象都有效,而不能再作額外的、缺乏根據的選擇。相反,在存在性證明中,方便的顯式構造是受歡迎的,只要它滿足對見證元所施加的每一項條件。
否定令這些責任格外清楚。要反駁全稱命題,一個反例已經足夠。要反駁存在命題,則每一個可能的見證元都必須失敗。因此,幾次失敗的嘗試並不能證明不存在見證元。不存在性的證明需要結構性的障礙,例如奇偶性、整除性,或對所有候選者一致適用的界。這一區別將在計數論證和算法不可能性的論斷中反覆出現。
蘊涵與空洞情況
蘊涵式並不斷言其假設會出現。如果沒有任何對象滿足假設,則該蘊涵式在整個論域上都為真。這就是為甚麼關於空集合中所有元素的全稱命題為真:沒有反例,因為沒有元素能夠滿足假設而違反結論。而對同一空集合的存在命題為假,因為它沒有見證元。
空洞真並非例外,而是有用的工具。它使得關於序列所有更早項的陳述在第一項處也有意義,也使得關於孤立頂點所關聯的全部邊的斷言無須虛構特殊對象便可理解。撰寫證明的人仍須檢查所要得到的結論是全稱的還是存在的。一個空的構造可能對每個被選中的對象都滿足某個條件,卻不滿足至少要選出一個對象這另一項要求。
反例模式
逆命題改變了斷言
命題「若一個整數能被四整除,則它是偶數」為真。其逆命題為假:整數二是偶數,但不能被四整除。逆否命題「若一個整數不是偶數,則它不能被四整除」與原命題等價。若要修正一個無意中使用了逆命題的證明,要麼補充更強的假設,要麼找出只使用有效蘊涵的論證。
需要多少個基礎情況?
基礎情況的數目由遞推式或證明步驟決定。如果證明由緊接的前一情況推出下一情況,則一個有效的起點便可以向前傳遞。如果由前兩個情況推出一個情況,則必須給出兩個初始情況。一個每次前進二的步驟,從單一起點出發只能到達一個奇偶類;要涵蓋另一個奇偶類,還需要第二個起點。
這可以不借助非正式的「傳遞」之類的說法來表達。考慮由已證明的起始情況出發,利用容許的步驟所能到達的指標集合。只有在這個集合中的指標處,結論才有根據。如果所要求的論域包含無法到達的指標,證明便有缺口。對於強歸納法,通常的表述涵蓋所有更早的指標,但具體的論證仍可能需要若干個小的情況,因為所設想的分解對最小的輸入並不存在。
作為一個具體應用,每個不小於十二的整數都可以寫成四和五的非負整數組合。四個初始值十二、十三、十四和十五都有這樣的表示。任何更大的整數都比某個仍不小於十二的較小整數大四。於是強歸納法透過再加一個四給出該表示。單一基礎值無法證明其他餘數類,因為加四不改變模四的餘數。
有意地加強歸納命題
有時所要的結論太弱,不足以支撐它自己的下一步。標準的做法是證明一個更強的斷言,其中包含所需的額外資訊。只有當這個更強的斷言有自己的證明(包括其基礎情況)時,這樣做才是正當的。把一個沒有根據的斷言加入歸納假設,等於假定了結果的一部分。
例如,序列的證明可能需要關於相鄰兩項的界,而不是一項的界。可以定義一個新的謂詞,同時斷言這兩個界。在歸納步驟中,原來的第二個界成為新的第一個界,而遞推式證明新的第二個界。這樣便把遞推式恰好需要的資訊打包在一起。該方法與在算法中引入迴圈不變量相同:記錄足夠多的狀態,使更新可以被證明。
審查任何歸納證明也遵循同樣的紀律。確定正在證明的指標,並列出實際用到的更早指標。檢查每個指標都嚴格更早,並且位於假設的論域之內。然後單獨檢查最小的指標,因為在那裏分解或遞推式可能尚不適用。最後驗證當前指標處的任何斷言都沒有在被證明之前就被使用。這一審查可以找出隱藏的循環論證和欠缺的基礎情況。
從例子到有用的猜想
在證明之前,例子能發揮實際作用:它們可以揭示規律,提示正確的起始指標,或暴露欠缺的假設。在公式推出之後,它們亦可用來檢驗所提出的公式。它們的局限是邏輯上的而非實際上的:任何有限的表格都留下無窮多個未檢驗的後續輸入。證明必須提供一種機制來涵蓋這些未檢驗的輸入。
一個好的反例往往比一長串的驗證性情況更有啟發性。當猜想不成立時,要問:甚麼樣的假設可以防止這一失敗?如果除法步驟在零處失敗,也許需要一個非零的假設來修復。如果消去律在合數模下失敗,也許可逆性就是欠缺的條件。修復後的陳述應當由其修訂後的假設來證明;排除第一個反例並不能保證其他所有失敗都已被排除。
這些習慣說明了為甚麼精確的陳述應當出現在證明的開頭,而不是事後重構。陳述記錄了論證必須兌現的確切承諾,證明則記錄了每項承諾如何得出。把這兩種角色分開,才使日後的推廣成為可能:人們可以檢查哪些假設被用到了,哪些只是出於方便。
常見錯誤
常見錯誤
(檢驗個別情況不是歸納步驟)
證明 並檢驗 不是歸納步驟。反過來,即使所有 都為假,蘊涵 對每個 也可能為真:假設為假的蘊涵式對結論的真假甚麼也沒有說明。
常見錯誤
(馬群論證在哪一步失效)
「任何有限的馬群中所有的馬顏色都相同」這一斷言有一個著名的錯誤歸納:在兩端各去掉一匹馬,再透過共有的一匹馬比較兩個較小的馬群。當原集合的大小為 時,這兩個馬群並不重疊。因此,所謂從大小 到大小 的步驟是失敗的。應當指出究竟是哪個假設失敗,而不是僅僅報告結論看起來不合理。
總結
量詞的次序記錄了容許的依賴關係。否定改變每個量詞,同時保持這一次序。歸納法之所以能證明無窮多個情況,是因為假設的最小失敗情況與歸納步驟矛盾;歸納步驟與基礎情況必須涵蓋所斷言的每個指標。
練習
快速檢查
(證明對每個非負整數 , 整除 。)
使用恆等式 。
解答 · 答案
當 時, 能被 整除。若對某個整數 有 ,則 ,同樣能被 整除。由歸納法,命題對所述的每個指標都成立。
快速檢查
(否定下列命題:對每個整數 ,存在整數 ,使得 。判定原命題及其否定的真假。)
保持兩個論域以及量詞的次序。
解答 · 答案
其否定為 。它為假。對任意整數 ,取 ,則 。這一取法證明了原命題,並排除了其否定中每一個被提出的界。
快速檢查
(設 ,且對 有 。證明對每個 都有 ,並說明歸納步驟需要多少個基礎情況。)
歸納步驟用到前兩項。
解答 · 答案
兩個基礎情況都成立:,。需要兩個,是因為在 處證明公式的步驟要用到 與 處的公式;若只檢驗 ,步驟連一次都無法應用。若公式在 與 處成立,則 ,而 ,所以這正是 處的公式。例如 ,。