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

《离散数学-4-5可数集与不可数集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章集合与关系4-5可数集与不可数集授课人：李朔Email:chn.nj.ls@gmail.com1、可数集在上节中，我们提到自然数集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、多可数集。2、可数集的性质定理4-5.1A为可数集的充分必要条件是可以排列成A＝{a1，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，

3、则A-(a1，a2)也是非空集，所以又可取一元素a3，如此继续下去，就得到A的可数子集。2、可数集的性质定理4-5.3任一无限集合必与其某一真子集等势。证明设无限集合M，按定理4-5.2，必含有可数子集A＝{a1，a2，…，an}，设M-A＝B，我们定义集合M到其自身的映象，f：M→M-{a1}，使得f(an)＝an+1(n＝1，2，…)且对于任何b∈B，有f(b)＝b。这个f是双射的。    这个定理亦可用下图所示。    设线段AB，其上有线段CD，则线段AB与CD上所有的点，可作成一一对应。其作法是：

4、把CD移出与AB平行，联AC、BD延长交于G，则AB上任意点E与G的联线EG必与CD交于F。反之，CD上任意点F，与G的联线FG延长必交AB于E，上述E，F的对应作法，即说明AB～CD。2、可数集的性质定理4-5.4可数集的任何无限子集是可数的。证明：设A为可数集合，BA为一无限子集，如将A的元素排成a1，a2，…，an，…，从a1开始，向后检查，不断地删去不在B中的元素，则得到新的一列ai1，ai2，…，ain，…，它与自然数一一对应，所以B是可数的。2、可数集的性质定理4-5.5可数个两两不相交的可数集合

5、的并集，仍然是一可数集。证明：设，，…是可数个两两不相交的可数集。的并集用外延的方法表示出来，即从开始，按下图箭头所示路径排出其元素,每一斜方向上元素的下标之和相同，故是一个可数集。a11a12a13a14a15…a21a31a41a51…a22a32a42a52…a23a33a43a53…a24a34a44a54…a25a35a45a55………………这个定理的基数可表达形式为2、可数集的性质定理4-5.6设自然数集合N，则N×N是可数集。证明：将N×N的元素枚举下图所示，用0,1,2,…标记它们，从直观上说明

6、N×N与N之间存在着双射f。<0,0><1,0><2,0><3,0><4,0>025914<0,1>1<1,1>4<2,1>8<3,1>13<4,1>19<0,2>3<1,2>7<2,2>12<3,2>18<4,2>25<0,3>6<1,3>11<2,3>17<3,3>24<4,3>32<0,4>10<1,4>16<2,4>23<3,4>31<4,4>41……………………………2、可数集的性质作函数f：N×NN，则f是从N×N到N的双射函数（f(m,n)看作序偶的标号）。(1)f是入射任给序偶

7、n>N×N，而，所以，2、可数集的性质即有此式表明对任意序偶N×N，在N中有唯一的自然数在f下为的象。(2)f是满射任意uN，有唯一的N×N，使得所以，且2、可数集的性质令v=m+n，于是化简得：对求根得：对求根得：因为v=m+nN，故v不能取负值且为整数，于是合适的v必须满足条件且v为正整数。取（其中[x]表示不超过x的最大整数）。令，则有，2、可数集的性质于是，m，nN，m，n由u唯一确定，故在f下，u有唯一的原象N×N与之对应。由(1)和(2)知：N×

8、N～N。2、可数集的性质定理4-5.7有理数的全体组成的集合是可数集证明：由定理4-5.6中可知N×N是可数的，在N×N集合中删除所有m和n不是互为质数的序偶，得集合sN×N，s＝{

9、m∈N，n∈N且m和n互质}。因为S是N×N的无限子集，故据定理4-5.4可知，S是可数的。    令g：S→Q+，即g：→m/n(其中m，n互质)，因为g是双射，故Q+