证明方法 II：逆否、反证与存在唯一性

上一章的直接证明有一条很清楚的主线：接受题目给出的条件，把定义和已经知道的事实一件件接上去，最后抵达结论。能这样走时，直接证明通常最省事。

麻烦在于，有些结论并不给我们一个好用的“把手”。“$n$ 是偶数”可以写成 $n=2k$，可“$n^2$ 是偶数”要怎样直接拆开？“不存在最大的整数”甚至没有一个具体对象让我们从头推起。遇到这种题，证明停住不一定是知识不够，也可能是站的位置不合适。

这一章做的事情，就是换一个入口。条件命题可以转向它的逆否命题；否定式结论可以先假设它失败，再有目的地制造矛盾；含“存在唯一”的结论则要拆成“确实有”和“不可能有两个”两项任务。

先把一个写作习惯定下来：正式推理之前，用一句话交代路线。例如，“结论的否定能写成奇数的标准形式，所以改证逆否命题”，或者“若素数只有有限多个，就能把它们全部列出，因此采用反证法”。这句话不属于计算，却能回答读者最想问的事：你为什么会想到这样做？

先看目标的逻辑形状，再选择能直接进入定义的证明路线。

先看目标，再选入口

面对一道证明题，先别急着搬模板。把题目中的前提和结论分别圈出来，再问下面几个问题。

1. 目标是条件命题 $P\Rightarrow Q$ 吗？如果是，直接证明与逆否证明都有可能。
2. $Q$ 的否定是否比 $Q$ 更容易写成定义、等式或标准形式？如果是，逆否证明往往会打开局面。
3. 目标是否含“不存在”“不可能”“不是有理数”“有无限多个”？这些结论的反面常常会给出一个可利用的对象、有限列表或最简表示，适合反证法。
4. 目标是否含“存在”“恰有一个”“存在唯一”？这时先数清楚任务：只要一个、至多一个，还是两者都要。

这里最重要的动作是准确否定目标。例如，“所有整数都满足 $P$”的否定不是“所有整数都不满足 $P$”，而是“至少有一个整数不满足 $P$”：

同样，“存在一个 $x$ 满足 $P(x)$”的否定是“每个 $x$ 都不满足 $P(x)$”：

否定写错，后面的推理再漂亮也证明不了原题。很多所谓“方法不会选”，其实在这一步就已经偏了。

逆否证明：从结论的否定出发

要证明

可以改证它的逆否命题

这不是经验上的替代方案，而是逻辑等价：原命题与逆否命题在每一种真假取值下都同真同假。原命题唯一失败的情况是 $P$ 真而 $Q$ 假；在同一种取值下，$\neg Q$ 真而 $\neg P$ 假，逆否命题也恰好失败。两句话的真假完全同步，所以证明其中一句，就证明了另一句。

什么时候逆否会更顺

逆否证明最适合这样的情形：原命题的前提不好拆，而结论的否定有明确形式。

例如，对整数来说：

• “不是偶数”就等于“是奇数”，可以写成 $2k+1$；
• “不能被 $m$ 整除”可以转成除法余数不为 $0$；
• “两个集合不相等”意味着至少有一个元素只属于其中一个；
• “函数不是单射”意味着存在两个不同输入得到相同输出。

这些否定都给了我们可操作的材料。方法选择的诀窍很朴素：哪一边更容易进入定义，就从哪一边开始。

可复用的写法

要用逆否证明 $P\Rightarrow Q$，可以按下面的顺序组织。

例题：平方是偶数，原数也是偶数

命题：若整数 $n$ 的平方 $n^2$ 是偶数，则 $n$ 是偶数。

先看为什么选逆否。直接从“$n^2$ 能被 $2$ 整除”去拆 $n$，需要额外处理平方的因子；结论“$n$ 是偶数”的否定却很具体：整数 $n$ 不是偶数，就一定是奇数。奇数能写成 $2k+1$，代入平方后会立刻暴露奇偶性。

