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