离散数学-4-5可数集与不可数集.ppt

第三章集合与关系,4-5可数集与不可数集授课人：李朔Email:chn.nj.ls,1、可数集,在上节中，我们提到自然数集N是无限的。但是并非所有无限集都可与自然数集建立一一对应。定义4-5.1与自然数集合等势的任意集合称为可数的，可数集合的基数用0表示。(是希伯莱文的第一个字母，读成“阿列夫”）例如，A=1,4,9,16,n2,B=1,8,27,64,n3,C=3,12,27,3n2,D=1,1/2,1/3,1/n,均为可数集我们把有限集和可数集统称为至多可数集。,2、可数集的性质,定理4-5.1A为可数集的充分必要条件是可以排列成Aa1，a2，an，的形式。证明：若A可排成上述形式，那么将A的元素an与足标n对应，就得到A与N之间的一一对应，故A是可数集。反之，若A为可数集，那么在A与N之间存在一种一一对应关系f，由f得到n的对应元素an，即A可写为a1，a2，an，的形式。定理4-5.2任一无限集，必含有可数子集。证明：设A为无限集合，从A中取出一个元素a1，因为A是无限的，它不因取出a1而耗尽，所以从A-a1可取元素a2，则A-(a1，a2)也是非空集，所以又可取一元素a3，如此继续下去，就得到A的可数子集。,2、可数集的性质,定理4-5.3任一无限集合必与其某一真子集等势。证明设无限集合M，按定理4-5.2，必含有可数子集Aa1，a2，an，设M-AB，我们定义集合M到其自身的映象，f：MM-a1，使得f(an)an+1(n1，2，)且对于任何bB，有f(b)b。这个f是双射的。这个定理亦可用下图所示。设线段AB，其上有线段CD，则线段AB与CD上所有的点，可作成一一对应。其作法是：把CD移出与AB平行，联AC、BD延长交于G，则AB上任意点E与G的联线EG必与CD交于F。反之，CD上任意点F，与G的联线FG延长必交AB于E，上述E，F的对应作法，即说明ABCD。,2、可数集的性质,定理4-5.4可数集的任何无限子集是可数的。证明：设A为可数集合，BA为一无限子集，如将A的元素排成a1，a2，an，从a1开始，向后检查，不断地删去不在B中的元素，则得到新的一列ai1，ai2，ain，它与自然数一一对应，所以B是可数的。,2、可数集的性质,定理4-5.5可数个两两不相交的可数集合的并集，仍然是一可数集。证明：设，是可数个两两不相交的可数集。的并集用外延的方法表示出来，即从开始，按下图箭头所示路径排出其元素,每一斜方向上元素的下标之和相同，故是一个可数集。,这个定理的基数可表达形式为,2、可数集的性质,定理4-5.6设自然数集合N，则NN是可数集。证明：将NN的元素枚举下图所示，用0,1,2,标记它们，从直观上说明NN与N之间存在着双射f。,2、可数集的性质,作函数f：NNN，则f是从NN到N的双射函数（f(m,n)看作序偶的标号）。(1)f是入射任给序偶NN，而，所以，,2、可数集的性质,即有此式表明对任意序偶NN，在N中有唯一的自然数在f下为的象。(2)f是满射任意uN，有唯一的NN，使得所以，且,2、可数集的性质,令v=m+n，于是化简得：对求根得：对求根得：因为v=m+nN，故v不能取负值且为整数，于是合适的v必须满足条件且v为正整数。取（其中x表示不超过x的最大整数）。令，则有，,2、可数集的性质,于是，m，nN，m，n由u唯一确定，故在f下，u有唯一的原象NN与之对应。由(1)和(2)知：NNN。,2、可数集的性质,定理4-5.7有理数的全体组成的集合是可数集证明：由定理4-5.6中可知NN是可数的，在NN集合中删除所有m和n不是互为质数的序偶，得集合sNN，s|mN，nN且m和n互质。因为S是NN的无限子集，故据定理4-5.4可知，S是可数的。令g：SQ+，即g：m/n(其中m，n互质)，因为g是双射，故Q+是可数集。又因为Q+Q-，故QQ+0Q-是可数集。,3、不可数集,不是可数集的无限集称为不可数集。定理4-5.8全体实数构成的集合R是不可数的。证明因为f：(0，1)R是双射函数，令Sx|xR(0x1)若能证S是不可数集，则R也必为不可数集。用反证法。假设S是可数的，则S必可表示为：SS1，S2，其中Si是(0，1)间的任一实数。设SiO.y1y2y3，其中yi0，1，2，9(如0.2和0.123可记为0.1999和0.12299)，设要s1=0.a11a12a13a1n,s2=0.a21a12a23a2n,s2=0.a31a12a33a3n，,3、不可数集,其次，构造实数，使这样，r与S中的所有实数都不相同，即rS，产生矛盾。故S是不可数集，因此R也是不可数集。*此定理的证明方法称为“对角化”方法*定义：我们把集合(0，1)的基数记为“”，