第3卷 第2章 皮亚诺算术

学习目标

• 能用 PA1–PA5 解释起点、后继闭包、非前驱、单射和归纳覆盖各自排除什么异常
• 能通过删公理反模型区分循环、会合、前驱进入 1 与不可达额外分量
• 能按基步—归纳步完成奇数和证明，说明条件假设为何不是循环论证
• 能用 ADD1、ADD2 递归计算 1+2 与 2+3，并区分对象语言和元语言

从一张写满公理的卡片开始

第3卷第2章中，泰朵拉拿到村木老师的研究卡片。正面是五条皮亚诺公理，背面是逻辑公式。她认识自然数，却第一次碰到一个更根本的问题：我们能否不用熟悉的1,2,3,\ldots，只凭少量规则重新刻画自然数？

先预测：只说“1是自然数”“每个自然数有后继”为什么还可能产生循环或会合；数学归纳法为何不是先假设待证结论；尚未定义加法时，后继n'凭什么不能直接写成n+1；等号、量词和蕴含又由谁提供？

原章从1开始。许多现代教材从0开始，两套版本只差一次平移，本章遵循原书记号。把n的后继写成：

$$n'=S(n).$$

S目前只是一个一元后继运算，不预设它等于“加1”。这场学习被泰朵拉称为“装作不知道的游戏”：

1. 可以使用已给公理；
2. 可以使用由公理和逻辑规则推出的结论；
3. 可以反复使用公理；
4. 没有定义过的加法、大小和次序都暂时不能偷用。

五条皮亚诺公理逐项拆解

PA1：给出起点

$$\mathrm{PA1}\qquad 1\in\mathbb N.$$

它只断言1属于自然数集合。还没有2，也没有“1最小”，因为数字2、大小关系和“最小”都尚未定义。

PA2：让后继留在集合内

$$\mathrm{PA2}\qquad \forall n\in\mathbb N,\quad S(n)\in\mathbb N.$$

由PA1与PA2依次得到：

$$1,\quad S(1),\quad S(S(1)),\quad S(S(S(1))),\ldots$$

都属于\mathbb N。之后才给这些表达式命名：

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

“无数个愿望”一节把这一点比作元愿望：不是逐个许下无限多个愿望，而是用一条“对任意自然数都可取后继”的规则生成任意有限深度的后继表达式。有限句子由此规定无限结构。

PA3：1不是任何数的后继

$$\mathrm{PA3}\qquad \forall n\in\mathbb N,\quad S(n)\ne1.$$

PA3不是在说“1最小”，因为次序还没有定义；它只规定后继箭头永远不能指回起点1。

PA4：后继运算是单射

$$\mathrm{PA4}\qquad \forall m,n\in\mathbb N,\quad S(m)=S(n)\Longrightarrow m=n.$$

这叫后继运算是单射。PA4直接阻止两条后继路径会合，也连带排除了从主链中途形成的有限循环。

它不能用“等式两边减1”证明，因为减法尚未定义；后继可消去正是PA4主动要求的结构性质。

PA5：归纳原则

对任意关于自然数的谓词P：

$$\mathrm{PA5}\qquad \left( P(1)\land \forall k\in\mathbb N\, \bigl(P(k)\Longrightarrow P(S(k))\bigr) \right) \Longrightarrow \forall n\in\mathbb N\,P(n).$$

P(n)可以理解为“自然数n是否具有某种性质”。PA5说：如果性质在起点成立，而且每次沿后继都能传下去，那么它覆盖全部自然数。

删掉一条公理，会放进什么异常结构

理解公理最有效的办法之一，是删掉它并构造仍满足其余规则的反模型。

没有PA4：后继路径可以会合

只保留PA1、PA2、PA3时，可以另有一个不从1出发的元素a，让它的后继接到主链某点：

$$S(a)=S(S(S(1))).$$

