【精品】1.3 映射及集合的基数（可编辑.ppt

《【精品】1.3 映射及集合的基数（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】1.3 映射及集合的基数（可编辑.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.3 映射及集合的基数1.3.1集合的基数集合的基数 基数是集合的一个重要特征，基数的研究基数是集合的一个重要特征，基数的研究是纯集合论研究的一个极其重要的方向，但它是纯集合论研究的一个极其重要的方向，但它作为离散数学课程的一部分，只是为了使读者作为离散数学课程的一部分，只是为了使读者对基数概念有一个正确的认识，并借此加深对对基数概念有一个正确的认识，并借此加深对映射概念的理解，提高正确运用映射工具的能映射概念的理解，提高正确运用映射工具的能力，获得一些特定的研究方法（如力，获得一些特定的研究方法（如“对角线法对角线法”）。）。l前面两节我们把基数看成是集合元素的个数，对前面两节我们把基数看

2、成是集合元素的个数，对于有限集合没有问题，而对无限集合而言便不合于有限集合没有问题，而对无限集合而言便不合适了。适了。l著名的伽利略悖论：著名的伽利略悖论：如一个有无限多个客房的旅如一个有无限多个客房的旅店，规定每个房间住一位旅客，并已住满，又来店，规定每个房间住一位旅客，并已住满，又来一位旅客投宿，店主欣然接纳，他让一号房的旅一位旅客投宿，店主欣然接纳，他让一号房的旅客住二号房，让二号房的旅客住三号房，如此下客住二号房，让二号房的旅客住三号房，如此下去，腾出一号房让新来的旅客住，用集合论的观去，腾出一号房让新来的旅客住，用集合论的观点来描述这一悖论，无疑是说集合点来描述这一悖论，无疑是说集合

3、I=1,2,3与与集合集合N=0,1,2,具有相同多元素，即具有相同多元素，即I=N。可是。可是N明明比明明比I多一个元素多一个元素“0”！l这表明必须给出基数的严格定义，按直观讨论的这表明必须给出基数的严格定义，按直观讨论的集合元素个数是行不通的，至少对于无限集合是集合元素个数是行不通的，至少对于无限集合是这样。这样。问题的提出问题的提出无限集合的大小如何比较?例:集合A:全体正整数做成的集合,集合B：全体正偶数做成的集合,这两个集合哪个包含的元素数更多?集合C=x,y,z,集合D=1,2,3有限集合的情形 xyz123CD定义1.3.7 l设设A，B是任意两个集合。是任意两个集合。(1)称

4、称A的基数的基数小于等于小于等于B的基数，记为的基数，记为 A B，如果有，如果有A到到B单射单射或有或有B到到A满射满射。(2)称称A的基数的基数小于小于B的基数，记为的基数，记为 AB，如果，如果AB且且 AB。l换句话说，若换句话说，若A与与B的某一子集有的某一子集有1-1对应对应关系，则关系，则AB；若；若A与与B的某一子集有的某一子集有1-1对应关系，且对应关系，且A与与B不存在不存在1-1对应关系，则对应关系，则 AB。l定理定理1.3.1(Bernstein定理定理-集合基数的关系集合基数的关系 具有反对具有反对称性称性)若存在若存在A的子集的子集A 和和B的子集的子集B，使得，

5、使得|A|=|B|且且|B|=|A|，则，则|A|=|B|。即若。即若|A|B|且且|B|A|，则，则|A|=|B|。l证明用到基数的三歧性定理证明用到基数的三歧性定理l基数的三歧性定理基数的三歧性定理对任意集合对任意集合A，B，或者，或者|A|B|，或者，或者|A|B|，或者，或者|B|A|，且不能有，且不能有两个式子同时成立。两个式子同时成立。1.3.2可数集合可数集合 定义定义1.3.8 一个集合，如果它的元一个集合，如果它的元素为有限个，或者它与自然数集合素为有限个，或者它与自然数集合之间存在一个之间存在一个1-1映射，则称此集合映射，则称此集合为为可数集合可数集合。否则称该集合为。否

