反證法與逆否命題法

本文的閱讀等級:中級

英國數學家哈代 (G. H. Hardy) 說[1]:「歐幾里得喜好的歸謬法是數學家最精良的武器之一。它比起棋手所用的任何戰術還要好:棋手可能需要犧牲一個卒子或其他棋子,但數學家提供整個遊戲。」歸謬法 (reductio ad absurdum) 是一種間接論證方式,先假設某個命題不成立,然後推理出矛盾、不符合已知的事實或荒謬的結果,從而論斷該命題成立。在命題易於作否定陳述,假設條件僅提供少量訊息,或缺乏明確的直接證明思路時,歸謬法便可派上用場。反證法 (proof by contradiction) 是狹義的歸謬法,兩者的差別在於反證法只限於推理出邏輯上矛盾的結果。因此,反證法經常應用於證明數學定理。具體地說,我們要證明一個陳述「若 PQ」,記為 P\to Q,其中 P 是條件,Q 是命題,也就是說,PQ 的一個充分條件,QP 的一個必要條件。反證法假定 P\neg Q (非 Q) 同時成立,然後設法推論出 \neg R。但 R 是某個已知的事實或條件,這樣就得到一個矛盾 R\wedge\neg R。在反證法中,R 可以是 \neg QP,或其他已知的事實或條件。如果 R=\neg Q,反證法要證明 P\wedge\neg Q\to \neg(\neg Q),即 P\wedge\neg Q\to Q。如果 R=P,反證法要證明 P\wedge\neg Q\to\neg P

 
另一種很容易與反證法混淆的證明方法稱為逆否命題法 (proof by contrapositive),也就是證明 P\to Q 的等價陳述 \neg Q\to\neg P。逆否命題法假定 \neg Q 成立,然後設法推理出 \neg P。反證法與逆否命題法的主要差異在於反證法使用了條件 P,逆否命題法則否。請注意,反證法的推理過程中必須使用假設條件 P\neg Q。如果在不使用 \neg Q 的情況下,P 可以推論出 Q,我們不須說「因為 Q\neg Q 相矛盾,因此得證」。這樣的證明其實是一個直接證法,但由於在論證敘述引入矛盾一詞,你可以稱之為「假反證法」。類似地,如果在不使用 P 的情況下,\neg Q 可以推論出 \neg P,這個證明誠然是一個逆否命題法,因此也可以稱之為「假反證法」。

 
為便利理解,我們將三種證明方法以邏輯符號表示如下:欲證明 P\to Q 為真,

  • 直接證法:P\to Q
  • 反證法:P\wedge\neg Q\to \neg R (假定 R 成立)
  • 逆否命題法:\neg Q\to \neg P

下面舉幾個例子說明。

 
定理 1. 令 A 為一個方陣。若存在一個非零向量 \mathbf{x} 使得 A\mathbf{x}=\mathbf{0},則 A 是一個不可逆矩陣。

定理 1 的條件 P 是「存在一個非零向量 \mathbf{x} 使得 A\mathbf{x}=\mathbf{0}」,命題 Q 是「A 是一個不可逆矩陣」。定理 1 有很多種直接證法,但必須引進一些線性代數知識,證明 1.1, 1.2, 1.3 分別使用秩─零度定理、線性相關以及特徵值 (見“可逆矩陣定理”)。

 
證明 1.1. 令 A 為一個 n\times n 階矩陣。假設存在一個 \mathbf{x}\neq\mathbf{0} 使得 A\mathbf{x}=\mathbf{0},意即 A 的零空間 (nullspace) N(A) 包含非零向量,因此 \dim N(A)>0。秩─零度定理聲明 \hbox{rank}A=n-\dim N(A)<n,故 A 是一個奇異矩陣 (singular matrix),也就是說,A 是不可逆的。

 
證明 1.2. 令 A=\begin{bmatrix}  \mathbf{a}_1&\cdots&\mathbf{a}_n  \end{bmatrix} 為一個 n\times n 階矩陣。假設存在 \mathbf{x}=(x_1,\ldots,x_n)^T\neq\mathbf{0} 使得 A\mathbf{x}=\mathbf{0},即 x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0},表明 \{\mathbf{a}_1,\ldots,\mathbf{a}_n\} 是一個線性相關向量集,故 \hbox{rank}A<n (\hbox{rank}A 等於 A 的最大線性獨立行向量數),證畢。

 
證明 1.3. 假設存在 \mathbf{x}\neq\mathbf{0} 使得 A\mathbf{x}=\mathbf{0},可知 A 有一個特徵值 0,故 \det A=0 (行列式等於特徵值之積),證畢。

 
證明 1.4. 使用逆否命題法。假設 A 是一個可逆矩陣 (條件 \neg Q),我們的目標要證明不存在一個非零向量 \mathbf{x} 使得 A\mathbf{x}=\mathbf{0},也就是說 A\mathbf{x}=\mathbf{0} 蘊含 \mathbf{x}=\mathbf{0} (命題 \neg P)。考慮 A\mathbf{x}=\mathbf{0}。等號兩邊左乘 A^{-1}