这不违反“1在集合内”“后继封闭”“1不是后继”，却违反后继单射。米尔嘉纠正“PA4主要防循环”的说法：更准确地说，PA4防止会合；循环只是会合的一种后果。

没有PA3：1可以有前驱

只保留PA1、PA2、PA4时，可以出现一条向左没有起点的链：

$$\cdots\longrightarrow a\longrightarrow1 \longrightarrow S(1)\longrightarrow S(S(1)) \longrightarrow\cdots.$$

后继仍是单射，却有某个元素的后继等于1。这与原书想要的自然数起点不符，说明PA3不能由PA4替代。

没有PA5：可能有不可达的额外分量

PA1至PA4只约束局部箭头，还没有说“集合中每个元素都能从1经过有限次后继抵达”。因此可以在标准链旁边放置另一条不与它相交的后继链。归纳原则承担全局覆盖职责。

不过这里要区分两种正式版本：

• 二阶Peano公理允许P遍历所有子集或性质，能把标准自然数结构刻画到同构。
• 一阶把PA5实现为对每个一阶公式各给一条归纳公理。它仍然存在非标准模型。

原章用五条规则“定义自然数”的说法适合作为二阶直觉；进入哥德尔不完备定理时，必须切换到可机械枚举公式与证明的一阶形式系统。

PA5就是数学归纳法

米尔嘉让泰朵拉证明：

$$1+3+5+\cdots+(2n-1)=n^2.$$

她先提醒“蠢货才会忘记示例”。计算：

$$1=1^2,$$ $$1+3=4=2^2,$$ $$1+3+5=9=3^2.$$

实例不能证明全称命题，却帮助发现“前n个奇数之和是n^2”这一压缩表达。定义：

$$P(n)\colon 1+3+5+\cdots+(2n-1)=n^2.$$

基步

当n=1时：

$$1=1^2,$$

所以P(1)成立。

归纳步

固定任意自然数k，假设P(k)：

$$1+3+\cdots+(2k-1)=k^2.$$

要证明P(k+1)，在两边加上下一个奇数：

$$2(k+1)-1=2k+1.$$

于是：

$$\begin{aligned} 1+3+\cdots+(2k-1)+(2k+1) &=k^2+2k+1\\ &=(k+1)^2. \end{aligned}$$

所以：

$$P(k)\Longrightarrow P(k+1).$$

基步与归纳步都成立，由PA5得到：

$$\forall n\in\mathbb N,\quad P(n).$$

为什么归纳假设不是循环论证

泰朵拉困惑：目标本来是“所有n都有P(n)”，归纳步为什么可以先假设P(k)？

因为归纳步证明的是整个蕴含：

$$\forall k\, \bigl(P(k)\Longrightarrow P(k+1)\bigr),$$

不是先假设：

$$\forall k\,P(k).$$

固定k的P(k)只是条件证明中的临时前提。原章的多米诺骨牌比喻里，“若一块倒下，下一块会倒”不等于“所有块已经倒下”；还要基步推倒第一块，PA5才把两者合成全称结论。

与最终结论的量词范围不同，括号不能省略。

动态脚步与静态全称

回家路上，泰朵拉把归纳法想成一步一步前进，米尔嘉提醒这只是直觉的一面。形式结论：

$$\forall n\in\mathbb N\,P(n)$$

是关于整个自然数集合的静态陈述，不是人在时间里真的完成无限次检查。有限的基步、有限描述的传递规则与PA5，使逻辑一次抓住全部自然数。

多米诺图像解释“如何传播”，全称量词解释“最终断言什么”。两种视角互补，不能把无限证明误解为一个永远执行不完的循环程序。

加法不是预装功能

周末，尤里追问“加法也能定义吗”。原章给出以第二个参数递归的两条方程：

$$\mathrm{ADD1}\qquad \forall m\in\mathbb N,\quad m+1=S(m),$$ $$\mathrm{ADD2}\qquad \forall m,n\in\mathbb N,\quad m+S(n)=S(m+n).$$