6、则称该集合为不可不可数集合数集合。元素个数不是有限的可数。元素个数不是有限的可数集合称为集合称为可数无穷集合。可数无穷集合。例 l正整数的平方数集合是可数无穷集。正整数的平方数集合是可数无穷集。证法一：可排列：证法一：可排列：B=1,4,9,16,。证法二：可建立证法二：可建立NB的映射的映射：(x)=(x1)2l整数的集合整数的集合Z是可数无穷集。是可数无穷集。证法一：可排列：证法一：可排列：Z=0,1,-1,2,-2,3,-3,证法二：可建立证法二：可建立NZ的映射的映射：l例：例：有理数集合有理数集合Q是可数集合是可数集合.l证：证：任意非零有理数均可以表示成确定的既约任意非零有理数均可

7、以表示成确定的既约分数（即分数（即m/n的形式，其中的形式，其中m,n互质）互质）按如下方法排列：按如下方法排列：lStep1排排lStep2对对Q中正分数中正分数p=m/n，若若m+n在未排过在未排过的数中最小，且和相同者中的数中最小，且和相同者中m最小，则排最小，则排p。（按它的分子与分母的和数由小到大排列，和数（按它的分子与分母的和数由小到大排列，和数相同，则分子小的先排）相同，则分子小的先排）lStep3排排-p（对负分数，把它紧排在相应的正（对负分数，把它紧排在相应的正分数之后）。转分数之后）。转Step2。显然，任意有理数总会排入此序列中。显然，任意有理数总会排入此序列中。则则Q可

8、排成可排成0，1/1，-1/1，1/2,-1/2,2/1,-2/1,1/3,-1/3,3/1,-3/1,1/4,-1/4,2/3,-2/3,3/2,-3/2,4/1,-4/1,，因此，因此，Q是可数集合。是可数集合。l定理定理1.3.2 可数集合的子集仍为可数集合。可数集合的子集仍为可数集合。l定理定理1.3.3设设A，B是可数集合，是可数集合，AB=，则，则AB是可数集合。是可数集合。u例例.整数的集合整数的集合Z是可数无穷集。是可数无穷集。证：因自然数集证：因自然数集0，1，2，3，是可数集，是可数集，-1，-2，-3，亦是可数集，因此，这两个亦是可数集，因此，这两个互不相交的可数集合的并

9、集，即整数集，仍是互不相交的可数集合的并集，即整数集，仍是可数集。可数集。定理1.3.4l设设A1,A2,An,是可数无穷多个可是可数无穷多个可数集合的序列，则数集合的序列，则 是可数集合。即是可数集合。即可数无穷多个可数无穷多个可数集合的并集是可数集可数集合的并集是可数集合。合。证明：l不失一般性，设不失一般性，设A1,A2,An,都是可数都是可数无穷集合，且为无穷集合，且为A1=a11,a12,a1n,A2=a21,a22,a2n,A3=a31,a32,a3n,An=an1,an2,ann,证明：A1=a11,a12,a13,a14,a1n,A2=a21,a22,a23,a24,a2n,A

10、3=a31,a32,a33,a34,a3n,A4=a41,a42,a43,a44,a4n,.证明：l对于任意的对于任意的aij，规定按各元素，规定按各元素(i+j)之和的之和的大小大小排序，相同者排序，相同者按按i的大小的大小排序，如果当排序，如果当前排序者与前面已排好序的某元素相同则前排序者与前面已排好序的某元素相同则删去该当前元素，如此排下去，最后得删去该当前元素，如此排下去，最后得=a11,a12,a21,a13,a22,a31,a1n,a2(n-1),an1,。由定义。由定义1.3.8可知可知是可数集合。是可数集合。l定理定理1.3.5 设设A，B是可数无穷集合，则是可数无穷集合，则A

