3.2 归纳法与递归算术

递归规则告诉我们怎样计算加法和乘法。本节要解决的问题是：这些规则为什么能够推出熟悉的代数定律？证明顺序很重要：先建立加法恒等式，再把它们用于乘法证明，最后用消去律支持更大数系的构造。

递归加法

定义

加法的递归定义

对自然数 $a$ 和 $b$，加法定义为：

• $a + 0 = a$
• $a + S(b) = S(a + b)$

这是一个递归定义。你先知道第二个输入是 $0$ 时的结果，再由较早 的值推出之后的每一步。

例题

由定义计算 $2 + 3$

把 $2$ 写成 $S(S(0))$，把 $3$ 写成 $S(S(S(0)))$。

那么：

$2 + 3 = 2 + S(S(S(0)))$

$= S(2 + S(S(0)))$

$= S(S(2 + S(0)))$

$= S(S(S(2 + 0)))$

$= S(S(S(2)))$。

这就是通常叫做 $5$ 的数。

常见错误

递归公式本身还不是证明

这些公式只告诉你运算怎样定义，不会自动证明一个关于所有自然数 的命题。要做那一步，你还是要用归纳法。

递归乘法

乘法也可以用同一种递归方式引入。加法已经定义好之后，乘法可以理解为由 第二个输入控制的重复加法。

定义

乘法的递归定义

对自然数 $a$ 和 $b$，乘法定义为：

• $a \cdot 0 = 0$
• $a \cdot S(b) = (a \cdot b) + a$

基本情况说明：把 $a$ 加零次得到 $0$。递归步骤说明：如果已经知道 $a \cdot b$，那么乘以后继 $S(b)$ 就是在原来结果上再加一个 $a$。

例题

由定义计算 $3 \cdot 2$

把 $2$ 写成 $S(S(0))$。那么

$$3\cdot 2 =3\cdot S(S(0)) =(3\cdot S(0))+3$$

而

$$3\cdot S(0)=(3\cdot 0)+3=0+3=3.$$

因此

$$3\cdot 2=3+3=6.$$

熟悉的“三取两次”其实是由这个递归规则重新得到的。

归纳法真正证明什么

递归定义能够支撑普通代数定律，是因为背后有归纳原理。典型证明具有以下 形式。

定理

归纳原理

设 $P(n)$ 是关于自然数 $n$ 的命题。如果：

1. $P(0)$ 成立；
2. 只要 $P(n)$ 成立，就能推出 $P(S(n))$ 成立；

那么 $P(n)$ 对每个 $n\in N$ 都成立。

基本情况把命题固定在起点 $0$。归纳步骤证明真值会在做一次后继时被保留。 两者合起来，排除了命题一开始成立但后面突然失败的可能。

跟随归纳论证

下面的步骤器把一个归纳证明拆成基本情况、归纳假设、归纳步骤和结论。

建立后继恒等式

证明：$S(a) + b = S(a + b)$ 对 $b$ 归纳

我们对 $b\in N$ 证明这个命题。

基本情况：当 $b = 0$，

$S(a) + 0 = S(a) = S(a + 0)$。

归纳步骤：假设 $S(a) + b = S(a + b)$。那么

$S(a) + S(b) = S(S(a) + b)$，因为加法是这样定义的，

$= S(S(a + b))$，用归纳假设，

$= S(a + S(b))$，再用一次加法定义。

所以只要对 $b$ 成立，它就对 $S(b)$ 也成立。

为什么 $a \cdot S(b) = a \cdot b + a$ 是定义

对乘法来说，公式

$$a\cdot S(b)=(a\cdot b)+a$$

不是在乘法已知之后才证明出来的定理，而是乘法本身的递归步骤。之后的 代数定律，例如分配律，才是需要用归纳法证明的命题。

代数定律是在定义之后证明的

加法与乘法用递归方式定义之后，熟悉的算术定律就成为需要证明的定理。

定理

用归纳法证明的算术定律例子

对自然数 $a$、$b$、$c$，可以证明：

$$a+b=b+a,$$$$a\cdot(b+c)=a\cdot b+a\cdot c,$$

以及

$$a\cdot b=b\cdot a.$$

重点是逻辑顺序：先定义运算，再证明它们具有我们熟悉的运算性质。

证明：加法的结合律

固定 $a$、$b$，对 $c$ 归纳证明

