数学复健2-证明

小故事

小镇上有一位铁匠，发明了一种给马蹄钉淬火的方法。

他试了第一块铁，成功了；第二块成功；第三块、第四块……连续一百次都成功。于是他在店门口挂出一块牌子：

任何铁块，只要用这种方法淬火，就一定不会断。

一位年轻学徒没有争论，只是拿来一块更薄、更脆的铁，按照完全相同的方法处理。铁块断了。

铁匠的一百次实验并没有毫无价值。它们说明方法可能有效，帮助我们形成猜想，也告诉我们应该去哪里寻找规律。但它们没有证明“任何铁块”都不会断。

后来，铁匠重新描述自己的方法：

对于厚度、含碳量和温度都满足某些条件的铁块，这种方法能保证淬火后的强度不低于某个数值。

这句话虽然没有原来的牌子醒目，却更接近科学。它明确了研究对象，也明确了条件和结论。

数学中的证明做的事情与这位学徒相反又相似：

反例负责指出一句全称断言哪里会失败；
证明负责说明在给定条件下，结论为什么对所有对象都成立。

历史插页

欧几里得编纂了《几何原本》，试图建立一种“从少数起点出发，逐步推出更多结论”的秩序

命题

定义

一个能够明确判断为真或假的陈述，叫作命题。

判断为真的命题叫做真命题，判断为假的命题叫做假命题

例如：

$$
2+3=5
$$

是一个真命题；

而

$$
2+3=6
$$

是一个假命题。

如果一个命题讨论某个集合中的每一个对象，并以“对于所有”开始，它叫作全称命题。

谓词

带有变量、代入变量后可以判断真假的表达式，叫作谓词。

例如：

$$
P(x):\quad x^2\ge0
$$

是关于 $x$ 的谓词，对任意实数 $x$，命题 $P(x)$ 都为真。

复合命题

数学中经常需要把几个命题组合起来。先设 $P$ 和 $Q$ 是两个命题。

否定（非）

命题 $P$ 的否定记作

$$
\neg P.
$$

它的真值与 $P$ 相反：

$P$	$\neg P$
$\mathrm T$	$\mathrm F$
$\mathrm F$	$\mathrm T$

如果

$$
P:\quad 2+3=5,
$$

那么

$$
\neg P:\quad 2+3\neq5.
$$

合取（与）

命题 $P$ 与 $Q$ 的合取记作

$$
P\land Q,
$$

读作“$P$ 且 $Q$”。只有当两个命题都为真时，合取才为真。

$P$	$Q$	$P\land Q$
$\mathrm T$	$\mathrm T$	$\mathrm T$
$\mathrm T$	$\mathrm F$	$\mathrm F$
$\mathrm F$	$\mathrm T$	$\mathrm F$
$\mathrm F$	$\mathrm F$	$\mathrm F$

析取（或）

命题 $P$ 与 $Q$ 的析取记作

$$
P\lor Q,
$$

读作“$P$ 或 $Q$”。在数学逻辑中，“或”通常是包容性的：只要至少一个命题为真，析取就为真。

$P$	$Q$	$P\lor Q$
$\mathrm T$	$\mathrm T$	$\mathrm T$
$\mathrm T$	$\mathrm F$	$\mathrm T$
$\mathrm F$	$\mathrm T$	$\mathrm T$
$\mathrm F$	$\mathrm F$	$\mathrm F$

蕴含

命题 $P$ 蕴含命题 $Q$，记作

$$
P\Longrightarrow Q.
$$

它读作“如果 $P$，那么 $Q$”。

蕴含只有在一种情况下为假：

$$
P=\mathrm T,\qquad Q=\mathrm F.
$$

因为这时我们承诺了“只要 $P$ 发生，$Q$ 就发生”，但 $P$ 确实发生而 $Q$ 没有发生。

$P$	$Q$	$P\Longrightarrow Q$
$\mathrm T$	$\mathrm T$	$\mathrm T$
$\mathrm T$	$\mathrm F$	$\mathrm F$
$\mathrm F$	$\mathrm T$	$\mathrm T$
$\mathrm F$	$\mathrm F$	$\mathrm T$

