數學歸納法 (Mathematical Induction)

3/21/2014 03:23:00 上午

Enoch Lai from en.wikipedia.org [GFDL or CC-BY-SA-3.0], via Wikimedia Commons

學過基礎邏輯都知道,語句邏輯有構型規則 (formulation rules) ,規定哪些符號合規格(文法),哪些不符合。符合規格的符號,就叫做合規式 (well-formed formula,wff) 。語句邏輯的構型規則一般會寫成:
  1. 所有簡單語句 $P_1, P_2, P_3, ...$ 都是合規式
  2. 如果 $α$ 是合規式,則 $(∼α)$ 也是合規式
  3. 如果 $α$ 和 $β$ 都是合規式,則 $(α∧β)$, $(α∨β)$, $(α→β)$, $(α↔β)$ 也是合規式。
  4. 除了符合條件 1-3 的符號,其他全部不是合規式。
使用這個構型規則的邏輯系統,符號包括左括號「(」 和右括號「)」。假如有人問:有沒有合規式的左括號比右括號多?自詡熟悉語句邏輯,應該知道答案是「沒有」。然而,假如發問的人追問為甚麼,可以怎樣回答?

其中一個回答是訴諸直覺:「很明顯,沒有合規式的左括號比右括號多,這實在再清楚不過。」訴諸直覺不是不好,只是,有時候我們其實有更可靠的方法,譬如數學歸納法 (mathematical induction) 。要證明沒有合規式的左括號比右括號多,可以先證明所有合規式的左括號數目都和右括號數目一樣。假如所有合規式的左右括號數目一樣,自然不會有合規式的左括號比右括號多。於是問題變成:怎樣證明所有合規式的左右括號數目一樣?

仔細觀察構型規則,會發現合規式可分為兩大類。第一類是完全沒有連詞的簡單語句(如 $P_1$, $P_{20}$),第二類是透過簡單語句配合連詞組成的複合語句(如 $(∼P_1)$, $((∼P_1)∨(P_{20}))$)。基於這個觀察,只要用證明以下三點,便可以證明所有合規式的左右括號數目一樣:
  1. 簡單語句的左右括號數目一樣
  2. 如果 $α$ 的左右括號數目一樣,則 $(∼α)$ 的左右括號數目一樣
  3. 如果 $α$ 和 $β$ 的左右括號數目一樣,則 $(α∧β)$, $(α∨β)$, $(α→β)$, $(α↔β)$ 的左右括號數目也是一樣。
第一點叫做 Base Case ,第二、三點叫做 Inductive Step 。單單第一點不足以證明所有合規式的左右括號一樣,頂多只可以證明簡單語句的左右括號一樣。只有第二、三點同樣不足夠,那兩點只可以證明:由左右括號數目一樣的合規式,透過連詞組出新的合規式,左右括號數目也會一樣。但不是所有合規式都是由左右括號數目一樣的合規式組成,所以只有第二、三點同樣無法證明所有合規式左右括號一樣。可是,當第一、二、三點都成立,自然所有合規式的左右括號數目一樣。

假如第一點成立,所有簡單語句左右括號數目一樣。根據第二點,所有由簡單語句加上一個連詞組成的複合語句左右括號數目一樣。再根據第二點,再加上一個連詞的複合語句也會有一樣數目的左右括號。再根據第二點,再再加上一個連詞同樣左右括號數目一樣。再再根據第二點,……如此類推,涵蓋所有合規式。

實際上那三點很易證明,一下子就寫完:

Base Case.
  1. 由於簡單語句沒有左括號,也沒有右括號,左右括號數目都是 0 ,因此簡單語句的左右括號數目一樣。
Inductive Step.
  1. 假設 $α$ 的左右括號數目一樣。 $(∼α)$ 的左括號數目是 $α$ 的左括號數目加 1 ,右括號數目是 $α$ 的右括號數目加 1 ,因此 $(∼α)$ 的左右括號數目一樣。
  2. 假設 $α$ 和 $β$ 的左右括號數目一樣。令 $⋆$ 為任何一個二位連詞。 $(α⋆β)$ 的左括號數目等於 $α$ 的左括號數目加 $β$ 的左括號數目再加 1 ,右括號數目等於 $α$ 的右括號數目加 $β$ 的右括號數目再加 1 ,所以 $(α⋆β)$ 的左右括號數目一樣。

數學歸納法有幾種形式,其中兩種在後設邏輯較為常見,分別是普通歸納法 (ordinary induction,弱歸納法 (weak induction)) 和完全歸納法 (complete induction,強歸納法 (strong induction)) 。「數學歸納法」這個名字有點誤導,不知其然望文生義,會誤以為數學歸納法是歸納法的一種,只可以概然地(而非必然地)支持結論,但數學歸納法其實屬演繹法,前提百分百支持結論。

嚴格來說,數學歸納法是對自然數做歸納。普通歸納法和完全歸納法通常寫成這兩個陳構方式出自 Bostock (1997, p. 48). 從普通歸納法可以導出完全歸納法,見 Bostock (1997, pp. 48-49). 完全歸納法有另一個寫法,但視乎用法可寫成這個版本,見 Enderton (1977, p. 87) 與 Epstein & Carnielli (2000, p. 101).