$$(a+b)+c=a+(b+c).$$

当 $c=0$ 时，两边都等于 $a+b$。若归纳假设对 $c$ 成立，则

$$\begin{aligned} (a+b)+S(c)&=S((a+b)+c)\\ &=S(a+(b+c))\\ &=a+S(b+c)\\ &=a+(b+S(c)) \end{aligned}$$

第二行使用归纳假设，第一行和最后一行使用加法的递归规则。因此，在后面的证明 使用它来重排各项以前，加法结合律已经被证明。

证明：$0 \cdot a = 0$

对 $a$ 归纳。基本情形是定义给出的 $0\cdot 0=0$。若 $0\cdot a=0$，则

$$0\cdot S(a)=0\cdot a+0=0+0=0$$

所以 $0\cdot a=0$ 对每个自然数 $a$ 成立。

从递归规则走向证明

后继模式有两种相关但不同的用途。递归定义告诉我们如何由较早的值计算新值； 归纳证明则告诉我们如何把命题推广到每一个自然数。计算可以提示定理，但不能 代替证明。

例题

逐步计算 $2 \cdot 3$

利用 $3=S(S(S(0)))$ 与乘法规则，

$$\begin{aligned} 2\cdot3 &=2\cdot S(S(S(0)))\\ &=(2\cdot S(S(0)))+2\\ &=((2\cdot S(0))+2)+2\\ &=(((2\cdot0)+2)+2)+2\\ &=((0+2)+2)+2\\ &=2+2+2=6 \end{aligned}$$

每一行都把第二个输入降低，直到到达基本情形 $2\cdot0=0$；之后才化简得到的 加法。

完整证明 $0+n=n$

令 $P(n)$ 表示命题 $0+n=n$。

基本情形由递归加法规则给出：$0+0=0$。

归纳步骤中，假设 $P(n)$ 成立，即 $0+n=n$。则

$$0+S(n)=S(0+n)=S(n)$$

第一个等号来自递归定义，第二个等号使用归纳假设。因此 $P(S(n))$ 由 $P(n)$ 推出。归纳法遂得 $0+n=n$ 对每个 $n\in N$ 成立。

这个小证明提供了后续算术所需要的恒等式，也说明为什么应明确写出归纳假设， 不能只说“规律会继续”。

定理

加法在归纳引理之后是交换的

对所有 $a,b\in N$，都有 $a+b=b+a$。

加法交换律的证明

固定 $a$，对 $b$ 归纳。

当 $b=0$ 时，

$$a+0=a=0+a$$

前一个等号是定义，后一个等号使用引理 $0+a=a$。

现在假设 $a+b=b+a$。则

$$\begin{aligned} a+S(b)&=S(a+b)\\ &=S(b+a)\\ &=S(b)+a \end{aligned}$$

中间等号使用归纳假设，最后一个等号使用左边后继恒等式。因此 $S(b)$ 情况 成立，归纳完成。 这正是后来证明算术定律的模式：先证明递归方向直接给出的恒等式，再用这些恒等 式证明熟悉的对称规律。

证明：自然数中的消去律

我们对 $a$ 归纳证明左消去律

$$a+b=a+c\quad\Longrightarrow\quad b=c$$

当 $a=0$ 时，$0+b=0+c$ 根据 $0+n=n$ 化为 $b=c$。归纳步骤中，若 $S(a)+b=S(a)+c$，先用左侧后继引理和后继映射的单射性得到 $a+b=a+c$，再用归纳 假设得到 $b=c$。这条自然数消去律正是之后证明整数等价关系传递性所需的事实。

常见错误

算几个例子不等于归纳

计算 $2+0$、$2+1$ 和 $2+2$ 只能检查三个输入。归纳证明必须命名任意的 $n$， 证明基本情形，并说明命题如何从 $n$ 传到 $S(n)$。

思考检查

递归定义和归纳假设有什么区别？

说明它们各自允许做什么。

解答 · 答案

递归定义通过把输入降到基本情形来给出运算值。归纳假设则是假定命题对某个任意 固定的 $n$ 成立，再用它证明 $S(n)$ 的命题。

分配律的完整归纳证明

固定 $a$ 与 $b$，令

$$P(c):\quad a\cdot(b+c)=a\cdot b+a\cdot c$$

当 $c=0$ 时，

$$a\cdot(b+0)=a\cdot b=a\cdot b+0=a\cdot b+a\cdot0$$

