Lecture 2: Proof Techniques II（证明技巧进阶）

目录 · ← l2 · l4 →

Lecture 2: Proof Techniques II（证明技巧进阶）

概述

上一讲（L01）我们把命题逻辑的真值表语言建立起来，并学会了最基础的直接证明 (Direct Proof)：要证 $P \Rightarrow Q$，就假设 $P$ 成立，一路推导出 $Q$。但很多命题用直接证明几乎无从下手——比如”若 $n$ 是奇数，则 $n$ 的每个因子都是奇数”，假设了”$n$ 是奇数”之后我们手上其实什么结构都没有，无法往下走。

本讲补齐证明工具箱的第二层：逆否证明 (Proof by Contraposition)、反证法 (Proof by Contradiction)、分情形证明 (Proof by Cases)，并顺带引入本课程最常用的计数工具之一 鸽笼原理 (Pigeonhole Principle)。最后官方 Note 3 用一整节讨论写证明时的常见错误（Common Errors），这批”错误证明”是本讲最有价值的部分：它们示范的不是怎么证对，而是怎么一眼看穿哪里证错了。

至此，L00–L03 四讲构成完整的”证明工具箱”：直接证明 → 命题逻辑 → 逆否/反证/分情形 → 归纳法。后续 L04 起的数论、L09 起的图论、L12 的可数性、L13 的停机问题，全部依赖这一讲的技巧。

核心概念的直观解释

概念一：逆否证明 (Proof by Contraposition)

• 定义：设待证命题为 $P \Rightarrow Q$。逆否命题 (contrapositive) 是 $\neg Q \Rightarrow \neg P$。逆否证明的做法就是：假设 $\neg Q$ 成立，推导出 $\neg P$ 成立，从而完成对 $P \Rightarrow Q$ 的证明。
• 直观解释（”它是什么意思？”）：把蕴含 $P \Rightarrow Q$ 想象成一条单行道——”凡是走 $P$ 这条路的人都必然到 $Q$”。逆否说的是”凡是没到 $Q$ 的人，一定没走 $P$”，这显然是同一件事的换一种说法。它不是在说”没走 $P$ 的人一定没到 $Q$”（那是否命题 (inverse) $\neg P \Rightarrow \neg Q$，与原命题不等价）。
• 为什么合法：因为 $P \Rightarrow Q$ 与 $\neg Q \Rightarrow \neg P$ 是逻辑等价的（真值表完全相同），所以证明了后者就等于证明了前者。这里完全没有用到矛盾，只是在陈述一件等价的事实——这一点是本讲最容易被混淆的地方，后面会专门展开。
• 具体示例：命题”若 $n$ 是奇数，则 $n+1$ 是偶数”。直接证：设 $n = 2m+1$，则 $n+1 = 2m+2 = 2(m+1)$，偶数 ✓。逆否证：设 $n+1$ 不是偶数（即 $n+1$ 是奇数，$n+1 = 2t+1$），则 $n = 2t$，是偶数，即 $n$ 不是奇数 ✓。两条路都通，但第二条路只用了”奇偶的定义”，不需要对 $n$ 做任何化简。

概念二：鸽笼原理 (Pigeonhole Principle)

• 定义：设 $n, k$ 为正整数。把 $n$ 个物体放进 $k$ 个盒子。若 $n > k$，则至少有一个盒子里装了多于一个物体。
• 直观解释：$n$ 只鸽子要住进 $k$ 个鸽笼，笼子比鸽子少，必然有两只鸽子被迫挤在同一个笼子里。名字就来自这个画面（”pigeon” + “hole”）。
• 关键性质（务必记住）：这条定理的结论与物体怎么摆放完全无关（regardless of the configuration）。无论摆放方案多么刁钻、多么”刻意避开重复”，只要 $n>k$，重复就必然存在。正是这一点让它能给出反直觉的结论：我们不需要知道任何一只鸽子的具体位置，就能断言重复存在。
• 具体示例：13 个人分配到 12 个月份（把”人”当鸽子、”出生月份”当盒子）。$13 > 12$，所以至少有两个人同月出生。我们完全不知道是哪两个人、是哪个月，但存在性是确定的。
• 加强形式（实用版）：把 $n$ 个物体放进 $k$ 个盒子，则至少有一个盒子装有 $\lceil n/k \rceil$ 个或更多物体。例如 $n=13,k=12$ 给出 $\lceil 13/12\rceil = 2$；$n=10,k=3$ 给出 $\lceil 10/3 \rceil = 4$（3 个盒子装 10 个东西，必有一个装 $\ge 4$ 个）。这个形式在很多题目里比原始版本好用得多。

概念三：反证法 (Proof by Contradiction / reductio ad absurdum)

• 定义：要证命题 $P$。做法是假设 $\neg P$，从 $\neg P$ 出发经过合法推导得到某个 $R$ 又得到 $\neg R$，即推出矛盾 $R \wedge \neg R$，从而断定 $P$ 必为真。
• 直观解释：反证法是”把命题暂时当成假的，看看世界会烂成什么样”。如果假设它为假会让整个逻辑体系崩溃（同时推出 $R$ 和 $\neg R$），那只能是假设错了，命题为真。拉丁语 reductio ad absurdum 直译是”归约到荒谬”。
• 形式化依据：反证法证明的是 $\neg P \Rightarrow (\neg R \wedge R)$。而 $\neg R \wedge R \equiv \text{False}$，所以 $\neg P \Rightarrow \text{False}$。这个蕴含式的逆否命题是 $\text{True} \Rightarrow P$，即 $P$ 为真。注意这里用到了一条在 L01 学过的逻辑定律：命题非真即假，不存在第三种可能（排中律 / law of excluded middle）。这正是反证法”黑白分明”世界观的来源。
• 具体示例：用反证法证明”$\sqrt{2}$ 不是有理数”（见后文完整证明）。假设它是有理数，写成分式 $\sqrt 2 = a/b$（最简），能推出 $a,b$ 都为偶数，与”最简”直接打架。

