3.1 自然數與 Peano 公理

乍看之下，自然數太熟悉，似乎根本不需要定義。我們從小到大數數，彷彿

$$0,1,2,3,\ldots$$

已經把內容完整說明。

但嚴格的構造觀點會問：到底甚麼結構令自然數成為自然數？ 答案不在於符號本身，而在於一個起點、一個後繼運算，以及一條歸納原理。

為甚麼要形式定義

如果我們只是寫下 $0,1,2,3,\ldots$，其實未曾真正解釋：

• 省略號究竟代表甚麼；
• 為甚麼這個過程會一直延續；
• 為甚麼歸納法有效。

Peano 觀點就是直接把這些核心性質說明。它不靠直覺，而是說明：凡是 自然數模型，都必須具備某幾條基本公理。

一個模型包含些甚麼

定義

自然數的模型

設 $N$ 是一個集合，並且有：

• 一個指定元素 $0 \in N$；
• 一個函數 $S : N \to N$，稱為 後繼映射。

如果三元組 $(N, 0, S)$ 滿足以下 Peano 公理，就叫做 自然數模型：

1. $S$ 是單射：若 $S(x)=S(y)$，則 $x=y$。
2. 沒有元素會等於自己的後繼：對每個 $x \in N$，都有 $S(x)\ne x$。
3. 零不是任何元素的後繼：不存在 $x \in N$ 使 $S(x)=0$。
4. 歸納成立：若某性質 $P$ 對 $0$ 成立，而且每當 $P(x)$ 成立時， $P(S(x))$ 都成立，那麼 $P$ 就對所有 $x \in N$ 成立。

核心思想是：自然數由它們之間的結構關係決定，而不是由寫法決定。

每條公理各自做緊甚麼

每條公理都排除某一類病態情況。

• 單射性表示兩個不同數不可以在做一步後繼之後突然合流。
• $S(x)\ne x$ 排除固定點。
• $S(x)\ne 0$ 表示零是起點，而不是之後才回到去的位置。
• 歸納排除額外斷開的部分，確保所有元素都在由 $0$ 出發生成的鏈上。

合在一起，這幾條公理就迫出我們熟悉的「一步一步向前數」的圖像。

用後繼去讀出各個數

例題

平時的數字其實由 $0$ 與 $S$ 生出來

一旦 $0$ 與後繼映射固定，接下來的數就可以理解為

$$1 = S(0), \qquad 2 = S(S(0)), \qquad 3 = S(S(S(0))).$$

所以記號 $2$ 只是「由 $0$ 開始連做兩次後繼得到的對象」的簡寫。 方便是方便，但結構先是根本。

因此，當這裏想保留定義感而不想被熟悉記號遮蔽時，就會再寫回後繼形式。

歸納不是附加技巧

許多學生會先把歸納法視為一種證明工具，之後才覺得自然數已經理解完成。 嚴格的構造觀點正好倒轉這個次序。

在 Peano 觀點之中，歸納原理本身就屬於自然數定義的一部分。也就是話， 歸納不只是用來證明 $N$ 上命題的技巧；它本身就是令 $N$ 成為自然數的 結構事實之一。

定理

歸納真正給你甚麼

要證明命題 $P(n)$ 對所有 $n \in N$ 成立，只需要證明：

1. $P(0)$ 成立；
2. 對每個 $x \in N$，若 $P(x)$ 成立，則 $P(S(x))$ 成立。

一旦兩步完成，歸納公理就保證 $P(n)$ 對每個自然數 $n$ 都成立。

一個失敗例子

例題

為甚麼有限循環不是自然數模型

考慮集合 $\{0,1,2\}$，並定義後繼為

$$S(0)=1, \qquad S(1)=2, \qquad S(2)=0.$$

這個結構不滿足 Peano 公理。

首先，因為 $S(2)=0$，所以 $0$ 竟然是某個元素的後繼，第三條公理失敗。 這一點已經足以排除它作為自然數模型。這個例子不應該讀成「歸納公理失敗」： 由 $0$ 反覆取後繼仍然會到達整個有限集合。真正問題是後繼映射回到起點， 並令 $0$ 成為某個元素的後繼。

因此，雖然符號看起來熟悉，這個結構也不是自然數模型。

這個例子重要，因為它說明 Peano 公理不是裝飾，而是用來排除「表面似數數， 實際上不是」的結構。

常見錯誤

常見錯誤

不好把記號同角色混為一談

Peano 觀點不是話寫出來個符號 $2$ 天生有神秘意思，而是話 $2$ 所代表的對象，就是 $0$ 的第二個後繼。

常見錯誤

歸納不是可有可無的附加品

如果沒有歸納公理，一個結構即使包含由 $0$ 開始的熟悉後繼鏈，仍然可以有額外 斷開的部分，甚至循環。歸納原理正正是用來排除這些情況。