这里真正起作用的不是“逆否”两个字，而是奇数的定义。换方向之后，定义能立即代入，这就是选择该方法的理由。

再看一个带无理数的例子

命题：设 $r$ 是非负实数。若 $r$ 是无理数，则 $\sqrt r$ 是无理数。

原命题同时出现两个否定式定义，直接写会很绕。它的逆否命题是：“若 $\sqrt r$ 是有理数，则 $r$ 是有理数。”这个方向只需使用有理数的分数表示。

设

其中 $m,n$ 是整数且 $n\ne0$。两边平方可得

因为 $m^2,n^2$ 都是整数且 $n^2\ne0$，$r$ 是有理数。逆否命题成立，原命题也成立。

逆否命题不是逆命题

对原命题 $P\Rightarrow Q$，最容易混淆的三个相关命题是：

举个具体例子：

若一个整数能被 $4$ 整除，则它是偶数。

原命题是真的。它的逆命题“若一个整数是偶数，则它能被 $4$ 整除”却是假的，整数 $6$ 就是反例。它的逆否命题是“若一个整数不是偶数，则它不能被 $4$ 整除”，这与原命题等价，也是真的。

还有一种常见错误，是把 $P\Rightarrow Q$ 的逆否写成 $\neg P\Rightarrow\neg Q$。一个稳妥的口头检查是：先交换前后，再分别否定。交换后得到 $Q\Rightarrow P$，再否定两端，才是 $\neg Q\Rightarrow\neg P$。

反证法：让错误假设撞上不可能

反证法要证明命题 $R$，先暂时假设它不成立，也就是接受 $\neg R$。如果这个假设与题目的其他条件一起必然推出矛盾，那么 $\neg R$ 就不可能为真，只能留下 $R$。

逻辑骨架可以写成：

其中 $\bot$ 表示矛盾。因为 $\neg R$ 会导向不可能，$\neg R$ 为假，所以 $R$ 为真。

矛盾从哪里来

初学反证法时，最难的并不是“先假设相反”，而是接下来往哪里推。比较可靠的办法是查看反面假设新送给了你什么结构。

• 反设“某个最大对象存在”，你就得到一个名为 $M$ 的对象，以及“其他对象都不超过 $M$”的性质；接着尝试造出更大的对象。
• 反设“某数是有理数”，你就得到一个整数分数；接着考虑最简表示、整除性与奇偶性。
• 反设“某类对象只有有限多个”，你就能把它们全部列出；接着构造一个逃出列表的新对象。
• 反设“存在两个不同的解”，你就得到两个同时满足同一条件的对象；接着尝试推出它们其实相等。

所以，矛盾不是凭空等来的。我们通常根据反面假设的关键词，专门设计一个会击中它的对象或等式。

一份完整的反证结构

例题：整数没有最大的一个

命题：不存在最大的整数。

为什么选反证？“不存在”没有一个对象可供直接操作，反面“存在最大的整数”却会给我们一个具体的 $M$。一旦拿到 $M$，最自然的构造就是 $M+1$，因为它既保留整数身份，又专门破坏“最大”。

这类证明的构造常常只有一步，但那一步很有针对性。若假设声称“已经到顶”，就往上加一点；若假设声称“已经最小”，就尝试缩小一点。

逆否与反证怎样区分

两种方法都可能从否定开始，但任务并不相同。

• 证明 $P\Rightarrow Q$ 的逆否命题时，假设 $\neg Q$，目标是推出 $\neg P$。
• 用反证法证明 $P\Rightarrow Q$ 时，假设整个条件命题失败，也就是同时假设 $P$ 与 $\neg Q$，目标是推出矛盾。

写成符号就是：

它们在经典逻辑中都能证明原条件命题，但证明过程中持有的假设不同。写作时明确说出方法和假设，读者就不会在中途猜方向。

为什么 $\sqrt2$ 不是有理数

