集合论与图论 · 第 10 讲：自然数与递归定义
集合论与图论
2026年 10月20日 笔记 补充来源：《集图笔记(1)》PDF 第 18 页：函数下的封闭、后继、归纳集、自然数与 Peano 系统。
1. 复习
- 封闭的概念：
- 后继的概念
表示的后继,
- 归纳集
是归纳集是指
若 为正整数，则后继尾集 在后继下封闭，但不包含 ，所以不是归纳集。
2. 自然数
def 自然数是属于每个归纳集的集合
从而广义交、广义并运算就有更新了：可以计算。
自然数集
取一个归纳集 （无穷公理保证存在），以分离公理定义
这避免把所有归纳集组成的真类当成集合取广义交。 不依赖所选的 。
属于每个归纳集，所以 。若 ，则对每个归纳集 有 ，由封闭性得 ；同时 ，故 。因此 是归纳集，且包含于每个归纳集。
Peano系统是指：满足以下五条的有序三元组，其中为一个集合，是到的函数，是首元素：
- 是单射，即
- 对任意，若，且，则
举例：是一个Peano系统，其中
下面逐条验证：
首元素属于。
由于是归纳集，故。
对封闭。
任取。由于是归纳集，，所以。
不在的值域中。
对任意，都有，所以。因此。
是单射。
任取并设。若，不妨设。由自然数的冯·诺依曼表示， ，而，但，故，矛盾。 因此，所以是单射。
归纳原理成立。
任取。若，且，则本身是归纳集。 由于包含于每个归纳集，故；又因，所以。
综上，满足Peano系统的全部五条条件。
自然数集上的递归定理
设A是一个集合，是一个函数，则存在唯一的函数，使得：
- ，对所有成立。
自然数的加法
Def. ，对于任意的，定义为：
其中是满足以下条件的唯一函数：
- ，对所有成立。
3. 递归定义与运算
递归定理说明初值与后继规则唯一确定函数。对两个满足同一规则的函数作归纳：初值相同，每步相同，则全部值相同。
加法：，。乘法：，。幂：，。
归纳法证明的是性质，递归定义构造的是对象。证明加法交换律需先归纳得到 与 ，再对第二变量归纳。