概念四：引理 (Lemma)

• 定义：在一项较大证明中充当辅助工具的、独立的子命题，称为引理。引理本身也需要证明。
• 直观解释：引理之于定理，就像子程序 (subroutine) 之于主程序。一个长证明如果一次写完，读者读到最后已经忘了前面假设了什么；拆成若干命名清晰的引理，每块都能单独检查、单独复用。
• 具体示例：”若 $a^2$ 是偶数，则 $a$ 是偶数”就是这样一个引理——它在”$\sqrt 2$ 是无理数”的证明里被用了两次，本身也值得单独记住。设计引理时应当尽量做得通用（general），这样才可能被其他证明重复使用。
• 定理与引理的分界：并不清晰。通常一条命题是”定理”还是”引理”，取决于作者想让外界”导出”哪一条——定理是面向外部世界的成果，引理是局部使用的工具。但也有引理比它服务的定理更出名（例如可计算性理论里的 Pumping Lemma）。

概念五：分情形证明 (Proof by Cases / Case Analysis)

• 定义：当无法直接判断几种可能情形中哪一种成立、但确知至少有一种成立时，可以分别对每一种情形证明同一个结论；所有情形都证完，总体结论即成立。
• 直观解释：就像”不知道今天是不是周末，那就分’是工作日’和’是休息日’两种情形各写一份计划”——只要两种情形的计划都可行，无论今天实际是哪天，计划都能用。
• 两个必要条件（极易出错）：
  • 穷尽 (exhaustive)：所有情形合起来必须覆盖全部可能。遗漏一种情形，证明就漏了一个洞。
  • 互斥 (mutually exclusive)：通常要求情形之间不重叠，否则同一个对象被证两遍——这不算错，只是啰嗦；但若重叠部分用了互相矛盾的假设，就会出问题。最干净的做法是让情形构成一个划分 (partition)。
• 具体示例：证明”对任意整数 $m$，$m(m+1)$ 是偶数”。分两种情形：$m$ 是偶数 → $m(m+1)$ 含因子 $m$，偶；$m$ 是奇数 → 则 $m+1$ 是偶数，$m(m+1)$ 含因子 $m+1$，偶。两种情形穷尽且互斥（按奇偶二分），结论成立。

概念六：非构造性证明 (Non-constructive Proof)

• 定义：证明了”某个对象 $X$ 存在”，但没有（也无法）明确指出 $X$ 究竟是哪一个的证明。
• 直观解释：这听起来像作弊——”我知道那里有一个东西，但我不告诉你是啥”。但在数学上它完全合法：存在量词 $\exists$ 只要求”至少有一个”，并不要求证据被显式给出。本讲的分情形证明就会产出一个著名的非构造性存在性证明。
• 具体示例：定理”存在无理数 $x,y$ 使得 $x^y$ 是有理数”。证明把所有可能情形都覆盖了，但读者走到最后仍不知道 $x,y$ 到底是 $\sqrt 2, \sqrt 2$ 还是 $\sqrt 2^{\sqrt 2}, \sqrt 2$。有趣的是，事后我们知道 $\sqrt 2^{\sqrt 2} \approx 1.6325$ 确实是无理数（Gelfond–Schneider 定理，远超本课程范围），所以真正成立的是情形 (b)；但证明本身并不需要知道这一点。

完整证明与推导（核心）

一、逆否证明为什么合法（逻辑地基）

定理 2.1（逆否等价）：对任意命题 $P, Q$，有 $P \Rightarrow Q \;\equiv\; \neg Q \Rightarrow \neg P$。

证明策略：用真值表直接枚举。这是”元层面”的陈述，其证明只能是穷举所有取值组合。

逐步推导：把 $P,Q$ 的所有真假组合列出，分别计算 $P\Rightarrow Q$ 与 $\neg Q \Rightarrow \neg P$ 的真值。

 P     Q    |  P=>Q  |  ~Q  |  ~P  |  ~Q=>~P  |  两列是否相同
------------+--------+------+------+----------+----------------
 T     T    |   T    |   F  |   F  |    T     |     同
 T     F    |   F    |   T  |   F  |    F     |     同
 F     T    |   T    |   F  |   T  |    T     |     同
 F     F    |   T    |   T  |   T  |    T     |     同

第 2 列与第 6 列逐行相同，故两个命题逻辑等价。$\blacksquare$

【证明机制解说】：注意第 1、2 行——$P$ 为真时，$P\Rightarrow Q$ 的真假完全由 $Q$ 决定；而逆否命题在 $\neg Q$ 为真（即第 2 行）时正确地把 $P$ 判为假。换句话说，逆否命题把”$P$ 真 $Q$ 假”这个唯一的反例场景，翻译成了”$\neg Q$ 真 $\neg P$ 假”这同一个场景。两个命题共享同一个反例集合，因此同真同假。

必须区分：逆否命题 vs. 逆命题 vs. 否命题

一个具体例子说明逆命题为什么不等价：设 $P$ 是”$n$ 能被 4 整除”，$Q$ 是”$n$ 能被 2 整除”。原命题成立；逆命题”$n$ 能被 2 整除则 $n$ 能被 4 整除”在 $n=6$ 处失败。

逆否证明与反证法的严格区别（本讲最重要的一条）

这是一个高频混淆点，必须讲透。

所以：逆否证明不是反证法的一个特例，它是”换一条等价的路走”，而反证法是”把假设推向自我毁灭”。 判断标准很简单：如果你的证明最后写下的是”这与 $\neg Q$ 的假设矛盾”或”这证明了 $\neg P$”，那是逆否证明；如果你最后写下的是”$R$ 且 $\neg R$，矛盾”，那才是反证法。

二、逆否证明实战：奇数与因子

