反證法

反證法（粵拼：Faan² zing³ faat³；英國話：Proof by contradiction），又叫做證偽法、矛盾證明，係一個數學上一個攞嚟證明啲嘢唔啱嘅方法。係拉丁話入面，反證法畀人嗌做「reductio ad absurdum」（英國話：reduction to the absurd），意思係「推斷出荒謬嘅嘢」。

呢個方法嘅橋妙係咁：首先整一個命題（Proposition）$p$，然後就假設（Assume）$p$ 呢個命題係啱嘅；跟住就推一啲只要 $p$ 係啱，就一定會發生嘅結果出嚟，最後就指出呢個結果係唔成立或者係喺邏輯上矛盾嘅，咁就可以證明 $p$ 係錯嘅。

真值表

反證法可以用真值表嚟證明：因為如果「$p\rightarrow q$」係真（True；T）但係 $q$ 係假（False；F）嘅，咁 $p$ 嘅值只可能係假。

推論

$p$	$q$	$p$ → $q$
T	T	T
T	F	F
F	T	T
F	F	T

簡單例子

要求：

證明「如果 $n\in \mathbb {Z}$ 係一個單數，咁 $n^{2}$ 都會係一個單數」。

證明：

假設有個情況， $n\in \mathbb {Z}$ 係一個單數，但係 $n^{2}$ 係一個雙數。

即係對應某啲 $k\in \mathbb {Z}$，$n=2k+1$。計吓

$${\begin{aligned}n^{2}&=(2k+1)^{2}\\&=4k^{2}+2k+1\\\end{aligned}}$$

好明顯呢個情況下 $n^{2}$ 唔係一個雙數，所以同前提矛盾。所以 $n^{2}$ 佢一定係個單數。「如果 $n\in \mathbb {Z}$ 係一個單數，咁 $n^{2}$ 有可能係一個雙數」呢句嘢唔成立－「如果 $n\in \mathbb {Z}$ 係一個單數，咁 $n^{2}$ 都會係一個單數」。

進階例子

要求：

證明冇任何兩個正整數（Positive integer）$x,y\in \mathbb {Z} _{>0}$ 可以乎合 $x^{2}-y^{2}=1$ 呢條式。呢個證明需要用到分類證明（Proof by exhaustion）。

證明：

假設有兩個正整數 $x,y\in \mathbb {Z} _{>0}$ 符合 $x^{2}-y^{2}=1$ 呢條式。（假設）

利用 $(a+b)(a-b)=a^{2}-b^{2}$，得知 $(x+y)(x-y)=1$。

如果淨係睇整數，$1$ 只可以係 $1\cdot 1=1$ 同 $-1\cdot -1=1$ 嗰度嚟。

如果係 $1\cdot 1=1$，即係 $x+y=1$ 同 $x-y=1$。

因此，$x=1,y=0$。（由假設推出個矛盾－因為唔可能有一個正整數係比一更細。）

如果係 $-1\cdot -1=1$，即係 $x+y=-1$ 同 $x-y=-1$。

因此，$x=-1,y=0$。（又試由假設推出個矛盾：更冇可能，因為要求正整數。）

總括所有可能，個假設都係唔成立，所以一定唔存在 $x,y\in \mathbb {Z} _{>0}$－冇任何兩個正整數可以乎合 $x^{2}-y^{2}=1$ 呢條式。

${\sqrt {2}}$ 係非有理數

要求：

利用矛盾證明嚟證明「${\sqrt {2}}$ 係非有理數（Irrational number；冇辦法用整數寫做分數嘅數字）。」

證明：

假設 ${\sqrt {2}}$ 可以係個有理數（Rational number；可以用整數寫做分數嘅數字）。咁即係喺至少一個情況下 ${\sqrt {2}}={\frac {m}{n}}$，而 $m\in \mathbb {Z}$ 同 $n\in \mathbb {Z}$ 都係整數。

喺呢度，進一步假設 ${\frac {m}{n}}$ 係已經約咗簡，費事有約數嘅撈絞。

${\begin{aligned}{\sqrt {2}}&={\frac {m}{n}}\\({\sqrt {2}})^{2}&={\bigl (}{\frac {m}{n}}{\bigr )}^{2}\\2&={\frac {m^{2}}{n^{2}}}\\2n^{2}&=m^{2}\end{aligned}}$

由上面得出，$m^{2}$ 係雙數。

假設 $m$ 係單數，利用簡單例子嘅定理，咁 $m^{2}$ 一定係單數。（矛盾：因為 $m^{2}$ 係雙數。）

所以，$m$ 係雙數，而且可以寫成 $m=2k$，$k\in \mathbb {Z}$ 係某個整數。

${\begin{aligned}2n^{2}&=m^{2}\\2n^{2}&=(2k)^{2}\\2n^{2}&=4k^{2}\\n^{2}&=2k^{2}\end{aligned}}$

利用上面，再總結得出 $n$ 係雙數，而且可以寫成 $n=2j$，$j\in \mathbb {Z}$ 係某個整數。

${\sqrt {2}}={\frac {m}{n}}={\frac {2k}{2j}}={\frac {k}{j}}$

因為，假設 ${\frac {m}{n}}$ 係已經約咗簡，所以唔可以有另一個 ${\frac {k}{j}}$。

所以 ${\sqrt {2}}$ 唔可以用整數寫做分數。

可以利用呢個步驟推出 ${\sqrt {3}}$、${\sqrt {5}}$、${\sqrt {p}}$，$p$ 係質數，都唔係有理數。

反證法嘅步驟

1. 寫低要證明嘅命題。
2. 再寫低頭先嗰句命題嘅相反，再假設呢句新命題係啱。
3. 利用呢條假設，推斷啲野出嚟。
4. 搵下有咩矛盾。
5. 如果個假設引致矛盾，咁就可以話個假設係錯。咁嘅話個假設嘅相反－即係想證明嗰句命題－就會係啱。

更多例子

以下命題係可以用反證法嚟證明：

• $x^{5}-2x^{3}-3=0$ 嘅值係一定少過 $2$。
• 對所以嘅整數 $x$、$y$，如果 $xy$ 係單數，咁 $x$ 同 $y$ 都係單數。

睇埋

• 數學史
• 直接證明
• 分類證明
• 數學歸納法
• 否定證明

參考

• Beth, E. W. (1970). Proof by Contradiction. In Aspect of Modern Logic (pp. 30-41). Springer Netherlands.
• Antonini, S., & Mariotti, M. A. (2006). Reasoning in an absurd world: difficulties with proof by contradiction. In Proceedings of the 30th PME Conference, Prague, Czech Republic (Vol. 2, pp. 65-72).