[分享] 關於數學證明的一點點思路 (II)-contrapositive proof 與 proof by contradiction

OK，承接上篇證明的思路(I):
在搞清楚定義之後。才可以開始證明!

再者寫下證明的每一步。都必須是 "正確無誤" 的陳述。如果寫下的陳述有一部分是錯的或者在有一些情況下可能是錯的。那麼整個證明就必然無疑的存在嚴重的瑕疵。這種證明並非是證明，單純只是錯誤的陳述或者在某種情況下會出錯的陳述。

所以在確保定義清楚 外加 每一步都正確的概念之下，我們才可以來討論證明的策略。

數學證明的方法(策略)，就種類來說大致可分成四種
今天想要分享的是 逆否命題法(contrapositive proof) 與 矛盾證法(proof by toward to contradiction)

考慮命題為 : If P then Q

1. 直接證明法 (用已知假設P 透過逐步邏輯推演以及已經證畢的定理，逐步直接的 推出Q)
2. 反證法(逆否命題)  (將原命題改為 If NOT Q, then NOT P: 亦即用 NOT Q 當作假設 透過逐步證明推出 NOT P)
3. 間接證明-矛盾證法 或稱 歸謬法 (維持原命題假設 If P 而且額外再假設 if NOT Q, 逐步證明與某個已知事實矛盾? i.e., 將原命題改為 If P and NOT Q 去證明某個矛盾)
4. 數學歸納法

以下我們先看個例子說明 歸謬證法

FACT: 令 $a,b$為兩實數，若對任意 $\varepsilon >0$，$a \le b + \varepsilon$，則 $a \le b$。
Proof
利用歸謬法，假設 $a > b$。並試圖找出矛盾點。

由於我們已知 對任意 $\varepsilon >0$，$a \le b + \varepsilon$，故我們觀察
\[\left\{ \begin{array}{l}
a \le b + \varepsilon \\
a > b
\end{array} \right. \Rightarrow b < a \le b + \varepsilon  \Rightarrow 0 < a - b \le \varepsilon
\]故現在令
\[
\varepsilon := \frac{a-b}{2}
\]仍滿足 $\varepsilon >0$。將上述 $\varepsilon $ 帶入 $a \le b + \varepsilon $ 得到
\[a \le b + \varepsilon  \Rightarrow a \le b + \frac{{a - b}}{2} \Rightarrow a \le b
\]上式結果與 $a > b$ 矛盾；故我們一開始假設的 $a > b$ 有誤。至此得證。$\square$


事實上關於反證 與 矛盾證明常有時機使用的問題，就是到底何時該採用反證法 何時 適用 矛盾證明?

使用時機:任何時候對一個證明應先嘗試直接證明法，如果對於 直接證明 完全毫無頭緒時，再接著嘗試採用反證法或者矛盾證法

例: 欲證 質數(prime numbers)有無窮多個
如果透過直接證法，你就必須真的去找出 "無窮多個" 質數，但這種方法很明顯無法使用(why?)
因為我們時間有限，無法真的找出無窮多個 質數出來，你也不可以說你找到很多個就OK，因為原命題是要求要找出"無窮多個"故此時應轉而使用反證法/矛盾證法 來處理這類問題。

事實上，對於大多數 存在性的命題(existential statment) : 
If X then there exists Y such that Z
都可考慮採用矛盾證明法，因為在這命題中，我們被要求用X當假設，然後必須"建構" OR "找出" 一個Y使得Z成立。但大多時候我們對Y基本上沒有頭緒。這時可以採用矛盾證法，將其納入為額外假設，試著找出矛盾點。