定理 2.2（官方 Note 3 的 Theorem 3.1）：设 $n$ 为正整数，$d \mid n$。若 $n$ 为奇数，则 $d$ 为奇数。

证明策略：用逆否证明。理由是：直接证明只能假设”$n$ 是奇数”，而 $n$ 是奇数这件事对因子 $d$ 没有任何可操作的代数结构（$n = 2m+1$，$d \mid n$ 只给出 $n = d\ell$，无从下手）。反过来假设”$d$ 是偶数”则立刻得到 $d = 2k$ 这个可以代入的表达式。当一个命题的否定假设能给出更强的代数结构时，就选逆否。

逐步推导：

1. 先写出逆否命题：$\neg Q$ 是”$d$ 不是奇数”即”$d$ 是偶数”；$\neg P$ 是”$n$ 不是奇数”即”$n$ 是偶数”。故逆否命题为：若 $d$ 是偶数，则 $n$ 是偶数。（这一步必须在证明开头显式做出来，否则读者不知道你在证什么。）
2. 采用逆否证明：假设 $d$ 是偶数。
3. 由”偶数”的定义，存在整数 $k$ 使 $d = 2k$。
4. 由 $d \mid n$ 的定义，存在整数 $\ell$ 使 $n = d\ell$。
5. 把 (3) 代入 (4)：$n = d\ell = (2k)\ell = 2(k\ell)$。
6. 因整数对乘法封闭，$k\ell \in \mathbb{Z}$，故 $n = 2(k\ell)$ 满足”偶数”的定义，即 $n$ 是偶数。
7. 我们已从 $\neg Q$ 推出 $\neg P$。由逆否等价（定理 2.1），原命题 $P\Rightarrow Q$ 成立。$\blacksquare$

【证明机制解说】：整个证明的”灵光一现”在第 3 步——把”$d$ 是偶数”翻译成一个可以代入的等式 $d=2k$。这之后全是代换与封闭性，几乎不需要思考。这也解释了为什么逆否方向更好走：偶数条件天然携带一个因子 2，可以乘进 $d\ell$ 里；而”$n$ 是奇数”携带的是 $n = 2m+1$ 这个加 1 的式子，因子 $d$ 藏在 $n$ 的分解中，加 1 结构对它毫无帮助。

顺带得到的更强结论：把上述论证中”$2$”换成任意正整数 $t$，可得到”若 $t \mid n$ 则 $t \mid d$”——这正是”因子传递性”的雏形，在 L04 的模运算里会以”若 $a\equiv b \pmod m$ 且 $d\mid m$ 则 $a \equiv b \pmod d$”的形式再次出现。

三、鸽笼原理及其逆否证明

定理 2.3（鸽笼原理 Pigeonhole Principle，官方 Note 3 的 Theorem 3.2）：设 $n, k$ 为正整数。把 $n$ 个物体放入 $k$ 个盒子。若 $n > k$，则至少有一个盒子含有多个物体。

证明策略：用逆否证明。原因是：命题的结论是”至少有一个盒子有 $\ge 2$ 个物体”，这个存在性断言在直接证明中没有起点（你无法”假设 $n>k$ 然后指向某个盒子”）。而它的否定”每个盒子都至多含 1 个物体”是一个全称断言，非常方便利用——直接对物体总数计数即可。

逐步推导：

1. 写出逆否命题。$\neg Q$：没有任何盒子含多个物体，即每个盒子至多含 1 个物体。$\neg P$：物体数不多于盒子数，即 $n \le k$。故逆否命题为：”若每个盒子至多含 1 个物体，则 $n \le k$。”
2. 假设每个盒子至多含 1 个物体。
3. 设有 $k$ 个盒子 $B_1,\dots,B_k$，记盒子 $B_i$ 中的物体数为 $c_i$。由假设，$c_i \le 1$ 对每个 $i$ 成立。
4. 所有物体都在某个盒子里，故 $n = c_1 + c_2 + \cdots + c_k$。
5. 于是 $n = \sum_{i=1}^k c_i \le \sum_{i=1}^k 1 = k$，即 $n \le k$。
6. 由逆否等价，原命题成立：$n>k \Rightarrow$ 至少一个盒子含多个物体。$\blacksquare$

【证明机制解说】：整个证明只用了一步实质运算——第 5 步的求和上界。它的力量来自一个朴素事实：在”每盒至多 1 个”的约束下，容器能装下的物体总数有一个硬上界 $k$。当供给 $n$ 超过容量 $k$，约束必然被打破。注意这个论证对配置完全无感：无论怎么摆，第 3 步的 $c_i \le 1$ 和第 4 步的求和恒等式都成立。这就是”与配置无关”的技术含义。

应用一（官方例子）：旧金山的头发

• 建模：把旧金山居民看作”鸽子”，把”某人头上的头发根数”看作”盒子编号”。
• 已知数据：一个人头上的头发数平均约 $100000$，可以合理确定没有人的头发超过 $500000$ 根。于是可能的头发数只有 $0, 1, 2, \dots, 500000$ 共 $500001$ 个取值——这就是盒子数 $k = 500001$。
• 旧金山人口（截至 2024 年）超过 $800000$——这就是鸽子数 $n = 800000$。
• 因为 $800000 > 500001$，由鸽笼原理：旧金山至少有两个人的头发根数完全相同。
• 注意这个论证的”反直觉”之处：它完全没有告诉我们那个数字是多少、那两个人是谁。它只是断言重复必然存在。（脚本验算：$\lceil 800000/500001 \rceil = 2$，确认结论。）

应用二（补充）：13 个人的生日月份