\begin{aligned}  A\mathbf{x}=\mathbf{0}&\Rightarrow A^{-1}A\mathbf{x}=A^{-1}\mathbf{0}\\  &\Rightarrow I\mathbf{x}=\mathbf{0}\\  &\Rightarrow \mathbf{x}=\mathbf{0}.  \end{aligned}

 
證明 1.5. 使用反證法。假設存在一個非零向量 \mathbf{x} 使得 A\mathbf{x}=\mathbf{0} (條件 P) 且 A 是一個可逆矩陣 (條件 \neg Q),我們的目標要推理出 \mathbf{x}=\mathbf{0} (命題 \neg P)。逆否命題法的論證稍加修飾即可寫出反證法,如下:若 \mathbf{x}\neq\mathbf{0} 使得 A\mathbf{x}=\mathbf{0},上式左乘 A^{-1} 可導出 \mathbf{x}=\mathbf{0},我們得到一個矛盾,證畢。

 
討論:證明 1.5 與證明 1.4 的推論步驟相同,皆未使用條件 \mathbf{x}\neq\mathbf{0}。因此,證明 1.5 其實是逆否命題法的偽裝,它是一個「假反證法」。

 
定理 2. 令 AB 為兩個同階方陣。若 AB=0,則 BA 的所有特徵值為零。

C 為一個 n\times n 階矩陣。我們稱 C 為冪零矩陣 (nilpotent matrix),若存在一個正整數 k 使得 C^k=0。冪零矩陣的一個充要條件為所有的特徵值為零 (見“特殊矩陣 (1):冪零矩陣”)。因此,定理 2 可以這樣描述:若 AB=0,則 BA 是一個冪零矩陣。

 
證明 2.1. 使用直接證法。因為 AB=0(BA)^2=BABA=0,可知 BA 是一個冪零矩陣,其特徵值全部為零。

 
證明 2.2. 使用直接證法。考慮特徵方程 BA\mathbf{x}=\lambda\mathbf{x}\mathbf{x}\neq\mathbf{0}。因為 AB=0,可得 ABA\mathbf{x}=A(\lambda \mathbf{x})=\lambda(A\mathbf{x})=\mathbf{0}。分開兩個情況討論:若 A\mathbf{x}\neq\mathbf{0},則 \lambda=0;若 A\mathbf{x}=\mathbf{0},則 BA\mathbf{x}=\mathbf{0},也就有 \lambda\mathbf{x}=\mathbf{0}。但 \mathbf{x}\neq\mathbf{0},推得 \lambda=0

 
證明 2.3. 使用逆否命題法。假設 BA 有一個非零特徵值。使用這個性質 (見“AB 和 BA 有何關係?”):ABBA 有相同的非零特徵值 (包含相重數),推論 AB 也有相同的一個非零特徵值,故 AB\neq 0

 
證明 2.4. 使用反證法。假設 BA\mathbf{x}=\lambda\mathbf{x}\lambda\neq 0\mathbf{x}\neq\mathbf{0}。因為 AB=0,可得 ABA\mathbf{x}=\lambda A\mathbf{x}=\mathbf{0},就有 A\mathbf{x}=\mathbf{0},故 \lambda\mathbf{x}=BA\mathbf{x}=\mathbf{0},意味 \lambda=0\mathbf{x}=\mathbf{0},我們得到一個矛盾,證畢。

 
討論:證明 2.3 假設 BA 有一個非零特徵值 (條件 \neg Q),利用 ABBA 的特徵值不變性推理出 AB\neq 0 (命題 \neg P)。證明 2.3 可以改寫為直接證法:因為 AB=0AB 的特徵值為零,故 BA 的特徵值也為零。證明 2.4 使用了 AB=0 (條件 P) 與 BA 有非零特徵值 (條件 \neg Q),推理出 BA 的特徵值必為零 (命題 Q)。因此,證明 2.4 確實是一個反證法。

 
定理 3. 令 A 為一個 n\times n 階矩陣,\lambda_1,\ldots,\lambda_n 為特徵值,\mathbf{x}_1,\ldots,\mathbf{x}_n 為對應的特徵向量。若 \lambda_1,\ldots,\lambda_k 為相異特徵值,則 \mathbf{x}_1,\ldots,\mathbf{x}_k 組成一個線性獨立集。

