反證法

反證法（英語：proof by contradiction；拉丁語：reductio ad absurdum）是一種在經典邏輯中有效的數學證明方法，適用於證明一個數學命題為真。當命題$A$為假時，可應用反證法到$\lnot A$。反證法是一種間接證明方法，常用於難以直接證明的情形。

反證法的操作步驟是：

- 假設原命題的否定為真部分中學數學教材或網路資料的表述里「反證法第一步是假設『在原命題的條件下，結論不成立』」是面向簡單蘊含式的中學教學簡化說法，並非經典邏輯中反證法的嚴格定義。嚴格意義上，反證法的第一步是假設整個原命題為假（否定原命題），而非僅否定結論。二者在複雜命題中存在本質區別。例如「證明不存在最大的素數」、「證明有的全等三角形是直角三角形」、「證明存在兩個無理數$a,b$，使得$a^b$是有理數」，此類命題沒有明確的「條件-結論」二分結構，否定結論自然無從談起。
- 經過一系列正確的推理，得出根據矛盾律知恆為假的矛盾。
- 根據否定後件律，矛盾的根源只可能是原命題的否定為假（即假設不成立）。
- 根據排中律，知原命題為真。

反證法中得到的矛盾，有以下三種可能：

- 與已知條件矛盾。
- 與已知定理、公理、定義、法則或顯然成立的事實等矛盾。
- 與假設矛盾。

## 理據

給出命題 $p$ 和命題 $\bar{p}$（非 $p$），根據排中律，兩者之中起碼有一個是真（更強的說法為，除了真和假之外並無其他的情況），所以如果其中一個是假的，另一個就必然是真。給出命題 $q$ 和命題 $\bar{q}$（非 $q$），根據無矛盾律，兩者同時為真的情況為假。給出命題 $\bar{p}$ 和 $r$，根據否定後件律，如果若 $\bar{p}$ 成立時出現 $r$，則 $r$ 為假時 $\bar{p}$ 即為假。反證法在要證明 $p$ 時，透過顯示出若 $\bar{p}$ 成立時出現矛盾（$q$ 和 $\bar{q}$），即 $\bar{p}$ 為假，從而證明 $p$ 為真。

## 例子

### 單稱命題：$\sqrt{2}$是無理數的證明（古希臘）

證明：假設原命題不成立，即$\sqrt{2}$不是無理數，那麼$\sqrt{2}$是有理數這裡用到了隱含前提：$\sqrt{2}$是實數。在實數集中，有理數集與無理數集互為補集（不交且併集為全體實數），二者非此即彼，滿足反證法的排中律要求。根據有理數的定義，$\sqrt{2}$可以寫成 $\frac{p}{q}$ 的形式，其中 $p$、$q$ 皆為正整數且 $p$、$q$ 互質。等式兩邊同乘$q$得$p=\sqrt{2}\, q$，故$p^2=2 q^2$，由此可知 $p^2$是偶數，所以 $p$ 也是偶數這裡又使用一次反證法/逆否命題法：假設$p$為奇數，則可把$p$表示為$p=2k+1$（其中$k$為整數），$\Longrightarrow p^2 = (2k+1)^2 = 2(2k^2 +2k)+1$為奇數，所以奇數的平方一定為奇數，這和$p^2$是偶數矛盾，故$p$必為偶數。因此可設 $p=2s$，從而 $p^2 = 4s^2$，代入上式，得$q^2=2s^2$。同理可知 $q^2$也是偶數，故 $q$ 也為偶數。此時 $p$、$q$ 均為偶數，不互質，這與 $p$、$q$ 互質的初始假設矛盾本證明的核心矛盾是「$p,q$互質」的前提與推導得出的「$p,q$不互質」相衝突。事實上，反證法初始假設中「$p,q$互質」並非必需條件：若假設$\sqrt{2}$為有理數時不附加互質約束，重複上述推導可得到無窮多組數值不斷縮小的正整數解，這正是無窮遞降法的證明思路，無窮遞降法本質上是反證法的一種特殊形式。因此原假設不成立，$\sqrt{2}$為無理數。

