返回：0100 离散数学课程总目录 · 上一章：0104 自然数的定义与性质 · 下一章：0106 图的基本概念、通路回路与连通性

1、资料来源与学习目标

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

资料 内容
5.1 集合的等势、有穷集与无穷集合 等势、典型等势例子、Cantor 定理、有穷集、无穷集
5.2 基数和基数的比较运算 基数定义、优势/劣势、Schröder-Bernstein 定理、可数集、基数运算
5.3 集合论习题课 4-5 章 第四、五章习题复盘
5.3 序数和集合论公理 序数、连续统假设、ZF/ZFC 公理、罗素悖论
005 习题与答案 习题 2、5、11、12、补充题，重点考察等价类、等势、可数性和基数运算

本章的核心目标：分清基数和序数。基数回答“有多少”，靠双射匹配；序数回答“排第几、先后如何”，靠良序结构。

2、颜色标注

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

3、章节主线

模块 本章要会什么 后续连接
等势 会用双射证明两个集合一样大 基数定义
Cantor 定理 知道 N 不可枚举 R，且 card A < card P(A) 不可数、幂集
有穷与无穷 会用“是否与自然数等势”或“是否与真子集等势”判定 可数性
基数比较 会用单射定义 ≤，用 Schröder-Bernstein 判等 基数偏序
可数集 记住 Z,Q,N×N 可数，R,P(N) 不可数 数据枚举
基数运算 会写和、积、幂的集合定义 组合计数
序数 知道 ω,ω+1,2ω 等描述的是顺序类型 良序、序数
ZFC 知道集合论公理是为了避免悖论并保证构造合法 理论边界

4、等势

集合 A 与 B 等势，记作 A≈B：

1
A≈B ⇔ 存在双射 f:A→B

常见例子：

等势关系 双射思路
N≈N_even f(n)=2n
N≈N_odd g(n)=2n+1
Z≈N 0,1,-1,2,-2,... 重新编号
N×N≈N 用配对函数或斜线枚举
N≈Q 把既约分数排成序列
(0,1)≈R 如 tan((x-1/2)π)
[0,1]≈(0,1) Hilbert 旅馆式搬家

无限集合的直觉会“反常”：一个集合可以和自己的真子集等势，比如 N≈N_even。这正是无穷集区别于有穷集的地方。

等势关系是等价关系：

性质 证明思路
自反 I_A:A→A 是双射
对称 若 f:A→B 双射，则 f^-1:B→A 双射
传递 若 f:A→B、g:B→C 双射，则 g∘f:A→C 双射

幂集与特征函数等势：

1
P(A)≈2^A={f|f:A→{0,1}}

对应关系是：

1
2
B⊆A  ↔  χ_B:A→{0,1}
χ_B(x)=1 ⇔ x∈B

5、Cantor 定理

Cantor 定理有两条核心结论：

1
2
N 不与 R 等势
对任意集合 A，A 不与 P(A) 等势

第二条可加强成：

1
card A < card P(A)

证明 A 不与 P(A) 等势的标准反证：

1
2
3
4
5
假设 f:A→P(A) 是满射。
令 B={x∈A | x∉f(x)}。
因为 B⊆A，所以 B∈P(A)。
若 f 满射，则存在 x0∈A，使 f(x0)=B。
于是 x0∈B ⇔ x0∉f(x0) ⇔ x0∉B，矛盾。

证明 N 不与 R 等势的思想是对角线法：假设 [0,1] 中所有实数能排成序列 x1,x2,x3,...，构造一个新小数 x，让它第 n 位不同于 xn 的第 n 位，于是 x 不在这个序列中。

N≈Q 但 N≉R。有理数虽然稠密，看起来很多，但仍能排成一个序列；实数不能。

6、有穷集、无穷集与可数集

6.1 有穷与无穷

有穷集：

1
A 是有穷集 ⇔ A≈n，某个 n∈N

等价说法：

1
有穷集不能与自己的真子集建立双射

无穷集：

1
A 是无穷集 ⇔ A 不与任何自然数 n 等势

等价说法：

1
无穷集能与自己的某个真子集建立双射

重要结论：

结论 说明
不存在与自己真子集等势的自然数 自然数是标准有限大小
不存在与自己真子集等势的有穷集 有穷集继承自然数的有限性
N 是无穷集 因为 N≈N-{0}
任何有穷集都与唯一自然数等势 这个自然数就是它的大小
有穷集的子集仍为有穷集 子集不会比原有穷集更大

6.2 可数集

可数集，也叫可列集：

1
A 可数 ⇔ card A≤ℵ0

无穷可数集就是可以写成：

1
A={a1,a2,a3,...}

常见结论：

集合 基数
N ℵ0
Z ℵ0
Q ℵ0
N×N ℵ0
R 𝔠=2^ℵ0
P(N) 2^ℵ0

定理：

1
A 是无穷集 ⇒ P(A) 不是可数集

7、基数与基数比较

7.1 基数定义

