返回：0100 离散数学课程总目录 · 上一章：0103 函数与集合论习题课 · 下一章：0105 等势、基数、序数与集合论公理

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第四章。Auto_Tutor 中整理到的资料包括：

资料 内容
4.1 自然数的定义 Peano 系统、封闭、后继、归纳集、自然数集、后继函数、数学归纳法
4.2 自然数的性质 传递集、递归定理、加法、乘法、自然数上的序
004 习题与答案 习题 2、3、5、7，重点考察自然数作为集合、非零自然数是后继、传递集和递归定义出的单射

本章的核心目标：用集合论构造自然数。这里的 0,1,2,3,... 不再只是熟悉的数字，而是冯·诺依曼自然数：0=∅，1={0}，2={0,1}，3={0,1,2}。

2、颜色标注

颜色 含义
粉色 必背、必会证明、后续章节反复使用
蓝色 核心术语和定义
橙色 易错点、边界条件
绿色 理解提示和后续连接

3、章节主线

模块 本章要会什么 后续连接
Peano 系统 理解起点、后继、单射、极小性 自然数公理化
后继与归纳集 会写 A+=A∪{A}，知道归纳集含 ∅ 且对后继封闭 数学归纳法
自然数集 N 知道 N 是最小归纳集 递归定义
数学归纳法 会构造 `S={n∈N P(n)}并证明S=N`
自然数作为集合 会算 2∪3、2∩3、∪5、∩6 基数、序数
传递集 会用 ∪A⊆A、A⊆P(A) 判定 序数
递归定义 理解加法、乘法都由递归定理保证存在唯一 运算律
自然数上的序 用 m∈n 表示 m<n 良序、序数

4、Peano 系统

设 F:M→M，三元组 <M,F,e> 称为 Peano 系统，要求：

条件 含义
e∈M 有起点
M 在 F 下封闭 对任意 x∈M，F(x)∈M
e∉ran F 起点不是任何元素的后继
F 是单射 不同元素的后继不同
A⊆M ∧ e∈A ∧ A 在 F 下封闭 ⇒ A=M 极小性公理

极小性公理就是数学归纳法的来源。 如果一个子集含起点，又对后继封闭，那么它不能漏掉任何自然数。

封闭的定义：

1
2
3
A 在 F 下封闭
⇔ F(A)⊆A
⇔ F:A→A

例：f:N→N，f(x)=x+1。偶数集 {0,2,4,6,...} 在 f 下不封闭；集合 {2,3,4,...} 在 f 下封闭。

5、后继、归纳集与自然数

5.1 后继

集合 A 的后继定义为：

1
A+ = A∪{A}

它有两个特征：

1
2
A⊆A+
A∈A+

几个例子：

1
2
3
∅+   = {∅}
∅++  = {∅,{∅}}
∅+++ = {∅,{∅},{∅,{∅}}}

5.2 归纳集

集合 A 是归纳集，当且仅当：

1
2
(1) ∅∈A
(2) ∀x(x∈A ⇒ x+∈A)

也就是：A 含有 ∅，并且对后继运算封闭。

归纳集不是“有限列出几个后继”就够了。比如 {∅+,∅++,∅+++} 少了 ∅，不是归纳集；{∅,∅+,∅++,...,a} 少了 a+、a++，也不是归纳集。

5.3 自然数与自然数集

自然数是属于每个归纳集的集合。按冯·诺依曼构造：

1
2
3
4
5
0 = ∅
1 = ∅+  = {∅}       = {0}
2 = ∅++ = {∅,{∅}}   = {0,1}
3 = ∅+++            = {0,1,2}
n = {0,1,2,...,n-1}

自然数集 N 是最小的归纳集：

1
2
N = {0,1,2,3,...}
∀v(v 是归纳集 ⇒ N⊆v)

课件里提到 D={v|v 是归纳集} 不是集合，而是“类”。如果把所有归纳集组成集合，容易撞上集合论悖论。博客复盘时记结论即可：N 是每个归纳集都包含的最小归纳集。

定理 4.1：N 是归纳集。

证明思路：

1
2
3
4
1. 任意归纳集都含 ∅，所以 ∅∈N。
2. 若 a∈N，则 a 属于任意归纳集。
3. 任意归纳集对后继封闭，所以 a+ 也属于任意归纳集。
4. 因此 a+∈N。

6、后继函数与数学归纳法

后继函数：

1
2
σ:N→N
σ(n)=n+

于是：

