2 证明方法

2.1 证明

在科学研究中，我们常常是通过实验的方式来积累证据，从而判断一个命题的有效性。但是在数学中，我们会追求一种更加绝对的确定性。一个数学证明提供了一种 确保(guaranteeing) 一个命题为真的手段。

证明是非常强大的，并且从某种程度上证明其实很像计算机程序。其实，在数学证明与计算机程序这两个我们将在这个系列中触及的概念之间有着很深的历史渊源——在大约一个世纪以前，计算机的发明与数学证明思想的探索之间是紧密绑定的。

2.1.1 证明的应用

所以我们可能会想要证明怎样的一些“和计算机科学相关的”命题呢？这里有两个例子：

1. 程序P对于每一个输入都会终止吗？
2. 程序P是否正确地计算了函数f(x)，也就是说对于每个输入x，它是否输出了f(x)？

注意到这些命题指的是一个程序在 无穷(infinitely) 多输入下的行为。对于这样的一种命题，我们可以通过大量输入测试的方式提供 证据(evidence) ，说明它对于很多的x的值来说是正确的。

但不幸的是，这并不能保证这个命题对于我们还未测试的无穷多个x来说也是正确的！为了确保这个命题的正确性，我们必须提供一个 严格的证明(rigorous proof) 。

2.1.2 证明的概念

那么，什么是 证明(proof) 呢？证明是一个有穷的步骤序列，其中每个步骤称为 逻辑推导(logical deduction) ，这些一步一步的逻辑推演保证了我们想要证明的那个命题是真的。特别地，一个证明的力量在于，通过 有限(finite) 的方法和步骤，我们能够确保一个关于 无穷多个案例(infinitely many cases) 的命题为真。

2.1.3 证明的典型结构

更特别的，证明通常具有如下的典型结构。

1. 回忆我们已经有的一些命题，在不需要证明的情况下我们承认它们是对的（我们总得从某个地方开始），这些命题称之为 公理(axiom) 或者 假设(postulate) 。
   • 我们认为公理与假设是不证自明的，有时候还会用到一些已经被证明正确的命题，我们称之为 定理(theorem) 或者 引理(lemma) 。
   • 一般定理是我们的最终结论，而引理是为了证明结论而引入的辅助结论。
2. 从这些公理与假设开始，一个证明由一系列的逻辑推导（单纯应用逻辑规则的步骤）组成。这最终会形成一系列的语句，如果上一句话是真的，那么下一句话就必然是真的（否则这就是一个伪证）。
   • 这个性质是由逻辑规则保证的：每个语句都是遵照前面的语句推导而来的。
   • 这些逻辑规则被认为是深藏在人类思考中的精华。它们在计算机的设计中起到了中心的作用，从数字逻辑或者电路设计背后的基本原则开始，到整个计算机大厦的构建。
   • 从一个更高层的视角来看，这些逻辑规则在人工智能的发展中起到了不可替代的作用，人工智能的一个终极目标就是在电脑上模拟出人脑。

2.1.4 本讲结构

在这一讲中，我们会先规定一些数学符号以及引入一些后续会使用到的基本数学事实（第2.2节）。

之后，我们会介绍4种不同的证明技巧：

• 直接法(direct proof) - 第2.3节
• 逆否法(proof by contraposition) - 第2.4节
• 反证法(proof by contradiction) - 第2.5节
• 例举法(proof by cases) - 第2.6节

再然后，我们会简单地讨论一些常见的陷阱（第7节）以及证明风格（第8节）上的建议。

最后，我们会有一些证明的练习题（第9节）和作业题（第10节）。

2.2 一些数学记号与基本事实

在这一讲当中，我们会使用到如下的一些数学记号和基本事实：

• 用 $\mathbb{Z}$ 表示整数集，也就是说 $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$ ；用 $\mathbb{N}$ 表示自然数集， 也就是 $\mathbb{N} = \{0, 1, 2, ...\}$ 。
• 两个整数的和与积是一个整数，也就是说整数集对于加法与乘法运算 封闭(closed) ；自然数集同样也对于加法和乘法运算封闭。
• 给定整数a和b，我们称a整除b（记为 $a|b$ ）当且仅当存在一个整数q使得 $b = aq$。
  • 例如 $2 | 10$ ，因为存在一个整数 $q = 5$ 使得 $10 = 5\cdot 2$。
• 如果一个自然数 $p$ 只被1和它本身整除，我们称这是一个 质数(prime number) 。
• 我们使用 $:=$ 来表示一个定义。比如说 $q := 6$ 定义了一个初值为6的变量q。

2.3 直接证明

2.3.1 概念

有了第1讲的命题逻辑的语言，我们现在就可以讨论证明方法了，真正有趣的部分就要开始了（说实话，命题逻辑挺无聊的），你准备好了吗？如果准备好了，下面是我们的第一个证明方法，叫做 直接证明(direct proof) 。

在这个小节里面，记住我们的目标是给出一个清晰而又简洁的证明。让我们从一个简单的例子开始吧。

定理2.1

对于任意 $a,b,c \in \mathbb{Z}$ ，如果 $a | b$ 且 $a | c$ ，那么 $a | (b + c)$ 。