快問快答

思考檢查

為甚麼公理 $S(x)\ne 0$ 那麼重要？

想想若果 $0$ 可以是某個數的後繼，會對整體結構造成甚麼影響。

解答 · 答案

如果 $0$ 可以是某個後繼，數數鏈就可能回頭成環，而不再有真正起點。 這樣就不再符合我們對自然數「由起點一路向前」的理解。

思考檢查

後繼映射是單射，究竟防止咗甚麼事發生？

用「兩個不同數想共享同一個下一步」去回答。

解答 · 答案

它防止兩個不同元素擁有同一個後繼。若果沒有單射性，兩個不同數可能在下一步 突然合流，破壞通常的線性計數結構。

思考檢查

當你證明咗基本情況與後繼步驟之後，可以精確推出甚麼？

答案要說明範圍。

解答 · 答案

你可以推出該命題對 $N$ 之中每一個元素都成立，而不只是對頭幾個例子成立。

後繼結構的兩種失敗方式

必須逐條檢查四條 Peano 公理：(1) 後繼單射；(2) $S(x)\ne x$；(3) $0$ 不是任何後繼；(4) 歸納原理。

思考檢查

令 $N=\{0,1,2\}$，並令 $S(0)=1$、$S(1)=2$、$S(2)=1$。四條 Peano 公理哪些失敗？

檢查單射性、固定點、$S$ 的像，以及所有包含 $0$ 而且在 $S$ 下封閉的子集。

解答 · 引導解答

公理 (1) 失敗，因為 $S(0)=S(2)=1$ 而 $0\ne2$。公理 (2) 成立：$1\ne0$、$2\ne1$ 而 $1\ne2$。公理 (3) 成立，因為 $S$ 的像是 $\{1,2\}$，不包含 $0$。公理 (4) 亦成立：任何包含 $0$ 而且在 $S$ 下封閉的子集，都一定先包含 $1=S(0)$，再包含 $2=S(1)$，所以包括整個 $N$；循環只是返回已經包含的元素。

思考檢查

令 $M=\mathbb N\sqcup\{a,b,c\}$，在 $\mathbb N$ 上令 $S(n)=n+1$，並令 $S(a)=b$、$S(b)=c$、$S(c)=a$。四條 Peano 公理哪些失敗？

同時檢查三個循環元素同自然數鏈。

解答 · 引導解答

公理 (1) 成立：自然數後繼是單射，三循環的像互不相同，而且與自然數後繼的像分開。公理 (2) 成立，因為自然數鏈一路向前，而三循環沒有固定點。公理 (3) 成立，因為沒有後繼等於 $0$。公理 (4) 失敗：$\mathbb N$ 是 $M$ 的真子集，包含 $0$ 而且在 $S$ 下封閉，卻漏掉 $a,b,c$。

以下要用的遞歸定義

在證明算術恆等式之前，先寫出令計算有意義的遞歸定義。對 $a,b\in N$，定義

$$a+0=a,\qquad a+S(b)=S(a+b),$$

以及

$$a\cdot0=0,\qquad a\cdot S(b)=a\cdot b+a$$

後繼出現在第二個輸入，所以除非已經證明左側引理，之後的歸納都要遵守這個方向。

加法規則 $a+0=a$ 與 $a+S(b)=S(a+b)$ 不只是記號；它們指定了怎樣把一個後繼輸入化為較早的輸入。乘法規則 $a\cdot 0=0$ 與 $a\cdot S(b)=a\cdot b+a$ 也同樣把乘法化為重複加法。於是 $2+3$ 會逐步減到 $2+0$，$2\cdot 3$ 會逐步變成 $2\cdot 2+2$。這些規則尚未證明交換律；交換律和分配律必須在此基礎上另行歸納證明。

第一個遞歸恆等式

加法的遞歸定義把後繼寫在第二個輸入上。若要把後繼放在左邊，不能在尚未證明 交換律以前直接交換兩個輸入；我們要先證明一個獨立的恆等式。

定理

左邊的後繼可以穿過加法

對所有 $a,b\in N$，都有

$$S(a)+b=S(a+b).$$

證明 $S(a)+b=S(a+b)$

固定 $a$，令 $P(b)$ 表示 $S(a)+b=S(a+b)$。

基本情況。 當 $b=0$ 時，加法定義給出

$$S(a)+0=S(a)$$

而右邊亦滿足

$$S(a+0)=S(a)$$

所以 $P(0)$ 成立。

歸納步驟。 假設 $P(b)$ 成立，即 $S(a)+b=S(a+b)$。於是

