反证法 — 先假设它不成立,再逼出矛盾
这一章讲三件事: 从正面推不动的结论,怎么换个方向拿下; 这套办法的两个步骤,以及为什么它看着像「投机取巧」其实不是; 还有一处很少见的东西——中文版编者当场指出了原书的一步不严密。
它在全书链条里的位置: 这是第 16、17 章的工具。 那两章要证的是「做不到」和「写不出来」,而这类结论只能反着证。 需要的基础: 知道「命题非真即假」(第 02 章)就够了。
1. 先看现象:为什么不存在「最大的整数」
这一节先用一道三行就完的题,把这套办法的形状亮出来。
问:为什么不存在最大的整数?1
① 先假设它存在,把这个「最大的整数」叫作 M
② 那么 M + 1 也是整数,而且比 M 大
③ 于是「M 是最大的整数」和「M 不是最大的整数」同时成立 —— 这不可能
→ 所以最初那个假设是错的:不存在最大的整数
图说:整条论证里没有一步是在直接找「最大的整数」。
它做的是把假设推到自相矛盾,然后回头否定假设。
这就是反证法。 请注意第 ③ 步那个词:两句互相否定的话同时成立,这叫矛盾2。
为什么「矛盾」就能否定假设? 因为一个命题非真即假,没有第三种(第 02 章)。 假设导出了不可能的事,那假设本身就只能是假的3。
2. 反证法的两步
这一节把上一节的形状写成可以照做的两步4:
步骤 1:假设「要证的那句话的否定」成立
步骤 2:从这个假设出发往下推,推出一个矛盾
→ 结论:那个假设是错的,所以原来要证的那句话成立
因为最后推出的是荒谬的结果,所以它有时也叫归谬法5。
这套办法难在哪?难在它不直接证明命题6—— 你全程都在拿一句你认为是错的话往下推,推得越顺、离结论越近。 这和平时「从已知一步步推到结论」的方向是反的。
3. 先说清楚什么是质数
这一节是下一节的准备,一句话就够。
质数是「只能被 1 和它本身整除的、大于 1 的整数」7。
| 数 | 是不是质数 | 为什么 |
|---|---|---|
| 1 | 不是 | 质数必须大于 1 |
| 2 | 是 | 只能被 1 和 2 整除 |
| 3 | 是 | 只能被 1 和 3 整除 |
| 4 | 不是 | 除了 1 和 4,还能被 2 整除 |
从小到大排开就是:2、3、5、7、11、13、17、19、23……8
4. 主走查:质数有无穷多个
这一节是全章的主走查。
要证的是:质数有无穷多个。 按第 2 节的两步来9:
步骤 1:假设它的否定成立——假设质数只有有限个。 那么就可以把它们全部列出来:2、3、5、7、……、P(P 是最大的那个)。
步骤 2:从这个假设出发,造一个数。 把所有质数乘起来,再加 1,把结果叫 Q10:
Q = 2 × 3 × 5 × 7 × … × P + 1
为了看清这一步在干什么,我们拿一个小例子走一遍 (下面这几个数是我们为演示编的:假装质数只有 2、3、5、7 这四个):
假设质数只有:2、3、5、7
全部乘起来: 2 × 3 × 5 × 7 = 210
再加 1: Q = 211
211 ÷ 2 = 105 …… 余 1
211 ÷ 3 = 70 …… 余 1
211 ÷ 5 = 42 …… 余 1
211 ÷ 7 = 30 …… 余 1
图说:关键就在这一列余数上 —— 全是 1,一个都除不尽。
这不是巧合:Q 比「所有质数的积」正好多 1,
而那个积能被列表里每一个质数整除,所以 Q 除以它们必定余 1。
于是两句话同时成立了11:
| 说法 | 理由 |
|---|---|
| Q 不是质数 | Q 比列表里所有质数都大,而列表号称已经列全了所有质数 |
| Q 是质数 | Q 除以列表里任何一个数都除不尽 |
矛盾。所以最初那个假设——「质数只有有限个」——是错的。 质数有无穷多个,证完了12。主走查走完了。
原书在这里挂了一条脚注:这个证法参考的是欧几里得的论证13。
5. 一条必须守住的规矩
这一节回答:既然前提本来就是假的,中间是不是可以马虎点。
不可以。 原书专门写了一小节讲这件事: 反证法从一个错误的假设出发,但到引出矛盾为止的论证过程本身必须正确14。
理由很直接:如果中途推错了,那么最后那个矛盾可能是你自己推错造成的, 而不是假设造成的——这时你什么也没证明。
原书还老实说了一句:从错误的假设出发、还要想着推翻这个假设并进行正确的论证, 这确实不太容易15。
6. 三个声音:编者当场指出原书这一步不严密
这一节另起一处走查,而且是全书唯一一处「书自己被挑错」。
第 4 节那张表的第二行——「Q 除不尽任何一个,所以 Q 是质数」——其实有漏洞。
中文版编者在这里加了一条注,原话的意思是: Q 除以 2、3、5、7、……、P 中的任何一个都余 1,并不能说明 Q 只能被 1 和它本身整除; 也有可能 Q 能被一个比 P 大、比 Q 小的数整除16。
这个补丁值得看懂:
原书的论证: Q 除不尽 2、3、5、7…P ⇒ Q 是质数 ← 这一步跳了
编者的质疑: 万一 Q 能被某个比 P 大的数整除呢?
真正成立的: Q 除不尽 2、3、5、7…P
⇒ Q 的质因数里没有一个在列表中
⇒ 存在一个不在列表里的质数(要么 Q 自己,要么它的某个因数)
⇒ 列表没列全 —— 同样与假设矛盾
图说:结论不变,但中间的台阶要多踩一级。
编者指出的正是原书跳掉的那一级。
注意这里出现了三个不同的声音,读的时候必须分开:
| 声音 | 这一章里的例子 |
|---|---|
| 原作者 | 「Q 除不尽任何一个,所以 Q 是质数」 |
| 中文版编者 | 「此处论证不严密」那条脚注 |
| 我们 | 上面那张图里补的那一级台阶,以及这张表本身 |
这一处也正好印证上一节:论证过程本身必须正确。 原书讲完这条规矩,自己就在下一页被编者抓到了一次——这不是黑材料, 这恰恰说明这条规矩有多难守。
7. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 不存在最大的整数 | 给了完整走查,三行 |
| 质数有无穷多个 | 给了完整走查,并注明参考欧几里得 |
| 论证过程必须正确 | 给了理由:否则得不出「因为假设错所以矛盾」 |
| 「Q 是质数」这一步 | 原作者跳了一级,中文版编者当场指出 |
判断(我们的,不是书里的):反证法在写代码时的对应物, 是「假设这段代码是对的,那么这个现象就不该出现」。 排查故障时你常常这么想:如果那份结果真的被存下来复用了, 屏幕上那行「重新算了一遍」就不该每次都冒出来;它冒出来了,所以根本没复用。 这就是反证法的日常形态。 它的价值在于:你不需要先知道正确答案是什么,只需要找出一处不该出现的东西。 如果错,会错在: 现实里的「矛盾」常常不是真矛盾,而是你的前提没列全 (比如还有另一条路也会让那行字冒出来)。判据是: 你能不能说清「除了这一种可能,还有没有别的解释」。
这一章的边界:
- 原书对「矛盾」只给了一句定义(命题 P 和它的否定 ¬P 都成立),没有展开;
- 质数无穷的证明有一步不严密,靠中文版编者的注补上——这一处我们照实转述了;
- 没有讲反证法和逆否命题的关系(第 04 章那条);两者是近亲但不是一回事;
- 没有讲什么时候不该用反证法(有些场合直接证更短、更清楚);
- 原书这一章后面还有可数与停机问题,分别在我们的第 16、17 章。
8. 可带走的
- 反证法两步:先假设「要证的话的否定」成立,再从它推出矛盾;
- 矛盾 = 一句话和它的否定同时成立;因为命题非真即假,所以这不可能;
- 不存在最大的整数:假设最大的是 M,M + 1 立刻更大——三行就完;
- 质数是「只能被 1 和自身整除、且大于 1 的整数」;1 不是质数;
- 质数有无穷多个:把假设中的全部质数乘起来加 1,得到的数除谁都余 1;
- 拿 2、3、5、7 走一遍就是 211,它对 2、3、5、7 全部余 1;
- 前提可以是错的,中间的每一步不能错——否则矛盾可能是自己推出来的;
- 中文版编者在这里指出了原书一步不严密:「除不尽列表里的数」推不出「它是质数」;
- 读书时要分清三个声音:原作者、编者、拆解者(我们)。
9. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 反证法的两步 | 第8章 不可解问题 | text/13-ch08.txt:30(搜「所谓反证法」) · :35(搜「一言以蔽之」) · :38(搜「归谬法」) |
| 矛盾的定义 | 第8章 不可解问题 | text/13-ch08.txt:37(搜「矛盾就是」) |
| 不存在最大的整数 | 第8章 不可解问题 | text/13-ch08.txt:48(搜「假设存在」) · :66(搜「这就产生了矛盾」) |
| 质数的定义 | 第8章 不可解问题 | text/13-ch08.txt:75(搜「质数是」) · :80(搜「2, 3, 5, 7, 11, 13, 17, 19, 23」) |
| 质数无穷的证明 | 第8章 不可解问题 | text/13-ch08.txt:93(搜「用反证法证明质数是无穷的」) · :104(搜「所有质数的积」) · :111(搜「余数都为 1」) · :115(搜「通过反证法证明了」) |
| 编者注:这一步不严密 | 第8章 不可解问题 | text/13-ch08.txt:133(搜「此处论证不严密」) · :135(搜「参考欧几里得」) |
| 反证法的注意事项 | 第8章 不可解问题 | text/13-ch08.txt:120(搜「必须先假设错误的命题成立」) · :123(搜「这确实不太容易呀」) |