基数表示集合大小：

1
card A=card B ⇔ A≈B

对于有穷集：

1
card A=n ⇔ A≈n

常用记号：

记号 含义
0,1,2,... 有穷基数
ℵ0 N 的基数
𝔠 R 的基数，也等于 2^ℵ0
κ,λ,μ 任意基数

7.2 优势、劣势与基数比较

B 比 A 优势，或 A 比 B 劣势：

1
A≼B ⇔ 存在单射 f:A→B

等价说法：

1
A≼B ⇔ 存在 C⊆B，使 A≈C

基数比较定义：

1
2
κ≤λ ⇔ A≼B，其中 card A=κ，card B=λ
κ<λ ⇔ κ≤λ 且 κ≠λ

重要结论：

1
2
3
A⊆B ⇒ A≼B
A≈B ⇒ A≼B 且 B≼A
card A < card P(A)

Schröder-Bernstein 定理：

1
2
A≼B 且 B≼A ⇒ A≈B
κ≤λ 且 λ≤κ ⇒ κ=λ

做基数比较题时，常用三件套：找单射、找双射、夹逼。比如 A⊆A∪B⊆N 且 A≈N，就能推出 card(A∪B)=ℵ0。

8、基数运算

设 card K=κ，card L=λ。

运算 集合定义
加法 κ+λ=card(K∪L)，其中 K∩L=∅
乘法 κ·λ=card(K×L)
幂 κ^λ=card(L→K)

基本性质：

1
2
3
4
5
6
κ+λ=λ+κ
(κ+λ)+μ=κ+(λ+μ)
κ·(λ+μ)=κ·λ+κ·μ
κ^(λ+μ)=κ^λ·κ^μ
(κ·λ)^μ=κ^μ·λ^μ
(κ^λ)^μ=κ^(λ·μ)

幂集相关：

1
2
3
4
2^card(A)=card P(A)
κ<2^κ
card P(N)=2^ℵ0
card R=2^ℵ0

无穷基数运算常用结论：

1
2
3
4
若 κ 为无穷基数，则 κ·κ=κ
若 κ 为无穷基数，λ≠0，则 κ+λ=κ·λ=max{κ,λ}
κ+κ=κ·κ=κ
κ^κ=2^κ

9、序数与集合论公理

9.1 序数

基数关心“多少”，序数关心“顺序类型”。良序集可以按最小元不断取出：

1
2
3
4
t0=min(A)
t1=min(A-{t0})
t2=min(A-{t0,t1})
...

典型序数：

1
2
3
4
0,1,2,3,...
ω,ω+1,ω+2,...
2ω,2ω+1,...
ω^2,ω^3,...

三类序数：

类型 例子 直觉
0 0 起点
后继序数 1,2,...,ω+1,ω+2 有直接前一个
极限序数 ω,2ω,ω^2 有头无尾，没有最后一步

初始序数是不与前面任何序数等势的序数，用它们代表基数。

9.2 连续统假设

连续统假设 CH 说的是：

1
不存在基数 κ，使 ℵ0<κ<2^ℵ0

它在通常的 ZFC 公理系统中既不能被证明，也不能被否定。

9.3 ZF/ZFC 公理

ZF 系统包括这些核心公理：

