集合的基数 (Cardinal Number) 离散数学－集合论 南京大学计算机科学与技术系

集合的基数 引言：有限与无限 集合的等势关系 集合的基数 可数集(Countable set) Cantor定理 优势关系 Bernstein定理

我们怎么比较集合的大小 “数得清”的我们就数元素个数。 “数不清”的咋办？ “常识”不一定经得起追问。

有限与无限：“宇宙旅馆” 啊？客满啦？ 没关系，让住在 k 号房间的客人移到 k+1号。你就住进第1号房间吧！ 客 满

有限与无限：怎样的差别 传统观点：“整体大于部分” {1, 2, 3,…}与{12, 22, 32,…}一一对应

集合的等势关系 等势关系的定义 “等势”的集合就被认为是“一样大” 如果存在从集合A到B的双射，则称集合A与B等势。 集合A与B等势记为：AB, 否则A≉B。 AB意味着：A，B中的元素可以“一一对应”。 要证明AB，找出一个从A到B的双射。 “等势”的集合就被认为是“一样大”

等势关系是等价关系  

有限集与无限集 S是有限集合 iff 存在自然数n，使得S与n等势 S不是有限集合(无限集、无穷集)， iff 存在S的真子集S’，使得S与S’等势  S一定包含一个与自然数集合等势的子集M = {a0,a1,a2,…} 令S’=S-{a0}，可以定义ƒ:SS’如下： 对于任意aiM, ƒ(ai)= ai+1； 对于任意x S-M, ƒ(x)= x. 显然这是双射，即S与其真子集S’等势。  假设S是有限集，令|S|=n, 则对S的任意真子集S’, 若|S’| =m，必有m<n, 因此从S ’到S的任一单射不可能是满射。

集合A的基数 若A与自然数n等势，则card A = n 若A与自然数集合N等势，则card A = 0 若A与实数集合R等势，则card A =  如果存在从A到N的单射，则称A为可数集，或可列集。[ card A  0 ]

无限可数集（无穷可列集） 与自然数集等势的集合称为无限可数集 整数集(包括负数)与自然数集等势 直观上说：集合的元素可以按确定的顺序线性排列，所谓“确定的”顺序是指对序列中任一元素，可以说出：它“前”、“后”元素是什么。 整数集(包括负数)与自然数集等势 0, -1, 1, -2, 2, -3, 3, -4, ...... 0, 1, 2, 3, 4, 5, 6, 7, ......

... 自然数集的笛卡儿积是可列集 所有的自然数对构成的集合与自然数集等势 类似的图形显示：可列个可列集的并集仍然是可列集合 <0,0> <1,0> <2,0> <3,0> <4,0> <0,1> <1,1> <2,1> <3,1> <0,2> <1,2> <2,2> <0,3> <1,3> <0,4> ... 类似的图形显示：可列个可列集的并集仍然是可列集合 <0,0>, <0,1>, <1,0>, <0,2>, <1,1>, <2,0>, <0,3>, ......

(这实际上意味着：任意长的线段与任意短的线段等势) 证明无限集等势的例子 (0,1)与整个实数集等势 双射：f : (0,1)R : f (x) =tg(x- ) 对任意不相等的实数a,b(a<b), [0,1]与[a,b]等势 双射： f : [0,1][a,b]: f (x) =(b-a)x+a (这实际上意味着：任意长的线段与任意短的线段等势)

实数集不是可列集 (0,1)不是可列集 //注意：(0,1)与实数集合等势 “对角线证明法” 假设(0,1)中的元素可以线性排列： (0,1)不是可列集 //注意：(0,1)与实数集合等势 “对角线证明法” 假设(0,1)中的元素可以线性排列： 0.b11b12b13b14… 0.b21b22b23b24… 0.b31b32b33b34… 0.b41b42b43b44… ⋮ 则0. b1b2b3b4…（bi≠bii）不含在上述序列中

直线上的点集与平面上的点集等势 这实际上意味着直线上的点与任意有限维空间的点“一样多”！ 0.a1a2a3....... 0.b1b2b3...... 0.a1b1a2b2a3b3..... 这实际上意味着直线上的点与任意有限维空间的点“一样多”！

Cantor（康托尔）定理 任何集合与其幂集不等势, 即：A≉(A) 证明要点： 设g是从A到(A)的函数，构造集合B如下： B={xA | xg(x)} 则B(A)，但不可能存在xA，能满足g(x)=B，因为，如果有这样的x0, 则x0 B  x0 B。 因此，g不可能是满射。

集合的优势关系 如果存在从集合A到集合B的单射，则称“集合B优势于集合A”，记为 A≼•B [card A  card B] 如果集合B优势于集合A，且B与A不等势，则称“集合B真优势于集合A”，记为A≺•B [card A  card B] 实数集合真优势于自然数集 例子：对任意集合A，A的幂集真优势于集合A

集合优势关系的性质 自反性：恒等函数 若A≼•B，且B≼•A，则AB (比较:反对称性) 传递性：单射的复合仍然是单射 (Cantor-Bernstein定理) 传递性：单射的复合仍然是单射

Bernstein定理的证明 若A≼•B，且B≼•A，则AB。 由A≼•B可知,存在从A到B的单射f，同样，由B≼•A可知，存在从B到A的单射g，于是： g ◦ f 是从A到A的单射。 显然，g(f(A))g(B)A, 且f, g的一对一性质保证了：g(f(A))A, g(B)B。 “三明治”引理可推出：A g(B), 从而AB。

g(B) g(f(A)) A B f(A) g f g(f(A))g(B)A g(f(A))A, g(B)B

“三明治”引理的证明 若A1BA, 且A1A, 则：BA 1. 令A0=A, B0=B. 2. 设f是从A0到A1的一一对应函数（A0 A1）令An+1=f(An), Bn+1=f(Bn), 递归地得到序列： A0, A1, …, An,… 以及　B0, B1, …, Bn, … 3. 由A1B0A0, 得An+1 Bn An 4.令Cn=An-Bn, Cn=C（C即左图阴影部分）, D=A-C（图中白色部分） 可以定义从A0到B0 的一一对应函数g如下： B1 A1 B0 A0 阴影部分 白色部分

证明等势 证明实数集的两个子集(0,1)和[0,1]等势。 直接找双射不太容易 关键是如何安排在[0,1]中但不在(0,1)中的0和1。 想象那个“宇宙旅馆”。我们可以取(0,1)的一个与自然数集合等势的子集(一定有){a1,a2 ,a3 ,...}, “腾出”前两个位置安排0和1

证明等势 (续) 证明实数集的两个子集(0,1)和[0,1]等势。 分别找两个一对一的映射往往比找一个双射容易

实数集与(N)等势 [0, 1) {0, 1}N 从而 R  (N) [0,1)中的数唯一地表示为0.b1b2b3b4… 不容许连续无数个1，比如1/2=0. 1000… (NOT 0.0111…) f : [0, 1)  {0, 1}N 0.b1b2b3b4…  b1, b2, b3, b4… f是单射 g : {0, 1}N  [0, 1) b1, b2, b3, b4…  0.b1b2b3b4… //看做十进制数 g是单射 根据Bernstein定理，得证

连续统假设 不存在集合S： 0 card S  

作业 教材[2.4] p. 120：32, 35, 38