1
2
3
σ(0)=1
σ(1)=2
σ(2)=3

定理 4.2：

1
<N,σ,0> 是 Peano 系统

对应五条：

条件 证明来源
0∈N N 是归纳集
σ(n)=n+∈N N 对后继封闭
0∉ran σ 任意 n+ = n∪{n} 非空
σ 是单射 由自然数元素性质推出
极小性 若 S⊆N 含 0 且后继封闭，则 S 是归纳集，故 N⊆S

数学归纳法原理：

1
2
3
4
5
6
7
目标：证明 ∀n∈N，P(n)

构造 S={n|n∈N∧P(n)}
证明：
(1) 0∈S
(2) n∈S⇒n+∈S
于是 S=N

归纳证明不是“从 0、1、2 看起来都对”，而是证明使命题成立的自然数集合本身就是归纳集。

7、自然数作为集合的性质

7.1 基本元素性质

自然数有这些重要性质：

定理 内容
定理 4.3 任意自然数的元素都是它的子集：x∈n⇒x⊆n
定理 4.4 m+∈n+ ⇔ m∈n
定理 4.5 任意自然数都不是自己的元素：n∉n
定理 4.6 0 属于除 0 以外的任何自然数
定理 4.7 对任意自然数 m,n，m∈n、m=n、n∈m 恰有一个成立

定理 4.7 就是自然数上的三歧性，后面把 m∈n 读成 m<n。

7.2 自然数的集合运算

因为：

1
n={0,1,2,...,n-1}

所以自然数之间的集合并、交可以直接转成大小比较：

1
2
n∪m = max(n,m)
n∩m = min(n,m)

广义并和广义交：

1
2
3
∪0 = 0
∪n = n-1，n≠0
∩n = 0，n≠0

例：

1
2
3
4
5
2∪3 = 3
2∩3 = 2
∪5 = 4
∩6 = 0
∪∪7 = ∪6 = 5

这里的 2∪3 是集合运算，不是普通算术。因为 2={0,1}，3={0,1,2}，所以并起来是 {0,1,2}=3。

8、传递集

集合 A 是传递集，当且仅当：

1
∀x∀y(x∈y∧y∈A ⇒ x∈A)

直觉：A 中元素的元素，还得留在 A 里。

传递集的等价条件：

1
2
3
4
A 为传递集
⇔ ∪A⊆A
⇔ ∀x(x∈A⇒x⊆A)
⇔ A⊆P(A)

常用结论：

定理 内容
定理 4.11 A 为传递集 ⇔ P(A) 为传递集
定理 4.12 若 A 为传递集，则 ∪(A+)=A
定理 4.13 每个自然数都是传递集
定理 4.14 自然数集 N 是传递集

例子：

集合 是否传递 原因
{∅,{∅},{{∅}}} 是 元素继续拆开仍在集合中
{0,1,2} 是 它就是自然数 3
{{a}} 否 a∈{a}，但 a 不一定在集合中
<0,1>={{0},{0,1}} 否 其中元素继续拆开会出现未包含项

9、递归定理、加法、乘法与序

9.1 递归定理

设 A 为集合，a∈A，F:A→A，则存在唯一函数 h:N→A，使得：

1
2
h(0)=a
h(n+)=F(h(n))

这就是递归定义的合法性来源。

9.2 加法

固定 m∈N，定义“加 m”函数 A_m:N→N：

1
2
A_m(0)=m
A_m(n+)=(A_m(n))+

二元加法定义为：

1
m+n=A_m(n)

基本性质：

1
2
3
4
5
6
7
m+0=m
m+n+ = (m+n)+
0+n=n
m++n=(m+n)+
m+n=n+m
(m+n)+k=m+(n+k)
m+k=n+k ⇒ m=n

9.3 乘法

固定 m∈N，定义“乘 m”函数 M_m:N→N：

1
2
M_m(0)=0
M_m(n+)=M_m(n)+m

二元乘法定义为：

1
m·n=M_m(n)

基本性质：

1
2
3
4
5
1·n=n·1=n
n·m=m·n
(m·n)·k=m·(n·k)
m·(n+k)=m·n+m·k
m·k=n·k ∧ k≠0 ⇒ m=n

9.4 自然数上的序

自然数上的严格序：

1
m<n ⇔ m∈n

非严格序：

1
m≤n ⇔ m∈n ∨ m=n

自然数上的这个序是线序，也是良序。

10、习题与答案

习题 2：自然数的集合运算

题目：计算：