这道经典题很适合学习“如何构造矛盾”，因为矛盾不是算到一半偶然出现的，而是在反设时就已经埋好了位置。

目标是“$\sqrt2$ 不是有理数”。它的反面“$\sqrt2$ 是有理数”允许我们把 写成整数之比。可分数表示有很多种，例如 ；如果最后只推出分子、分母都是偶数，这对任意分数表示并不矛盾。于是我们在一开始就选择，让“分子分母还有公因数”成为可以击中的矛盾点。

先准备一个奇偶性事实

前面已经证明：若整数 $n^2$ 是偶数，则 $n$ 是偶数。这个事实会用两次，分别把 $p^2$ 和 $q^2$ 的偶性传回 $p$ 和 。

完整证明

每一步为什么不能省

“取最简分数”不能省。若没有这项条件，推出 $p,q$ 同为偶数只说明当前表示还能约分，并不矛盾。

从 $p^2$ 偶推出 $p$ 偶也不能只写“显然”。这里使用了一个已经证明的命题，而那个命题恰好由逆否法得到。证明常常这样搭积木：先证明一个小引理，再在主证明里清楚地使用它。

最后，矛盾必须写完整：一边是“$p,q$ 没有大于 $1$ 的公因数”，另一边是“$2$ 同时整除 $p,q$”。只写“所以矛盾”会把最关键的逻辑连接藏起来。

存在性：先回答“有没有”

存在命题的标准形式是

它只要求至少有一个 $D$ 中的对象满足 $P$。对象可以有很多个，也可以只有一个；仅从存在性还看不出来。

构造性证明

最直接的存在性证明，是亲手给出一个对象，再核对它的性质。

命题：存在一个偶素数。

取 $x=2$。因为 $2=2\cdot1$，它是偶数；又因为 $2>1$ 且正因数只有 $1$ 和 $2$，它是素数。因此偶素数确实存在。

这个证明很短，却包含两个不同动作：给出对象，验证性质。只写“答案是 $2$”还不算完整证明，因为读者需要看到 $2$ 同时满足“偶数”和“素数”两项要求。

构造不一定意味着猜数。对象也可以来自公式、集合运算或算法。例如要证明“对每个实数 $a$，存在实数 $x$ 使 $x-a=0$”，题目中的等式已经提示我们取 $x=a$。

非构造性证明

有时可以证明某种对象一定存在，却不确定当前证明的哪一个候选对象满足条件。

命题：存在无理数 $a,b$，使 $a^b$ 是有理数。

先考虑正实数

数 $c$ 不是有理数，就是无理数。下面分两种互相覆盖的情况。

这个证明没有判断 $c$ 到底属于哪一类，因此没有在证明结束时锁定同一对具体数字。它仍然有效，因为无论 $c$ 落在哪一类，至少有一对数可以工作。

唯一性：再回答“会不会有两个”

“存在唯一的 $x$ 满足 $P(x)$”常记为

这句话实际上打包了两项结论：

以及

第一项保证“至少一个”，第二项保证“至多一个”。两项合在一起，才是“恰好一个”。

唯一性证明的常用动作

要证明至多一个，不必先猜哪一个对象才是正确答案。任取两个满足条件的对象 $a,b$，然后利用它们共同满足的性质，证明 $a=b$ 即可。

例题：线性方程的解存在且唯一

命题：设 $u,v$ 是实数且 $u\ne0$。方程

有唯一实数解。

这个目标必须分两段。先造出一个解，证明“有”；再让任意两个解相遇，证明“只有一个”。

这里也能看出条件 $u\ne0$ 为什么必要。若 $u=0,v=0$，每个实数都是解；若 $u=0,v\ne0$，一个解也没有。题目中的条件不是装饰，它同时支撑了构造中的除法和唯一性中的消去。

“唯一”不等于“我只找到一个”

找到 $x_0$ 只能证明存在。也许还有另一个 $x_1$ 同样满足条件，只是我们暂时没看见。唯一性必须排除这种可能。反过来，证明“任意两个候选都相等”只说明至多一个，也不能保证候选真的存在。