11、 B是是可数集合。可数集合。l例：例：有理数集合是可数集合有理数集合是可数集合l证：任意有理数都可以表示成证：任意有理数都可以表示成p/q形式，其中形式，其中p Z(整整数集合数集合)，q Z+(正整数集合正整数集合)。集合集合Z Z+=(p,q)|p Z,q Z+是可数集合，是可数集合，取其一个子集取其一个子集S=(0,1)(p,q)|(p,q)Z Z+,且且p/q是既约分数是既约分数,显然，显然，S是可数集合。是可数集合。有理数集合可以与有理数集合可以与S建立建立1-1映射映射:0(0,1),既约分数既约分数p/q(p,q)，故有理数集合是可数集合。故有理数集合是可数集合。定理l若若A1,

12、A2,An是可数集合，则是可数集合，则A1 A2 An是可数集合。是可数集合。小结：判断可数集合 l方法一方法一.按照可数集合的定义，按照可数集合的定义，若若A为有限集，为有限集，则则A一定是可数集合，否则若一定是可数集合，否则若A与自然数集之间与自然数集之间存在一个存在一个1-1映射，则映射，则A为可数集合。为可数集合。l方法二方法二.若若A与某可数集合之间存在与某可数集合之间存在1-1映射，则映射，则A为可数集合为可数集合l方法三方法三.若若A中所有元素可按某种规律进行排序，中所有元素可按某种规律进行排序，则则A是可数集合。是可数集合。l方法四方法四.若若A是是n(1)个可数集合的并集，则

13、个可数集合的并集，则A是可数集合。是可数集合。l方法五方法五.若若A是某个已知是可数集合的子集，是某个已知是可数集合的子集，则则A是可数集合。是可数集合。l方法六方法六.若若A是可数无穷多个可数集合的并集，是可数无穷多个可数集合的并集，则则A是可数集合。是可数集合。l方法七方法七.若若A是是n(1)个可数集合的笛卡儿乘个可数集合的笛卡儿乘积，则积，则A是可数集合。是可数集合。1.3.3不可数集合不可数集合 1872年Contor考虑实数集与自然数集是否有1-1对应，1873年得出否定结论l定理定理1.3.6 全体实数做成的集合是不可数集合。全体实数做成的集合是不可数集合。证证明明：由由定定理理

14、1.3.2(的的逆逆否否命命题题)知知，只只要要证证明明(0,1)区间内的实数不可数就可以了。区间内的实数不可数就可以了。若不然，我们可以把若不然，我们可以把(0,1)区间内的数排成一个序区间内的数排成一个序列：列：0.a11a12a130.a21a22a230.a31a32a33(2)我们考虑下面的数：我们考虑下面的数：0.r1r2rk()其中其中显显然然，(3)是是(0,1)区区间间内内的的数数，但但它它却却不不是是序序列列(2)中中的的任任一一个个数数。事事实实上上，对对(2)中中任任一一个个数数0.ak1ak2akk，因为，因为rkakk，故，故0.ak1ak2akk0.r1r2rk与