• 建模：13 个人 = 13 只鸽子；12 个月份 = 12 个盒子。
• $13 > 12$，由鸽笼原理：至少有两个人的出生月份相同。
• 这不是概率陈述——不是”很可能”，而是必然。这是鸽笼原理最容易被误解的地方：它给出的是确定性结论，不需要任何独立性假设。概率方法要到 L14–L15 才登场。
• 加强形式给出更强结论：至少有一个月份含有 $\lceil 13/12 \rceil = 2$ 个人；若问 100 个人分到 9 个”盒子”，则至少有一个盒子含 $\lceil 100/9\rceil = 12$ 个人。

应用三（补充）：5 个整数中必有两个之差被 4 整除

• 任取 5 个整数 $a_1,\dots,a_5$。
• “盒子”= 模 4 的余数，只有 $4$ 个盒子：$0,1,2,3$。鸽子 $n=5>4=k$。
• 于是必有两个整数落在同一个余数盒子里，即 $a_i \equiv a_j \pmod 4$，从而 $4 \mid (a_i - a_j)$。
• 算例验算：取 $\{3, 11, 7, 19, 26\}$，模 4 余数依次为 $3,3,3,3,2$。前四个都落在盒子 3 中：$3-11=-8$、$3-7=-4$、$3-19=-16$、$11-7=4$、$11-19=-8$、$7-19=-12$，全部被 4 整除 ✓（脚本已核验）。

注意：鸽笼原理有一个”阈值”性质——$n > k$ 这个条件是不可省的。若 $n \le k$，则完全可以把物体一一分开摆放，使得每个盒子恰好至多 1 个。例如 $n=k=12$：12 个人可以分别出生在 12 个不同月份，没有重复。这就是”去掉 $n>k$ 条件命题失效”的反例。

四、反证法实战（一）：质数有无穷多个

定理 2.4（Euclid，官方 Note 3 的 Theorem 3.3）：质数有无穷多个。

证明策略：用反证法。为什么不用直接证明？因为”无穷多个”是一个否定性断言——等价于”不存在最大的质数”“不存在一个包含全部质数的有限列表”。要正面构造出无穷多个质数并逐一展示，是做不到的；但假设”只有有限多个”，我们手上就得到了一个有限的、可枚举的完整列表，而完整列表可以被”乘积加一”这个操作攻击。凡是要证明”某物不存在”（不存在最大的质数 / 不存在满足 $\sqrt 2 = a/b$ 的整数 $a,b$），反证法就是首选。

先陈述引理（Lemma 3.1）：每个大于 1 的自然数要么是质数，要么有质因子。

（官方把这个引理的证明推后到讲归纳法的 Note 4——事实上 Theorem 4.7”每个 $n>1$ 可写成质数之积”用强归纳证明后，本引理只是它的直接推论。见 L03 的思考题 Q3。）

逐步推导（主定理）：

1. 反证法：假设定理为假，即质数只有有限多个，设有 $k$ 个。
2. 于是可以把它们全部列举出来：$p_1, p_2, \dots, p_k$。（这一步是反证法的全部收益——”有限”意味着”可以写完”。）
3. 构造 $q := p_1 p_2 \cdots p_k + 1$，即”所有质数之积再加一”。
4. 断言 $q$ 不可能是质数。理由：$q = p_1p_2\cdots p_k + 1 > p_i$ 对每个 $i = 1,\dots,k$ 都成立（因为乘积 $p_1\cdots p_k \ge p_i$，加 1 后严格更大；注意 $k\ge 2$、$p_1 = 2$ 时乘积至少为 $2$）。所以 $q$ 严格大于列表中的每一个质数；而按假设这个列表已经包含了全部质数，因此 $q$ 不在其中，$q$ 不是质数。
5. 引用引理：$q > 1$ 且 $q$ 不是质数，故 $q$ 有质因子 $p$。把它记为断言 $R$。
6. 因为 $p_1,\dots,p_k$ 是全部质数，而 $p$ 是质数，所以 $p$ 必等于某个 $p_i$。
7. 于是 $p \mid p_i$，从而 $p$ 整除 $r := p_1p_2\cdots p_k$。
8. 又由第 5 步 $p \mid q$。由整除的线性性（L00 已证：$a\mid b$ 且 $a\mid c$ $\Rightarrow$ $a \mid (b-c)$），得 $p \mid (q - r)$。
9. 但 $q - r = (p_1p_2\cdots p_k + 1) - p_1p_2\cdots p_k = 1$。故 $p \mid 1$。
10. 一个整除 1 的正整数只能是 1，故 $p = 1$。但 1 不是质数——这与第 5 步”$p$ 是质数”（断言 $R$）直接冲突。这是 $\neg R$。
11. 于是 $R \wedge \neg R$ 成立，矛盾。故假设为假，质数有无穷多个。$\blacksquare$

【证明机制解说】：Euclid 这个证明的精髓在第 3 步的构造 $q = (\text{全部质数之积}) + 1$。加 1 是全部魔法所在：它保证 $q$ 除以列表中任何一个质数都余 1，因此 $q$ 的每一个质因子都不可能出现在那份”完整”的列表里。于是”完整列表”这个假设自我否定——列表既是完整的，又漏掉了 $p$。这正是反证法最漂亮的收束方式：不是我们构造出矛盾，而是被假设出来的对象自己拆掉了自己的地基。

重要澄清（高频误解）：$q$ 本身不一定是质数。脚本验算：

$k=6$ 时 $q$ 是合数，但证明依然完全有效：我们不需要 $q$ 是质数，只需要它有一个质因子，而 $59$ 确实不在列表 $\{2,3,5,7,11,13\}$ 中——矛盾照样成立。把”$q$ 是质数”当成证明的一部分，是学生最常见的错误之一。

五、反证法实战（二）：$\sqrt 2$ 是无理数（引理嵌套）

定理 2.5（官方 Note 3 的 Theorem 3.4）：$\sqrt{2}$ 是无理数。