让第二个参数每次少一个后继，最终落到ADD1。

例如，暂时不使用2与3的名字：

$$\begin{aligned} 1+S(1) &=S(1+1)\\ &=S(S(1)). \end{aligned}$$

命名2=S(1)、3=S(S(1))后，才得到：

$$1+2=3.$$

再算2+3：

$$\begin{aligned} S(1)+S(S(1)) &=S\bigl(S(1)+S(1)\bigr)\\ &=S\bigl(S(S(1)+1)\bigr)\\ &=S(S(S(S(1)))). \end{aligned}$$

右边命名为5，因此：

$$2+3=5.$$

同样可以继续递归定义乘法：

$$m\cdot1=m,$$ $$m\cdot S(n)=m\cdot n+m.$$

交换律、结合律和分配律不是定义的一部分，必须再用归纳法证明。

尤里的追问：等号与量词的公理在哪里

看到奇数和证明后，尤里发现一个层次问题：我们刚定义加号，却早已使用：

$$=,\qquad \in,\qquad \forall,\qquad \Longrightarrow.$$

这些符号并不都由皮亚诺算术内部临时产生：

• 1,S,+,\cdot是算术的非逻辑符号，用来谈自然数对象与运算。
• =,\forall,\Longrightarrow属于背景的一阶逻辑；等号配有自反与替换等逻辑规则，量词和蕴含也有各自的语法、语义及推理规则。
• \in属于集合论语言。严格的一阶PA通常直接规定论域是自然数，不把“n\in\mathbb N”写进对象语言；它常是元语言中的范围说明。

谈自然数，谈“哪些串是公式”“哪些步骤是证明”。尤里的问题把下一阶段的任务点了出来：若要研究数学证明本身，就必须先把背景逻辑也明确形式化。

概念证据索引：从五条公理到一套可计算语言

