反证法

反证法（proof by contradiction）先把待证结论的否定当作临时假设，再从它与已经确认的前提推出不可能同时成立的两件事。矛盾说明临时假设不能成立。在通常的经典数学逻辑中，由此可回到原结论。

证明“ $\sqrt{2}$ 不是有理数”时，直接列举所有分数没有办法完成任务，因为分数有无限多个。反证法把“它是某个分数”具体化，接下来只需检验这种表示会带来什么后果。

一份完整的无理数证明

假设 $\sqrt{2}$ 是有理数。把它写成已经约到最简的正整数之比 $p / q$ ，其中 $q > 0$ 且 $gcd (p, q) = 1$ 。平方并整理： $p^{2} = 2 q^{2} .$ 因此 $p^{2}$ 是偶数。要从这里推出 $p$ 是偶数，还需要说明“奇整数的平方仍是奇数”：若 $p = 2 k + 1$ ，则 $p^{2} = (2 k + 1)^{2} = 2 (2 k^{2} + 2 k) + 1,$ 与 $p^{2}$ 为偶数不相容。故 $p = 2 r$ ，其中 $r$ 为整数。

把它代回原等式： $4 r^{2} = 2 q^{2}$ ，即 $q^{2} = 2 r^{2}$ 。同样的奇偶论证迫使 $q$ 也为偶数。于是 2 同时整除 $p$ 和 $q$ ，与分数已约到最简、 $gcd (p, q) = 1$ 矛盾。原先“ $\sqrt{2}$ 是有理数”的假设因此为假。

证明的关键不是“算出一个奇怪结果”，而是找到了同一对整数必须既互素又有公因数 2的冲突。只证明 $p$ 为偶数还不能结束：最简分数的分子单独为偶数并无问题，例如 $2 / 3$ 。

先否定准确的结论

若要证明“不存在最大的整数”，其否定是“存在一个最大的整数 $M$ ”。此时 $M + 1$ 仍是整数而且更大，立即矛盾。同一句话也可以说成“每个整数 $x$ 都有一个比它大的整数”；它的否定则是“存在某个整数 $x$ ，没有整数比它大”。两种表述在整数范围内等价，但量词的位置必须交代清楚。

一般地，对“每个 $x$ 都有某个 $y$ 满足 $R (x, y)$ ”取反，得到“存在 $x$ ，使所有 $y$ 都不满足 $R (x, y)$ ”。不能只把“都有”改成“都没有”而保留原来的量词次序。逻辑中的量词规则提供了检查办法。

与逆否证明的分工

要证 $P \Rightarrow Q$ ，可以证明等价的逆否命题 $\neg Q \Rightarrow \neg P$ 。例如“若整数 $n^{2}$ 为偶数，则 $n$ 为偶数”可改证“若 $n$ 为奇数，则 $n^{2}$ 为奇数”，展开 $(2 k + 1)^{2}$ 即可。这个证明从 $\neg Q$ 直接到 $\neg P$ ，不一定要写出一对互相冲突的结论。

反证法更适合目标为“不存在”或直接假定否定后能得到清楚冲突的情形。它不是跳过构造和验算的许可证。证明一个对象存在时，仅排除“不存在”可能仍要用到上确界原理之类的存在性条件；证明一个对象唯一时，还要另行排除两个不同对象同时满足要求。

核对矛盾来自哪里

使用反证法时，可以把论证写成三栏：原有前提、为反证临时加入的假设、由二者推得的冲突。若某一步未经证明地把目标结论当成前提，或者临时假设实际上比目标的否定更强，即使最后写出“矛盾”，也没有完成原命题的证明。

在 $\sqrt{2}$ 的例子中，实数算术与奇偶性质是原有规则；“ $\sqrt{2} = p / q$ 且分数最简”来自临时假设和约分；“ $p, q$ 都是偶数”来自等式。冲突恰好落在互素条件上。读者可照此检查素数条目中“素数不能只有有限多个”的证明：构造出的新数不必本身是素数，只需拥有清单以外的素因子。

参考资料

ProofWiki，Proof by Contradiction：间接证明的逻辑规则。
Oscar Levin，Discrete Mathematics: An Open Introduction，§3.2 Proofs：直接证明、逆否证明与反证法的比较。
继续阅读：逻辑、数学归纳法、素数。