最后两行常常让人困惑。如果 $P$ 根本没有发生，那么“如果 $P$，那么 $Q$”没有被反驳，因此在形式逻辑中仍记为真。这种定义使蕴含能稳定地进行推理。

例如：

$$
x>2\Longrightarrow x^2>4.
$$

当 $x=3$ 时，前件和后件都为真；当 $x=1$ 时，前件为假，所以这条蕴含没有被 $x=1$ 反驳。

等价

命题 $P$ 与 $Q$ 等价，记作

$$
P\Longleftrightarrow Q,
$$

意思是两个方向的蕴含都成立：

$$
P\Longleftrightarrow Q
\quad\Longleftrightarrow\quad
(P\Longrightarrow Q)\land(Q\Longrightarrow P).
$$

例如，对实数 $x$：

$$
x^2=0\Longleftrightarrow x=0.
$$

这表示两边总是同时为真或同时为假。

量词

全称量词

符号

$$
\forall
$$

读作“对于所有”。若谓词 $P(x)$ 对集合 $X$ 中的每个元素都成立，就写作

$$
\forall x\in X,\quad P(x).
$$

例如：

$$
\forall x\in\mathbb R,\quad x^2\ge0.
$$

它表示每一个实数的平方都非负。

存在量词

符号

$$
\exists
$$

读作“存在至少一个”。如果集合 $X$ 中至少有一个元素使 $P(x)$ 成立，就写作

$$
\exists x\in X,\quad P(x).
$$

例如：

$$
\exists x\in\mathbb R,\quad x^2=1.
$$

因为 $x=1$ 和 $x=-1$ 都可以。

存在唯一

符号

$$
\exists!
$$

读作“存在唯一一个”。表达式

$$
\exists!x\in X,\quad P(x)
$$

表示：

至少存在一个 $x\in X$ 使 $P(x)$ 成立；
任意两个满足 $P$ 的元素必须相同。

完整地写成：

$$
\exists x\in X,\quad
\left(
P(x)\land
\forall y\in X,\ P(y)\Longrightarrow y=x
\right).
$$

函数定义中的“每个输入对应唯一输出”，就是一个存在唯一的陈述。

否定量词

量词的否定是证明中非常重要的工具：

$$
\neg\left(\forall x\in X,\ P(x)\right)
\Longleftrightarrow
\exists x\in X,\ \neg P(x),
$$

$$
\neg\left(\exists x\in X,\ P(x)\right)
\Longleftrightarrow
\forall x\in X,\ \neg P(x).
$$

用普通语言说：

“不是所有天鹅都是白色的”等价于“存在一只不是白色的天鹅”；
“没有任何整数满足某条件”等价于“每个整数都不满足该条件”。

全称命题的否定，就是一个存在命题。

量词顺序

量词的顺序不能随意交换。

比较：

$$
\forall x\in\mathbb R,\ \exists y\in\mathbb R,\quad y>x,
$$

与

$$
\exists y\in\mathbb R,\ \forall x\in\mathbb R,\quad y>x.
$$

第一句话为真：给定任意 $x$，取 $y=x+1$ 即可。

第二句话为假：不存在一个固定的实数 $y$，比所有实数 $x$ 都大。

这就是数学中“对每个输入，都可以选择一个答案”和“先选一个答案，它必须适用于所有输入”的区别。

条件

前件与后件

在蕴含

$$
P\Longrightarrow Q
$$

中，$P$ 叫作前件，$Q$ 叫作后件。

如果一个条件 $P$ 足以保证 $Q$，就说 $P$ 是 $Q$ 的充分条件。

如果 $Q$ 要成立就必须有 $P$，就说 $P$ 是 $Q$ 的必要条件。

因此：

$$
P\Longrightarrow Q
\quad\Longleftrightarrow\quad
\begin{cases}
P\text{ 是 }Q\text{ 的充分条件};\
Q\text{ 是 }P\text{ 的必要条件}.
\end{cases}
$$

逆命题、逆否命题

原命题是

$$
P\Longrightarrow Q.
$$

交换前件和后件，得到逆命题：

$$
Q\Longrightarrow P.
$$