概念检查

用P(x,y)表示“x|y”，理解上述的语句等价于：

$(\forall a,b,c\in\mathbb{Z})((P(a,b)\wedge P(a,c))\Longrightarrow P(a, b + c))$

2.3.2 基本步骤

从一个更高的层次来看，一个直接证明的进行过程如下。

对于每个x，我们尝试证明的命题具有形式 $P(x)\Longrightarrow Q(x)$ 。

它的一个直接证明会对于一个泛化的，一般的值x，从假设P(x)开始，通过一系列的蕴含最终得出Q(x)：

直接证明(direct proof)

$\quad$ 目标：证明 $P\Longrightarrow Q$ 。

$\quad$ 方法：假设P

$\quad\quad$ ......

$\quad\quad$ 于是Q

2.3.3 实例

定理2.1证明

假设 $a | b$ 且 $a | c$ ，也就是说，存在 $q_1\in\mathbb{Z}, q_2\in\mathbb{Z}$ 使得 $b = q_1a, c = q_2a$。

于是， $b + c = q_1a+q_2a = (q_1+q_2)a$。

而整数集 $\mathbb{Z}$ 对于加法封闭，我们有 $(q_1 + q_2)\in\mathbb{Z}$；

因此 $a|(b+c)$ 。 $\square$

是不是非常简单？但是请停下来稍微思考一下，先前我们说定理2.1等价于

$(\forall a,b,c\in\mathbb{Z})((P(a,b)\wedge P(a,c))\Longrightarrow P(a, b + c))$

那么在证明的哪个地方我们遇到了量词 $\forall$ 呢？

这个地方的关键是证明并没有给a、b、c假设任何 特定的值(specific value) ，实际上，我们的证明对于任意随机的 $a, b, c\in\mathbb{Z}$ 都成立。也因此，我们才真正地证明了我们想要的结论。

概念检查

请给出下面语句的直接证明：

对于任意 $a,b,c\in\mathbb{Z}$ ，如果 $a|b$ 且 $a|c$ ，那么 $a | (b - c)$ 。

下面让我们来尝试一点更具有挑战性的证明吧。

定理2.2

令 $0 < n < 1000$ 是一个整数。如果n的各数位和被9整除，那么n也被9整除。

我们可以看到，这个语句等价于

