皮亚诺公理

皮亚诺公理（Peano axioms）用一个起点和“取下一个数”的规则来刻画自然数。它回答的不是“怎样更快地计算”，而是“自然数及其运算最基本的规则是什么”。数学归纳法之所以能够从起点与一步推导覆盖所有自然数，就与这套公理中的归纳原则有关。

本文把自然数记为 $0,1,2,3,\dots$，从零开始。有的教材从一开始，使用 $1,2,3,\dots$；两种约定的起点不同，阅读时应先确认。下文先用集合语言介绍公理的结构，再说明它与一阶皮亚诺算术的区别。

先有“下一个”，再给数取名字

设 $N$ 是准备作为自然数的集合，里面有一个指定元素 $0$。用函数 $S:N\to N$ 表示后继：给定一个数，$S$ 指定它的下一个数。

暂时不用加法来定义后继，而是反过来把

$$1=S(0),2=S(S(0)),3=S(S(S(0)))$$

作为数字的简写。这样，“加一”的含义以后可以由后继来解释，不会一边用加法定义自然数，一边又用自然数解释加法。

下图中的每个箭头都是同一个操作 $S$。图只画出有限几个位置；公理所要求的是整个集合中的后继规则，而不是一幅画到某处就停止的图。

数字是位置的名称；后继操作规定怎样从一个位置走到下一个位置。

用集合表述的公理

在已经指定集合 $N$、元素 $0\in N$ 和函数 $S:N\to N$ 后，再要求：

1. 零不是任何数的后继。对所有 $n\in N$，都有 $S(n)\ne 0$。
2. 相同后继来自相同的数。对所有 $m,n\in N$，若 $S(m)=S(n)$，则 $m=n$。也就是说，$S$ 是单射。
3. 归纳原则。如果子集 $A\subseteq N$ 含有零，并且每当 $n\in A$ 时都有 $S(n)\in A$，那么 $A=N$。

连同“零属于集合”“每个数都有属于集合的后继”这两条起始约定，常见教材也把它们排成五条。因此看到三条、五条或更多条的列表时，应比较具体内容，而不是只比较条数；等号的逻辑规则是否另列，也会改变表面形式。Stanford Encyclopedia of Philosophy：后继与归纳对自然数的刻画

第一条使零成为起点。例如若把三个位置接成 $0\to 1\to 2\to 0$ 的循环，就违反 $S(2)\ne 0$。第二条防止两条后继路径合并：若把不同的 $u,v$ 都接到同一个 $w$，就有 $S(u)=S(v)$ 而 $u\ne v$，违反单射。

这两条还说明从零出发不会在某一步回到以前的位置。若 $S^i(0)=S^j(0)$ 且 $i<j$，利用单射连续消去两边最外层的 $S$ 共 $i$ 次，会得到 $0=S^{j-i}(0)$。右边至少施加了一次后继，与零不是后继矛盾。因此从零反复出发得到的各个位置互不相同。

归纳公理排除了哪种多余结构

只有起点与单射后继，还不足以排除完全游离在起点之外的元素。考虑一个更大的集合：一部分是普通的链 $0,1,2,\dots$；另一部分是带不同名称的元素 $u_k$，其中 $k$ 遍历全部整数。规定

$$S(n)=n+1,S(u_k)=u_{k+1}.$$

第二部分与第一部分互不相交，$u_0$ 尤其不等于自然数零。这个结构中，每个元素都有后继，后继函数是单射，零也不是任何后继，但还多出了一整条双向延伸的链。

归纳原则不是只检查相邻箭头；它还要求包含起点且对后继封闭的子集已经是整个集合。

现在取 $A=\{0,1,2,\dots \}$，即只取上排。它含有零，对后继也封闭，却没有包含任何 $u_k$，所以 $A$ 不是整个集合。这恰好违反第三条归纳原则。图中的额外链是说明“缺少归纳时会出现什么”的反例，只涉及后继结构，并不是一个已经满足完整皮亚诺算术的模型。

对于任意性质 $P(n)$，可以把满足该性质的数收集成 $A=\{n\in N:P(n)\}$。要证明 $A=N$，便分成两件事：证明 $P(0)$，以及证明对任意 $n$，由 $P(n)$ 可推出 $P(S(n))$。这就是数学归纳法的起始步骤与归纳步骤。

