1、集合的基数(Cardinal Number),离散数学集合论 南京大学计算机科学与技术系,集合的基数,引言：有限与无限集合的等势关系集合的基数可数集(Countable set)Cantor定理优势关系Bernstein定理,我们怎么比较集合的大小,“数得清”的我们就数元素个数。“数不清”的咋办？“常识”不一定经得起追问。,有限与无限：“宇宙旅馆”,啊？客满啦？没关系，让住在 k 号房间的客人移到 k+1号。你就住进第1号房间吧！,客 满,有限与无限：怎样的差别,传统观点：“整体大于部分”1, 2, 3,与12, 22, 32,一一对应,集合的等势关系,等势关系的定义如果存在从集合A到B的双射
2、，则称集合A与B等势。集合A与B等势记为：AB, 否则AB。AB意味着：A，B中的元素可以“一一对应”。要证明AB，找出一个从A到B的双射。“等势”的集合就被认为是“一样大”,等势关系是等价关系,有限集与无限集,S是有限集合 iff 存在自然数n，使得S与n等势S不是有限集合(无限集、无穷集)， iff 存在S的真子集S，使得S与S等势 S一定包含一个与自然数集合等势的子集M = a0,a1,a2, 令S=S-a0，可以定义:SS如下： 对于任意aiM, (ai)= ai+1； 对于任意x S-M, (x)= x. 显然这是双射，即S与其真子集S等势。 假设S是有限集，令|S|=n, 则对S的
3、任意真子集S, 若|S| =m，必有mn, 因此从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
4、, 5, 6, 7, .,自然数集的笛卡儿积是可列集,所有的自然数对构成的集合与自然数集等势, , , , , , , .,类似的图形显示：可列个可列集的并集仍然是可列集合,证明无限集等势的例子,(0,1)与整个实数集等势双射：f : (0,1)R : f (x) =tg(x- )对任意不相等的实数a,b(ab), 0,1与a,b等势双射： f : 0,1a,b: f (x) =(b-a)x+a(这实际上意味着：任意长的线段与任意短的线段等势),实数集不是可列集,(0,1)不是可列集 /注意：(0,1)与实数集合等势“对角线证明法”假设(0,1)中的元素可以线性排列：0.b11b12b13b1
5、40.b21b22b23b240.b31b32b33b340.b41b42b43b44则0. b1b2b3b4（bibii）不含在上述序列中,直线上的点集与平面上的点集等势,0.a1b1a2b2a3b3.,0.a1a2a3.0.b1b2b3.,这实际上意味着直线上的点与任意有限维空间的点“一样多”！,Cantor（康托尔）定理,任何集合与其幂集不等势, 即：A(A)证明要点：设g是从A到(A)的函数，构造集合B如下： B=xA | xg(x) 则B(A)，但不可能存在xA，能满足g(x)=B，因为，如果有这样的x0, 则x0 B x0 B。因此，g不可能是满射。,集合的优势关系,如果存在从集合
6、A到集合B的单射，则称“集合B优势于集合A”，记为 AB card A card B如果集合B优势于集合A，且B与A不等势，则称“集合B真优势于集合A”，记为AB card A card B实数集合真优势于自然数集例子：对任意集合A，A的幂集真优势于集合A,集合优势关系的性质,自反性：恒等函数若AB，且BA，则AB (比较:反对称性)(Cantor-Bernstein定理)传递性：单射的复合仍然是单射,Bernstein定理的证明,若AB，且BA，则AB。由AB可知,存在从A到B的单射f，同样，由BA可知，存在从B到A的单射g，于是： g f 是从A到A的单射。显然，g(f(A)g(B)A,
7、且f, g的一对一性质保证了：g(f(A)A, g(B)B。“三明治”引理可推出：A g(B), 从而AB。,f(A),g(f(A)A, g(B)B,f,g,g(f(A)g(B)A,“三明治”引理的证明,若A1BA, 且A1A, 则：BA,A0,A1,B0,B1,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. 由A1B0A0, 得An+1 Bn An4.令Cn=An-Bn, Cn=C（C即左图阴影部分）, D=A-C（图中白色部
8、分）可以定义从A0到B0 的一一对应函数g如下：,阴影部分白色部分,证明等势,证明实数集的两个子集(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, 1N 从而 R (N)0,1)中的数唯一地表示为0.b1b2b3b4 不容许连续无数个1，比如1/2=0. 1000 (NOT 0.0111)f : 0, 1) 0, 1N0.b1b2b3b4 b1, b2, b3, b4f是单射g : 0, 1N 0, 1) b1, b2, b3, b4 0.b1b2b3b4 /看做十进制数 g是单射根据Bernstein定理，得证,连续统假设,不存在集合S：0 card S ,作业,教材2.4p. 120：32, 35, 38,
