第 9章 集合的基数离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 集合的等势及其性质
– 重要的等势或不等势的结果
– 集合的优势及其性质
– 自然数与自然数集合
– 集合的基数
– 可数集
9.1 集合的等势与优势
9.2 集合的基数本章小结习题作业本章内容定义 9.1 设 A,B是集合，如果存在着从 A到 B的 双射函数,
就称 A和 B是等势 （ same cardinality） 的,记作 A≈B 。
如果 A不与 B等势，则记作 A B。
9.1 集合的等势与优势
≈
通俗的说，集合的势是量度集合所含元素多少的量。
集合的势越大，所含的元素越多。
（ 1） Z≈N。
20:,( )
2 1 0
xxf Z N f x
xx
则 f是 Z到 N的双射函数。 从而证明了 Z≈N。
等势集合的实例 (1)
等势集合的实例 (2)
（ 2） N× N≈N。
( 1 ) ( ):,(,)
2
m n m nf N N N f m n m双射函数等势集合的实例 (3)
（ 3） N≈Q 。
把所有形式为 p/q (p,q为整数且 q>0) 的数排成一张表。
-2/1
[5]
-1/1
[4]
-3/1
[18]
2/1
[10]
3/1
[11]
0/1
[0]
1/1
[1]
-2/2 -1/2
[3]
-3/2
[17]
2/2 3/2
[12]
0/2 1/2
[2]
-2/3
[6]
-1/3
[7]
-3/3 2/3
[9]
3/30/3 1/3
[8]
-2/4 -1/4
[15]
-3/4
[16]
2/4 3/4
[13]
0/4 1/4
[14]
…
…
…
…
…
…
…
…
以 0/1作为第一个数，按照箭头规定的顺序可以,数遍,表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。
等势集合的实例 (4)
（ 4） (0,1)≈R。 其中实数区间 (0,1)={x| x∈ R∧ 0<x<1}。
21,( 0,1 ),( ) t a n
2
xf R f x
则 f 是 (0,1)到 R的双射函数。从而证明了 (0,1)≈R。
等势集合的实例 (5)
（ 5） [0,1]≈(0,1)。 其中 (0,1)和 [0,1]分别为实数开区间和闭区间。
2
1
1 / 2 0
1 / 2 1
()
1 / 2 1 / 2,1,2,...
nn
x
x
fx
xn
xx
其 它双射函数 f,[0,1]?(0,1)，
n32 2121212110
22121 2n543 2 1212121?
2
等势集合的实例 (6)
（ 6）对任何 a,b∈ R,a<b,[0,1]≈[a,b]。
双射函数 f,[0,1]→[ a,b],f(x)＝ (b?a)x+a。
例 9.2 设 A为任意集合，则 P(A)≈{0,1}A。
构造 f,P(A)→{0,1} A，
f(A?)=?A?,?A?∈ P(A)。
其中?A?是集合 A?的特征函数 。
(1)易证 f 是单射的 。
(2)对于任意的 g∈ {0,1}A，
那么有 g,A→{0,1} 。 令
B={x| x∈ A∧ g(x)=1}
则 B?A,且?B=g,即?B∈ P(A),使得 f(B)=g。
所以 f 是满射的。
由等势定义得 P(A)≈{0,1}A。
例 9.2
证明复习定理 9.1 设 A,B,C是任意集合，
（ 1） A≈A。
（ 2） 若 A≈B,则 B≈A。
（ 3） 若 A≈B,B≈C,则 A≈C。
（ 1） IA是从 A到 A的双射，因此 A≈A。
（ 2） 假设 A≈B，存在 f,A?B是双射，
那么 f?1,B?A是从 B到 A的双射，所以 B≈A。
（ 3） 假设 A≈B,B≈C,存在 f,A?B,g:B?C是双射，
则 f?g,A?C是从 A 到 C 的双射 。
所以 A≈C。
等势的性质证明
N ≈ Z ≈ Q ≈ N× N
R ≈ [0,1] ≈(0,1)
任何的实数区间（开区间、闭区间以及半开半闭的区间）
都与实数集合 R等势。
问题,N和 R是否等势？
若干等势集合
（ 1）如果能证明 N [0,1],就可以断定 N R。
只需证明任何函数 f,N→[0,1] 都不是满射的。
构造一个 [0,1]区间的小数 b,使得 b在 N中不存在原像。
（ 2）任取函数 f,A?P(A),构造 B∈ P(A),使得 B在 A中不存在原像。
或者使用反证法。
定理 9.2 康托定理
（ 1） N R。
（ 2） 对任意集合 A都有 A P(A)。
康托定理
≈
≈
≈ ≈
分析
（ 1） 首先规定 [0,1]中数的表示 。
对任意的 x∈ [0,1],令 x = 0.x1x2…,（ 0 ≤ xi≤ 9）
注意：为了保证表示式的唯一性，如果遇到 0.24999…,则将 x
表示为 0.25000… 。
设 f:N→[0,1] 是从 N到 [0,1]的任何一个函数。 f的所有函数值为,
f(0)=0.a1(1)a2(1)…
f(1)=0.a1(2)a2(2)…
…
f(n?1)=0.a1(n)a2(n)…
…
令 y的表示式为 0.b1b2…,并且满足 bi ≠ ai(i),i=1,2,…,
则 y∈ [0,1],但 y与上面列出的任何一个函数值都不相等 。
即 f不是满射的。 所以,N R。
康托定理
≈
康托定理
假设 A≈P(A),则必有函数 f,A→P(A) 是双射函数。
如下构造集合 B：
B＝ {x| x∈ A∧ x? f (x)}
可知 B∈ P(A)。
于是存在唯一一个元素 b∈ A,使得 f(b)＝ B。
若 b∈ B,则由 B的定义知,b? f (b),即 b?B,矛盾 。
若 b?B,则 b? f (b),于是由 B的定义知,b∈ B,矛盾。
（ 2）设 g,A→ P(A)是从 A到 P(A)的任意函数,如下构造集合 B：
B＝ {x| x∈ A∧ x?g(x)}
则 B∈ P(A)。
但是 对任意 x∈ A,都有
x∈ B? x?g(x)
所以，对任意的 x∈ A都有 B≠g(x),即 B?ran g
即 P(A) 中存在元素 B,在 A中找不到原像。
所以,g不是满射的。
所以,A P(A)。
说明康托定理
≈
根据这个定理可以知道 N P(N)。
综合前面的结果，可知 N {0,1}N 。
实际上,P(N),{0,1}N和 R都是比 N“更大,的集合。
≈
≈
定义 9.2
（ 1） 设 A,B是集合，如果存在从 A到 B的 单射 函数，就称 B优势于 A,记作 A≤ ·B。 如果 B不是优势于 A,则记作 A≤ ·B。
（ 2） 设 A,B是集合，若 A≤ ·B且 A B,则称 B真优势于 A,记作 A＜ ·B。 如果 B不是真优势于 A,则记作 A≮ ·B。
例如：
N ≤ ·N
N ≤ ·R
A ≤ ·P(A)
N ＜ ·R
A ＜ ·P(A)
R ≮ ·N
N ≮ ·N
优势
≈
R≤ ·N
定理 9.3 设 A,B,C是任意的集合，则
（ 1） A≤ ·A。
（ 2） 若 A ≤ ·B且 B ≤ ·A,则 A≈B。
（ 3） 若 A ≤ ·B且 B ≤ ·C,则 A ≤ ·C 。
证明：
（ 1） IA是 A到 A的单射,因此 A≤ ·A。
（ 2）证明略。
（ 3）假设 A ≤ ·B且 B ≤ ·C，那么存在单射 f:A→B,g:B→C,
于是 f?g,A→ C也是单射的，因此 A ≤ ·C 。
优势的性质说明
该定理为证明集合之间的等势提供了有力的工具 。
构造两个单射 f,A?B 和 g,B?A函数容易集合等势 。
例题例题,证明 [0,1]与 (0,1)等势。
证明,构造两个单射函数
f,(0,1)→[0,1],f(x)＝ x
g,[0,1]→(0,1),g(x)＝ x/2+1/4
证明 {0,1}N≈[0,1)
(1) 设 x?[0,1),0.x1x2… 是 x的 二进制表示 。
为了使表示唯一，规定表示式中不允许出现连续无数个 1。
例如 x＝ 0.1010111?,应按规定记为 0.1011000? 。
对于 x,如下定义 f,[0,1)→{0,1} N,使得
f(x) = tx,且 tx,N→{0,1},tx(n) = xn+1,n = 0,1,2,…
例如 x = 0.10110100…,则对应于 x的函数 tx是,
n 0 1 2 3 4 5 6 7…
tx(n) 1 0 1 1 0 1 0 0…
易见 tx∈ {0,1}N,且对于 x,y∈ [0,1),x≠y,必有 tx ≠ ty，
即 f(x) ≠ f(y)。
所以,f,[0,1)→{0,1} N是单射的。
(2) 定义函数 g,{0,1}N→[0,1) 。
g的映射法则恰好与 f 相反,即
t∈ {0,1}N,t,N→{0,1},g(t)=0.x1x2…,其中 xn+1=t(n)。
但不同的是，将 0.x1x2… 看作数 x的十进制表示 。
例如 t1,t2∈ {0,1}N,且 g(t1)＝ 0.0111…,g(t2)＝ 0.1000…,
若将 g(t1)和 g(t2)都看成二进制表示，则 g(t1)＝ g(t2)；
但若看成十进制表示，则 g(t1)≠ g(t2)。
所以,g,{0,1}N→[0,1) 是单射的。
根据定理 9.3，有 {0,1}N≈[0,1)。
证明 {0,1}N≈[0,1)
总结
N ≈ Z ≈ Q ≈ N× N
R ≈ [a,b] ≈ (c,d) ≈ {0,1}N ≈ P(N)
其中 [a,b],(c,d)代表任意的实数闭区间和开区间 。
{0,1}A ≈ P(A)
N ＜ ·R
A ＜ ·P(A)
9.2 集合的基数
上一节我们只是抽象地讨论了集合的等势与优势。
本节将进一步研究度量集合的势的方法。
最简单的集合是有穷集。尽管前面已经多次用到,有穷集
” 这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。
定义 9.3 设 a为 集合，称 a∪{ a}为 a的 后继,记作 a+,即
a+=a∪ {a}。
例 9.3考虑空集的一系列后继。
+
=? ∪ {?}
={?}
++
= {?}+
= {?}∪ {{?}}
= {?,{?}}
= {?,?+}
+++
={?,{?}}+
= {?,{?}}∪ {{?,{?}}}
= {?,{?},{?,{?}}}
= {?,?+,?++ }
后继说明
前边的集合都是后边集合的元素。
前边的集合都是后边集合的子集。
利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义,即
0=?
1=0+＝?+ ＝ {?}＝ {0}
2=1+＝ {?}+ ＝ {?}∪ {{?}}＝ {?,{?}}＝ {0,1}
3＝ 2+＝ {?,{?}}+＝ {?,{?},{?,{?}}}＝ {0,1,2}
…
n＝ {0,1,…,n?1}
…
说明自然数的定义这种定义没有概括出自然数的共同特征。
定义 9.4 设 A为 集合，如果满足下面的两个条件：
（ 1）?∈ A
（ 2）?a(a∈ A→ a+∈ A)
称 A是 归纳集 。
例如,下面的集合
{?,?+,?++,?+++,…}
{?,?+,?++,?+++,…,a,a+,a++,a+++,…}
都是归纳集。
归纳集定义 9.5 自然数
（ 1）一个 自然数 n是属于每一个归纳集的集合。
（ 2） 自然数集 N是所有归纳集的交集。
说明,根据定义 9.5得到的自然数集 N 恰好由?,?+,?++,?
+++,… 等集合构成。而这些集合正是构造性方法所定义的全体自然数。
例如,自然数都是集合，集合的运算对自然数都适用。
2∪ 5＝ {0,1}∪ {0,1,2,3,4}＝ {0,1,2,3,4}＝ 5
3∩ 4＝ {0,1,2}∩ {0,1,2,3}＝ {0,1,2}＝ 3
4-2＝ {0,1,2,3}-{0,1}={2,3}
2× 3＝ {0,1}× {0,1,2}＝ {<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}
自然数 n和自然数集合 N的定义
P(1)＝ P({0})＝ {?,{0}}＝ {0,1}
23＝ {0,1}{0,1,2}＝ {f | f,{0,1,2}→{0,1}} ＝ {f0,f1,…,f 7}
其中 f0＝ {<0,0>,<1,0>,<2,0>}
f1 ＝ {<0,0>,<1,0>,<2,1>}
f2 ＝ {<0,0>,<1,1>,<2,0>}
f3 ＝ {<0,0>,<1,1>,<2,1>}
f4 ＝ {<0,1>,<1,0>,<2,0>}
f5 ＝ {<0,1>,<1,0>,<2,1>}
f6 ＝ {<0,1>,<1,1>,<2,0>}
f7 ＝ {<0,1>,<1,1>,<2,1>}
举例
（ 1） 对任何自然数 n,有 n ≈ n。
（ 2） 对任何自然数 n,m,若 m? n,则 m ≈ n。
（ 3） 对任何自然数 n,m,若 m∈ n,则 m? n。
（ 4） 对任何自然数 n和 m,以下三个式子：
m∈ n,m ≈ n,n∈ m
必成立其一且仅成立其一。
（ 5） 自然数的相等与大小顺序对任何自然数 m和 n,有
m = n? m ≈ n
m < n? m∈ n
自然数的性质定义 9.6 有穷集、无穷集
（ 1）一个集合是 有穷的 当且仅当它与某个自然数等势；
（ 2）如果一个集合不是有穷的，就称作 无穷集 。
例如：
{a,b,c}是有穷集，
因为 3＝ {0,1,2}，且 {a,b,c}≈{0,1,2}＝ 3
N和 R都是无穷集，
因为没有自然数与 N和 R等势。
任何有穷集只与唯一的自然数等势。说明有穷集和无穷集定义 9.7
（ 1）对于有穷集合 A,称与 A等势的那个唯一的自然数为 A的基数,记作 card A,即
card A＝ n? A ≈ n （ 对于有穷集 A,card A也可以记作 |A|）
（ 2） 自然数集合 N的基数记作?0，即
card N =?0
（ 3） 实数集 R的基数记作?（读作阿列夫），即
card R =?
基数 (cardinality)
定义 9.8 设 A,B为集合，则
（ 1） card A＝ card B? A≈B
（ 2） card A≤card B? A ≤ ·B
（ 3） card A < card B? card A≤card B∧ card A≠card B
例如：
card Z ＝ card Q ＝ card N× N ＝?0
card P(N) ＝ card 2N ＝ card [a,b] ＝ card (c,d) ＝?
0<?
说明,集合的基数就是集合的势，基数越大，势就越大。
基数的相等和大小关于基数的说明
由于对任何集合 A都满足 A ≤?P(A),所以有
card A < card P(A),这说明 不存在最大的基数 。
将已知的基数按从小到大的顺序排列就得到：
0,1,2,…,n,…,?0,?,…
0,1,2…,n,… 是全体自然数，是 有穷基数 。
0,?,… 是 无穷基数 。
0是最小的无穷基数,?后面还有更大的基数，如
card P(R)等。
可数集定义 9.9 设 A为集合，若 card A≤?0,则称 A为 可数集
(enumerable)或 可列集。
例如：
{a,b,c},5,整数集 Z,有理数集 Q,N× N等都是可数集。
实数集 R不是可数集，与 R等势的集合也不是可数集。
对于任何的可数集，都可以找到一个,数遍,集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。
说明
（ 1） 可数集的任何子集都是可数集 。
一个集合的无限子集若不可数,则该集合也不可数 。
（ 2） 两个可数集的并是可数集 。
（ 3） 两个可数集的笛卡儿积是可数集 。
（ 4） 可数个可数集的笛卡儿积仍是可数集 。
（ 5）无穷集 A的幂集 P(A)不是可数集。
可数集的性质例 9.4 求下列集合的基数 。
（ 1） T＝ {x | x是单词,BASEBALL”中的字母 }
（ 2） B＝ {x | x∈ R∧ x2=9∧ 2x=8}
（ 3） C＝ P(A),A={1,3,7,11}
（ 1） 由 T＝ {B,A,S,E,L}知,card T＝ 5。
（ 2） 由 B＝?可知,card B＝ 0。
（ 3） 由 |A|＝ 4可知,card C＝ card P(A)＝ |P(A)|＝ 24＝ 16。
解答例 9.4
方法一由 card A＝?0,card B＝ n,可知 A,B都是可数集。
令 A={a0,a1,a2,…},B={b0,b1,b2,…,bn?1}。
对任意的 <ai,bj>,<ak,bl>∈ A× B,有
<ai,bj> ＝ <ak,bl>? i ＝ k∧ j ＝ l
定义函数 f,A× B→ N
f(<ai,bj>)＝ in+j,i＝ 0,1,…,j＝ 0,1,…,n?1
由于 f 是 A× B到 N的双射函数，所以 card A× B＝ card N＝?。
例 9.5
解答例 9.5 设 A,B为集合,且 card A＝?0,card B＝ n,n是自然数,n≠0。 求 card A× B。
例 9.5
方法二因为 card A＝?0,card B＝ n,所以 A,B都是可数集。
根据性质（ 3）可知,A× B也是可数集，所以，
card A× B≤?0
当 B≠?时,card A≤card A× B,这就推出
0≤card A× B
综合所述,card A× B ＝?0
本章主 要内容
集合等势的定义
等势的性质
集合优势的定义
优势的性质
重要的集合等势以及优势的结果
自然数及其自然数集合的定义
可数集与不可数集
集合的基数本章学习要求
能够证明两个集合等势 。
能够证明一个集合优势于另一个集合 。
知道什么是可数集与不可数集 。
会求一个简单集合的基数 。
等势的证明方法
证明集合 A与 B等势的方法
– 直接构造从 A到 B的双射函数 f
需要证明 f 的满射性和 f的单射性 。
– 构造两个单射函数 f,A?B 和 g,B?A。
给出函数 f和 g,证明 f和 g的单射性 。
– 利用等势的传递性
– 直接计算 A与 B的基数,得到 card A＝ card B。
证明集合 A与自然数集合 N等势的方法
– 找到一个,数遍,A中元素的顺序 。
例题选讲
1,已知 A＝ {n7|n∈ N},B＝ {n109|n ∈ N },求下列各题：
（ 1） card A （ 2） card B
（ 3） card (A∪ B) （ 4） card (A∩B)
（ 1） 构造双射函数 f,N?A,f(n)=n7,因此 card A＝?0。
（ 2） 构造双射函数 g,N?A,g(n)=n109,因此 card B＝?0。
（ 3） 可数集的并仍旧是可数集 (或者由于 A∪ B?N)，
因此 card (A∪ B)≤?0，
但是?0 ＝ card A≤card (A∪ B)，
从而得到 card (A∪ B)＝?0。
（ 4） 因为 7与 109互素,card (A∩B)＝ {n7?109 | n?N}，
与（ 1）类似得到 card (A∩B)＝?0 。
解答例题选讲
2.已知 card A＝?0,且 card B<card A,求 card (A?B) 。
由 A?B?A,得到 card (A?B)≤card A,即 card(A?B)≤?0。
由 card B<card A可知,B为有穷集,
即存在自然数 n,使得 card B=n。
假设 card (A?B)<?0,那么存在自然数 m,使
card (A?B)＝ m。
从而得到,card A＝ card ((A?B)∪ B)≤n+m
与 card A＝?0矛盾。
因此,card (A?B)＝?0。
解答作业习题九,1,2,3,6,7,8,9,11
复习 —特 征函数
设 A为集合，对于任意的 AA,A?的 特征函数
A?,A→{0,1} 定义为
1,a∈ A?
0,a∈ A?AA?(a) ＝
举例,A的每一个子集 A?都对应于一个特征函数，不同的子集对应于不同的特征函数。
例如 A＝ {a,b,c},则有
＝ {<a,0>,<b,0>,<c,0>},?{a} ＝ {<a,1>,<b,0>,<c,0 >}
{a,b} ＝ {<a,1>,<b,1>,<c,0 >}
例题选讲 (略 )
1,设 A,B为二集合，证明：如果 A≈B,则 P(A)≈P(B)。
因为 A≈B,因此存在双射函数 f,A?B,存在反函数 f?1,B?A，
构造函数 g,P(A)?P(B),
g(T) = f(T),?T?A（ 这里的 f(T)是 T在函数 f的像 ）
首先，证明 g的满射性。
对于任何 S?B,存在 f?1(S)?A,且 g(f?1(S)) = f?f?1(S) = S 。
所以 g是满射的。
其次，证明 g的单射性。
g(T1) = g(T2)? f(T1) = f(T2)
f?1(f(T1) = f?1(f(T2))
IA(T1) = IA(T2)? T1=T2
综合上述，可知 P(A)≈P(B)。
两个可数集的并集为可数集设 A,B为可数集，不妨设 A∩B ＝?。
(1)若两个集合都是有穷集，比如 A＝ {a0,a1,…,an-1},B＝
{b0,b1,…,bm-1},那么 card (A∪B) ＝ n+m≤?0 。
(2)如果其中一个集合是有穷集，另一个是无穷可数集，比如
A＝ {a0,a1,…,an-1},card B＝?0
如下构造双射 h,A∪ B→N,
当 x∈ A时,x＝ ai,h(x)＝ i；
当 x∈ B时,x＝ bj,j＝ 0,1,…,那么 h(x)＝ j+n。
(3)如果 card A＝ card B＝?0,那么存在双射 f,A→N 和 g：
B→N 。 如下构造函数 h,A∪ B→N
当 x∈ A且 f(x)＝ i时,h(x)＝ 2i
当 x∈ B且 g(x)＝ j时,h(x)＝ 2j+1
显然 h为双射。
综上所述,card (A∪ B)＝?0 。
本章的主要内容
– 集合的等势及其性质
– 重要的等势或不等势的结果
– 集合的优势及其性质
– 自然数与自然数集合
– 集合的基数
– 可数集
9.1 集合的等势与优势
9.2 集合的基数本章小结习题作业本章内容定义 9.1 设 A,B是集合，如果存在着从 A到 B的 双射函数,
就称 A和 B是等势 （ same cardinality） 的,记作 A≈B 。
如果 A不与 B等势，则记作 A B。
9.1 集合的等势与优势
≈
通俗的说，集合的势是量度集合所含元素多少的量。
集合的势越大，所含的元素越多。
（ 1） Z≈N。
20:,( )
2 1 0
xxf Z N f x
xx
则 f是 Z到 N的双射函数。 从而证明了 Z≈N。
等势集合的实例 (1)
等势集合的实例 (2)
（ 2） N× N≈N。
( 1 ) ( ):,(,)
2
m n m nf N N N f m n m双射函数等势集合的实例 (3)
（ 3） N≈Q 。
把所有形式为 p/q (p,q为整数且 q>0) 的数排成一张表。
-2/1
[5]
-1/1
[4]
-3/1
[18]
2/1
[10]
3/1
[11]
0/1
[0]
1/1
[1]
-2/2 -1/2
[3]
-3/2
[17]
2/2 3/2
[12]
0/2 1/2
[2]
-2/3
[6]
-1/3
[7]
-3/3 2/3
[9]
3/30/3 1/3
[8]
-2/4 -1/4
[15]
-3/4
[16]
2/4 3/4
[13]
0/4 1/4
[14]
…
…
…
…
…
…
…
…
以 0/1作为第一个数，按照箭头规定的顺序可以,数遍,表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。
等势集合的实例 (4)
（ 4） (0,1)≈R。 其中实数区间 (0,1)={x| x∈ R∧ 0<x<1}。
21,( 0,1 ),( ) t a n
2
xf R f x
则 f 是 (0,1)到 R的双射函数。从而证明了 (0,1)≈R。
等势集合的实例 (5)
（ 5） [0,1]≈(0,1)。 其中 (0,1)和 [0,1]分别为实数开区间和闭区间。
2
1
1 / 2 0
1 / 2 1
()
1 / 2 1 / 2,1,2,...
nn
x
x
fx
xn
xx
其 它双射函数 f,[0,1]?(0,1)，
n32 2121212110
22121 2n543 2 1212121?
2
等势集合的实例 (6)
（ 6）对任何 a,b∈ R,a<b,[0,1]≈[a,b]。
双射函数 f,[0,1]→[ a,b],f(x)＝ (b?a)x+a。
例 9.2 设 A为任意集合，则 P(A)≈{0,1}A。
构造 f,P(A)→{0,1} A，
f(A?)=?A?,?A?∈ P(A)。
其中?A?是集合 A?的特征函数 。
(1)易证 f 是单射的 。
(2)对于任意的 g∈ {0,1}A，
那么有 g,A→{0,1} 。 令
B={x| x∈ A∧ g(x)=1}
则 B?A,且?B=g,即?B∈ P(A),使得 f(B)=g。
所以 f 是满射的。
由等势定义得 P(A)≈{0,1}A。
例 9.2
证明复习定理 9.1 设 A,B,C是任意集合，
（ 1） A≈A。
（ 2） 若 A≈B,则 B≈A。
（ 3） 若 A≈B,B≈C,则 A≈C。
（ 1） IA是从 A到 A的双射，因此 A≈A。
（ 2） 假设 A≈B，存在 f,A?B是双射，
那么 f?1,B?A是从 B到 A的双射，所以 B≈A。
（ 3） 假设 A≈B,B≈C,存在 f,A?B,g:B?C是双射，
则 f?g,A?C是从 A 到 C 的双射 。
所以 A≈C。
等势的性质证明
N ≈ Z ≈ Q ≈ N× N
R ≈ [0,1] ≈(0,1)
任何的实数区间（开区间、闭区间以及半开半闭的区间）
都与实数集合 R等势。
问题,N和 R是否等势？
若干等势集合
（ 1）如果能证明 N [0,1],就可以断定 N R。
只需证明任何函数 f,N→[0,1] 都不是满射的。
构造一个 [0,1]区间的小数 b,使得 b在 N中不存在原像。
（ 2）任取函数 f,A?P(A),构造 B∈ P(A),使得 B在 A中不存在原像。
或者使用反证法。
定理 9.2 康托定理
（ 1） N R。
（ 2） 对任意集合 A都有 A P(A)。
康托定理
≈
≈
≈ ≈
分析
（ 1） 首先规定 [0,1]中数的表示 。
对任意的 x∈ [0,1],令 x = 0.x1x2…,（ 0 ≤ xi≤ 9）
注意：为了保证表示式的唯一性，如果遇到 0.24999…,则将 x
表示为 0.25000… 。
设 f:N→[0,1] 是从 N到 [0,1]的任何一个函数。 f的所有函数值为,
f(0)=0.a1(1)a2(1)…
f(1)=0.a1(2)a2(2)…
…
f(n?1)=0.a1(n)a2(n)…
…
令 y的表示式为 0.b1b2…,并且满足 bi ≠ ai(i),i=1,2,…,
则 y∈ [0,1],但 y与上面列出的任何一个函数值都不相等 。
即 f不是满射的。 所以,N R。
康托定理
≈
康托定理
假设 A≈P(A),则必有函数 f,A→P(A) 是双射函数。
如下构造集合 B：
B＝ {x| x∈ A∧ x? f (x)}
可知 B∈ P(A)。
于是存在唯一一个元素 b∈ A,使得 f(b)＝ B。
若 b∈ B,则由 B的定义知,b? f (b),即 b?B,矛盾 。
若 b?B,则 b? f (b),于是由 B的定义知,b∈ B,矛盾。
（ 2）设 g,A→ P(A)是从 A到 P(A)的任意函数,如下构造集合 B：
B＝ {x| x∈ A∧ x?g(x)}
则 B∈ P(A)。
但是 对任意 x∈ A,都有
x∈ B? x?g(x)
所以，对任意的 x∈ A都有 B≠g(x),即 B?ran g
即 P(A) 中存在元素 B,在 A中找不到原像。
所以,g不是满射的。
所以,A P(A)。
说明康托定理
≈
根据这个定理可以知道 N P(N)。
综合前面的结果，可知 N {0,1}N 。
实际上,P(N),{0,1}N和 R都是比 N“更大,的集合。
≈
≈
定义 9.2
（ 1） 设 A,B是集合，如果存在从 A到 B的 单射 函数，就称 B优势于 A,记作 A≤ ·B。 如果 B不是优势于 A,则记作 A≤ ·B。
（ 2） 设 A,B是集合，若 A≤ ·B且 A B,则称 B真优势于 A,记作 A＜ ·B。 如果 B不是真优势于 A,则记作 A≮ ·B。
例如：
N ≤ ·N
N ≤ ·R
A ≤ ·P(A)
N ＜ ·R
A ＜ ·P(A)
R ≮ ·N
N ≮ ·N
优势
≈
R≤ ·N
定理 9.3 设 A,B,C是任意的集合，则
（ 1） A≤ ·A。
（ 2） 若 A ≤ ·B且 B ≤ ·A,则 A≈B。
（ 3） 若 A ≤ ·B且 B ≤ ·C,则 A ≤ ·C 。
证明：
（ 1） IA是 A到 A的单射,因此 A≤ ·A。
（ 2）证明略。
（ 3）假设 A ≤ ·B且 B ≤ ·C，那么存在单射 f:A→B,g:B→C,
于是 f?g,A→ C也是单射的，因此 A ≤ ·C 。
优势的性质说明
该定理为证明集合之间的等势提供了有力的工具 。
构造两个单射 f,A?B 和 g,B?A函数容易集合等势 。
例题例题,证明 [0,1]与 (0,1)等势。
证明,构造两个单射函数
f,(0,1)→[0,1],f(x)＝ x
g,[0,1]→(0,1),g(x)＝ x/2+1/4
证明 {0,1}N≈[0,1)
(1) 设 x?[0,1),0.x1x2… 是 x的 二进制表示 。
为了使表示唯一，规定表示式中不允许出现连续无数个 1。
例如 x＝ 0.1010111?,应按规定记为 0.1011000? 。
对于 x,如下定义 f,[0,1)→{0,1} N,使得
f(x) = tx,且 tx,N→{0,1},tx(n) = xn+1,n = 0,1,2,…
例如 x = 0.10110100…,则对应于 x的函数 tx是,
n 0 1 2 3 4 5 6 7…
tx(n) 1 0 1 1 0 1 0 0…
易见 tx∈ {0,1}N,且对于 x,y∈ [0,1),x≠y,必有 tx ≠ ty，
即 f(x) ≠ f(y)。
所以,f,[0,1)→{0,1} N是单射的。
(2) 定义函数 g,{0,1}N→[0,1) 。
g的映射法则恰好与 f 相反,即
t∈ {0,1}N,t,N→{0,1},g(t)=0.x1x2…,其中 xn+1=t(n)。
但不同的是，将 0.x1x2… 看作数 x的十进制表示 。
例如 t1,t2∈ {0,1}N,且 g(t1)＝ 0.0111…,g(t2)＝ 0.1000…,
若将 g(t1)和 g(t2)都看成二进制表示，则 g(t1)＝ g(t2)；
但若看成十进制表示，则 g(t1)≠ g(t2)。
所以,g,{0,1}N→[0,1) 是单射的。
根据定理 9.3，有 {0,1}N≈[0,1)。
证明 {0,1}N≈[0,1)
总结
N ≈ Z ≈ Q ≈ N× N
R ≈ [a,b] ≈ (c,d) ≈ {0,1}N ≈ P(N)
其中 [a,b],(c,d)代表任意的实数闭区间和开区间 。
{0,1}A ≈ P(A)
N ＜ ·R
A ＜ ·P(A)
9.2 集合的基数
上一节我们只是抽象地讨论了集合的等势与优势。
本节将进一步研究度量集合的势的方法。
最简单的集合是有穷集。尽管前面已经多次用到,有穷集
” 这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。
定义 9.3 设 a为 集合，称 a∪{ a}为 a的 后继,记作 a+,即
a+=a∪ {a}。
例 9.3考虑空集的一系列后继。
+
=? ∪ {?}
={?}
++
= {?}+
= {?}∪ {{?}}
= {?,{?}}
= {?,?+}
+++
={?,{?}}+
= {?,{?}}∪ {{?,{?}}}
= {?,{?},{?,{?}}}
= {?,?+,?++ }
后继说明
前边的集合都是后边集合的元素。
前边的集合都是后边集合的子集。
利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义,即
0=?
1=0+＝?+ ＝ {?}＝ {0}
2=1+＝ {?}+ ＝ {?}∪ {{?}}＝ {?,{?}}＝ {0,1}
3＝ 2+＝ {?,{?}}+＝ {?,{?},{?,{?}}}＝ {0,1,2}
…
n＝ {0,1,…,n?1}
…
说明自然数的定义这种定义没有概括出自然数的共同特征。
定义 9.4 设 A为 集合，如果满足下面的两个条件：
（ 1）?∈ A
（ 2）?a(a∈ A→ a+∈ A)
称 A是 归纳集 。
例如,下面的集合
{?,?+,?++,?+++,…}
{?,?+,?++,?+++,…,a,a+,a++,a+++,…}
都是归纳集。
归纳集定义 9.5 自然数
（ 1）一个 自然数 n是属于每一个归纳集的集合。
（ 2） 自然数集 N是所有归纳集的交集。
说明,根据定义 9.5得到的自然数集 N 恰好由?,?+,?++,?
+++,… 等集合构成。而这些集合正是构造性方法所定义的全体自然数。
例如,自然数都是集合，集合的运算对自然数都适用。
2∪ 5＝ {0,1}∪ {0,1,2,3,4}＝ {0,1,2,3,4}＝ 5
3∩ 4＝ {0,1,2}∩ {0,1,2,3}＝ {0,1,2}＝ 3
4-2＝ {0,1,2,3}-{0,1}={2,3}
2× 3＝ {0,1}× {0,1,2}＝ {<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}
自然数 n和自然数集合 N的定义
P(1)＝ P({0})＝ {?,{0}}＝ {0,1}
23＝ {0,1}{0,1,2}＝ {f | f,{0,1,2}→{0,1}} ＝ {f0,f1,…,f 7}
其中 f0＝ {<0,0>,<1,0>,<2,0>}
f1 ＝ {<0,0>,<1,0>,<2,1>}
f2 ＝ {<0,0>,<1,1>,<2,0>}
f3 ＝ {<0,0>,<1,1>,<2,1>}
f4 ＝ {<0,1>,<1,0>,<2,0>}
f5 ＝ {<0,1>,<1,0>,<2,1>}
f6 ＝ {<0,1>,<1,1>,<2,0>}
f7 ＝ {<0,1>,<1,1>,<2,1>}
举例
（ 1） 对任何自然数 n,有 n ≈ n。
（ 2） 对任何自然数 n,m,若 m? n,则 m ≈ n。
（ 3） 对任何自然数 n,m,若 m∈ n,则 m? n。
（ 4） 对任何自然数 n和 m,以下三个式子：
m∈ n,m ≈ n,n∈ m
必成立其一且仅成立其一。
（ 5） 自然数的相等与大小顺序对任何自然数 m和 n,有
m = n? m ≈ n
m < n? m∈ n
自然数的性质定义 9.6 有穷集、无穷集
（ 1）一个集合是 有穷的 当且仅当它与某个自然数等势；
（ 2）如果一个集合不是有穷的，就称作 无穷集 。
例如：
{a,b,c}是有穷集，
因为 3＝ {0,1,2}，且 {a,b,c}≈{0,1,2}＝ 3
N和 R都是无穷集，
因为没有自然数与 N和 R等势。
任何有穷集只与唯一的自然数等势。说明有穷集和无穷集定义 9.7
（ 1）对于有穷集合 A,称与 A等势的那个唯一的自然数为 A的基数,记作 card A,即
card A＝ n? A ≈ n （ 对于有穷集 A,card A也可以记作 |A|）
（ 2） 自然数集合 N的基数记作?0，即
card N =?0
（ 3） 实数集 R的基数记作?（读作阿列夫），即
card R =?
基数 (cardinality)
定义 9.8 设 A,B为集合，则
（ 1） card A＝ card B? A≈B
（ 2） card A≤card B? A ≤ ·B
（ 3） card A < card B? card A≤card B∧ card A≠card B
例如：
card Z ＝ card Q ＝ card N× N ＝?0
card P(N) ＝ card 2N ＝ card [a,b] ＝ card (c,d) ＝?
0<?
说明,集合的基数就是集合的势，基数越大，势就越大。
基数的相等和大小关于基数的说明
由于对任何集合 A都满足 A ≤?P(A),所以有
card A < card P(A),这说明 不存在最大的基数 。
将已知的基数按从小到大的顺序排列就得到：
0,1,2,…,n,…,?0,?,…
0,1,2…,n,… 是全体自然数，是 有穷基数 。
0,?,… 是 无穷基数 。
0是最小的无穷基数,?后面还有更大的基数，如
card P(R)等。
可数集定义 9.9 设 A为集合，若 card A≤?0,则称 A为 可数集
(enumerable)或 可列集。
例如：
{a,b,c},5,整数集 Z,有理数集 Q,N× N等都是可数集。
实数集 R不是可数集，与 R等势的集合也不是可数集。
对于任何的可数集，都可以找到一个,数遍,集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。
说明
（ 1） 可数集的任何子集都是可数集 。
一个集合的无限子集若不可数,则该集合也不可数 。
（ 2） 两个可数集的并是可数集 。
（ 3） 两个可数集的笛卡儿积是可数集 。
（ 4） 可数个可数集的笛卡儿积仍是可数集 。
（ 5）无穷集 A的幂集 P(A)不是可数集。
可数集的性质例 9.4 求下列集合的基数 。
（ 1） T＝ {x | x是单词,BASEBALL”中的字母 }
（ 2） B＝ {x | x∈ R∧ x2=9∧ 2x=8}
（ 3） C＝ P(A),A={1,3,7,11}
（ 1） 由 T＝ {B,A,S,E,L}知,card T＝ 5。
（ 2） 由 B＝?可知,card B＝ 0。
（ 3） 由 |A|＝ 4可知,card C＝ card P(A)＝ |P(A)|＝ 24＝ 16。
解答例 9.4
方法一由 card A＝?0,card B＝ n,可知 A,B都是可数集。
令 A={a0,a1,a2,…},B={b0,b1,b2,…,bn?1}。
对任意的 <ai,bj>,<ak,bl>∈ A× B,有
<ai,bj> ＝ <ak,bl>? i ＝ k∧ j ＝ l
定义函数 f,A× B→ N
f(<ai,bj>)＝ in+j,i＝ 0,1,…,j＝ 0,1,…,n?1
由于 f 是 A× B到 N的双射函数，所以 card A× B＝ card N＝?。
例 9.5
解答例 9.5 设 A,B为集合,且 card A＝?0,card B＝ n,n是自然数,n≠0。 求 card A× B。
例 9.5
方法二因为 card A＝?0,card B＝ n,所以 A,B都是可数集。
根据性质（ 3）可知,A× B也是可数集，所以，
card A× B≤?0
当 B≠?时,card A≤card A× B,这就推出
0≤card A× B
综合所述,card A× B ＝?0
本章主 要内容
集合等势的定义
等势的性质
集合优势的定义
优势的性质
重要的集合等势以及优势的结果
自然数及其自然数集合的定义
可数集与不可数集
集合的基数本章学习要求
能够证明两个集合等势 。
能够证明一个集合优势于另一个集合 。
知道什么是可数集与不可数集 。
会求一个简单集合的基数 。
等势的证明方法
证明集合 A与 B等势的方法
– 直接构造从 A到 B的双射函数 f
需要证明 f 的满射性和 f的单射性 。
– 构造两个单射函数 f,A?B 和 g,B?A。
给出函数 f和 g,证明 f和 g的单射性 。
– 利用等势的传递性
– 直接计算 A与 B的基数,得到 card A＝ card B。
证明集合 A与自然数集合 N等势的方法
– 找到一个,数遍,A中元素的顺序 。
例题选讲
1,已知 A＝ {n7|n∈ N},B＝ {n109|n ∈ N },求下列各题：
（ 1） card A （ 2） card B
（ 3） card (A∪ B) （ 4） card (A∩B)
（ 1） 构造双射函数 f,N?A,f(n)=n7,因此 card A＝?0。
（ 2） 构造双射函数 g,N?A,g(n)=n109,因此 card B＝?0。
（ 3） 可数集的并仍旧是可数集 (或者由于 A∪ B?N)，
因此 card (A∪ B)≤?0，
但是?0 ＝ card A≤card (A∪ B)，
从而得到 card (A∪ B)＝?0。
（ 4） 因为 7与 109互素,card (A∩B)＝ {n7?109 | n?N}，
与（ 1）类似得到 card (A∩B)＝?0 。
解答例题选讲
2.已知 card A＝?0,且 card B<card A,求 card (A?B) 。
由 A?B?A,得到 card (A?B)≤card A,即 card(A?B)≤?0。
由 card B<card A可知,B为有穷集,
即存在自然数 n,使得 card B=n。
假设 card (A?B)<?0,那么存在自然数 m,使
card (A?B)＝ m。
从而得到,card A＝ card ((A?B)∪ B)≤n+m
与 card A＝?0矛盾。
因此,card (A?B)＝?0。
解答作业习题九,1,2,3,6,7,8,9,11
复习 —特 征函数
设 A为集合，对于任意的 AA,A?的 特征函数
A?,A→{0,1} 定义为
1,a∈ A?
0,a∈ A?AA?(a) ＝
举例,A的每一个子集 A?都对应于一个特征函数，不同的子集对应于不同的特征函数。
例如 A＝ {a,b,c},则有
＝ {<a,0>,<b,0>,<c,0>},?{a} ＝ {<a,1>,<b,0>,<c,0 >}
{a,b} ＝ {<a,1>,<b,1>,<c,0 >}
例题选讲 (略 )
1,设 A,B为二集合，证明：如果 A≈B,则 P(A)≈P(B)。
因为 A≈B,因此存在双射函数 f,A?B,存在反函数 f?1,B?A，
构造函数 g,P(A)?P(B),
g(T) = f(T),?T?A（ 这里的 f(T)是 T在函数 f的像 ）
首先，证明 g的满射性。
对于任何 S?B,存在 f?1(S)?A,且 g(f?1(S)) = f?f?1(S) = S 。
所以 g是满射的。
其次，证明 g的单射性。
g(T1) = g(T2)? f(T1) = f(T2)
f?1(f(T1) = f?1(f(T2))
IA(T1) = IA(T2)? T1=T2
综合上述，可知 P(A)≈P(B)。
两个可数集的并集为可数集设 A,B为可数集，不妨设 A∩B ＝?。
(1)若两个集合都是有穷集，比如 A＝ {a0,a1,…,an-1},B＝
{b0,b1,…,bm-1},那么 card (A∪B) ＝ n+m≤?0 。
(2)如果其中一个集合是有穷集，另一个是无穷可数集，比如
A＝ {a0,a1,…,an-1},card B＝?0
如下构造双射 h,A∪ B→N,
当 x∈ A时,x＝ ai,h(x)＝ i；
当 x∈ B时,x＝ bj,j＝ 0,1,…,那么 h(x)＝ j+n。
(3)如果 card A＝ card B＝?0,那么存在双射 f,A→N 和 g：
B→N 。 如下构造函数 h,A∪ B→N
当 x∈ A且 f(x)＝ i时,h(x)＝ 2i
当 x∈ B且 g(x)＝ j时,h(x)＝ 2j+1
显然 h为双射。
综上所述,card (A∪ B)＝?0 。