定理 3 說對應相異特徵值的特徵向量是線性獨立的。直接證法請參見“相異特徵值對應線性獨立的特徵向量之簡易證明”,底下給出一個使用逆否命題法的證明。

 
證明 3. 使用逆否命題法。假設 \{\mathbf{x}_1,\ldots,\mathbf{x}_k\} 是一個線性相關集。在不失一般性的原則下,設 \{\mathbf{x}_1,\ldots,\mathbf{x}_{p-1}\} 為最大的線性獨立集使得 \mathbf{x}_p=c_1\mathbf{x}_1+\cdots+c_{p-1}\mathbf{x}_{p-1},其中 c_1,\ldots,c_{p-1} 不全為零 (因為 \mathbf{x}_p\neq\mathbf{0})。上式左乘 A,可得

\displaystyle  \begin{aligned}  A\mathbf{x}_p&=c_1A\mathbf{x}_1+\cdots+c_{p-1}A\mathbf{x}_{p-1}\\  &=c_1\lambda_1\mathbf{x}_1+\cdots+c_{p-1}\lambda_{p-1}\mathbf{x}_{p-1}  \end{aligned}

而且

\displaystyle  A\mathbf{x}_p=\lambda_p\mathbf{x}_p  =c_1\lambda_p\mathbf{x}_1+\cdots+c_{p-1}\lambda_p\mathbf{x}_{p-1}

令上面兩式相減,c_1(\lambda_1-\lambda_p)\mathbf{x}_1+\cdots+c_{p-1}(\lambda_{p-1}-\lambda_p)\mathbf{x}_{p-1}=\mathbf{0}。因為 \mathbf{x}_1,\ldots,\mathbf{x}_{p-1} 是線性獨立的,c_i(\lambda_i-\lambda_p)=01\le i\le p-1。但至少有一個 c_i\neq 0 使得 \lambda_i=\lambda_p,證畢。

 
討論:如果證明 3 的最後一段改成:「因為 \mathbf{x}_1,\ldots,\mathbf{x}_{p-1} 是線性獨立的,且 \lambda_1,\ldots,\lambda_{p} 兩兩相異,可推論 c_i=01\le i\le p-1。我們得到一個矛盾,故得證。」修改後的證明就變成了反證法。

 
直接證法是建構式的證明方法,往往須引用較多的關聯性質與技巧,而反證法則相對簡單,原因在於矛盾可以是任何一樣東西。因此,反證法比逆否命題法的應用範圍來得廣泛。使用反證法的主要缺點是無從掌握從條件至命題的推理路徑,空白的部分只能仰賴你的直覺來彌補。

 
註解
[1] 原文:“Reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest weapons. It is a far finer gambit than any chess play: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game. ”

This entry was posted in 線性代數專欄, 證明細解 and tagged , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s