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 · 0 = 0$
$a · S(b) = (a · b) + a$

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

例题

由定义计算 `3 · 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 的命题。如果：

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

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

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

先看互动步骤

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

边读边试

跟着走一遍归纳证明

互动步骤器把归纳证明拆成三个会动的部分。

命题

命题：对每个自然数 n，都有 0 + n = n。

证明草图

证明

为什么 $S(a) + b = S(a + b)$ 可由归纳法得到

证明

为什么 $a · S(b) = a · 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 · S(b)` 等于什么？

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

解答

答案

快速检查

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

用一句短句回答。

解答

答案

先备连结

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

3.2 归纳法与递归算术

MATH1090：集合论

递归加法

加法的递归定义

由定义计算 $2 + 3$

递归公式本身还不是证明

递归乘法

乘法的递归定义

由定义计算 `3 · 2`

归纳法真正证明什么

归纳原理

先看互动步骤

跟着走一遍归纳证明

证明草图

为什么 $S(a) + b = S(a + b)$ 可由归纳法得到

为什么 $a · S(b) = a · b + a$ 是定义而不是定理

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

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

分配律的证明结构

快问快答

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

答案

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

答案

按递归规则，`a · S(b)` 等于什么？

答案

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

答案

先备连结

先备知识

本单元重点词汇

本系列更多笔记

3.2 归纳法与递归算术

MATH1090：集合论

递归加法

加法的递归定义

由定义计算 2+32 + 32+3

递归公式本身还不是证明

递归乘法

乘法的递归定义

由定义计算 3 · 2

归纳法真正证明什么

归纳原理

先看互动步骤

跟着走一遍归纳证明

证明草图

为什么 S(a)+b=S(a+b)S(a) + b = S(a + b)S(a)+b=S(a+b) 可由归纳法得到

为什么 a⋅S(b)=a⋅b+aa · S(b) = a · b + aa⋅S(b)=a⋅b+a 是定义而不是定理

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

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

分配律的证明结构

快问快答

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

答案

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

答案

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

答案

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

答案

先备连结

先备知识

本单元重点词汇

本系列更多笔记

由定义计算 $2 + 3$

由定义计算 `3 · 2`

为什么 $S(a) + b = S(a + b)$ 可由归纳法得到

为什么 $a · S(b) = a · b + a$ 是定义而不是定理

按递归规则，`a · S(b)` 等于什么？