证明策略：用反证法，并且嵌套一层引理。先说第二点：引理 2.6 本身也是一条蕴含式，”若 $a^2$ 偶则 $a$ 偶”。它最自然的证法是逆否（假设 $a$ 是奇数，写出 $a=2t+1$，则 $a^2 = 4t^2+4t+1$ 是奇数）。所以本定理的完整结构是：反证法（主）$\to$ 逆否证明（引理）——两种技巧上下叠放。这种”引理套在定理里、引理自己换一种技巧”的分层结构，是数学写作的标准做法，也是本讲最值得学习的形式。

引理 2.6（Lemma 3.2）：若 $a^2$ 是偶数，则 $a$ 是偶数。

引理 2.6 的逐步推导（逆否证明）：

1. 逆否命题：若 $a$ 不是偶数（即 $a$ 是奇数），则 $a^2$ 不是偶数（即 $a^2$ 是奇数）。
2. 假设 $a$ 是奇数，则由定义存在整数 $t$ 使 $a = 2t+1$。
3. 两边平方：$a^2 = (2t+1)^2 = 4t^2 + 4t + 1 = 2(2t^2+2t) + 1$。
4. 因 $2t^2 + 2t \in \mathbb{Z}$（整数对加法和乘法封闭），上式说明 $a^2$ 形如 $2(\text{整数})+1$，即 $a^2$ 是奇数。
5. 由逆否等价，引理成立。$\blacksquare$

（脚本验算 $a = 1,3,5,7,9$：$a^2 = 1,9,25,49,81$，全部为奇数 ✓。）

定理 2.5 的逐步推导（反证法）：

1. 反证法：假设 $\sqrt 2$ 是有理数。
2. 由有理数的定义，存在整数 $a$ 与 $b \ne 0$ 使 $\sqrt 2 = a/b$，并且我们可以要求这个分式已经约到最简（$a,b$ 除 1 外没有公因子）。把这个”互质”事实记为断言 $R$。
3. 由 $x = y \Rightarrow x^2 = y^2$，得 $2 = a^2/b^2$。
4. 两边乘以 $b^2$：$a^2 = 2b^2$。
5. 因 $b$ 是整数，$b^2$ 是整数，故 $a^2 = 2b^2$ 是偶数（偶数定义）。
6. 应用引理 2.6：$a$ 是偶数。故存在整数 $c$ 使 $a = 2c$。
7. 代入第 4 步：$2b^2 = a^2 = (2c)^2 = 4c^2$，两边除以 2 得 $b^2 = 2c^2$。
8. 因 $c$ 是整数，$c^2$ 是整数，故 $b^2$ 是偶数。再次应用引理 2.6：$b$ 是偶数。
9. 于是 $a$ 与 $b$ 都是偶数，它们共享公因子 2。这否定了断言 $R$。记作 $\neg R$。
10. 我们既有 $R$（第 2 步），又有 $\neg R$（第 9 步），矛盾。故 $\sqrt 2$ 不是有理数，即 $\sqrt 2$ 是无理数。$\blacksquare$

【证明机制解说】：全部力量集中在第 2 步的”约到最简”。这一步看似只是书写习惯，实际上是证明的关键杠杆——它把我们想要的性质（”不存在”）编码成了一个可被攻击的假设 $R$。之后的推导是双轨同步的：奇偶性从 $a^2$ 传染到 $a$，又从 $b^2$ 传染到 $b$，两条轨道在第 9 步汇合，把公因子 2 亮出来。这说明“最简分式”的约定本身就含有信息：它不是无成本的规范性要求，而是一条可以被推出的性质所反驳的假设。

反例（说明”最简”条件不可省）：如果去掉”$a,b$ 互质”这个要求，证明立刻失效。例如写 $\sqrt 2 = \frac{2\sqrt 2}{2}$ 或者用 $a=2\sqrt 2$ 这类非整数——但更直接的例证是：$a = 2, b = \sqrt 2$ 时 $a^2 = 4 = 2b^2$ 成立，$a$ 是偶数，但 $b$ 根本不在整数范围内，”$b$ 是偶数”这个结论无从谈起。没有”整数 $+$ 互质”这两条约束，”两个都是偶数”就完全推不出来。

六、分情形证明实战：无理数的无理数次幂可以是有理数

定理 2.7（官方 Note 3 的 Theorem 3.5）：存在无理数 $x, y$，使得 $x^y$ 是有理数。

证明策略：用分情形证明。为什么？因为待证命题带存在量词 $\exists x \exists y$，只需给出一对 $(x,y)$ 即可；而自然的第一猜想 $x = y = \sqrt 2$ 是否奏效，取决于 $\sqrt 2^{\sqrt 2}$ 到底是不是有理数——这是一个我们无法在本课程范围内判定的问题。分情形证明的精妙之处在于：我们不必知道答案，只要把两种可能都走一遍，两条路都能通向结论即可。

逐步推导：

1. 取 $x = \sqrt 2$，$y = \sqrt 2$。（两者都是无理数，由定理 2.5。）
2. 对 $\sqrt 2^{\sqrt 2}$ 分两种情形。由于”有理”与”非有理”穷尽且互斥，必有一种成立：
   • (a) $\sqrt 2^{\sqrt 2}$ 是有理数；
   • (b) $\sqrt 2^{\sqrt 2}$ 是无理数。
3. 情形 (a)：假设 $\sqrt 2^{\sqrt 2}$ 是有理数。取 $x = \sqrt 2$，$y = \sqrt 2$。此时 $x,y$ 都是无理数，而 $x^y = \sqrt 2^{\sqrt 2}$ 按情形假设是有理数。结论成立。✓
4. 情形 (b)：假设 $\sqrt 2^{\sqrt 2}$ 是无理数。原先的猜想的两个数不奏效了，但我们手上多了一个新的无理数 $\sqrt 2^{\sqrt 2}$。于是改取 \(x = \sqrt 2^{\sqrt 2}, \qquad y = \sqrt 2 .\) 两者都是无理数（$x$ 由情形假设，$y$ 由定理 2.5）。计算 \(x^y = \left(\sqrt 2^{\sqrt 2}\right)^{\sqrt 2} = \sqrt 2^{\sqrt 2 \cdot \sqrt 2} = \sqrt 2^{\,2} = 2,\) 其中第二个等号用到指数律 $(x^y)^z = x^{yz}$（本课程把它作为公理接受），最后一个等号用 $(\sqrt 2)^2 = 2$。而 $2 = 2/1$ 当然是有理数。结论成立。✓
5. 因为情形 (a) 与 (b) 必有一种成立，且两种情形下结论都已证明，故定理成立。$\blacksquare$

