3.2 归纳法与递归算术

递归规则给出了加法和乘法的计算方法，但交换律与分配律并没有直接出现在这些规则中。证明顺序很重要：先建立加法恒等式，再把它们用于乘法证明，最后用消去律支持更大数系的构造。

递归规则为什么定义唯一的函数

归纳法在函数已经存在后证明它的性质；递归定理同时提供存在性与唯一性。这里的集合论背景允许子集、幂集与交集；在 $N$ 上使用后继单射、零不是后继以及归纳公理。

定理 3.2.1

（自然数递归定理）

设 $A$ 是集合，选定 $a_0\in A$，并设 $T:A\to A$ 是函数。存在唯一函数 $h:N\to A$，使 $h(0)=a_0$，且对每个 $n\in N$ 有 $h(S(n))=T(h(n))$。不要求 $T$ 单射或满射。

证明

（由最小封闭关系证明存在性）

考虑全部关系 $R\subseteq N\times A$，要求它包含 $(0,a_0)$，且在 $(n,a)\mapsto(S(n),T(a))$ 下封闭。这个族非空，因为 $N\times A$ 属于它。其交集 $R_*$ 仍满足这两个条件，并包含于每一个这样的关系。归纳法说明每个 $n$ 都作为第一坐标出现：零出现，$n$ 处任意一个数对都会产生 $S(n)$ 处的数对。

再归纳证明第二坐标唯一。对零，删除全部 $a\ne a_0$ 的数对 $(0,a)$。剩余关系仍含基本数对，而且仍封闭，因为后继从不等于零。$R_*$ 的最小性迫使这次删除没有移走任何数对。

现假设 $n$ 处恰有一个数对 $(n,a)$。封闭性给出 $(S(n),T(a))$。删除 $S(n)$ 处第二坐标不等于 $T(a)$ 的全部数对。因 $S(n)\ne0$，基本数对保留。封闭性也保留：由后继单射，后继步骤只有从第一坐标 $n$ 才能进入这一个受影响的纤维；该处唯一第二坐标为 $a$，要求产生的恰是已经保留的数对。再次由最小性，没有数对被移走，故 $S(n)$ 处也唯一。因此 $R_*$ 是满足所需递归的全函数 $h$ 的图像。

若 $h_1,h_2$ 都满足规则，则它们在零处相等；在 $n$ 处相等后，应用同一个 $T$，便在 $S(n)$ 处相等。归纳得 $h_1=h_2$，完成唯一性证明。

对每个固定的 $a\in N$，取 $A=N$、$a_0=a$、$T=S$，所得关于 $b$ 的函数就是 $a+b$。加法存在后，再取 $a_0=0$、$T(x)=x+a$，定义 $a\cdot b$。这样两种运算的定义不需要预设后面的代数法则；下文才按依赖顺序证明那些法则。

递归加法

定义 3.2.2

（加法的递归定义）

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

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

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

例题 3.2.3

（由定义计算 $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$ 的数。

常见错误

（递归公式本身还不是证明）

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

递归乘法

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

定义 3.2.4

（乘法的递归定义）

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

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

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

例题 3.2.5

（由定义计算 $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.$$

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

归纳法真正证明什么

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

定理 3.2.6

（归纳原理）

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

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

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

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

跟随归纳论证

归纳证明把基本情形与任意输入处的推导分开。区分这两个角色，才能看清归纳假设在何处被使用。

算术证明中的后继恒等式

3.1 自然数与 Peano 公理 中的左侧后继恒等式，让后面的证明可以处理第一个输入中的后继。这个恒等式只需使用递归规则，无须预先假设交换律。

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

固定 $a$，对每个 $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$$

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

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

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

定理 3.2.7

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

对自然数 $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$ 成立。

从递归规则走向证明

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

例题 3.2.8

（逐步计算 $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$；之后才化简得到的加法。

交换律所需的左侧零恒等式

令 $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$ 成立。

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

定理 3.2.9

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

对所有 $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$。这条自然数消去律正是 3.3 由等价类构造整数 中证明整数等价关系传递性所需的事实。

常见错误

（算几个例子不等于归纳）

计算 $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$ 中的带符号代表元论证。

例题 3.2.10

（证明 $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\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$$

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

快问快答

快速检查

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

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

解答 · 答案

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

快速检查

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

看第二个输入。

解答 · 答案

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

快速检查

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

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

解答 · 答案

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

快速检查

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

用一句短句回答。

解答 · 答案

它是假设命题对任意固定的自然数 $n$ 成立，再用这个假设证明 $S(n)$ 的情形。

先备连结

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