15、与假假设设矛矛盾盾。故故(0,1)区区间间内内的的实实数数不不可可数数，所所以以整个实数集不可数。整个实数集不可数。推 论 l实数集合实数集合R，区间，区间(a,+)、a,b、a,b)、(a,b，其中，其中ab，都是不可数的，且与区间，都是不可数的，且与区间(0,1)等浓。等浓。仅看构造区间仅看构造区间0,1与与(0,1)之间之间1-1映射的一映射的一个例子。我们知道全体有理数的集合是可个例子。我们知道全体有理数的集合是可数的，于是数的，于是(0,1)区间中的有理数是可数的，区间中的有理数是可数的，不妨将它们排成不妨将它们排成a1,a2,an,的形式。的形式。而闭区间而闭区间0,1比区间比区间

16、(0,1)多两个数多两个数0和和1，它们是，它们是有理数，于是可建立闭区间有理数，于是可建立闭区间0,1中的有理数到区中的有理数到区间间(0,1)中的有理数的中的有理数的1-1映射映射 1：0，1，a1，a2，an，a1，a2，a3，a4，,an+2,令区间令区间0,1中的无理数到区间中的无理数到区间(0,1)中的无理数的中的无理数的1-1映射映射 2为自己对应自己。则映射为自己对应自己。则映射=1 2为为区间区间0,1到区间到区间(0,1)的的1-1映射。从而区间映射。从而区间0,1与与(0,1)等浓。等浓。l我们把我们把(0,1)区间内的实数集合的基数记为区间内的实数集合的基数记为c，也，

17、也记为记为1。即。即c=1。l定理定理1.3.7 设设A1,A2,An,是互不相交的是互不相交的集合序列，它们的基数都是集合序列，它们的基数都是c，则，则的的基数也是基数也是c。即。即可数可数(无穷多无穷多)个个基数为基数为c的集的集合的并集基数仍为合的并集基数仍为c。ll注注:c是实数集合的基数。是实数集合的基数。下一步的问题无限集合的基数有多少个无限集合的基数有多少个?自然数集合 其它的集合?实数集合 其它的集合?定理1.3.8（Contor基本定理-1883年由康托尔证明）l集合的元素不能与集合的元素不能与2建立建立1-1映射。映射。证明：反证法。证明：反证法。假设假设 为为A到到2上的

18、上的1-1映射。映射。令令=x|x A并且并且x(x)显然，显然，A。于是，存在唯一一个元素于是，存在唯一一个元素b A，使得，使得(b)=若若b B，则由，则由B的定义知，的定义知，b(b)=B,即即b B，矛盾。，矛盾。若若b,因为因为(b)=,所以所以b(b)，于，于是由的定义知，是由的定义知，b B，矛盾。，矛盾。因此，在与因此，在与2之间不能建立之间不能建立1-1映射。映射。连续统问题 l根据定理根据定理1.3.8，我们可以构造基数任意大，我们可以构造基数任意大的集合。如的集合。如|A|2A|l按照基数的大小可排为：按照基数的大小可排为：0,1,2,n,0,1,2是否存在集合是否存在

19、集合S，使得，使得0|S|1即能否找到一实数集的子集，它是不可数即能否找到一实数集的子集，它是不可数集合，但又不能与实数集合建立一一对应。集合，但又不能与实数集合建立一一对应。n1900年，第二届国际数学大会在巴黎召开，年，第二届国际数学大会在巴黎召开，20世纪国际数学界的头号巨人德国数学家世纪国际数学界的头号巨人德国数学家Hilbert(希尔伯特，希尔伯特，1862-1943)提出了提出了23个基本问题，个基本问题，几乎指导了一个世纪，现只解决了一半。第一几乎指导了一个世纪，现只解决了一半。第一个问题就是如何证明集合论中的连续统假设。个问题就是如何证明集合论中的连续统假设。n连续统假设是数学

20、中最基本的问题，近百年来连续统假设是数学中最基本的问题，近百年来一直是数理逻辑的中心问题之一，也是集合论一直是数理逻辑的中心问题之一，也是集合论最难的问题之一，经过许多著名数学家的不懈最难的问题之一，经过许多著名数学家的不懈努力，已取得了重大进展：努力，已取得了重大进展：l1930年，德国年，德国Godel给出了连续统假设给出了连续统假设与选择公理是相容的，从而证明了连续与选择公理是相容的，从而证明了连续统假设不成立是不可能的。统假设不成立是不可能的。l1963年，年，24岁的美国岁的美国Cohen证明了选择证明了选择公理与连续统假设是相互独立的，从而公理与连续统假设是相互独立的，从而给出了：证明连续统假设成立是不可能给出了：证明连续统假设成立是不可能的。的。l由此得到，在我们所使用的公理系统中，由此得到，在我们所使用的公理系统中，连续统假设是连续统假设是不能判定不能判定的。的。作业作业l习题习题1.3，第，第25页：页：3，8