这两个半边可以用一句对账问题检查：

• 我有没有展示至少一个满足条件的对象？
• 我有没有证明任意两个满足条件的对象必定相同？

只有两个答案都是“有”，存在唯一性证明才完成。

素数为什么不可能只有有限多个

“素数有无限多个”看起来很难直接证明，因为我们不可能把无限多个素数逐一列完。它的否定却非常具体：如果素数只有有限多个，那就能把全部素数写成一张完整清单。反证法正好能利用这张清单。

构造之前先想目的

假设全部素数是

要推翻这张清单，我们想造一个正整数，它不被清单中的任何素数整除。怎样同时避开所有 $p_i$？先把它们相乘，得到一个能被每个 $p_i$ 整除的数，再加 $1$。于是构造

“乘积加 $1$”不是灵光一现的装饰：乘积负责同时对齐所有旧素数，加 $1$ 负责让除以每个旧素数时都余 $1$。

完整证明

证明中用到的“小事实”也能快速说明：若整数 $N>1$ 本身不是素数，就在它大于 $1$ 的正因数中取最小的一个 $q$。若 $q$ 还是合数，它还能分成两个都比 $q$ 小且大于 $1$ 的因数，其中一个也整除 $N$，这与 最小矛盾。因此 必是素数。

最容易误读的一步

证明没有声称 $N$ 一定是素数。比如从一些素数的乘积加 $1$ 得到的数可能是合数。我们真正需要的是：$N>1$，所以它至少有一个素因子；而这个素因子不在旧清单里。只要出现一个新素因子，有限清单就已经被推翻。

举一个小规模演示。若暂时列出 $2,3,5$，则

这里恰好得到新素数 $31$。这个例子帮助我们看懂构造，却不是一般证明；一般证明依靠的是“余数恒为 $1$”和“$N$ 有素因子”，不是一次具体计算。

证明方法怎样选择

同一道题有时能用多种方法。选择方法不是猜标准答案，而是比较哪一种写法能最快接上定义，并让读者清楚看到主线。

草稿阶段可以这样试

若目标是条件命题，先在草稿上并排写三行：

然后把每个符号换回题目语言。哪一行最容易进入定义，通常就是更好的入口。

例如，“若 $n^2+1$ 是偶数，则 $n$ 是奇数”的逆否命题是“若 $n$ 是偶数，则 $n^2+1$ 是奇数”。后者只需写 $n=2k$，一行计算就能完成，显然比围着原结论硬推更自然。

成稿要像一段解释

正确证明还需要让人读懂。可以用下面四项自检。

1. 开头交代路线，尤其在使用逆否、分类或反证时。
2. 推理按发生顺序书写，不把关键依据放到结论之后补说。
3. 公式之间加入完整句子，说明这次变形得到了什么、下一步为什么可用。
4. 结尾明确回到原目标，不让读者自己猜“这些计算究竟证明了哪句话”。

证明不是一串孤立算式。式子负责压缩计算，文字负责说明逻辑。两者配合，读者才能检查每一步，也能学会这一步是怎样想到的。

常见误区与修正

把逆命题当作逆否命题

要证明 $P\Rightarrow Q$，却去证明 $Q\Rightarrow P$，方向已经变了。修正办法是每次都做“交换后否定”：逆否命题必须从 $\neg Q$ 出发，抵达 $\neg P$。

量词只改一半

“每个对象都有性质”的否定是“至少有一个对象没有性质”，而不是“每个对象都没有性质”。反证开始前，把否定句完整写成自然语言，往往比盯着符号更不容易错。

只得到奇怪结果，没有得到矛盾

“$x$ 很大”“结果不好看”“这似乎不合理”都不是矛盾。有效矛盾必须能指出两端，例如 $p,q$ 互素却又同被 $2$ 整除，或 $M$ 最大却存在 $M+1>M$。

