反證法與逆否命題法

Posted on 03/18/2016 by ccjou

本文的閱讀等級：中級

英國數學家哈代 (G. H. Hardy) 說[1]：「歐幾里得喜好的歸謬法 (reductio ad absurdum) 是數學家最精良的武器之一。它比起棋手所用的任何戰術還要好：棋手可能需要犧牲一個卒子或其他棋子，但數學家提供整個遊戲。」歸謬法是一種間接論證方式，先假設某個命題不成立，然後推理出矛盾、不符合已知的事實或荒謬的結果，從而論斷該命題成立。在命題易於作否定陳述，假設條件僅提供少量訊息，或缺乏明確的直接證明思路時，歸謬法便可派上用場。反證法 (proof by contradiction) 是狹義的歸謬法，兩者的差別在於反證法只限於推理出邏輯上矛盾的結果。因此，反證法經常應用於證明數學定理。具體地說，我們要證明一個陳述「若 P 則 Q」，記為 P\to Q，其中 P 是條件，Q 是命題，也就是說，P 是 Q 的一個充分條件，Q 是 P 的一個必要條件。反證法假定 P 與 \neg Q (非 Q) 同時成立，然後設法推論出 \neg R。但 R 是某個已知的事實或條件，這樣就得到一個矛盾 R\wedge\neg R。在反證法中，R 可以是 \neg Q，P，或其他已知的事實或條件。如果 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. 令 A 與 B 為兩個同階方陣。若 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 有何關係？”)：AB 與 BA 有相同的非零特徵值 (包含相重數)，推論 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)，利用 AB 與 BA 的特徵值不變性推理出 AB\neq 0 (命題 \neg P)。證明 2.3 可以改寫為直接證法：因為 AB=0，AB 的特徵值為零，故 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)=0，1\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=0，1\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.

Leave a comment