普通歸納法 (ordinary induction)
1. 最小的自然數 (通常是 0) 有性質 P
2. 如果自然數 n 有性質 P ,則 n+1 也有性質 P
────────────
/∴ 所有自然數都有性質 P

完全歸納法 (complete induction)
1. 對於每一個自然數 n ,如果所有小於 n 的自然數都有性質 P ,則 n 也有性質 P
────────────
/∴ 所有自然數都有性質 P

這兩個版本的前提都有句「如果…則…」,緊接著「如果」的句子叫做歸納假設 (inductive hypothesis) 。使用普通歸納法,證明第二點時可以假設「自然數 n 有性質 P」;使用完全歸納法,可以假設「所有小於 n 的自然數都有性質 P 」。

上面的證明表面上是對合規式做歸納,但其實(間接)對自然數做歸納 ── 對合規式的連詞數目做歸納。見 Bostock (1997, p. 50).有些書籍不需涉及太多後設證明,省去這個轉折,直接將用在邏輯系統上的數學歸納法寫成另一個版本,例如取自 Sider (2010, p. 53). 略有修改。

歸納原則 (Induction Principle)
1. 所有簡單語句有性質 P
2. 如果合規式 $α$ 有性質 P ,則 $(∼α)$ 也有性質 P
3. 如果合規式 $α$ 和 $β$ 有性質 P ,則 $(α∧β)$, $(α∨β)$, $(α→β)$, $(α↔β)$ 也有性質 P
────────────
/∴ 所有合規式都有性質 P

在上面的證明,這個性質 P 就是「左右括號數目一樣」。我在〈連詞只包含「∼」和「↔」的合規式〉整理的證明,性質 P 是「如果的連詞最多只有 $∼$ 和 $↔$ ,並且真值表只有四行,則真值表最後一欄有四個 T ,或四個 F ,或兩個 T 兩個 F 」。利用數學歸納法,可以輕易證明以下這點:

如果一個合規式最多只包含 $P_1$, $∧$, 和 $→$ ,則當 $P_1$ 為真時那個合規式也會為真。
(以證明 $∧$ 和 $→$ 不足以定義五個古典連詞。 )

數學歸納法在後設邏輯是基本功。許多邏輯系統的後設證明都會用到數學歸納法,例如古典邏輯的演繹定理 (Deduction Theorem) 、公理證明系統的有效定理 (Soundeness Theorem) 、 樹枝證明系統的完備引理 (Completeness Lemma) 等等等等,多不勝數。用數學歸納法證明公理系統的演繹定理,可參考 Hunter (1973, pp. 84-88) 和 Sider (2010, pp. 58-59). 利用數學歸納法證明有效定理可見 Sider (2010, p. 54). 用數學歸納法證明樹枝系統的完備引理可見 Priest (2008),該書幾乎每套系統的完備引理都是用數學歸納法證明。不懂數學歸納法,說誇張點就是不懂後設邏輯。

最後舉一個簡單的數學例子。這個例子很常見,我參考的是 Causey (2006, p. 229) 與 Epstein & Carnielli (2000, p. 29).方便書寫,先將 $sum(k)$ 定義為

$sum(k) =_{df} 0+1+2+...+k$

要證明:對於任何自然數 $n$ , $sum(n)=\frac{n(n+1)}{2}$ 。換句話說,這次要證明的性質 P (或 Px) 是「$sum(x)=\frac{x(x+1)}{2}$」。成功證明代表以下所有情況都成立

$$sum(1)=\frac{1(1+1)}{2}$$
$$sum(2)=\frac{2(2+1)}{2}$$
$$sum(3)=\frac{3(3+1)}{2}$$


證明大致可以這樣寫:

Base Case.
  1. $sum(0)=0=\frac{0(0+1)}{2}$
Inductive Step.
  1. 假設 $sum(k)=\frac{k(k+1)}{2}$ ,要證明 $sum(k+1)=\frac{(k+1)((k+1)+1)}{2}$。

    \begin{split} sum(k+1) & = & sum(k)+(k+1) & \\ & = & \frac{k(k+1)}{2}+(k+1) & \text{(根據歸納假設)}\\ & = & \frac{{k(k+1)}+2(k+1)}{2} & \\ & = & \frac{(k+1)(k+2)}{2}& \end{split}
證明 (1) 和 (2) 後,根據普通歸納法,所有自然數 $n$ 都是: $sum(n)=\frac{n(n+1)}{2}$ 。



參考文獻
Bostock, David (1997). Intermediate Logic. Oxford University Press.
Causey, Robert (2006) Logic, Sets, and Recursion (2nd.). Jones and Bartlett Publishers.
Enderton, Herbert (1977). Elements of Set Theory. Academic Press, Inc.
Epstein, Richard & Carnielli, Walter (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics (2nd.). Wadsworth/Thomson Learning.
Hunter, Geoffrey (1973). Metalogic: An Introduction to the Metatheory of Standard First Order Logic. University of California Press.
Priest, Graham (2008). An Introduction to Non-Classical Logic (2nd.). Cambridge University Press.
Sider, Theodore (2010). Logic for Philosophy. Oxford University Press.
技術提供:Blogger.