同时否定前件和后件，得到逆否命题：

$$
\neg Q\Longrightarrow\neg P.
$$

一个命题总与它的逆否命题等价：

$$
P\Longrightarrow Q
\quad\Longleftrightarrow\quad
\neg Q\Longrightarrow\neg P.
$$

但原命题与逆命题不一定等价。

证明

定义规定一个概念的含义。例如“整数 $x$ 是偶数，当且仅当存在整数 $k$ 使 $x=2k$”；
命题是一个可以判断真假的陈述；
引理是为了证明其他结论而准备的小命题；
定理是具有重要意义、并且已经证明的命题；
推论是从定理直接得到的结论；
猜想是尚未证明、但被认为可能成立的命题。

一个证明是由定义、已知命题和合法推理组成的有限步骤序列。它的目标是说明某个命题为什么必然成立，而不是说明它曾经成功过很多次。

证明通常有三个部分：

假设：我们允许暂时使用的条件；
推理：从已知对象得到新对象；
结论：最终要证明的命题。

如果要证明

$$
\forall x\in X,\quad P(x),
$$

通常先任取一个

$$
x\in X,
$$

然后在不对 $x$ 添加额外条件的前提下证明 $P(x)$。因为 $x$ 是任意选取的，所以结论对 $X$ 中所有元素成立。

直接证明：使用定义

命题：两个偶数之和仍然是偶数。

证明：

设 $a$ 和 $b$ 是偶数。根据偶数定义，存在整数 $m,n$，使得

$$
a=2m,\qquad b=2n.
$$

于是

$$
a+b
=2m+2n
=2(m+n).
$$

因为整数的和 $m+n$ 仍是整数，所以根据偶数定义，$a+b$ 是偶数。证毕。

这份证明几乎没有计算技巧。它只做了一件关键的事：把“偶数”替换成它的定义。

直接证明：函数的单射性

回忆函数 $f:X\to Y$ 是单射，如果

$$
\forall x_1,x_2\in X,\quad
f(x_1)=f(x_2)\Longrightarrow x_1=x_2.
$$

命题：函数

$$
f:\mathbb R\to\mathbb R,\qquad f(x)=3x+1
$$

是单射。

证明：

取任意 $x_1,x_2\in\mathbb R$，并假设

$$
f(x_1)=f(x_2).
$$

代入函数公式：

$$
3x_1+1=3x_2+1.
$$

两边减去 $1$，再除以非零数 $3$，得到

$$
x_1=x_2.
$$

因此 $f$ 满足单射的定义，所以它是单射。证毕。

注意证明的开头不是“设 $x_1\neq x_2$”，而是从单射定义要求的条件 $f(x_1)=f(x_2)$ 开始。这是读懂定义后才会自然选择的方向。

逆否证明

有些命题直接证明不方便，但逆否命题很容易。

命题：如果整数 $n^2$ 是奇数，那么 $n$ 是奇数。

它的逆否命题是：如果整数 $n$ 是偶数，那么 $n^2$ 是偶数。

若 $n$ 是偶数，则存在整数 $k$ 使

$$
n=2k.
$$

于是

$$
n^2=(2k)^2=4k^2=2(2k^2),
$$
这里显然 $n^2$ 是偶数。逆否命题成立，因此原命题成立。证毕。

反证法

反证法先假设要证明的命题不成立，再从这个假设推出矛盾。

一个矛盾是同时要求某命题为真又为假的情况，例如

$$
P\land\neg P.
$$

命题：不存在有理数 $r$ 满足

$$
r^2=2.
$$

证明：

假设存在这样的有理数。一个有理数可以写成

$$
r=\frac ab,
$$

其中 $a,b\in\mathbb Z$，$b\neq0$，并且分数已经约分到最简形式，即 $a$ 与 $b$ 没有共同的非单位因子。

由 $r^2=2$ 得

$$
\frac{a^2}{b^2}=2,
$$

所以

$$
a^2=2b^2.
$$
观察可知 $a^2$ 必然是偶数。根据先前的结论，若 $a$ 是奇数，则 $a^2$ 也是奇数。所以 $a$ 必须是偶数。

