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