【证明机制解说】：这里有两个层次值得体会。

第一层是“用假设奖励自己”。在情形 (b) 中，我们并不知道 $\sqrt 2^{\sqrt 2}$ 是否真是无理数；但情形 (b) 的假设恰好告诉我们它是。于是我们可以”免费”使用这个新无理数作为底数。这就是分情形证明的典型手法：假设本身就是资源。

第二层是非构造性。走完整个证明，我们仍然不知道真正的 $(x,y)$ 是哪一对。情形 (a) 说”如果是 $\sqrt 2,\sqrt 2$ 就行”，情形 (b) 说”如果不是，那就换 $\sqrt 2^{\sqrt 2}, \sqrt 2$”——证明告诉我们必然存在一对，但不指示是哪一对。这在逻辑上完全合法（$\exists$ 只要求存在性），在实践中也是一种重要的思维方式：可以不构造而先证明存在。

补充数值事实（脚本验算）：$\sqrt 2^{\sqrt 2} \approx 1.632526919$。事实上 Gelfond–Schneider 定理（1934）告诉我们 $\sqrt 2^{\sqrt 2}$ 确实是无理数，所以真正成立的是情形 (b)，答案里的 $(x,y) = (\sqrt 2^{\sqrt 2}, \sqrt 2)$。但请注意：这个”事后真相”不是本证明的一部分，本证明也不需要它。

七、分情形证明的适用判据小结

什么时候该用分情形？经验判据是：当你手上的假设信息不足以直接推出结论，而某个”二分（或 $k$ 分）”能把情况拆成若干各自都容易处理的分支时。 三个正例：

• $m(m+1)$ 是偶数 → 按 $m$ 的奇偶二分（因为奇偶性决定了哪个因子含 2）。
• $\sqrt 2^{\sqrt 2}$ 是否有理 → 二分（因为两种情形的假设各自给出不同的可用资源）。
• 两色定理的归纳步骤（见 L03）→ 按”共享边界是不是新增的那条线”二分（因为两条边界的处理依据完全不同：一条靠归纳假设，一条靠构造）。

两条硬性检查（写完分情形证明后必须自问）：

1. 我列的情形覆盖了所有可能吗？（穷尽性）
2. 有没有哪个对象同时落在两个情形里、而我在这两个情形中推出了互相冲突的结论？（互斥性——若情形不互斥但结论一致则无害，若冲突则整个证明作废）

与经典问题的联系

本讲的四件工具在后续工程问题里有非常直接的下游用途。

（一）鸽笼原理 → 哈希冲突必然性（承 L20 的哈希与负载均衡）

哈希表把 $n$ 个键映射到 $k$ 个桶。若 $n > k$，鸽笼原理立刻断言：必然存在两个不同的键映射到同一个桶。这不是实现缺陷，而是数学必然——任何哈希函数都无法避免。这条结论是 L20 讨论”链地址法 (chaining)”“开放寻址”“期望链长 $\approx n/k$”的出发点：既然冲突不可消除，工程上就只能转而控制冲突的分布（让每个桶的期望负载为 $n/k$，并用集中不等式 L23 证明真实负载不会偏离期望太多）。请注意这里的分工：本讲的鸽笼原理给的是确定性的下界结论，L20 的期望分析给的是概率性的分布刻画，两者互补。

（二）反证法 → 不可满足性与不可判定性（预告 L12、L13）

“不存在”型命题是反证法的主场。后续两个最重要的”不存在”定理都靠它：

• L12 可数性：证明”实数集不可数”——假设存在一个把 $\mathbb{N}$ 到 $\mathbb{R}$ 的完整列举，用对角线法构造出一个不在列表中的实数，矛盾。（注意与 Euclid 证明的结构同构：都是”假设有一个完整列表，然后造出一个逃出列表的对象”。）
• L13 可计算性：证明”停机问题不可判定”——假设存在判定程序 $H$，构造一个在 $H$ 判定为停机时故意不停机的程序，让 $H$ 作用在自己身上，得到矛盾。

（三）逆否证明 → 算法正确性中的”逆否式”推理（贯穿全课程）

很多算法性质的证明都以逆否形式出现。例如 L05 费马小定理的应用中，”若 $a$ 不是 $p$ 的倍数则 $a^{p-1}\equiv 1$”的逆否形式”若 $a^{p-1}\not\equiv 1$ 则 $p \mid a$”，正是 Miller–Rabin 素性测试判定”$a$ 是一个见证 (witness)，$p$ 必为合数”的逻辑依据。RSA（L06）中”若 $m$ 与 $N$ 不互质则解密失败”的逆否”解密始终成功则 $m$ 与 $N$ 互质”也是同一套路。

（四）非构造性证明 → 概率方法（预告 L15、L23）

“证明存在但不必指出是哪一个”这种思维在概率方法中被推到极致：为了证明某个组合对象存在，我们随机选一个对象，证明”选到好对象的概率 $>0$”。概率大于零 $\Rightarrow$ 好对象存在——这正是一种非构造性的存在性证明。本讲的定理 2.7 是这一整套思想的雏形。

与其他讲次的关联