假设 $P(c)$ 成立。因为 $b+S(c)=S(b+c)$，由递归乘法规则与归纳假设，

$$\begin{aligned} a\cdot(b+S(c)) &=a\cdot S(b+c)\\ &=a\cdot(b+c)+a\\ &=(a\cdot b+a\cdot c)+a\\ &=a\cdot b+(a\cdot c+a)\\ &=a\cdot b+a\cdot S(c) \end{aligned}$$

倒数第二个等号使用加法结合律，而结合律本身已由较早的归纳证明。于是 $P(S(c))$ 成立，分配律对每个自然数 $c$ 成立。

证明：乘法的结合律

我们对 $c$ 归纳证明 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$，并使用已经证明的分配律和加法定律。基本情形为

$$(a\cdot b)\cdot0=0=a\cdot0=a\cdot(b\cdot0)$$

在归纳步骤中，由归纳假设和分配律，

$$\begin{aligned} (a\cdot b)\cdot S(c) &=(a\cdot b)\cdot c+a\cdot b\\ &=a\cdot(b\cdot c)+a\cdot b\\ &=a\cdot(b\cdot c+b)\\ &=a\cdot(b\cdot S(c)) \end{aligned}$$

最后一个等号使用乘法的递归规则，完成归纳。正自然数的乘积也为正：写成 $r=S(r')$、$s=S(s')$，则

$$r\cdot s=r\cdot S(s')=r\cdot s'+S(r')=S(r\cdot s'+r')\ne0.$$

最后一步使用加法的递归定义及零不是后继的公理。这将用于 $Z$ 中的带符号代表元论证。

如何组织乘法交换律的证明

递归定义展开的是第二个输入，因此不能只把符号交换，就断言 $a\cdot b=b\cdot a$。先对 $a$ 作归纳，证明辅助引理

$$S(b)\cdot a=b\cdot a+a$$

当 $a=0$ 时两边都是 $0$。若归纳假设对 $a$ 成立，使用第二个输入的后继规则，再使用归纳假设，得到

$$S(b)\cdot S(a)=S(b)\cdot a+S(b) =(b\cdot a+a)+S(b)$$

前面由递归加法证明的结合律和交换律可以重排这个式子，正好得到相应归纳步骤所需的等式：使用 $S(x)=x+1$ 以及递归展开 $b\cdot S(a)=b\cdot a+b$，目标右侧是 $b\cdot S(a)+S(a)=b\cdot a+b+a+1=b\cdot a+a+S(b)$。因此这个辅助引理补上了乘法定义的方向。接着对 $b$ 归纳证明交换律：基础步是 $a\cdot 0=0=0\cdot a$；后继步为

$$a\cdot S(b)=a\cdot b+a=b\cdot a+a=S(b)\cdot a$$

这个证明安排很关键：每次重排都引用已经证明的加法性质，每次展开都遵循给定的递归定义。这样可以避免循环论证，即因为记号看起来对称，就把乘法交换律当作已知。

例题

证明 $n+1=1+n$，而不是先假设交换律

写 $1=S(0)$。首先由递归规则，

$$n+1=n+S(0)=S(n+0)=S(n)$$

然后对 $S(n)=1+n$ 归纳。当 $n=0$ 时两边都是 $S(0)$。若 $S(n)=1+n$，则

$$S(S(n))=S(1+n)=1+S(n)$$

最后一个等号使用递归规则。因此 $S(n)=1+n$ 对所有 $n$ 成立；合并两条恒等式便 得到 $n+1=1+n$。

快问快答

思考检查

加法的递归定义中，基本情况是哪一句？

想想哪一个输入先被固定。

解答 · 答案

基本情况是 $a + 0 = a$。

思考检查

乘法的递归定义中，基本情况是哪一句？

看第二个输入。

解答 · 答案

基本情况是 $a \cdot 0 = 0$。

思考检查

按递归规则，$a \cdot S(b)$ 等于什么？

用前一个乘法值来表达下一步。

解答 · 答案

它等于 $(a \cdot b) + a$。

思考检查

在归纳证明中，归纳假设是什么？

用一句短句回答。

解答 · 答案

它是假设命题对某个固定的自然数 $n$ 成立，然后再证 $S(n)$ 的情况。

先备连结

如果你想先看自然数的正式设置，可以先读 3.1 自然数与 Peano 公理。