间接证明

当一个否定陈述能提供比原结论更具体的限制时，间接论证往往更方便。常用方法是逆否证明与反证法，它们的关系已在逆命题、否命题与逆否命题中说明。本篇把重点放在怎样选择假设，以及怎样把证明写完整。

全文使用经典逻辑。矛盾必须是与某个假设、定义或已有事实的明确冲突；算不下去不算矛盾。MIT 的证明入门讲义也提供了从假设建立结论的例子 [1][1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf。

计算之前先确定起点

证明 $P\to Q$ 的方法	假设什么	需要建立什么
直接证明	$P$	$Q$
逆否证明	$\neg Q$	$\neg P$
反证法	$P$ 和 $\neg Q$	矛盾 $\bot$

每一行都保留原有论域限制。反证一个全称定理时，假设反例存在，并取一个满足条件、违反结论的对象；证明不存在性时，则假设具有禁止性质的对象存在。开始运算前，要把包含量词在内的完整否定写出来。

两种间接方法可以重叠，例如用反证法证明逆否命题。名称描述的是论证的组织方式，不是互不相容的分类。

逆否证明：选择容易展开的表示

命题多项式的奇偶性

对每个整数 $x$，若 $x^2-6x+5$ 是偶数，则 $x$ 是奇数。

直接从多项式为偶数出发，不容易立刻得到 $x$ 的形式。结论的否定更好用：对整数，“不是奇数”就是“是偶数”，于是能写成 $x=2a$。

证明

证明逆否命题。设 $x=2a$，其中 $a\in\mathbb Z$。则

$$\begin{aligned} x^2-6x+5&=4a^2-12a+5\\ &=2(2a^2-6a+2)+1. \end{aligned}$$

括号内是整数，所以多项式为奇数，因而不是偶数。逆否命题得证，原命题也成立。

这里全程没有假设多项式为偶数。若改用反证法，就会同时假设它为偶数且 $x$ 不是奇数，最后得到同一个数既奇又偶。

反证法：指出不能同时成立的事实

命题二的平方根是无理数

正实数 $\sqrt2$ 不是有理数。

假设有理性可以得到分数表示，选取最简分数则提供了一个能被整除性推翻的条件。这里使用已经建立的奇偶事实：整数的平方为偶数，则这个整数也为偶数。

证明

假设 $\sqrt2=p/q$，其中 $p,q$ 为正整数，且没有大于一的公因数。任意正有理数都能选取这种最简表示。平方得到

$$p^2=2q^2.$$

于是 $p^2$ 为偶数，所以 $p$ 为偶数。写成 $p=2r$，其中 $r\in\mathbb Z$，代回并化简：

$$4r^2=2q^2, \qquad q^2=2r^2.$$

因此 $q$ 也为偶数。$p,q$ 都能被 $2$ 整除，与最简分数的选择矛盾，故 $\sqrt2$ 为无理数。

仅仅得到一个分子、分母均为偶数的分数，并不是矛盾，例如 $2/2$ 完全合法。冲突发生在“二者都为偶数”和“已经选成互素”之间。把这对事实写明，证明才真正结束。

用有限名单制造矛盾

命题素数有无穷多个

不存在能够列尽所有素数的有限名单。

这里使用一个初等事实：每个整数 $N>1$ 都有素因子。可以取它最小的大于一的因子 $d$；若 $d$ 为合数，$d$ 的一个更小的大于一的因子也整除 $N$，与最小性矛盾。

证明

假设全部素数组成有限名单 $p_1,\ldots,p_m$。因为 $2$ 是素数，名单非空。构造

$$N=p_1p_2\cdots p_m+1.$$

$N>1$，所以存在素因子 $q$。按照名单完整的假设，$q$ 必须在其中，因而也整除乘积 $p_1\cdots p_m$。它于是整除差 $N-p_1\cdots p_m=1$，但素数不可能整除 $1$，矛盾。故素数有无穷多个。

构造出的 $N$ 不必是素数，证明只需要它有一个名单之外的素因子。若把这一点换成“乘积加一总是素数”，就引入了错误陈述。

常见逻辑漏洞

“$a,b$ 都是奇数”的否定是“至少一个不是奇数”，不是“两个都是偶数”。“$a\ge8$ 或 $b\ge8$”的否定是同时有 $a<8$ 和 $b<8$。如果论域是整数，还能把每个上界收紧到 $7$；如果是实数，就不能这样做。

也要分清原命题和逆命题。证明偶数的平方为偶数，并没有证明平方为偶数的整数必为偶数。不确定时先明确写出 $P,Q$，对照当前假设和目标，再继续计算。

练习

练习补上素因子步骤的平方根证明

证明 $\sqrt5$ 为无理数。先说明为什么对整数 $t$，$5\mid t^2$ 蕴涵 $5\mid t$。

查看解析

解

$t$ 除以 $5$ 的余数为 $0,1,2,3,4$，平方的余数分别是 $0,1,4,4,1$。因此只有余数零才能让平方被 $5$ 整除。

若 $\sqrt5=p/q$ 是最简正分数，则 $p^2=5q^2$，所以 $p=5k$。代入得到 $q^2=5k^2$，故 $q$ 也被 $5$ 整除，与互素矛盾。余数论证补上了所需整除事实，不能默认同样的性质对任意整数除数都成立。

练习不存在最小正有理数

证明正有理数中没有最小者。

查看解析

解

假设正有理数 $r$ 最小。那么 $r/2$ 仍为有理数，且 $0<r/2<r$，与最小性矛盾。这题不需要最简分数表示。同一构造也可以直接证明：每个正有理数都有一个更小的正有理数。

练习反证法要保留两个假设

用反证法证明：若整数 $n$ 的平方为偶数，则 $n$ 为偶数。指出最后冲突的两个事实。

查看解析

解

同时假设 $n^2$ 为偶数、$n$ 不是偶数。由整数奇偶分类，写成 $n=2k+1$，则 $n^2=2(2k^2+2k)+1$ 为奇数。矛盾是 $n^2$ 既为偶数又为奇数。如果只从 $n$ 为奇数出发，推出 $n^2$ 为奇数，那就是直接证明逆否命题。

练习利用封闭性得到矛盾

证明一个无理实数与一个有理数之和是无理数。

查看解析

解

设 $r\notin\mathbb Q$、$s\in\mathbb Q$，假设 $t=r+s$ 为有理数。则 $r=t-s$ 由有理数对减法的封闭性仍为有理数，与 $r$ 的选择矛盾。具体地，若 $t=a/b$、$s=c/d$，整数分母都非零，则

$$t-s=\frac{ad-bc}{bd}\in\mathbb Q.$$

这不意味着两个无理数之和仍为无理数；$\sqrt2+(-\sqrt2)=0$ 就能反驳那个不同的命题。

练习正确否定合取

对整数 $a,b$，证明若 $ab$ 是奇数，则 $a,b$ 都是奇数。

查看解析

解

逆否命题假设至少一个因子为偶数。利用对称性，把它叫作 $a=2k$，其中 $k\in\mathbb Z$，则 $ab=2(kb)$ 为偶数。若偶数因子为 $b$，交换名称得到相同论证，因此整个逆否命题成立。

练习一次式的奇偶性

对整数 $n$，证明若 $3n+2$ 为偶数，则 $n$ 为偶数。

查看解析

解

证明逆否命题。若 $n=2k+1$，则 $3n+2=6k+5=2(3k+2)+1$ 为奇数，其中 $3k+2\in\mathbb Z$。所以原蕴涵成立。

练习整数论域确实有用

对整数 $a,b$，证明 $a+b\ge15$ 蕴涵 $a\ge8$ 或 $b\ge8$。换成实数后是否仍成立？

查看解析

解

假设结论的否定，即 $a<8$ 且 $b<8$。由于二者是整数，都至多为 $7$，所以 $a+b\le14<15$，逆否命题得证。换成实数就不成立：$a=b=7.5$ 时和为 $15$，二者却都不到 $8$。

从否定走向归纳

若否定目标能提供不可能存在的对象或极值条件，可以考虑反证法；若结论的否定有方便的表示，可以考虑逆否证明。对于按自然数规模排列的命题，最有用的信息还可能来自更小规模的结论，这就进入数学归纳法。

参考文献

1. [1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf ↩