自然数模型

把后继画成箭头，前两条公理保证零没有入箭头，而且两条不同的链不会在下一步合并。但它们尚未保证整个模型只有我们熟悉的那条链：远处仍可能另有一条与零无关的链，甚至有环。归纳条件的作用，是不让这些额外元素躲在“从零出发的部分”之外。

归纳与递归使用同一结构，却回答不同问题。递归负责造出对象：给出第一项及后续生成方式；归纳负责证明性质：证明起点成立，且每一步保持成立。它们不是用几个小数字猜测无限情形，而是利用模型规定的“没有遗漏部分”。

前两条为什么不够 ​

取标准自然数链与整数链的不交并

以 $(0,0)$ 为零，在各自的链上令 $S(k,i)=(k+1,i)$。零不是后继，后继也保持单射；但是 $A=\mathbb{N}\times \{0\}$ 包含零且对后继封闭，却不是整个 $M$。第三条公理正好排除了整数链。这个反例说明，“每个元素有唯一的下一个”并不足以定义自然数。

从递归得到加法，而不是预设运算法则 ​

固定 $m$，沿第二个变量定义

例如，递归式把一次加法逐步展开为

乘法再用已经建立的加法定义：

这里“重复相加”获得了明确的初值与更新规则，包括乘数为零的情形。

加法交换律不是第一行定义的直接重述。需要先对 $n$ 作归纳公理库数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。，得到两个辅助恒等式：

第一个的起点为 $0+0=0$，后继步为 $0+S(n)=S(0+n)=S(n)$。第二个的起点由加零得到；后继步两边都化为 $S(S(m+n))$。再固定 $m$，对 $n$ 归纳：起点使用 $0+m=m$，后继步为

这才完整建立了 $m+n=n+m$。相同方法可进一步证明结合律和分配律。

一种集合论实现 ​

von Neumann 编码取

因而 $1=\{0\}$，$2=\{0,1\}$，$3=\{0,1,2\}$。在通常集合论基础中，无穷公理配合相应构造提供包含这些对象的最小归纳集 $\omega$，它实现上述模型。

这种编码方便把自然数与集合大小、序数公理库序数Ordinal由属于关系良序且具有传递性的集合，表征良序的同构类型。联系起来，但数 $2$ 的算术性质不依赖于它是否真的被实现为某个集合。也可以使用二进制串或其他编码；证明其表示规则正确后，运算通过保持结构的对应迁移。

完整二阶归纳与一阶算术 ​

“一切子集”是范畴性结论中的关键量词。一阶 Peano 算术公理库皮亚诺算术Peano arithmetic · PA用一阶语言公理化自然数的零、后继、加法、乘法与归纳模式的形式理论。只对语言中可写出的公式提供归纳公理模式；它并不量化模型的所有子集，在标准集合论语义下允许非标准模型。因此，不能把本条的唯一模型结论直接搬到一阶公理系统，也不能把非标准模型理解成普通自然数运算出现了矛盾。

递归定理的唯一性有一个简洁证明。若 $f_1,f_2$ 满足同样的初值和更新规则，令 $A=\{n:f_1(n)=f_2(n)\}$。两函数在零处相同，且在 $n$ 处相同便在 $S(n)$ 处相同；归纳给出 $A=N$。存在性则可通过彼此兼容的有限阶段构造建立，不能仅凭这段唯一性论证省略。

范畴性也由递归与唯一性衔接起来。在两个自然数模型之间分别递归定义保零、保后继的映射 $h$ 与 $k$。复合 $kh$ 和恒等映射满足同一递归规则，故 $kh={\mathrm{id}}_N$；另一方向同理。因此两映射互逆，而保持结构的映射也只能有这一个。

对程序而言，这一结构解释了以自然数为指标的序列公理库序列Sequence以自然数为定义域的函数。、长度和循环不变量为何能协调工作。递归状态 $f(n)$ 描述执行到第 $n$ 步的结果，归纳证明描述每一步保持的性质；若循环是否终止尚未确定，仅有不变量并不能推出它会到达某个有限步数。