于是存在整数 $k$ 使

$$
a=2k.
$$

代回：

$$
4k^2=2b^2,
$$

从而

$$
b^2=2k^2.
$$

同理，$b$ 也是偶数。

但这与 $a/b$ 已经是最简形式矛盾，因为 $a$ 和 $b$ 都能被 $2$ 整除。假设不成立，因此不存在有理数 $r$ 满足 $r^2=2$。证毕。

这个证明的力量不在于算出了 $\sqrt2$ 的小数展开，而在于它证明了：无论我们怎样尝试用两个整数的比表示 $\sqrt2$，都会陷入无限约分。

存在性证明

要证明

$$
\exists x\in X,\quad P(x),
$$

只需要构造一个具体的 $x$，并验证 $P(x)$。

例如：

$$
\exists n\in\mathbb N,\quad n^2+n\text{ 是偶数}.
$$

取 $n=1$，则

$$
n^2+n=1^2+1=2,
$$

而 $2$ 是偶数。因此命题成立。

这个证明不需要说明所有自然数都有这个性质，因为原命题只要求存在一个。

数学归纳法

数学归纳法适合证明关于自然数的全称命题。

设 $P(n)$ 是关于自然数 $n$ 的命题。若满足：

基础步骤：$P(0)$ 成立；
归纳步骤：对任意自然数 $k$，若 $P(k)$ 成立，则 $P(k+1)$ 成立；

那么可以推出

$$
\forall n\in\mathbb N,\quad P(n).
$$

归纳步骤中的假设

$$
P(k)
$$

叫作归纳假设。它不是把结论偷偷当成已知，而是暂时假设第 $k$ 个位置成立，用来证明下一个位置也成立。

命题：对所有 $n\in\mathbb N$，

$$
0+1+2+\cdots+n=\frac{n(n+1)}2.
$$

证明：

定义

$$
P(n):\quad 0+1+2+\cdots+n=\frac{n(n+1)}2.
$$

基础步骤：当 $n=0$ 时，

$$
0=\frac{0\cdot1}{2},
$$

所以 $P(0)$ 成立。

归纳步骤：假设 $P(k)$ 成立，即

$$
0+1+\cdots+k=\frac{k(k+1)}2.
$$

那么

$$
\begin{aligned}
0+1+\cdots+k+(k+1)
&=\frac{k(k+1)}2+(k+1)\
&=\frac{k(k+1)+2(k+1)}2\
&=\frac{(k+1)(k+2)}2.
\end{aligned}
$$

这正是 $P(k+1)$。因此由数学归纳法，命题对所有自然数 $n$ 成立。证毕。

归纳法像一排站好的骨牌：基础步骤推倒第一块；归纳步骤保证每一块倒下都会推倒下一块。

反例：寻找命题的边界

一个反例足以推翻全称命题

要否定

$$
\forall x\in X,\quad P(x),
$$

只需找到一个 $x_0\in X$，使得

$$
\neg P(x_0).
$$

这样的 $x_0$ 叫作反例。

例如，证明命题

$$
\forall x\in\mathbb R,\quad x^2\ge x
$$

是假的

取

$$
x_0=\frac12,
$$

则

$$
x_0^2=\frac14<\frac12=x_0.
$$

所以 $1/2$ 是反例。

例子不能证明全称命题

无论我们验证多少个例子，都只覆盖了有限多个对象。全称命题的对象可能有无限多个。

例如：

$$
1^2+1=2,\qquad
2^2+2=6,\qquad
3^2+3=12.
$$

这些例子说明 $n^2+n$ 似乎总是偶数，但真正的证明必须从任意自然数 $n$ 出发，而不是只列出几个值。

反例不一定告诉你正确命题

命题

$$
\forall x\in\mathbb R,\quad x^2\ge x
$$

被 $x=1/2$ 推翻后，我们只知道原命题太强，并不知道正确版本是什么。

观察不等式：

$$
x^2-x=x(x-1).
$$

当 $x\le0$ 或 $x\ge1$ 时，$x^2\ge x$；当 $0<x<1$ 时，$x^2<x$。

反例负责指出边界，进一步分析才负责发现准确的命题。