• 皮亚诺算术 / Peano Arithmetic / 皮亚诺公理 / 用皮亚诺公理定义自然数：皮亚诺算术用少量公理重新刻画自然数；本章遵循原书记号从 1 开始的版本。
• 从1开始的版本 / 原章从1开始 / 后继数n撇 / n'=S(n) / 后继不是预先定义的n加1：起点是 1，后继数写作 n'=S(n)；S 不是预先定义的 n+1。
• 装作不知道的游戏 / 只能使用公理与逻辑推论 / 无数个愿望 / 元愿望 / 有限句子规定无限结构：装作不知道意味着只能使用公理与逻辑推论；有限句子可以通过元愿望生成无限深度的后继串。
• PA1一是自然数 / PA1 / 1属于自然数集合 / PA2自然数的后继仍是自然数 / PA2 / 后继闭包 / 对后继封闭：PA1 给出 1∈N，PA2 让自然数对后继封闭。
• 重复使用PA2生成后继串 / 给后继串命名2 3 4 / 2:=S(1)：重复使用 PA2 得到 1,S(1),S(S(1)),...，再把它们命名为 2、3、4。
• PA3没有自然数的后继等于1 / PA3 / 1不是任何数的后继 / 尚未定义最小与大小关系：PA3 只禁止 S(n)=1，并没有预先定义最小值或大小关系。
• PA4后继相等推出原数相等 / PA4 / 后继运算是单射 / 单射 / PA4防止会合：PA4 用 S(m)=S(n)⇒m=n 保证后继单射，阻止两条路径会合。
• 防止循环只是会合的后果 / 没有PA4可有外来元素会合 / 没有PA3可有前驱进入1 / 没有PA5可有不可达额外分量：删掉不同公理分别允许会合、前驱进入 1 或不可达的额外链；循环只是会合的一种后果。
• 五条公理各有职责 / PA5数学归纳法 / PA5就是数学归纳法 / 谓词P(n) / 基步P1 / P(1)：五条公理各有职责；PA5就是数学归纳法，它对谓词 P(n) 要求基步 P(1) 和后继传递。
• 归纳步P(k)推出P(S(k)) / P(k)\Longrightarrow P(S(k)) / 全称结论所有n都有P(n) / \forall n\in\mathbb N,P(n)：固定任意 k 证明 P(k)⇒P(S(k))，再由 PA5 得到所有 n 的全称结论。
• 二阶Peano公理刻画标准自然数 / 二阶Peano公理 / 一阶PA归纳公理模式 / 一阶PA存在非标准模型 / 仍然存在非标准模型：二阶版本能刻画标准结构；一阶 PA 用公理模式表达归纳，却仍然存在非标准模型。
• 先做具体例子 / 奇数的和与平方数 / 前n个奇数之和等于n的平方 / 1加3加到2n减1等于n平方：先做具体例子发现结构，再证明 1+3+...+(2n-1)=n²，实例本身不是全称证明。
• n等于1的基步 / 固定任意自然数k / 归纳假设P(k) / 假设P(k) / 添加下一个奇数2k加1 / 2k+1：基步取 n=1；归纳步固定任意 k，假设 P(k)，添加下一个奇数 2k+1。
• k平方加2k加1等于k加1平方 / k^2+2k+1 / QED证明完毕 / 基步与归纳步都成立：代数恒等式把 k²+2k+1 化为 (k+1)²；基步和归纳步成立后，证明完毕。
• 归纳假设不是循环论证 / 证明的是对所有k的蕴含 / 不是假设所有k都有Pk：归纳假设只是假定固定 k 的条件前件，不是先假设所有 k 都满足 P(k)。
• 多米诺骨牌比喻 / 动态脚步与静态全称 / 用有限规则抓住无限 / 数学归纳法面向整个自然数集合：多米诺是传播的动态比喻，PA5 给出关于整个自然数集合的静态全称命题，用有限规则抓住无限。
• 加法运算也能定义 / 加法不是预装功能 / ADD1 m加1等于S(m) / ADD1：加法不是预装功能；ADD1 规定 m+1=S(m)。
• ADD2 m加S(n)等于S(m加n) / ADD2 / 以第二参数递归定义加法：ADD2 规定 m+S(n)=S(m+n)，所以按第二参数递归定义加法。
• 计算1加2等于3 / 1+2=3 / 计算2加3等于5 / 2+3=5：展开后继串并使用 ADD1、ADD2，可机械计算 1+2=3 与 2+3=5。
• 后继串命名普通数字 / 把后继串命名成普通数字 / 递归定义乘法 / 继续递归定义乘法：普通数字名称只是后继串的缩写；乘法也可继续递归定义乘法。
• 交换律结合律分配律需要证明 / 交换律、结合律和分配律不是定义的一部分：运算方程给出定义，不自动给出交换律、结合律和分配律，这些性质还需要证明。
• 等号的公理在哪里 / 等号与量词的公理在哪里 / 属于号全称量词推出符号来自哪里：等号、量词、蕴含和属于号来自不同层次，不能假装都由 PA 临时生成。
• 算术非逻辑符号1 S 加法 乘法 / 算术的非逻辑符号 / 等号量词蕴含属于背景逻辑 / 属于背景的一阶逻辑：1,S,+,· 是算术非逻辑符号，=,∀,⇒ 属于背景一阶逻辑。
• 成员关系属于集合论语言 / 一阶PA变量默认在自然数论域取值 / 变量默认只在自然数论域上取值 / 对象语言 / 元语言：∈ 属于集合论语言；一阶 PA 的变量默认在自然数论域取值，要区分对象语言和元语言。
• 语法语义推理规则 / 语法、语义及推理规则 / 为形式化数学证明铺路：自然数公理、背景逻辑、语法、语义和推理规则共同为形式化数学证明铺路。

互动实验与四步复盘