$$\begin{aligned} S(a)+S(b) &=S(S(a)+b) &&\text{由遞歸規則}\\ &=S(S(a+b)) &&\text{由歸納假設}\\ &=S(a+S(b)) &&\text{再次使用 }a+S(b)\text{ 的遞歸規則} \end{aligned}$$

因此 $P(b)$ 推出 $P(S(b))$。歸納原理便給出所有 $b\in N$ 的結論。

這個證明顯示一個重要習慣：只有先把表達式改寫成歸納假設認得的形狀，才可以 使用歸納假設。歸納假設不是把任意表達式替換成後繼形式的許可。

例題

證明 $0+n=n$，而不是把它當作定義

加法定義給出 $0+0=0$，這是基本情況。假設 $0+n=n$，則

$$0+S(n)=S(0+n)=S(n)$$

所以歸納法證明 $0+n=n$ 對每個自然數 $n$ 成立。這是遞歸計算最後在左邊遇到 零時所需要的恆等式。

常見錯誤

歸納假設中的輸入是固定的

在上面的證明中，歸納假設是當前 $b$ 的 $S(a)+b=S(a+b)$。它並沒有直接說帶有 $S(b)$ 的命題已經成立；那正是歸納步驟必須證明的內容。

思考檢查

為甚麼證明 $S(a)+b=S(a+b)$ 時對 $b$ 歸納，而不是對 $a$ 歸納？

把歸納變量的選擇和遞歸定義的方向連起來。

解答 · 答案

遞歸定義會把第二個輸入降低：$a+S(b)$ 被改寫成 $a+b$ 的表達式。對 $b$ 歸納 正好沿着定義提供資料的方向進行。若對 $a$ 歸納，還需要先有另一條引理，才可以 使用這條遞歸規則。

定理

每個非零自然數都有唯一前驅

對每個 $x\in N$，若 $x\ne0$，就存在唯一一個 $y\in N$ 使 $S(y)=x$。

前驅命題如何由 Peano 歸納推出

令 $P(x)$ 表示：要麼 $x=0$，要麼存在唯一一個 $y$ 使 $S(y)=x$。基本情況直接成立， 因為第一個選項對 $0$ 成立。在步驟中，$S(x)$ 本身就是 $x$ 的後繼，所以存在性立即 成立。若 $S(y)=S(x)$，由後繼映射的單射性可得 $y=x$，因此唯一性成立。於是每個非零 自然數恰好有一個前驅。

後繼路徑與歸納範圍

歸納公理討論模型中的每個元素，但證明機制沿着一條明確路徑運行：從 $0$ 出發，連續應用後繼映射。基本情形把命題放在路徑起點；歸納步驟把它從一個點傳到下一個點；歸納公理保證沒有相關元素留在這條路徑之外。因此只驗證 $0$、$1$、$2$ 不是歸納證明，而對任意 $x$ 證明 $P(x)$ 蘊含 $P(S(x))$ 才是。

後繼映射和歸納原理也承擔不同工作。前者告訴我們如何向前走一步，後者說明一個在這一步下保持、並在起點成立的命題能夠到達所有自然數。一個結構可以看起來有計數式的後繼映射，卻因出現循環或額外部分而不滿足公理，所以必須先檢查模型條件。

接受歸納證明前的檢查

先寫清楚命題的定義域；然後逐字寫出基本情形；再以任意變量陳述歸納假設；最後只用允許的遞歸規則和已證恒等式推出後繼情形。把幾個數字算對、把目標本身當成假設，或只對一個具體數字證明步驟，都不能得到全稱結論。這個習慣以後會遷移到整數代表元和有理數代表元：要明確說出不變量，並驗證換表示後它仍保持。

可選模型：von Neumann 自然數

Peano 公理說明自然數必須有甚麼行為，但它不強迫我們採用某一種內部表示。 一個標準的集合論模型是 von Neumann 構造：

$$0:=\varnothing,\qquad 1:=\{0\},\qquad 2:=\{0,1\},\qquad 3:=\{0,1,2\}.$$

一般而言，

$$S(n)=n\cup\{n\}.$$

所以每個自然數都是所有較早自然數所組成的集合。在這個模型裏，屬於關係 反映大小次序：$m\in n$ 正好表示 $m$ 小於 $n$。

例題

為甚麼 $2$ 變成 $\{0,1\}$

由 $0=\varnothing$ 開始，後繼規則給出

$$1=S(0)=0\cup\{0\}=\{0\},$$

再得到

$$2=S(1)=1\cup\{1\}=\{0,1\}.$$

這不是說日常記號 $2$ 改變了意思，而是說我們建立了一個具體的集合論代表， 它滿足同樣的後繼模式。

前後銜接

這一節是構造數系篇章的起點。之後會接到 3.2 歸納法與遞歸算術， 而它使用的語言則可追溯到 2.2 函數與關係。