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)` 等於甚麼？