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 公理。