數學證明/證明方法/反證法

附錄

反證法是假設一個命題不成立，然後證明這個假設會導致矛盾。在試圖證明 $P\Rightarrow Q$ 的情況下，這等效於假設 $P\land \lnot Q$ ，也就是假設 $P$ 為真，而 $Q$ 為假。這種方法被稱為拉丁語的reductio ad absurdum（歸謬法），因為它最終得出無法成立的結論。

2 的平方根

一個很好的例子是證明 ${\sqrt {2}}$ 是無理數。直接證明（透過構造性證明）可能非常困難（如果不是不可能的話）。然而，透過反證法，我們有一個相當簡單的證明。

命題 2.3.1.

{\sqrt {2}}\notin \mathbb {Q}

證明：假設 ${\sqrt {2}}$ 是有理數。那麼 ${\sqrt {2}}={\frac {a}{b}}$ ，其中 $a$ 和 $b$ 是互質整數（a 和 b 沒有公因子）。^[1] 且 $b\neq 0$ 。所以

$2={\frac {a^{2}}{b^{2}}}$

$2b^{2}=a^{2}$

但由於 $a^{2}$ 是偶數， $a$ 也必須是偶數，因為奇數的平方也是奇數。然後我們有 $a=2a_{1}$ ，或 $2b^{2}=4a_{1}^{2},$ 所以 $b^{2}=2a_{1}^{2}$ 。

現在可以將相同的論點應用於 $b$ 以找到 $2b_{1}=b$ 。但是，這與 a 和 b 互質的原始假設相矛盾，上述情況是不可能的。因此，我們必須得出結論， ${\sqrt {2}}$ 是無理數。

當然，我們現在注意到，在這個證明中，除了 2 是素數之外，沒有什麼是特殊的。這使我們能夠說 $a$ 是偶數，因為我們知道 $a^{2}$ 是偶數。請注意，這對於 4 不起作用（主要是由於 ${\sqrt {4}}=2\in \mathbb {Q}$ ）因為 $4|a^{2}$ 不意味著 $4|a$ 。

更多想法

用英語來說，這個過程是這樣的：斷言一個陳述是錯誤的，然後證明自己錯了。（從而證明了原始陳述是正確的。）這是一種 Modus Tollens 的形式。

對於許多學生來說，反證法是一種巨大的禮物和特洛伊木馬，這兩種情況都來自於這種方法的強大之處。事實上，敏銳的讀者可能已經注意到，構造法和逆否法都可以從反證法中推匯出。

假設	證明	矛盾
$P\land \lnot Q\ which\ implies\ P$	$Q\ (from\ P\ only)$	$Q\land \lnot Q$
$P\land \lnot Q\ which\ implies\ \lnot Q$	$\lnot P\ (from\ \lnot Q\ only)$	$P\land \lnot P$