先猜：删除 PA4、PA3、PA5 时，哪一种异常结构会出现？再切换到归纳和加法视角，观察“有限规则如何覆盖无限对象”。

Peano Structure Lab

切换公理、归纳与递归计算的视角。

重置实验

公理职责归纳证明递归加法

结论：PA1–PA4 管局部结构，PA5 负责从起点覆盖全部自然数。

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 结构：沿后继串确认 PA1–PA4

从 1 开始反复取 S，再检查 PA3 不允许回到 1、PA4 不允许两条路径会合。

上一步播放下一步

本章回顾：用有限规则抓住无限

1. 原章从1与后继运算出发，暂时不借用加法、大小和普通数字名称。
2. PA1给出起点1，PA2保证自然数对后继封闭。
3. PA3规定1不是任何自然数的后继，阻止链从左侧进入1。
4. PA4规定后继为单射，直接阻止不同路径会合。
5. PA5把基步和后继传递规则提升为对全部自然数的结论。
6. 删除一条公理并构造反模型，能精确识别该公理排除的异常结构。
7. 二阶Peano公理可刻画标准自然数；一阶PA仍有非标准模型。
8. 归纳证明先从实例发现结构，再证明基步和对任意k的条件蕴含。
9. 归纳假设只服务于固定k的条件证明，不等于先假设全称结论。
10. 多米诺是动态直觉，PA5给出的则是关于整个集合的静态全称命题。
11. ADD1与ADD2递归定义加法，具体算式可机械归约为后继串。
12. 等号、量词与蕴含来自背景逻辑；区分对象语言与元语言是研究形式系统的前提。

练习与答案

练习

1. 问题 1：公理职责。 如果只删除 PA4，为什么可能出现 S(a)=S(S(S(1))) 而不立即违反 PA1–PA3？

查看答案

PA1 只要求 1 在自然数中，PA2 只要求后继仍在集合中，PA3 只禁止某个后继等于 1；它们都没有禁止两个不同元素拥有同一个后继。PA4 正是负责后继单射、阻止会合的公理。

2. 问题 2：数学归纳法。 对 P(n):1+3+…+(2n-1)=n²，写出基步和归纳步，并说明归纳假设为什么不是先假设所有 P(n)。

查看答案

基步是 P(1):1=1²。归纳步固定任意 k，只临时假设 P(k)，再计算 k²+(2k+1)=(k+1)²，得到 P(k)⇒P(k+1)。它证明的是对每个 k 成立的条件蕴含，不是预先假设全称结论。

3. 问题 3：递归加法。 使用 ADD1、ADD2 计算 1+2，说明为什么必须把 2 展开为 S(1)。

查看答案

1+2=1+S(1)=S(1+1)=S(S(1))，再把 S(S(1)) 命名为 3。2 只是后继串 S(1) 的名称；在 ADD1、ADD2 出现前，不能把 S(n) 偷换成 n+1。

4. 问题 4：对象语言与元语言。 为什么 ∈ 通常不属于一阶 PA 的对象语言？

查看答案

一阶 PA 通常把变量直接解释为自然数论域中的对象，基本非逻辑符号是 1、S、+、·；∈ 是集合论语言的成员关系。写“n∈N”常是元语言中说明变量范围，而不是 PA 内部的公式。

名词解释

本章出现的专业名词，用大白话再讲一遍。

皮亚诺公理

用起点、后继、单射、非前驱和归纳原则刻画自然数结构的公理集合。

后继运算

把自然数 n 送到下一个对象 S(n) 的一元运算；本章不预设它等于加一。

反模型

满足其余规则但呈现异常结构的模型，用来显示被删公理的职责。

数学归纳法

由基步和后继传递规则推出关于全部自然数的全称结论。

递归定义

用基础值和后继方程逐步定义加法、乘法等运算的方式。

非标准模型

满足一阶 PA 公理、但包含标准自然数链之外元素的模型。