3.1 自然數與 Peano 公理

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

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

已經把內容完整說明。

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

為甚麼要形式定義

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

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

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

一個模型包含些甚麼

定義 3.1.1

（自然數的模型）

設 $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$ 出發生成的鏈上。

這幾條公理共同刻畫了從零開始、逐次取後繼的計數結構。

用後繼去讀出各個數

例題 3.1.2

（通常的數字如何由 $0$ 與 $S$ 表示）

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

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

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

後繼記號使定義中的步驟保持可見，避免熟悉的數字符號掩蓋其結構。

歸納不是附加技巧

許多學生在接觸歸納法這種證明工具之前，已經認為自己理解了自然數。在嚴格的構造中，歸納原理卻屬於刻畫自然數的基本條件。

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

定理 3.1.3

（歸納真正給你甚麼）

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

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

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

一個失敗例子

例題 3.1.4

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

考慮集合 $\{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$。這些規則尚未證明交換律；交換律和分配律必須在此基礎上另行歸納證明。

第一個遞歸恆等式

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

定理 3.1.5

（左邊的後繼可以穿過加法）

對所有 $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$ 的結論。

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

例題 3.1.6

（證明 $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$ 歸納，還需要先有另一條引理，才可以使用這條遞歸規則。

定理 3.1.7

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

對每個 $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$，因此唯一性成立。於是每個非零自然數恰好有一個前驅。

歸納證明的範圍

後繼映射給出向前的一步；歸納原理說明，在零處成立並且在這一步下保持的性質，會對模型中的所有元素成立。因此，證明必須說明定義域和基本情況，對任意固定的 $n$ 假設 $P(n)$，再用容許的恆等式推出 $P(S(n))$。只檢查幾個數字、把後繼情況本身當作假設，或只對一個選定輸入證明步驟，都不能得到全稱結論。

遞歸規則通常決定適合的歸納變量。也可以選別的變量，但必須已有相應的輔助恆等式。這個習慣同樣適用於後面的商集構造：那時要保持的性質是結果不依賴所選代表元。明確說出需要保持的性質，才能判斷每一步計算究竟要證明甚麼。

可選模型：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$。

例題 3.1.8

（為甚麼 $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 函數與關係。