• 与 L00（直接证明）：本讲的三种技巧都是直接证明的变体或补充。逆否证明在形式上是”对 $\neg Q \Rightarrow \neg P$ 做一次直接证明”；反证法在推出矛盾前的所有步骤都是直接推导；分情形证明则是对每个分支各做一次直接证明。所以 L00 的直接证明功夫是地基，本讲只是教你如何选入口。
• 与 L01（命题逻辑）：本讲的合法性完全依赖 L01 的两条成果——(i) 真值表方法（用于验证 $P\Rightarrow Q \equiv \neg Q \Rightarrow \neg P$）；(ii) 排中律 $P \vee \neg P$（反证法”黑白分明”的依据）。如果 L01 没学扎实，本讲就变成了背套路。
• 与 L03（归纳法）：本讲的两个引理（”每个 $n>1$ 有质因子”、以及更一般的算术基本定理）在 L03 用强归纳正式证明。换句话说，本讲的 Euclid 证明是借用了一个尚未证明的引理——这在数学写作中完全合法（可以引用”将在后续证明的结果”），但你自己写证明时要意识到这个依赖方向。同时，L03 的”$\forall n, 3\mid n^3-n$”在线性推导上与本讲的 Theorem 2.2 同型。
• 与 L04–L05（模运算、Euclid/FLT/CRT）：定理 2.2（$t \mid d$ 的传递结构）是 L04 同余语言中”$a\equiv b \pmod m$ 且 $d \mid m$ $\Rightarrow$ $a\equiv b\pmod d$”的整数版本。Euclid 算法（L05）的终止性证明则同时用到”最小性论证”（一种隐式的分情形/反证混合）与不变式。
• 与 L12–L13（可数性、可计算性）：本讲应用一里”假设完整列表 → 造出逃逸对象 → 矛盾”的模式，将在 L12 的对角线论证与 L13 的停机问题证明中被复用两次，是整门课最重要的证明骨架之一。
• 与 L14–L15（计数、概率公理）：鸽笼原理是”计数论证给出确定性结论”的最简范例；到了 L15，同样的计数思想会被升级为等可能样本空间上的概率。此外，L18（容斥）中的”至少有一个事件发生”的计数，其逻辑起点就是鸽笼式的”反过来数每个盒子至多多少”。

关键要点

1. 一图记住三种技巧的入口选择：

                        要证命题的形态？
                              |
        +---------------------+---------------------+
        |                     |                     |
   P => Q （蕴含）       "不存在"/"无穷多"/       信息不足，
        |                "不可能" 型命题           需按情况拆分
        |                     |                     |
   直接证 P=>Q 难？      选【反证法】              选【分情形证明】
        |                  假设 ~P                    |
   +----+----+             推出 R 与 ~R            检查：情形是否
   |         |             => P 成立               (1) 穷尽
 假设 P    假设 ~Q                                    (2) 互斥
 推出 Q    推出 ~P ----+
（直接）  【逆否证明】  |
         靠逆否等价     |
         不出现矛盾  <--+ 注意：逆否证明不是 "假设 ~Q 推出矛盾"，
                          而是 "假设 ~Q 直接推出 ~P"

1. $P\Rightarrow Q$ 的等价物只有逆否 $\neg Q\Rightarrow\neg P$。逆命题 $Q\Rightarrow P$ 与否命题 $\neg P \Rightarrow \neg Q$ 都不等价于原命题。想清楚这一条，反证法与逆否法的区别就自动化开了。

2. 反证法的收尾必须显式写出 $R \wedge \neg R$。只写”故假设不成立”是不够的——读者需要看到矛盾的两半分别在哪一步出现（在 Euclid 证明里是”$p$ 是质数”与”$p=1$”；在 $\sqrt 2$ 证明里是”$a,b$ 互质”与”$a,b$ 都是偶数”）。

3. 鸽笼原理的威力来自”与配置无关”：$n>k$ 就必然有重复，不需要知道任何摆放细节，也不需要任何概率假设。加强形式 $\lceil n/k \rceil$ 在具体题目中比原版更好用。

4. 分情形证明的两条硬指标：穷尽、互斥。另外，分情形可以产出非构造性结论——证明”存在”却不指明”是哪个”，这在数学上完全合法。

5. 把长证明拆成引理，就像把长程序拆成子程序。引理要写得尽量通用，才可能被重复使用（引理 2.6 在同一证明里被用了两次）。

常见误区与注意事项

误区 1：假设了自己要证的东西（”循环论证”）

官方 Note 3 的第一个错误证明：

Claim 3.1. $-2 = 2$。 “证明”：假设 $-2 = 2$。两边平方得 $(-2)^2 = 2^2$，即 $4 = 4$，这是真的。故 $-2 = 2$。$\spadesuit$

错在哪：第一步就假设了待证结论。设 $P \equiv$ “$-2 = 2$”，这个”证明”实际建立的是 $P \Rightarrow \text{True}$，而 $P \Rightarrow \text{True}$ 是恒真的（任何命题都能推出真命题），它跟证明 $P$ 完全是两码事。用 L01 的真值表语言说：$P \Rightarrow \text{True}$ 这一列全是 T，与 $P$ 的真假无关。

附带错误：平方不是单射。$x^2 = y^2$ 只能推出 $x = y$ 或 $x = -y$，推不出 $x=y$。这一步”从 $x^2=y^2$ 推 $x=y$”忽略负号，是同一个错误的另一半。

误区 2：除以零

官方第二个错误证明：

Claim 3.2. $1 = 2$。 “证明”：设整数 $x,y$ 满足 $x = y$。则 \(x^2 - xy = x^2 - y^2 \quad(\text{因 } x=y)\) \(x(x-y) = (x+y)(x-y)\) \(x = x + y \quad(\text{两边除以 } x-y)\) \(x = 2x.\) 取 $x = y = 1$ 即得 $1 = 2$。$\spadesuit$