起始步骤不能省略。例如性质“$n$ 是正数”具有“若成立，则后继处仍成立”的特点，但在零处为假，所以不能推出所有自然数都为正数。只验算 $0,1,2$ 等若干项也不能代替一般的归纳步骤。

用后继逐步建立加法和乘法

有了后继，可以在通常自然数结构上递归定义运算。加法按第二个变量给出两条规则：

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

第一条说没有增加任何次；第二条说，在已有 $b$ 次的结果上再取一次后继。自然数的递归定理保证这些逐步规则确定唯一的运算；这里先看规则怎样进行一次具体计算。

因为 $3=S(2)$、$2=S(1)$、$1=S(0)$，所以

$$\begin{array}{cc}2+3& =S(2+2)\\ & =S(S(2+1))\\ & =S(S(S(2+0)))\\ & =S(S(S(2)))=5.\end{array}$$

下图把计算分成两行。上行记录第二个参数 $b$ 的变化，下行记录对应结果 $2+b$：上面每多走一步，下面也必须多走一步。运算结果不是由数字外观猜来的，而是由起点 $2+0=2$ 和递推规则共同决定。

固定第一个数 2；加上 3，就是从 2 连续取三次后继。

乘法再由加法递归定义：

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

于是 $2\cdot 1=0+2=2$，$2\cdot 2=2+2=4$，$2\cdot 3=4+2=6$。这里每增加一次第二个因子，就多加一份第一个因子；它与加法中每步多取一次后继相呼应。

递归规则并没有把所有熟悉的代数规律都预先列出来。例如 $a+0=a$ 是定义中的规则，但 $0+a=a$ 还需要证明，不能在证明交换律之前直接交换两个加数。

一次完整的归纳证明：零加在左边

证明对每个自然数 $n$，都有 $0+n=n$。

起始步骤。当 $n=0$ 时，按规则 $a+0=a$，取 $a=0$ 得 $0+0=0$。

归纳步骤。假设某个任意自然数 $n$ 满足 $0+n=n$。对于它的后继，先用加法的递归规则，再用这个假设：

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

所以性质从 $n$ 传递到 $S(n)$。由归纳原则，它对所有自然数成立。这个证明中的假设只用于“若第 $n$ 步成立，则下一步成立”的条件推导，并没有先假设结论对所有数成立。MIT：Peano Arithmetic，命题 2

同样的办法可以逐步证明加法交换律、结合律，以及乘法的相应规律。每个证明应说明使用的是哪条递归规则和哪一个归纳假设。

一阶皮亚诺算术：一个公理模式

在形式逻辑中，需要说明“对所有性质”怎样表达。一阶语言的变量只遍历结构中的数，不直接遍历数的所有子集。通常的一阶皮亚诺算术，简称 PA，使用常量 $0$、后继 $S$、加法 $+$、乘法 $\cdot$ 与等号。后继的非零性、单射性和上面的四条运算递归等式作为公理；归纳部分则是一个公理模式。

具体地，对这套语言里的每一个公式 $\phi (n,\overline{y})$，都取下面这个句子作为归纳公理：

$$\mathrm{\forall }\overline{y}\left[\right(\phi (0,\overline{y})\wedge \mathrm{\forall }n(\phi (n,\overline{y})\Rightarrow \phi (S(n),\overline{y})))\Rightarrow \mathrm{\forall }n\phi (n,\overline{y})].$$

这里 $\overline{y}$ 表示公式中可能出现的一组额外数值参数。选定参数后，它们在归纳过程中保持不变；最外层的全称量词使这条公理对所有参数值都适用。刚才证明 $0+n=n$，便对应没有额外参数的公式 $\phi (n):0+n=n$。

“模式”不是把字母 $\phi$ 当作一个可量化的数值变量，而是在理论外规定：每一个合适的公式都贡献一条公理。因此它包含无限多条公理，每一条仍然只在一阶语言中量化数。它保证所有用公式及参数可定义的性质满足归纳，但没有直接量化结构的全部子集。MIT Logic II：归纳模式与全体子集的区别

二阶归纳与“只有一种自然数结构”

若允许变量 $A$ 直接遍历子集，就能用一个二阶句子表达开头的归纳原则：

$$\mathrm{\forall }A\left[\right(0\in A\wedge \mathrm{\forall }n(n\in A\Rightarrow S(n)\in A))\Rightarrow \mathrm{\forall }n(n\in A)].$$