公理 作用
外延公理 元素相同则集合相同
空集公理 空集存在
无序对公理 {a,b} 存在
并集公理 集族的并存在
幂集公理 P(A) 存在
子集公理 从已有集合按性质筛子集
正则公理 防止 A∈A 这类循环
替换公理 函数像 `{f(a)
无穷公理 无穷集存在

ZFC = ZF + 选择公理。

选择公理的等价形式包括：良序原理、Zorn 引理、Hausdorff 极大原理等。

罗素悖论的典型集合：

1
S={x|x∉x}

若问 S∈S 是否成立，会得到：

1
S∈S ⇔ S∉S

所以现代集合论公理不允许随便用任意性质构造“所有满足性质的对象的集合”，只能在已有集合中用子集公理筛选。

10、习题与答案

习题 2：函数像相同诱导等价关系

题目：设 A≠∅，在 (A→A) 上定义关系：

1
R={<f,g>|f,g∈(A→A)∧ran f=ran g}

证明：

1
2
(1) R 是 A→A 上的等价关系
(2) (A→A)/R≈P(A)-{∅}

证明 (1)：

1
2
3
自反：ran f=ran f，所以 <f,f>∈R。
对称：若 <f,g>∈R，则 ran f=ran g，所以 ran g=ran f，故 <g,f>∈R。
传递：若 <f,g>∈R 且 <g,h>∈R，则 ran f=ran g=ran h，故 <f,h>∈R。

所以 R 是等价关系。

证明 (2)：定义：

1
2
F:(A→A)/R → P(A)-{∅}
F([f]_R)=ran f

良定义：若 [f]_R=[g]_R，则 <f,g>∈R，所以 ran f=ran g。

单射：

1
2
3
4
F([f]_R)=F([g]_R)
⇒ ran f=ran g
⇒ <f,g>∈R
⇒ [f]_R=[g]_R

满射：任取非空子集 B⊆A。取 b∈B，定义：

1
2
3
f(x)=
  x, x∈B
  b, x∈A-B

则 f:A→A 且 ran f=B，所以 F([f]_R)=B。

因此 F 是双射，(A→A)/R≈P(A)-{∅}。

习题 5：自然数真子集与更小自然数等势

题目：设 c 为某个自然数 n 的真子集，则 c 与属于 n 的某个自然数等势。

证明：用归纳法。令：

1
S={n|n∈N∧∀c(c⊂n⇒∃m(m∈n∧c≈m))}

证明 S=N。

  1. 0∈S。因为不存在 c⊂0=∅，蕴涵式前件为假，命题成立。
  2. 假设 n∈S，证明 n+=n∪{n}∈S。

任取 c⊂n+，分两类。

若 n∉c：

1
2
3
c⊆n。
若 c=n，则取 m=n∈n+，有 c≈m。
若 c⊂n，由归纳假设，存在 m∈n，使 c≈m；当然 m∈n+。

若 n∈c：

1
2
3
4
c' = c-{n} ⊂ n。
由归纳假设，存在 m∈n，使 c'≈m。
于是 c=c'∪{n}≈m∪{m}=m+。
因为 m∈n，所以 m+∈n+。

两种情况都找到 m∈n+ 使 c≈m，所以 n+∈S。由数学归纳法，S=N。

习题 11：幂集合的基数

题目：设：

1
2
A={n^7|n∈N∧n≠0}
B={n^109|n∈N∧n≠0}

求：

1
2
3
4
(1) card A
(2) card B
(3) card(A∪B)
(4) card(A∩B)

答案：

1
2
3
4
card A=ℵ0
card B=ℵ0
card(A∪B)=ℵ0
card(A∩B)=ℵ0

理由：

1
2
3
f:N→A，f(n)=(n+1)^7 是双射，所以 A≈N。
同理 B≈N。
A⊆A∪B⊆N，且 A≈N，所以 card(A∪B)=ℵ0。

对交集，令：

1
C={n^(7·109)|n∈N∧n≠0}

因为：

1
n^(7·109)=(n^109)^7=(n^7)^109

所以 C⊆A∩B⊆A，且 C≈N。夹逼得：

1
card(A∩B)=ℵ0

事实上，因为 gcd(7,109)=1，可以进一步证明 A∩B=C。

习题 12：等势集合的幂集基数相同

题目：设 A,B 为集合，证明如果 A≈B，则：

1
card P(A)=card P(B)

证明：因为 A≈B，存在双射 f:A→B。定义：

1
2
H:P(A)→P(B)
H(C)=f(C)={f(x)|x∈C}

单射：若 C1≠C2，则存在元素只属于其中一个集合。由于 f 单射，像集也不同，所以 H(C1)≠H(C2)。

满射：任取 D∈P(B)，因为 f 是双射，f^-1(D)∈P(A)，且：

1
H(f^-1(D))=f(f^-1(D))=D

所以 H 是双射，P(A)≈P(B)，从而 card P(A)=card P(B)。

补充题：三个基数恒等式

设 κ 为任意基数，证明：

1
2
3
(1) κ^0=1
(2) 当 κ≠0 时，0^κ=0
(3) κ+κ=2κ

证明：设 κ=card A。

(1)：

1
2
∅→A={∅}
κ^0=card(∅→A)=card{∅}=1

(2)：当 κ≠0 时，A≠∅。从非空集合到空集没有函数：

1
2
A→∅=∅
0^κ=card(A→∅)=0

(3)：取两个互不相交的副本：

1
2
3
4
5
({1}×A)∩({2}×A)=∅
({1}×A)∪({2}×A)={1,2}×A
card({1}×A)=κ
card({2}×A)=κ
card({1,2}×A)=2κ

所以：

1
κ+κ=card(({1}×A)∪({2}×A))=card({1,2}×A)=2κ

11、复盘清单

  1. 等势就是存在双射；基数相等就是等势。
  2. N≈Z≈Q≈N×N，但 N≉R。
  3. Cantor 定理：card A < card P(A)。
  4. 有穷集不能与自己的真子集等势；无穷集可以。
  5. A≼B 表示存在从 A 到 B 的单射。
  6. Schröder-Bernstein：互相能单射进去，就等势。
  7. 可数集就是基数不超过 ℵ0 的集合；P(N) 不可数。
  8. 基数幂 κ^λ 是函数集 λ→κ 的基数。
  9. 序数看顺序，基数看大小；ω 是第一个无限序数。
  10. ZFC 公理限制了“集合可以怎样构造”，避免罗素悖论。

12、下一步

第六章开始进入图论。复习第五章时，先把 双射 = 等势、单射 = 劣势、Cantor 对角线、可数/不可数 四件事稳住，再看基数运算和序数部分。