### 全稱蘊含式：$\forall a,b \in \mathbb{Z}$，$(a+b\sqrt{2} =0) \rightarrow b=0$.的證明

證明：反證法。

假設原命題的否定為真，即假設：$$\exists a_0 ,b_0 \in \mathbb{Z}, (a_0 + b_0 \sqrt{2}=0)\land \lnot (b_0 =0)$$為真。

則$b_0 \neq 0$，推出$\sqrt{2} = \cfrac{a_0}{b_0}$，這是矛盾，因為無理數$\sqrt{2}$是不可能等於有理數$\cfrac{a_0}{b_0}$的。因此假設不成立，即原命題的否定為假，故原命題為真。

## 其他可用反證法證明的例子

數學上有許多的定理可用反證法來證明，以下是一小部分的例子：

- 證明有無限多個質數。
- 任意6人當中，求證或者有3人兩兩相識，或者有3人互不相識。
- 現有90張紙，每張紙都寫有一個非負整數，已知這90個數之和小於1980，證明至少有三張數目相同的紙。
- 集合 $S = \{x: 0<x<1\}$ 沒有最小值。
- 設 $n$ 是大於1的整數，若所有小於或等於$\sqrt{n}$的質數都不能整除 $n$，則 $n$ 是質數。
- 已知三角形ABC是銳角三角形，且$\angle A>\angle B>\angle C$。求證：$\angle B>45^\circ$。
- 已知 $a$、$b$ 為正實數，求證：$\frac{a+b}{2}\ge \sqrt{ab}$。
- 已知 $a$、$b$、$c$、$d$ 是實數，且$ad-bc=1$，求證：$a^2+b^2+c^2+d^2+ab+cd\neq 1$。
- 一個群若同時是交換群和單群，則該群是循環群
- 若一個循環群是單群，則該群的階為質數
- 若一個循環群的階為質數，則該群為單群
- 鴿籠原理

## 數學家哈代關於反證法的名言

- 英國數學家高德菲·哈羅德·哈代在他的文章《一個數學家的辯白》描述：「反證法是數學家的拿手好戲。它比任何棋手棄子取勝的策略都更高明：棋手可能願意丟車保帥，但數學家卻是把全盤置諸死地而後生。」

## 辨析——數學教育中的反證法

反證法一詞，在不同地區、不同數學圈子裡有不同的含義。

### 高中數學教育中的反證法

- 台灣高中數學教育圈常將英文'proof by contradiction'翻譯為"歸謬證法"，將英文'proof by contrapositive'翻譯為"反證法"。
- 在香港高中數學教育圈，'proof by contradiction'翻譯為「反證法」或者「歸謬法」，而'proof by contrapositive'翻譯為逆否命題證明法（或簡稱逆否證法）。
- 在中國大陸高中數學教育圈，普通高中教學中往往將'proof by contrapositive'和'proof by contradiction'雜糅在一起，稱為「反證法」，實際指代的和台灣高中數學教育圈的"反證法"之意類似，證法的內容主體都是'proof by contrapositive'，原理都是原命題和逆否命題同真假，但卻用了「導出矛盾」的'proof by contradiction'框架的說法。'proof by contrapositive'的名詞在大陸西元2017年高中數學課綱中沒有提到，因為課綱已刪除了四種命題（原命題、逆命題、否命題、逆否命題），高中階段不再出現逆否命題證明法這一名詞，只以反證法之名行逆否命題證明法（'proof by contrapositive'）之實。

反證法是中學數學到大學數學教育銜接的難點之一，在不同國家地區都是一個教育難題。

### 大學數學教育中的反證法

大學數學的中文教材，對反證法的定義回歸到嚴謹的數學定義，均指'proof by contradiction'；並且大學數學教材嚴格區分反證法（'proof by contradiction'）與逆否命題證明法（'proof by contrapositive'）。

## 進一步閱讀

- J. Franklin and A. Daoud, Proof in Mathematics: An Introduction, Quakers Hill Press, 1996, ch. 6