错在哪：第三个等式两边除以了 $x-y$，而在本题设定下 $x = y$，所以 $x - y = 0$。除以零不是良定义的运算（在 L04 的模运算语言里我们会说得更精确：$0$ 在任何模数下都没有乘法逆元，所以”约掉 0”从来没有合法性）。前两个等式其实完全正确，错误精确地发生在第三个等号处。

注：这份”证明”的前两步本身还有个讽刺之处——$x^2 - xy = x^2-y^2$ 在 $x=y$ 时两边都等于 $0$，这一步是真的但完全空洞；真正被判死刑的是除法。

误区 3：对负数”开方”或”平方”时忽略符号

官方第三个错误证明：

Claim 3.3. $4 \le 1$。 “证明”：我们知道 $-2 \le 1$。两边平方得 $4 \le 1$。$\spadesuit$

错在哪：平方不保持不等号方向。$a \le b$ 推不出 $a^2 \le b^2$。这里 $-2 \le 1$ 为真，但 $(-2)^2 = 4 > 1 = 1^2$。根本原因是平方函数在 $\mathbb{R}$ 上不是单调的：它在 $(-\infty,0]$ 上递减、在 $[0,\infty)$ 上递增，所以跨过 0 的两个数无法比较平方后的大小。

官方给的检验问题：若 $a \le b$，是否必然有 $\vert a\vert \le \vert b\vert $？不是。反例：$a = -2, b = 1$，此时 $a \le b$ 成立，但 $\vert a\vert = 2 > 1 = \vert b\vert $（脚本验算确认）。这也正是本讲要求的”去掉某条件命题失效”的具体反例。

相关的第三课：不等式两边乘以负数会翻转方向。例如 $-2 < 5$ 两边乘 $-1$ 得 $2 > -5$（注意方向从 $<$ 变成 $>$）。学生常在心里把它当成”乘 $-1$ 只是变号”，忘了同时翻方向。

误区 4：把逆否证明说成反证法（或反之）

“我们假设 $d$ 是偶数……于是 $n$ 是偶数。矛盾，故原命题成立”——这是错的写法！定理 2.2 的证明里从头到尾没有出现任何矛盾：我们只是从 $\neg Q$ 推到了 $\neg P$，然后引用逆否等价就结束了。把这一过程描述成”矛盾”会让读者去找那个根本不存在的 $R\wedge\neg R$。

反过来，把 $\sqrt 2$ 的证明写成”用逆否证明”也是错的：$\sqrt 2$ 是无理数不是一个蕴含式，它没有”前件”和”后件”，根本谈不上逆否命题。

误区 5：把”$q$ 是质数”当成 Euclid 证明的一步

Theorem 2.4 的证明只需要 $q$ 有一个不在原列表中的质因子，完全不需要 $q$ 本身是质数。$k = 6$ 时 $q = 30031 = 59 \times 509$ 就是现成的反例（脚本验算）。如果你的证明写了”$q$ 是质数，矛盾”，那么在第 6 步就写不下去了。

误区 6：分情形证明遗漏情形，或情形之间不互斥

• 遗漏：证明”$m(m+1)$ 是偶数”时只讨论 $m$ 是偶数的情形，就漏掉了 $m$ 是奇数的一半（用 L01 的话说，这是把 $P \vee \neg P$ 的排中律丢掉了）。
• 不互斥且假设冲突：在某个有重叠的划分里，两个情形可能对重叠部分给出互相矛盾的假设（例如一边假设”$x \ge 0$”、一边假设”$x \le 0$”却仍声称情形互斥），此时证明无效。
• 正确的写法是：在证明开头显式说明”以下情形构成一个划分”，让读者一眼看到穷尽性与互斥性。

误区 7：用”显然”“易得”跳步

官方 Note 3 §5 明确提醒：写下一步之前先想清楚这一步的依据是什么。如果说不清为什么这步成立，那就是在跳步（making a leap），必须回去补。一条理由只有在满足”(1) 它是对的，(2) 读者会自动同意它是对的“时才可以不加证明地写出。例如”因 $a$ 是整数，$2a^2 + 2a$ 是整数”这一步通常可以省略中间推理（整数加法与乘法封闭），但如果读者群体不确定，就该展开。

思考题（带答案）

Q1.（纯计算） 用鸽笼原理回答：

(a) 一个班有 25 名学生，每人取一个 $1$ 到 $4$ 之间的整数作为编号。证明必有两人的编号相同，并指出至少有多少人共享同一个编号。 (b) 把 100 个球放进 9 个盒子，至少有一个盒子含多少个球？ (c) 在旧金山头发问题中，若已知旧金山人口为 $800000$，而”头发数”的盒子数改为 $400000$，结论还成立吗？为什么？

Q2.（概念理解） 判断下列推理使用的是直接证明、逆否证明、反证法还是分情形证明，并说明判断依据。

(a) “设 $a,b$ 为整数且 $ab$ 为奇数。假设 $a$ 是偶数，则 $a = 2k$，于是 $ab = 2kb$ 是偶数，与 $ab$ 为奇数矛盾。故 $a$ 是奇数。” (b) “设 $a,b$ 为整数且 $ab$ 为奇数。假设 $a$ 是偶数，则 $a = 2k$，于是 $ab = 2kb$ 是偶数，即 $ab$ 不是奇数。故若 $ab$ 是奇数则 $a$ 不是偶数，即 $a$ 是奇数。” (c) “对任意整数 $m$，$m(m+1)$ 是偶数：若 $m$ 偶，则 $m(m+1)$ 含因子 $m$，偶；若 $m$ 奇，则 $m+1$ 偶，$m(m+1)$ 含因子 $m+1$，偶。”

Q3.（证明能力） 设 $n$ 为整数。证明：若 $n^2$ 是奇数，则 $n$ 是奇数。（要求：分别用逆否证明和反证法各写一遍，并指出两个版本在哪一步分道扬镳。）