在反证中偷偷使用结论

反证法能使用题目条件、定义和已经证明的事实，不能因为“反正最后结论是真的”就提前使用结论。检查每一步依据，若某一步只能由目标结论得到，证明就是循环的。

证明存在时只报答案

给出候选对象后还要验证全部性质。题目说“存在一个同时满足 $A$ 与 $B$ 的对象”，证明就必须分别核对 $A$ 与 $B$。

证明唯一时只找到一个

“我找到一个”排除不了第二个。修正办法是另起一段：设 $a,b$ 都满足条件，然后证明 $a=b$。

用若干例子代替无限范围

检查 $n=1,2,3$ 能帮助发现规律，却不能证明对所有正整数都成立。这个误区也正好把我们带到下一章：当命题是一整族 $P(1),P(2),P(3),\ldots$ 时，需要一种能覆盖无限多个整数的推进方法。

练习与参考证明

下面的练习不只要求得到结论，也要求在第一句话说明为什么选择该方法。

练习一：用逆否处理奇偶性

证明：若整数 $n$ 满足 $3n+2$ 是偶数，则 $n$ 是偶数。

练习二：不存在最小正有理数

证明：正有理数中没有最小的一个。

练习三：推广无理数证明

证明：$\sqrt3$ 是无理数。可以使用事实：若 $3\mid m^2$，则 $3\mid m$。

练习四：存在唯一解

证明：对每个实数 $a$，存在唯一实数 $x$，使得 $x-a=0$。

练习五：找出素数证明中的错误

有人写道：“把前 $k$ 个素数相乘再加 $1$，得到的数一定是素数，所以总能得到下一个素数。”这句话哪里过强？正确结论是什么？

练习六：否定一个存在唯一命题

把下面命题的否定写成不含“并非”的形式：

从换入口到归纳推进

这一章的几种方法看似分散，实际都在训练同一个动作：先看清目标的逻辑形状，再把它改写成能操作的任务。

逆否证明把 $P\Rightarrow Q$ 换成等价的 $\neg Q\Rightarrow\neg P$；反证法把目标失败的情形具体化，再让它撞上定义或已知事实；存在唯一性把一句话拆成“至少一个”和“至多一个”。方法本身不替我们完成推理，它只把真正需要完成的工作摆到桌面上。

下一章要处理的目标是

全部成立。逐个检查永远检查不完，数学归纳法会再次进行“目标拆解”：先证明起点，再证明任意一项成立都能推动下一项成立。到那时，仍然要先说明路线、准确写出假设，并让每一步有明确依据——只是这一次，证明的入口会从“否定目标”变成“建立一条可以不断向前传递的链”。

并且 $p$ 与 $q$ 没有大于 $1$ 的公因数，也就是这个分数已经最简。

那么 $a,b$ 都是无理数，而 $a^b=c$ 是有理数。

有定义。代入可得

所以至少有一个实数解。

所以 $3n+2$ 是奇数。逆否命题成立，因此若 $3n+2$ 是偶数，则 $n$ 是偶数。

这与 $r$ 是最小正有理数矛盾。因此正有理数中没有最小的一个。

因此 $3\mid p^2$，从而 $3\mid p$。写 $p=3r$，代回得到

所以

于是 $3\mid q^2$，进而 $3\mid q$。这说明 $p,q$ 同有公因数 $3$，与分数最简矛盾。因此 $\sqrt3$ 是无理数。

补充说明所用事实：整数除以 $3$ 的余数只有 $0,1,2$，平方后的余数分别是 $0,1,1$。所以平方能被 $3$ 整除时，原数只能余 $0$，也就能被 $3$ 整除。

且

因此 $u-a=v-a$，两边同时加 $a$，得到 $u=v$。任意两个解都相同，所以解至多一个。结合存在性，满足条件的实数 $x$ 唯一。

这也再次说明，存在唯一性本来就是“至少一个”与“至多一个”的合并。