在完全语义下，“对所有 $A$”指的是结构底集的所有子集，而不只是可用一阶公式写出的那些子集。这个解释与后继公理一起，使自然数结构在同构意义下唯一，也称具有范畴性。所谓同构，是存在一个一一对应，保持起点与后继；元素可以换名字，但生成结构相同。Stanford Encyclopedia of Philosophy：归纳、完全语义与范畴性

证明的核心可以直接看出来。取一个满足这些二阶条件的结构 $M$，从通常自然数向它定义

$$f(k)=S_M^k(0_M).$$

第一步映到它的起点，每向前一步就映到后继，因此 $f(0)=0_M$，$f(k+1)=S_M(f(k))$。前面已证明从起点重复取后继不会碰到旧位置，所以 $f$ 单射。它的像集含有 $0_M$，又对 $S_M$ 封闭；全子集归纳可以应用到这个像集，推出像集就是整个 $M$，所以 $f$ 也满射。这就建立了保持后继的一一对应。若加法、乘法按上述递归规则给出，它们也随起点与后继一起被保持。

一阶 PA 的情况不同：它存在与通常自然数不同构的非标准模型。说明其存在的一种方法是在 PA 的语言里增加一个常量 $c$，再要求 $c>0,c>1,c>2,\dots$。这里可以用加法定义严格次序：$x>y$ 表示存在 $z$，使 $x=y+S(z)$，也就是比 $y$ 多一个正数。任何有限多条要求都能在通常自然数中满足，只需把 $c$ 取成一个足够大的数；一阶逻辑的紧致性定理因而给出满足全部要求的模型，其中 $c$ 大于每个标准数词。这里用了紧致性这一逻辑定理，并不是凭图画构造出了非标准模型。

这不意味着一阶归纳失效：模型满足每一个归纳公式。问题在于，外部所见的“从零走标准有限步得到的元素”在非标准模型中不能由一个带参数的一阶公式定义。否则，它含零又对后继封闭，归纳模式便会迫使它包含整个模型，与非标准元素的存在矛盾。因此不能直接拿这个外部子集代入一阶模式，当作对全部子集的量化。MIT：非标准模型与归纳模式

若二阶变量也只遍历指定的一族子集，即采用一般语义或 Henkin 语义，就不能照搬完全语义下的范畴性结论。区分一阶、二阶及其语义，是在讨论公理到底刻画了什么，而不是改变日常自然数的计算结果。

零起点与一起点怎样对应

把“起点”为零换成一，后继链仍然具有同样的形状。只看起点与后继时，映射 $k\mapsto k+1$ 把零起点的链一一对应到一起点的链，并保持后继。

不过，这不表示普通加法也在这个平移下自动保持。例如 $f(0+0)=1$，而 $f(0)+f(0)=2$。若要把整个算术结构也一并搬过去，需要相应搬运运算的定义；不能一面平移起点，一面原封不动地把加法单位元仍当作同一个标签。通常教材只是分别声明自然数是否包含零，并在各自范围中使用熟悉的运算。

历史与参考资料

朱塞佩·皮亚诺（Giuseppe Peano，1858—1932）在 1889 年的拉丁文著作 Arithmetices principia, nova methodo exposita 中发表了著名的算术公理。它将自然数的基本关系用符号明确列出，是数学基础与符号逻辑发展中的重要工作。圣安德鲁斯大学 MacTutor：Giuseppe Peano

自然数的结构刻画也与戴德金的工作紧密相关；MIT 的算术讲义将任意两个满足完整归纳原则的算术结构同构这一结果归于戴德金。因此文献中也会出现“戴德金—皮亚诺公理”的称呼。现代一阶 PA 的归纳模式、非标准模型以及完全二阶语义，是进一步澄清这些原始结构思想后形成的逻辑区分。

• Vann McGee，Peano Arithmetic，MIT 24.242 Logic II，2004。运算递归、公理模式、归纳证明与模型的区别。
• Jouko Väänänen，Second-order and Higher-order Logic，Stanford Encyclopedia of Philosophy。后继公理、二阶归纳、完全语义、一般语义与范畴性。
• J. J. O'Connor、E. F. Robertson，Giuseppe Peano，MacTutor。1889 年著作及历史背景。