$(\forall n\in\mathbb{Z}^{+})((n < 1000) \Longrightarrow (sum\ of\ n's\ digits\ divisible\ by\ 9 \Longrightarrow n\ divisible\ by\ 9))$

这里， $\mathbb{Z}^+$ 表示正整数集 $\{1, 2, ...\}$。

现在，证明的过程和之前类似：

• 我们从假设开始，假设一个一般的，各数位和被9整除的整数n；
• 然后我们用一系列的蕴含来导出n本身也被9整除的结论。

定理2.2证明

令 n 的十进制表示可以写作 $n = \overline{abc}$ ， 也就是说 $n = 100a + 10b + c$。

假设 $9 | a + b + c$ ，即 $\exists k \in\mathbb{Z}, s.t. a + b + c = 9k$ (这里 $s.t.$ 意为使得 - such that)。

于是我们有：

$n = 100a+10b+c = 99a+9b+(a+b+c) = 99a+9b+9k = 9(11a+b+k)$

所以， $9 | n$ 。 $\square$

定理2.2的逆是否也是真的呢？回忆一下 $P \Longrightarrow Q$ 的逆是 $Q \Longrightarrow P$ 。

因此定理2.2的逆定理就是在说对于任意的整数 $0 < n < 1000$ ，如果n被9整除，那么n的数位和也被9整除。

定理2.3(定理2.2的逆定理)

令 $0 < n < 1000$ 是一个整数。如果n被9整除，那么n的各数位和也被9整除。

定理2.3证明

对于n的数位采用定理2.2证明当中相同的表示法 $n = \overline{abc}$，

$9 | n \Longrightarrow n = 9l, l\in \mathbb{Z}$

$\Longrightarrow 100a+10b+c = 9l \Longrightarrow 99a + 9b + (a + b + c) = 9l$

$\Longrightarrow a + b + c = 9(l - b - 11a)$

$\therefore 9 | a + b + c. \square$

我们现在应该已经对于证明有所体悟了。结合定理2.2以及其逆定理2.3，我们会发现，9整除n的数位和当且仅当9整除n。换句话说，这两句话是逻辑上等价的。

在这里，我们需要学到的一个关键是：无论何时你想要证明一个等价式 $P \Longleftrightarrow Q$ ，总是通过分别证明 $P \Longrightarrow Q$ 且 $Q \Longrightarrow P$ 的方式来进行。（就像我们上面所做的那样）

这里的n不一定非得是3位数，无论是几位数的n，上面的两个结论都是成立的，这里是为了降低难度，所以限制了n<1000。

2.4 逆否法

2.4.1 概念

下面进入我们的第二个证明技巧。回忆一下之前命题逻辑的讨论中，我们学习过蕴含 $P\Longrightarrow Q$ 和 $\neg Q\Longrightarrow \neg P$ 是等价的（可以化成析取式来看）。其中，后者称为前者的逆否命题(contrapositive)。

然而，有的时候证明 $\neg Q\Longrightarrow \neg Q$ 要比证明 $P\Longrightarrow Q$ 简单得多。

因此逆否法通过证明逆否命题的正确性来证明原命题的正确性。

2.4.2 基本步骤

逆否法(proof by contrapositive)

$\quad$ 目标：证明 $P\Longrightarrow Q$ 。

$\quad$ 方法：假设 $\neg Q$

$\quad\quad$ ......

$\quad\quad$ 于是 $\neg P$

$\quad$ 结论： $\neg Q\Longrightarrow\neg P$ ，这与 $P\Longrightarrow Q$ 是等价的。

2.4.3 实例

考虑下面这个定理：

定理2.4

令n是一个正整数，并且d整除n。如果n是奇数，那么d也是奇数。

通过直接证明的手段证明这个结论看起来很困难：我们会在第一步假设n是任意一个奇数，但然后呢？从这个条件出发该怎么往后推导？此时，通过逆否命题来证明就会简单很多。

概念检查

定理2.4的逆否命题是什么？（答案：如果d是偶数，那么n也是偶数）

定理2.4证明

通过逆否命题来证明。

假设 $d$ 是偶数，由定义可得 $\exists k\in\mathbb{Z}, d = 2k$ 。

$\because d | n\quad \therefore \exists l\in\mathbb{Z}, n = dl$ 。

结合上述两式，我们有 $n = dl = (2k)l = 2(kl)$。

因此，n是偶数，逆否命题成立，原命题成立。$\square$

注意到这一次，我们证明的第一行声明了我们的证明技巧——这是写证明的好习惯，就好像在编程的时候写注释是一个好习惯一样。从像这样声明你的证明技巧开始书写证明会对你证明的读者带来极大的帮助，是他们能够理解你的证明接下来准备干什么。

作为另一个逆否法证明的例子，我们提供了一个著名的定理——鸽笼原理。尽管这个定理的表述很简单，但它之后能够为我们带来很多惊奇的结果。

定理2.5

鸽笼原理(pigeonhole principle) ：令n和k为正整数。将n个物品放进k个盒子中。如果 $n > k$ ，至少有一个盒子必须包含多个物品。

这个定理的名称来源于想象将n个鸽子放到k个鸽笼的过程。

定理2.5证明

通过逆否命题来证明。

如果每个盒子最多包含1个物品，那么物品的数量最多不超过盒子的数量，即 $n \le k$ 。

逆否命题成立，原命题成立。$\square$

这个定理的实用之处在于无论盒子里面的物品的 配置(configuration) 如何，它总是成立的。有一些情况，当物品以一种十分复杂的方式被放到盒子里面的时候，这个定理的结果就不是一眼就能看出来的了。

例如，有一个网上的调查显示人的头发平均大概有100000根。于是，我们或许可以有合理的自信认为没有人会有超过500000根头发。另一方面，人口普查显示狗熊岭的人口超过了800000。如果我们将狗熊岭的居民们视为鸽子，将居民的头发数量视为这个居民应当呆在的鸽笼，那么，根据鸽笼原理，我们就可以得出一个有趣的事实：狗熊岭至少有两个人头上的头发数量是完全相同的。而这个事实就没有鸽笼原理本身那么显然了。

2.5 反证法

2.5.1 概念

在这一讲讨论的所有证明技巧中，反证法或许是最具有吸引力的一种了。毕竟谁能够拒绝一种被称为“转化成不可能(reduction to an absurdity —— 也叫做归谬)”的技巧呢？

反证法的基本思想是假设你想要证明的东西是错的（是的，这看起来倒推了，但请再忍受一会儿）。然后，你想办法说明这会导致一个完全荒谬的结论：一个矛盾。于是，你就可以得出结论，你原本想要证明的东西实际上是对的。

概念检查

反证法的正确性依赖于一个事实：如果一个命题不是假的，那么它一定是真的。这种一个命题非黑即白的解释是我们上一讲的提到的哪个法则来着？

2.5.2 基本步骤

反证法(proof by contradiction)

$\quad$ 目标：证明P。

$\quad$ 方法：假设 $\neg P$

$\quad\quad$ ......

$\quad\quad R$

$\quad\quad$ ......

$\quad\quad\neg R$

$\quad$ 结论： $\neg P\Longrightarrow\neg R\wedge R$ ，这是一个矛盾，于是 $P$。

如果到此为止的关于反证法为什么对的直观地解释还不足以让你信服的话，这里有一个更加形式化的解释：

反证法证明了 $\neg P \Longrightarrow \neg R\wedge R$ ，而 $\neg R \wedge R \equiv False$。

于是 $\neg P \Longrightarrow False$，其逆否命题为 $True \Longrightarrow P$。

也就是说，反证法证明了 $True \Longrightarrow P$ 是真的，所以 P 是真的（这里可以回顾一下上一讲蕴含的真值表）。

2.5.3 实例

现在，让我们来试着用一下这个证明技巧。下面这个定理的证明最早可以追溯到2000年前的古希腊数学家欧几里得。

定理2.6

质数有无穷多个。

在见证反证法的力量之前，我们稍微停下来一会儿思考一下我们会怎么尝试去通过一种不同的证明技巧（比如说直接证明）去证明定理2.6？

这看起来有些困难，是吗？你如何去构造出无穷多个质数呢？然而，反证法最美妙的事情就是，当我们假设这个语句是错的时候，也就是只有有限多个质数的时候，坏事情会发生，这样我们就避免了无法直接构造出无限多个素数的困境。

在继续之前，我们先声明一个之后证明定理2.6会用到的一个简单的引理。这个引理的证明过程推迟到下一讲我们学习归纳法的时候再提，暂时我们先承认它是对的（当然，它看起来就很显然）。

引理2.1

每个比1大的自然数要么是一个质数，要么有一个质因数。

定理2.6证明

反证法。

假设定理2.6是错的，也就是说只有有限个质数，不妨记为k个。

那么，我们就可以枚举它们：$p_1, p_2, p_3, ... p_k$ 。

考虑 $q = p_1p_2p_3...p_k + 1$ ，是所有的质数相乘再加一的结果。

我们发现 $q$ 不可能是质数，因为根据定义，它比所有的质数 $p_1$ 到 $p_k$ 都大。

根据引理2.1，我们可以得到结论： $q$ 有一个质因数 $p$ 。将这个结论记为命题 $R$。

接下来，因为 $p_1, p_2, p_3, ..., p_k$ 是所有的质数，因此 $p$ 一定是其中一个。

于是，p整除 $r := p_1p_2p_3...p_k$。

从而我们有 $p | q$ 且 $p | r$ ， 说明 $p | (q - r)$。

但是 $q - r = 1$ ，说明 $p \le 1$ ， 也就是说 $p$ 不是质数，于是有 $\neg R$ 。

至此，我们找到了矛盾 $R \wedge \neg R$ 。 $\square$

现在，我们应该已经热身完了，接下来让我们来解决另一个经典的使用反证法的证明吧。先回忆一下一个 有理数(rational number) 是能够用两个整数作比的方法表示的数。

例如 $\frac23,\frac35,frac9{16}$ 都是有理数。

相对的，不能够用分数形式表示的数，称作 无理数(irrational number) 。

$\sqrt{2}$ 呢？你觉得它是有理数还是无理数？答案如下。

定理2.7

$\sqrt{2}$ 是无理数。

在给出证明之前，让我们问一个很重要的问题：为什么反证法是一个这里值得尝试的很好的备选证明方法？

我们可以考虑一下，然后我们会发现，定理2.6和定理2.7有一些基本的共通的东西——在这两个例子中，我们都想要证明某种东西不存在。比如说，

• 在定理2.6中，我们想要证明一个最大的质数是不存在的；
• 在定理2.7中，我们想要证明满足 $\sqrt{2} = \frac{a}{b}$ 的整数 $a$ 和 $b$ 是不存在的。

通常来说，证明某个东西不存在似乎是比较困难的。但这其实恰好是反证法发光发热的一个场景。

为了证明定理2.7，我们需要用到下面的这个简单的引理。引理2.2的证明留作习题。

当然，我不是在写数学教材，而是在写一个类似于笔记一样的教程，所以我会把我的解答也附在题目后面，不过读者最好能够自己先写，写完了之后再看我的解答。

引理2.2

如果 $a^2$ 是偶数，那么 $a$ 也是偶数。

定理2.7证明

反证法。

假设 $\sqrt{2}$ 是有理数，根据有理数定义，存在互质的两个整数 $a$ 、 $b$ ，满足 $\sqrt{2} = \frac{a}{b}$ 。

记 $a$ 与 $b$ 互质为命题 $R$ 。

由 $\sqrt{2} = \frac{a}{b}$ 有 $a^2 = 2b^2$，于是 $a^2$ 是偶数。

由引理2.2有 $a$ 也是偶数，即 $\exists k, a = 2k$ ，代入有 $(2k)^2 = 2b^2$，即 $b^2 = 2k^2$。

于是 $b^2$ 是偶数，根据引理2.2有 $b$ 也是偶数。

从而我们发现 $a$ 与 $b$ 有除了 $1$ 以外的公因数 $2$ ，不互质，即 $\neg R$ 。

至此，我们找到了矛盾 $R\wedge \neg R$ 。 $\square$

在上面的反证法证明中，为了能够清楚的标识出矛盾点，我将矛盾的两个命题分别用 $R$ 与 $\neg R$ 标了出来， 一般写证明的时候可以不用标出来，说清楚哪个地方矛盾了就行。

2.6 例举法

2.6.1 基本想法

下面你会看到一个证明，让你到此为止建立的安全感发痒，它基于另一种证明技巧，我们称之为 例举法(proof by cases) （这个词组有很多的翻译，在这个系列中，我暂且译为例举法），在这个小节里面，我们会非正式地触及一下这个技巧。

特别地，例举法背后的想法是：有时候，当我们想要证明某个主张，它可能有多种情况，我们知道，这么多种情况中至少有一种是真的，但我们并不确定到底哪一种情况是真的。但我们可以做的是，在每一种情况下都将最终的结论证明出来，那么，我们不需要知道到底哪一种情况为真，因为不管哪种情况为真，最终的结果是一致的，于是整个命题整体上就为真。

2.6.2 实例

定理2.8

存在无理数 $x$ 和 $y$ 使得 $x^y$ 是有理数。

定理2.8证明

例举法。

注意到要证明的定理是有存在量词修饰的存在性命题，要证明这样的命题，我们只需要能够给出一个满足要求的x和y即可。

令 $x = \sqrt{2}, y = \sqrt{2}$ ，分两种情况来证明，两种情况中一定恰好有一种是真的。

1. $\sqrt{2}^{\sqrt{2}}$ 是有理数：

   • 这样的话我们已经找到了满足要求的 $x$ 和 $y$ ，该情况下结论成立。

2. $\sqrt{2}^{\sqrt{2}}$ 是无理数：

   • 令无理数 $x = \sqrt{2}^{\sqrt{2}}, y = \sqrt{2}$ ，有：

     $x^y = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^{\sqrt{2}\sqrt{2}} = \sqrt{2}^2 = 2$

   • 即 $x^y$ 为有理数，该情况下结论成立。

由于上述两种情况必定恰有一种成立（回忆第一讲的排中律），我们可以得出结论，定理2.8成立。 $\square$

在结束这一小节之前，让我们来指出一个上面的证明中比较奇怪的地方。满足定理2.8的x和y到底是多少？

是 $x = \sqrt{2}, y = \sqrt{2}$ ？还是 $x = \sqrt{2}^{\sqrt{2}}, y = \sqrt{2}$ ?

嗯...由于我们做的是情况分析，我们并不清楚两种选择中到底哪一种是正确的。不过换句话说，我们刚刚其实展示了一种非常厉害的东西，称为 非构造性证明(non-constructive proof) ：我们在没有显示地指出某个东西X到底是什么的情况下证明了X是存在的。

2.7 书写证明时常犯的错误

2.7.1 一些唠叨

书写简洁清晰的证明是一种非常卓越的能力，并且可以说这是一个人能达到的最高形式的知识启迪之一。这需要你的思想非常审慎地反思它自己的内部工作（或者说你的思考过程），并且将它们重新组织成一条通顺且有逻辑的思考序列。

换句话说，在这个过程中你的思想正在一个非常底基的层次提升它自己，这种提升远远超过了计算机科学或者任何特定研究领域的边界。这种训练的好处将会触及到你生活的各个方面，实际上，它会塑造你应对生活本身的方式，你未来或许会体会到。

就像任何奠基级别的成就一样，培养书写严格证明的能力可能是你在大学学习生涯中会遇到的最大挑战之一，因此，如果这让你觉得困难的话请不要气馁，你不是一个人。在这条路上除了很多很多的练习没有其它的捷径。

2.7.2 常见的陷阱

为了帮助你上路，我现在为你亮起一些关于构造证明过程中常见陷阱的红灯。让我们从一个简单但是常见的错误开始吧。

陷阱1

主张1： $-2 = 2$

证明？ 假设 $-2 = 2$ ，两边同时平方，有 $(-2)^2 = 2^2$ ， 即 $4 = 4$ ，这是对的。于是 $-2 = 2$ 也是对的。 $\spadesuit$

这个主张显然是错的，那么我们到底做错了什么呢？我们的代数运算是正确的，并且每一步都是严格依照上一步得出的。

因此，错误一定是在证明的最开始产生的。在最开始的地方，我们做出了一个厚颜无耻的假设： $-2 = 2$。

但是等一下，这不就是我们要去证明的那个语句吗？确实。不妨记 $P \equiv (-2 = 2)$ ，上面的证明过程中，我们只证明了 $P\Longrightarrow True$ ，这和证明 $P$ 是不一样的。（因为存在空真的情况，详见第一讲的蕴含）

教训1

当书写证明的时候，不要假设你要证明的目标是对的。

陷阱2

主张2： $1 = 2$

证明？ 设整数 $x = y$ ，则有：

$x^2 - xy = x^2 - y^2 \tag{since\quad x = y}$

$x(x-y)=(x+y)(x-y)$

$x=x+y\tag{divide\quad both\quad sides\quad by\quad x - y}$

$x=2x$

令 $x = y = 1$ ，证毕。 $\spadesuit$

但是显然 $1\ne 2$，除非你的小学老师当时在骗你。那我们到底哪里错了呢？

在推导第3个等式的时候，我们将等式的两边同除以了 $(x-y)$。

在我们的设定中 $(x-y)$ 是多少呢？0！而同除以零是一个未定义的行为，因此第三个等式是不成立的。

教训2

关于数字0，不要忘了考虑变量值等于0的情况。

陷阱3

主张3： $4 \le 1$

证明？ 我们知道 $-2 \le 1$ ，不等式两边同时平方，有 $4 \le 1$ 。 $\spadesuit$

概念检查

为了查看为什么这个证明是错的，问一下自己：如果 $a\le b$ 是真的， $|a|\le |b|$ 一定是真的吗？你能给出一个反例吗？

教训3

处理不等式的时候要特别小心负数，不要忘了考虑负数在不等式中的特殊性（除了上面的那种情况以外，常见的另一种情况是不等式两边同乘除负数的时候不等号方向要改变）。

2.8 证明的风格与实质

这是除了后面题目以外的最后一个小节了，我们会以一些总体的建议结尾。

1. 首先，养成三思而后行的习惯。

   • 当你从证明中的一步推导到下一步的时候，如果你不清楚为什么这个推导是合理的，那么你就跳步了，此时你需要回头多想一想。
   • 理论上，一个证明的每个步骤都必须通过应用定义或者应用一个普遍公理的方式来说明合理性。不过实际操作过程中，我们要做到怎样的地步就是一个暧昧的事情了。
     • 一方面，在我们的世界中，除了定义和公理以外，还有很多前辈们已经证明完毕的定理可供使用。
     • 另一方面，如果某个结论我们需要应用多次，为了避免重复书写，我们会把这个结论以引理的方式先证明出来，然后多次应用这个引理去证明最终的结论。
       • 这其实和我们通过定义函数，然后多次调用，从而避免重复书写代码的过程很像。所以我常常觉得数学是最高级的编程。

     概念检查

     将“如果 $a$ 是整数，那么 $(2a^2 + 2a)$ 也是整数” 拆解成基于定义和公理的证明。

   • 只有当你绝对自信你的**理由(justification)**是对的并且读者会自动同意它是对的，你才可以不加证明的给出一个理由。

2. 注意到在证明 $\sqrt{2}$ 是无理数的过程中，我们用到了两次 “如果一个数的平方是偶数，这个数也是偶数” 这个结论。

   • 这说明了这句话可能对于许多的证明过程来说是一个有用的事实。
   • 在一个更复杂的证明当中非常有用的一个附属的结论称之为 引理(lemma) 。将一个冗长的证明分解成几个引理通常是一个好主意。这就好像在编程的时候将一个大的任务分解成几个更小的 子过程(subroutine) 一样。
   • 更进一步地，让每一个引理尽可能地更具一般性，这样它未来可能会在别的证明当中被复用（就像你编程的时候写子过程一样）。
   • 引理和定理之间的界限并不是非常分明的。通常，当我们写一篇论文的时候，定理会是一些你想要输出给其他人看的命题，而引理是在证明你的定理的过程当中用到的本地的命题。
     • 从编程的视角来看，定理是对外的公共接口，引理是内部的私有函数。
   • 但是，也有一些引理（比如说 泵引理(pumping lemma) 和 提升引理(lifting lemma) ）可能比它们原本被用来证明的定理更加著名。

3. 最后，你应该记住这一讲的重点并不是我们证明的几个特定的语句，而是这些不同的证明策略，以及它们的逻辑结构。

   • 请确保你清楚地理解了它们，你将会在你后续的各种练习题（当然，我们没有考试，这只是一个教程，不是一个正式的大学课程）的证明当中用到它们。

后面的习题解答为了节省时间，我就稍微简略一点写了，如果哪个步骤不清楚的可以在评论区问。

2.9 练习题

2.9.1 证明一般化的定理2.2

一般化定理2.2的证明，使得它对任意的正整数 $n$ 都成立。

提示：假设 $n$ 是一个 $k$ 位数，用 $a_i$ 表示 $n$ 的每个数位，则

$n = \sum_{i=0}^{k-1} a_i\cdot 10^i$

解答

证明：

先证明一个引理：$\forall i \in\mathbb{N}, 9|10^{i} - 1$。

$10^{i} - 1 = (10 - 1)(10^{i-1} + 10^{i - 2} + ... + 10 + 1) = 9 \sum_{j=0}^{i-1} 10^j$

其中，$\sum_{j=0}^{i-1} 10^j \in\mathbb{N}$，所以 $9 | 10^i - 1$。

注：任何数都整除0。

记十进制表示下的k位数 $n = \overline{a_{k-1}a_{k-2}...a_2a_1a_0}$，则有

$n = \sum_{i=0}^{k-1} a_i\cdot 10^i = \sum_{i=0}^{k-1} a_i + \sum_{i=0}^{k-1} a_i\cdot (10^i - 1)$

而 $9 | \sum_{i=0}^{k-1} a_i$（已知条件） 且 $9 | 10^i - 1$ （已证引理） ，于是由定理2.1，我们有

$9 | (\sum_{i=0}^{k-1} a_i + \sum_{i=0}^{k-1} a_i\cdot (10^i - 1))$

即 $9 | n$ 。 $\square$

2.9.2 证明引理2.2

证明引理2.2。

提示：首先尝试直接证明，然后尝试证明逆否命题。哪一种证明方法更适合这个引理？

解答

这一题适合通过逆否命题来证明。

证明：原命题的逆否命题为“若 $a$ 是奇数，则 $a^2$ 也是奇数。” 不妨设 $a = 2k+1$ ，于是 $a^2 = (2k+1)^2 = 4k(k+1) + 1$ 也是奇数。 逆否命题成立，原命题成立。 $\square$

2.9.3 证明或证伪

对于下面的每个命题，证明其为真或者通过找反例的方式证明其为假。

1. $(\forall x\in\mathbb{N})(n\ is\ odd\Longrightarrow n^2 + 4n\ is\ odd)$。
2. $(\forall a,b\in\mathbb{R})(a+b\le 15 \Longrightarrow (a\le 11\vee b\le 4))$。
3. $(\forall r\in\mathbb{R})(r^2\ is\ irrational\Longrightarrow r\ is\ irrational)$。
4. $(\forall n\in\mathbb{Z}^+)(5n^3>n!)$。（注： $\mathbb{Z}^+$ 表示正整数集）

解答

1. 真。 证明：$n$ 是奇数，不妨设 $n = 2k+1, k\in\mathbb{N}$ ，则

$n^2 + 4n = (2k+1)^2 + 4(2k+1) = 4(k^2 + 3k + 1) + 1$

于是 $n^2 + 4n$ 为奇数。 $\square$

2. 真。 证明：反证法。 若 $a > 11 \wedge b > 4$ ， 则 $a + b > 11 + 4 = 15$ 与 $a + b \le 15$ 矛盾。 $\square$

3. 真。 证明：反证法。 若 $r\in\mathbb{Q}$，不妨设 $r = \frac{q}{p}$ ， $p,q\in\mathbb{Z}$ ， $(p,q) = 1$ ， 则

$r^2 = \frac{q^2}{p^2}, q^2\in\mathbb{Z}, p^2\in\mathbb{Z}$

于是 $r^2\in\mathbb{Q}$ ， 与 $r^2\not\in\mathbb{Q}$ 矛盾。 $\square$

4. 假。反例：取 $n = 7$ ， 则 $5n^3 = 1715 < 5040 = n!$ 。

2.9.4 费马矛盾

求证对于任意整数 $n > 3$ ， $2^{\frac1n}$ 不是有理数。

提示：使用 费马大定理(Fermat’s Last Theorem) —— $\nexists a,b,c\in\mathbb{Z}^+ s.t. a^n + b^n = c^n (n\ge 3)$

解答

证明：反证法。 若 $2^{\frac1n}$ 是有理数， 记为 $2^{\frac1n} = \frac{q}p (p,q\in\mathbb{Z}^+ \wedge (p,q) = 1)$ ，于是

$2^{\frac1n} = \frac{q}p \Leftrightarrow 2 = \frac{q^n}{p^n} \Leftrightarrow q^n = p^n + p^n$

这与费马大定理是矛盾的。 $\square$

2.9.5 鸽笼原理

求证：将 $n + 1$ 个球放到 $n$ 个盒子里，无论怎么放，至少有一个盒子里会有两个球。

解答

证明：反证法。 若每个盒子都最多只有1个球，那么 $n$ 个盒子一共最多能放 $n$ 个球，这与我们放入了 $n + 1$ 个球是矛盾的。 $\square$

2.9.6 朋友个数

求证：如果聚会上有 n (n > 2) 个人，至少有两个人在聚会上的朋友数量是一样的。假设朋友关系是相互的，即如果熊桑是蜜蜂的朋友，那么蜜蜂也是熊桑的朋友。

提示：鸽笼原理告诉我们，如果将n个东西放进m个容器里面，且 n > m，那么至少有一个容器里面有不止一个东西。你可以直接用这个定理，不需要重新书写证明。

解答

证明：考虑到聚会上一共有 n 个人，所以每个人最多只能有 n - 1 个朋友。将聚会上每个人的朋友数量视为鸽笼，则我们最多有“0个朋友、1个朋友、2个朋友、...、n - 1个朋友”这n个笼子。

将参加聚会的每个人视为鸽子，则我们需要将这n个鸽子放到n个鸽笼里面。

但是，我们发现“0个朋友”与“n-1个朋友”这两个鸽笼里面不能同时有鸽子，因为它们互相矛盾。

如果有人有0个朋友，就不可能有人有n-1个朋友；如果有人有n-1个朋友，就不可能有人有0个朋友。

因此，我们实际上只有n-1个能用鸽笼，也就是说，我们其实需要将n个鸽子放到n-1个鸽笼里面。

根据鸽笼原理，至少有一个笼子里不止一个鸽子，于是这个鸽笼中的两只鸽子对应的人的朋友数量相同。

也就是说，聚会上至少有两个人的朋友数量是一样的。 $\square$

2.10 作业题

2.10.1 集合操作保留

对于一个函数 $f$ ，定义集合 $X$ 的 像(image) 为集合 $f(X) = \{y|y=f(x), x\in X\}$ 。

定义集合 $Y$ 的 原像(inverse image / preimage) 为集合 $f^{-1}(Y) = \{x|f(x) \in Y\}$ 。

证明下面的4句话，其中 $A$ 和 $B$ 都是集合。

1. $f^{-1}(A\cap B) = f^{-1}(A)\cap f^{-1}(B)$。
2. $f^{-1}(A - B) = f^{-1}(A) - f^{-1}(B)$。
3. $f(A\cap B)\subseteq f(A)\cap f(B)$ 并给出等号不成立的例子。
4. $f(A - B) \supseteq f(A) - f(B)$ 并给出等号不成立的例子。

通过这几句话你会发现，原像是可以保留集合操作的，而像不可以。（这是由函数的性质决定的）

回忆：对于集合 $X$ 和 $Y$ ， $X = Y$ 当且仅当 $X \subseteq Y \wedge Y\subseteq X$ 。 要证 $X \subseteq Y$ ， 只需证 $(\forall x)(x\in X \Longrightarrow x\in Y)$。

解答

1. 证明：任取 $x\in f^{-1}(A\cap B)$ ，有

   $f(x)\in A\cap B \Rightarrow f(x) \in A \wedge f(x) \in B \Rightarrow x\in f^{-1}(A) \wedge x\in f^{-1}(B)$

   即 $x\in f^{-1}(A) \cap f^{-1}(B)$ ，于是 $f^{-1}(A\cap B) \subseteq f^{-1}(A)\cap f^{-1}(B)$。 任取 $x\in f^{-1}(A) \cap f^{-1}(B)$ ，有

   $x \in f^{-1}(A) \wedge x\in f^{-1}(B) \Rightarrow f(x) \in A \wedge f(x) \in B \Rightarrow f(x) \in A\cap B$

   即 $x\in f^{-1}(A\cap B)$ ，于是 $f^{-1}(A)\cap f^{-1}(B) \subseteq f^{-1}(A\cap B)$。 综上，$f^{-1}(A\cap B) = f^{-1}(A)\cap f^{-1}(B)$ 。 $\square$

2. 证明：（详细的过程和1类似，这里我就简略地写了）

   $x \in f^{-1}(A - B) \equiv f(x) \in A - B \equiv f(x) \in A \wedge f(x)\not\in B$
   $\equiv x \in f^{-1}(A) \wedge x\notin f^{-1}(B) \equiv x \in f^{-1}(A) - f^{-1}(B)$

   $\therefore f^{-1}(A - B) = f^{-1}(A) - f^{-1}(B)$ 。 $\square$

3. 证明：任取 $y\in f(A\cap B)$ ，有

   $\exists x \in A\cap B, y = f(x) \Rightarrow \exists x \in A, y = f(x) \wedge \exists x \in B, y = f(x)$
   $\Rightarrow y\in f(A) \wedge y\in f(B)$

   即 $y\in f(A) \cap f(B)$ ，于是 $f(A\cap B)\subseteq f(A)\cap f(B)$。

   等号取不到的例子： 考虑 $a\in A, b\in B$ 满足 $f(a) = f(b)$ ，但 $A \cap B = \emptyset$ 的时候，$f(a) = f(b) \in f(A) \cap f(B)$，但 $f(A\cap B) = \emptyset$ 。

4. 证明：任取 $y\in f(A) - f(B)$ ，有

   $y \in f(A) \wedge y \notin f(B) \Rightarrow \exists x \in A, y = f(x) \wedge \nexists x \in B, y = f(x)$
   $\Rightarrow \exists x \in A - B, y = f(x)$

   即 $y\in f(A - B)$ ，于是 $f(A) - f(B)\subseteq f(A - B)$ 。 $\square$

   等号取不到的例子： 考虑 $B = \{0\}, A = \{0,1\}, f(1) = f(0) = 0$ 的情况。我们有 $A - B = \{1\}$ ，则 $f(A - B) = \{0\}$ ，而 $f(A) = f(B) = \{0\}$ ， $f(A) - f(B) = \emptyset$ 。

2.10.2 鹅卵石

假设你有一个长方形的鹅卵石阵列（就像广播体操的方阵一样，摆成几行几列），这些鹅卵石要么是红的，要么是蓝的。假设无论你以何种方式，从每一列中拿走一个鹅卵石，你拿走的鹅卵石当中一定有一个红色的。求证：一定存在某一列鹅卵石全部是红色的。

解答

证明：考虑逆否命题。如果不存在任何一列鹅卵石是全红色的，即每一列都至少有一个蓝色的鹅卵石。那么我从每一列当中拿走一个蓝色的鹅卵石，拿走的鹅卵石当中一个红色的都没有。逆否命题成立，原命题成立。

注：原命题中的“无论以何种方式”相当于全称量词，其逆否命题中“从每一列拿走一个蓝色”相当于存在量词。

2.10.3 逆否命题

求证：$x + y < z + w \Longrightarrow x < z \vee y < w$。（用直接证明和逆否证明两种方式证明）

解答

1. 直接证明。 证明：若 $x < z$ ，则结论已然成立；若 $x \ge z$ ， 则 $y < w + (z - x) \le w + 0 = w$ ，结论依然成立。综上，原命题为真。 $\square$

这里用到了“proof by case”的技巧，数学上常用的分类讨论思想。

2. 逆否证明。 证明：考虑逆否命题。如果 $x \ge z \vee y\ge w$ ，我们有 $x + y \ge z + w$。 逆否命题为真，原命题为真。 $\square$

进度

恭喜完成离散数学与概率论第2讲《证明方法》所有内容的学习！