1
2
3
4
5
(1) 2∪3
(2) 2∩3
(3) ∪5
(4) ∩6
(5) ∪∪7

答案：

1
2
3
4
5
(1) 2∪3 = {0,1}∪{0,1,2} = {0,1,2} = 3
(2) 2∩3 = {0,1}∩{0,1,2} = {0,1} = 2
(3) ∪5 = ∪{0,1,2,3,4} = {0,1,2,3} = 4
(4) ∩6 = ∩{0,1,2,3,4,5} = ∅ = 0
(5) ∪∪7 = ∪(∪7) = ∪6 = 5

总结：

1
2
3
4
5
n∪m=max(n,m)
n∩m=min(n,m)
∪0=0
∪n=n-1，n≠0
∩n=0，n≠0

习题 3：非零自然数都是后继

题目：证明任意非零自然数都是某个自然数的后继。

证明：

构造：

1
2
S'={n|n∈N∧n≠0∧∃m(m∈N∧n=m+)}
S=S'∪{0}

证明 S 是 N 的归纳子集。

  1. 0∈S，显然成立。
  2. 若 n∈S，证明 n+∈S。

分情况：

1
2
3
4
若 n=0，则 n+=0+=1，显然 1 是 0 的后继，所以 n+∈S'⊆S。

若 n≠0，则 n∈S'，存在 m∈N，使 n=m+。
于是 n+=m++，所以 n+ 也是某个自然数的后继，即 n+∈S'⊆S。

所以 S 是归纳集，故 S=N。因此每个非零自然数都属于 S'，也就是都是某个自然数的后继。

习题 5：传递集的后继仍为传递集

题目：设 A 是传递集，证明 A+ 也是传递集。

证明：因为 A+=A∪{A}。任取 x∈A+，再任取 y∈x，需要证明 y∈A+。

分情况：

1
2
3
(1) 若 x∈A。
因为 A 是传递集，y∈x∈A 推出 y∈A。
所以 y∈A⊆A+。
1
2
(2) 若 x=A。
因为 y∈x=A，所以 y∈A⊆A+。

两种情况都得到 y∈A+，所以 A+ 是传递集。

习题 7：递归定义出的 h 是单射

题目：设 f:A→A 是单射但不是满射，a∈A-ran f。定义 h:N→A：

1
2
h(0)=a
h(n+)=f(h(n))

证明 h 是单射。

证明：用反证法。若 h 不是单射，则存在 m,n∈N，m≠n，使 h(m)=h(n)。不妨设 m<n。

第一种情况：m=0。

1
2
3
4
n≥1，所以存在 n-1，使 n=(n-1)+。
h(n)=h((n-1)+)=f(h(n-1))。
又 h(0)=a，且 h(0)=h(n)，
所以 a=f(h(n-1))，即 a∈ran f。

这与 a∈A-ran f 矛盾。

第二种情况：0<m<n。

1
2
3
h(m)=h(n)
⇒ f(h(m-1))=f(h(n-1))
⇒ h(m-1)=h(n-1)      （f 单射）

不断重复这个“向前退一步”的过程，最终得到：

1
h(0)=h(n-m)

由于 n-m≥1，所以 n-m=(n-m-1)+，于是：

1
a=h(0)=h(n-m)=f(h(n-m-1))

这又推出 a∈ran f，与 a∈A-ran f 矛盾。

两种情况都矛盾，所以 h 必为单射。

习题 7 的直觉：从不在 ran f 里的 a 出发，不断套单射 f，会得到一条永不回头、永不相撞的序列。

11、复盘清单

  1. 后继定义是 A+=A∪{A}。
  2. 0=∅，1={0}，2={0,1}，一般 n={0,1,...,n-1}。
  3. N 是最小归纳集；数学归纳法来自最小性。
  4. n∪m=max(n,m)，n∩m=min(n,m)，这是自然数作为集合时的运算。
  5. 传递集的等价判定：∪A⊆A、∀x∈A(x⊆A)、A⊆P(A)。
  6. 每个自然数都是传递集，N 也是传递集。
  7. 加法和乘法通过递归定理定义，运算律多数用归纳法证明。
  8. 自然数序可写作 m<n ⇔ m∈n，这是后续序数思想的入口。

12、下一步

第五章进入等势、基数、序数与集合论公理。复习第四章时，先稳住 自然数 = 集合、后继 = 并上自身的单元素集、归纳法 = 最小归纳集 这三件事，再回头看传递集和递归定义。