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=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 函数与关系。