双射函数与集合的基数.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,8.3,集合的基数,离 散 数 学,南京农业大学本科生课程,数学系,本章说明,本章的主要内容,集合的等势及其性质,重要的等势或不等势的结果,集合的优势及其性质,自然数与自然数集合,集合的基数,可数集,8.3.1,集合的等势与优势,8.3.2,集合的基数,本节小结,习题,作业,本章内容,定义,8.8,设,A,B,是集合，如果存在着从,A,到,B,的,双射函数,，就称,A,和,B,是等势same cardinality,）,的,，记作,AB。,如果,A,不与,B,等势，则记作,A B。,8.3.1,集合的等势与优势,通俗的说，集合的势是量度集合所含元素多少的量。,集合的势越大，所含的元素越多。,（1）,Z,N,。,则,f,是,Z,到,N,的双射函数。从而证明了,Z,N,。,等势集合的实例(1),等势集合的实例(2),（2）,N,N,N,。,双射函数,等势集合的实例(3),（3）,NQ。,把所有形式为,p,/,q,(,p,q,为整数且,q,0),的数排成一张表。,-2/1,5,-1/1,4,-3/1,18,2/1,10,3/1,11,0/1,0,1/1,1,-2/2,-1/2,3,-3/2,17,2/2,3/2,12,0/2,1/2,2,-2/3,6,-1/3,7,-3/3,2/3,9,3/3,0/3,1/3,8,-2/4,-1/4,15,-3/4,16,2/4,3/4,13,0/4,1/4,14,以0/1作为第一个数，按照箭头规定的顺序可以,“,数遍,”,表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。,等势集合的实例(4),（4）,(0,1),R,。,其中实数区间,(0,1)=,x,|,x,R,0,x,1。,令双射函数,则,f,是,(0,1),到,R,的双射函数。从而证明了,(0,1),R,。,等势集合的实例(5),（5）,0,1(0,1),。,其中,(0,1),和,0,1,分别为实数开区间和闭区间。,双射函数,f,:0,1,(0,1)，,等势集合的实例(6),（6）对任何,a,b,R,，,a,b,，,0,1,a,b,。,双射函数,f,：0,1,a,b,，,f,(,x,)(,b,a,),x,+,a。,例,8.10,设,A,为任意集合，则,P,(,A,)0,1,A,。,构造,f,：,P,(,A,)0,1,A,，,f,(,A,)=,A,，,A,P,(,A,)。,其中,A,是集合,A,的特征函数,。,(1),易证,f,是,单射的,。,(2),对于任意的,g,0,1,A,，,那么有,g,：,A,0,1。,令,B,=,x,|,x,A,g,(,x,)=1,则,B,A,，,且,B,=,g,，,即,B,P,(,A,)，,使得,f,(,B,)=,g,。,所以,f,是满射的。,由等势定义,得,P,(,A,)0,1,A,。,例,8.10,证明,复习,定理,8.6,设,A,，,B,，,C,是任意集合，,（1）,A,A,。,（2）,若,A,B,，,则,B,A,。,（3）,若,A,B,，,B,C,，,则,A,C,。,（1）,I,A,是从,A,到,A,的双射，因此,A,A,。,（2）,假设,A,B,，存在,f,:,A,B,是双射，,那么,f,1,:,B,A,是从,B,到,A,的双射，所以,B,A,。,（3）,假设,A,B,，,B,C,，,存在,f,:,A,B,，,g,:,B,C,是双射，,则,f,g,:,A,C,是从,A,到,C,的双射,。,所以,A,C,。,等势的性质,证明,N,Z,Q,N,N,R,0,1(0,1),任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合,R,等势。,问题：,N,和,R,是否等势？,若干等势集合,（1）如果能证明,N 0,1,，,就可以断定,N R。,只需证明任何函数,f,：,N,0,1,都不是,满射,的。,构造一个,0,1,区间的小数,b,，,使得,b,在,N,中不存在原像。,（2）任取函数,f,：,A,P,(,A,)，,构造,B,P,(,A,)，,使得,B,在,A,中不存在原像。,或者使用反证法。,定理,8.7,康托定理,（1）,N R。,（2）,对任意集合,A,都有,A P,(,A,)。,康托定理,分析,（1）首先规定,0,1,中数的表示。,对任意的,x,0,1，,令,x,=0,.,x,1,x,2,（0,x,i,9）,注意：为了保证表示式的唯一性，如果遇到0.24999，则将,x,表示为0.25000。,设,f,:,N,0,1,是从,N,到,0,1,的任何一个函数。,f,的所有函数值为,：,f,(0)=0.,a,1,(1),a,2,(1),f,(1)=0.,a,1,(2),a,2,(2),f,(,n,1)=0.,a,1,(,n,),a,2,(,n,),令,y,的表示式为,0.,b,1,b,2,，,并且满足,b,i,a,i,(,i,),，,i,=1,2,，,则,y,0,1，,但,y,与上面列出的任何一个函数值都不相等,。,即,f,不是满射的。,所以,，,N R。,康托定理,康托定理,假设,A,P(A)，,则必有函数,f,:AP(A),是双射函数。,如下构造集合,B,：,B,x,|,x,A,x,f,(,x,),可知,B,P,(,A,)。,于是存在唯一一个元素,b,A,，,使得,f,(,b,)B,。,若,b,B,，,则由,B,的定义知，,b,f,(,b,)，,即,b,B,，,矛盾,。,若,b,B,，,则,b,f,(,b,)，,于是由,B,的定义知，,b,B,，,矛盾。,（2）设,g,：,A,P,(,A,),是从,A,到,P,(,A,),的任意函数，如下构造集合,B,：,B,x,|,x,A,x,g,(,x,),则,B,P,(,A,)。,但是,对任意,x,A,，,都有,x,B,x,g,(,x,),所以，对任意的,x,A,都有,B,g,(,x,)，,即,B,ran,g,即,P(A),中存在元素,B，,在,A,中找不到原像。,所以,，,g,不是满射的。,所以,，,A P,(,A,)。,说明,康托定理,根据这个定理可以知道,N,P,(,N,)。,综合前面的结果，可知,N,0,1,N,。,实际上，,P(N)，0,1,N,和,R,都是比,N,“,更大,”,的集合。定义,8.9,（1）设,A,B,是集合，如果存在从,A,到,B,的,单射,函数，就称,B,优势于,A,，,记作,A,B,。,如果,B,不是优势于,A,，,则记作,A,B,。,（2）,设,A,B,是集合，若,A,B,且,A B,，,则称,B,真优势于,A,，,记作,A,B,。,如果,B,不是真优势于,A,，,则记作,A,B,。,例如：,N,N,N,R,A,P,(,A,),N,R,A,P,(,A,),R,N,N,N,优势,R,N,定理,8.8,设,A,B,C,是任意的集合，则,（1）,A,A,。,（2）,若,A,B,且,B,A,，,则,A,B,。,（3）,若,A,B,且,B,C,则,A,C,。,证明：,（1）,I,A,是,A,到,A,的单射,，,因此,A,A,。,（2）证明略。,（3）假设,A,B,且,B,C,，那么存在单射,f,:AB，,g,:BC，,于是,f,g,：,A,C,也是单射的，因此,A,C,。,优势的性质,说明,该定理为证明集合之间的等势提供了有力的工具,。,构造两个单射,f,：A,B,和,g：B,A,函数容易集合等势,。,例题,例题：,证明0,1与(0,1)等势。,证明：,构造两个单射函数,f,:(0,1)0,1，,f,(,x,),x,g,:0,1(0,1)，,g,(,x,),x,/2+1/4,证明,0,1,N,0,1),(1),设,x,0,1)，0.,x,1,x,2是,x,的,二进制表示,。,为了使表示唯一，规定表示式中不允许出现连续无数个1。,例如,x,0.1010,111,，,应按规定记为,0.101,1000,。,对于,x,，,如下定义,f,：0,1)0,1,N,，,使得,f,(,x,)=,t,x,，,且,t,x,：,N,0,1，,t,x,(,n,)=,x,n,+1,，,n,=0,1,2,例如,x,=0.10110100，,则对应于,x,的函数,t,x,是,：,n,0 1 2 3 4 5 6 7,t,x,(,n,)1 0 1 1 0 1 0 0,易见,t,x,0,1,N,，,且对于,x,y,0,1)，,x,y,，,必有,t,x,t,y,，,即,fx,),f,(,y,)。,所以,，,f,：0,1)0,1,N,是单射的。,(2),定义函数,g,：0,1,N,0,1)。,g,的映射法则恰好与,f,相反，即,t,0,1,N,，,t,：,N,0,1，,g,(,t,)=0.,x,1,x,2,其中,x,n,+1,=,t,(,n,)。,但不同的是，将,0.,x,1,x,2,看作数,x,的十进制表示,。,例如,t,1,，,t,2,0,1N，,且,g,(,t,1,)0.0,111,，,g,(,t,2,)0.,1000,，,若将,g,(,t,1,),和,g,(,t,2,),都看成二进制表示，则,g,(,t,1,),g,(,t,2,)；,但若看成十进制表示，则,g,(,t,1,),g,(,t,2,)。,所以,，,g,：0,1,N,0,1),是单射的。,根据,定理9.3,，有,0,1,N,0,1)。,证明,0,1,N,0,1),总结,N,Z,Q,N,N,R,a,b,(,c,d,)0,1,N,P,(,N,),其中,a,b,，(,c,d,),代表任意的实数闭区间和开区间,。,0,1,A,P,(,A,),N,R,A,P,(,A,),8.3.2,集合的基数,上一节我们只是抽象地讨论了集合的,等势与优势,。,本节将进一步研究度量集合的势的方法。,最简单的集合是有穷集。尽管前面已经多次用到“有穷集”这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。,定义,8.10,设,a,为,集合，称,a,a,为,a,的,后继,，记作,a,+,，,即,a,+,=,a,a,。,例,考虑空集的一系列后继。,+,=,=,+,=,+,=,=,=,+,+,=,+,=,=,=,+,+,后继,说明,前边的集合都是后边集合的元素。,前边的集合都是后边集合的子集。,利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，,即,0=,1=0,+,+,0,2=1,+,+,0,1,32,+,+,0,1,2 ,n,0,1,n,1,说明,自然数的定义,这种定义没有概括出自然数的共同特征。,定义8.11,设,A,为,集合，如果满足下面的两个条件：,（1）,A,（2）,a,(,a,A,a,+,A,),称,A,是,归纳集,。,例如,：下面的集合,+,+,+,+,+,+,a,a,+,a,+,a,+,都是归纳集。,归纳集,定义,8.12,自然数,（1）一个,自然数,n,是属于每一个归纳集的集合。,（2）,自然数集,N,是所有归纳集的交集。,说明,：,根据定义,8.12,得到的自然数集,N,恰好由,+,+,+,等集合构成。而这些集合正是构造性方法所定义的全体自然数。,例如：,自然数都是集合，集合的运算对自然数都适用。,2,50,1,0,1,2,3,40,1,2,3,45,3,40,1,2,01,2,30,1,23,4-20,1,2,3-0,1=2,3,2,30,1,0,1,2,自然数,n,和自然数集合,N,的定义,P(1)P(0),00,1,2,3,0,1,0,1,2,f|f：0,1,20,1f,0,f,1,f,7,其中,f,0,f,1,f,2,f,3,f,4,f,5,f,6,f,7,举例,（1）,对任何自然数,n，,有,n,n,。,（2）,对任何自然数,n,m,，,若,m,n,，,则,m,n,。,（3）,对任何自然数,n,m,，,若,m,n,，,则,m,n,。,（4）,对任何自然数,n,和,m,，,以下三个式子：,m,n,，,m,n,，,n,m,必成立其一且仅成立其一。,（5自然数的相等与大小顺序,对任何自然数,m,和,n,，,有,m,=,n,m,n m,n,m,n,自然数的性质,定义,8.13,有穷集、无穷集,（1）一个集合是,有穷的,当且仅当它与某个自然数,等势,；,（2）如果一个集合不是有穷的，就称作,无穷集,。,例如：,a,b,c,是有穷集，,因为30,1,2，且,a,b,c,0,1,23,N,和,R,都是无穷集，,因为没有自然数与,N,和,R,等势。,任何有穷集只与唯一的自然数等势。,说明,有穷集和无穷集,定义,8.14,（1）对于有穷集合,A,，,称与,A,等势,的那个唯一的自然数为,A,的基数,，,记作,card,A,，,即,card,A,n,An,（,对于有穷集,A,，card,A,也可以记作,|,A,|,）,（2）,自然数集合,N,的基数记作,0,，即,card,N,=,0,（3）,实数集,R,的基数记作,（读作阿列夫），即,card,R,=,基数(,cardinality,),定义,8.15,设,A,B,为集合，则,（1）,card,A,card,B,A,B,（2）card,A,card,B,A,B,（3）card,A,card,B,card,A,card,B,card,A,card,B,例如：,card,Z,card,Q,card,N,N,0,card,P,(,N,)card 2,N,card,a,b,card(,c,d,)0,说明,：集合的基数就是集合的势，基数越大，势就越大。,基数的相等和大小,关于基数的说明,由于对任何集合,A,都满足,A,P,(,A,)，,所以有,card,A,card,P,(,A,)，,这说明,不存在最大的基数,。,将已知的基数按从小到大的顺序排列就得到：,0,1,2,n,0,0,1,2,n,是全体自然数，是,有穷基数,。,0,是,无穷基数,。,0,是最小的无穷基数,，,后面还有更大的基数，如,card P(,R,),等。,可数集,定义,8.16,设,A,为集合，若,card,A,0,，,则称,A,为,可数集(,enumerable),或,可列集。,例如：,a,b,c,、5、,整数集,Z,、,有理数集,Q,、,N,N,等都是可数集。,实数集,R,不是可数集，与,R,等势的集合也不是可数集。,对于任何的可数集，都可以找到一个,“,数遍,”,集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。,说明,（1）可数集的任何子集都是可数集。,一个集合的无限子集若不可数，则该集合也不可数。,（2）两个可数集的并是可数集。,（3）两个可数集的笛卡儿积是可数集。,（4）可数个可数集的笛卡儿积仍是可数集。,（5）无穷集,A,的幂集,P,(,A,),不是可数集。,可数集的性质,例,8.11,求下列集合的,基数,。,（1）,T,x,|,x,是单词,“,BASEBALL,”,中的字母,（2）,B,x,|,x,R,x,2,=92,x,=8,（3）,C,P,(,A,),A,=1,3,7,11,（1）,由,T,B,A,S,E,L,知,，,card,T,5。,（2）,由,B,可知，,card,B,0。,（3）,由,|,A,|4,可知,，,card,C,card,P,(,A,)|,P,(,A,)|2,4,16。,解答,例,8.11,方法一,由,card,A,0,，card,B,n,，,可知,A,B,都是可数集。,令,A,=,a,0,a,1,a,2,，,B,=,b,0,b,1,b,2,b,n,1,。,对任意的,，,A,B，,有 ,i,k,j,l,定义函数,f,：,A,B,Nf,(),in,+,j,i,0,1,j,0,1,n,1,由于,f,是,A,B,到,N,的,双射,函数，所以,card,A,B,card,N,。,例,8.12,解答,例,8.12,设,A,B,为集合,，,且,card,A,0,，card,B,n,，,n,是自然数,，,n,0。,求,card,A,B,。,例,8.12,方法二,因为,card,A,0,，card,B,n,，,所以,A,B,都是可数集。,根据性质（3）可知，,A,B,也是可数集，所以，,card,A,B,0,当,B,时，,card,A,card,A,B,，,这就推出,0,card,A,B,综合所述，,card,A,B,0,本章主要内容,集合等势的定义,等势的性质,集合优势的定义,优势的性质,重要的集合等势以及优势的结果,自然数及其自然数集合的定义,可数集与不可数集,集合的基数,本章学习要求,能够证明两个集合等势。,能够证明一个集合优势于另一个集合。,知道什么是可数集与不可数集。,会求一个简单集合的基数。,等势的证明方法,证明集合,A,与,B,等势的方法,直接构造从,A,到,B,的双射函数,f,需要证明,f,的满射性和,f,的单射性。,构造两个单射函数,f,：,A,B,和,g,：,B,A,。,给出函数,f,和,g，,证明,f,和,g,的单射性。,利用等势的传递性,直接计算,A,与,B,的基数，得到,card,A,card,B,。,证明集合,A,与自然数集合,N,等势的方法,找到一个“数遍”,A,中元素的顺序。,例题选讲,1已知,A,n,7,|,n,N,，,B,n,109,|,n,N,，,求下列各题：,（1）,card,A,（2）,card,B,（3）,card(,A,B,),（4）,card(,A,B,),（1）,构造双射函数,f,：,N,A,，,f,(,n,)=,n,7,，,因此,card,A,0,。,（2）,构造双射函数,g,：,N,A,，,g,(,n,)=,n,109,，,因此,card,B,0,。,（3）,可数集的并仍旧是可数集(或者由于,A,B,N,)，,因此,card(,A,B,),0,，,但是,0,card,A,card(,A,B,)，,从而得到,card(,A,B,),0,。,（4）,因为,7,与,109,互素,，,card(,A,B,),n,7,109,|,n,N,，,与（1）类似得到,card(,A,B,),0,。,解答,例题选讲,2.已知,card,A,0,，,且,card,B,card,A,，,求,card(,A,B,)。,由,A,B,A，,得到,card(,A,B,),card,A,，,即,card(,A,B,),0,。,由,card,B,card,A,可知，,B,为有穷集，,即存在自然数,n，,使得,card,B,=,n,。,假设,card(,A,B,),0,，,那么存在自然数,m,，,使,card(,A,B,),m,。,从而得到，,card,A,card(,A,B,),B,),n,+,m,与,card,A,0,矛盾。,因此，,card(,A,B,),0,。,解答,复习,特,征函数,设,A,为集合，对于任意的,A,A,，,A,的,特征函数,A,:,A,0,1,定义为,1，,a,A,0，,a,A,A,A,(,a,),举例:,A,的每一个子集,A,都对应于一个特征函数，不同的子集对应于不同的特征函数。,例如,A,a,b,c,则有,，,a,a,b,例题选讲(略),1,设,A,B,为二集合，证明：如果,A,B,，,则,P,(,A,),P,(,B,)。,因为,A,B,，,因此存在双射函数,f,：,A,B,，,存在反函数,f,1,：,B,A,，,构造函数,g,：,P,(,A,),P,(,B,),g,(,T,)=,f,(,T,)，,T,A,（,这里的,f,(,T,),是,T,在函数,f,的像,）,首先，证明,g,的满射性。,对于任何,S,B,，,存在,f,1,(,S,),A,，,且,g,(,f,1,(,S,)=,f,f,1,(,S,)=,S,。,所以,g,是满射的。,其次，证明,g,的单射性。,g,(,T,1,)=,g,(,T,2,),f,(,T,1,)=,f,(,T,2,),f,1,(,f,(,T,1,)=,f,1,(,f,(,T,2,),I,A,(,T1,)=,I,A,(,T,2,),T,1,=,T,2,综合上述，可知,P,(,A,),P,(,B,)。,两个可数集的并集为可数集,设,A、B,为可数集，不妨设,AB,。,(,1,),若两个集合都是有穷集，比如,Aa,0,a,1,a,n-1,，Bb,0,b,1,b,m-1,，,那么,card(AB)n+m,0,。,(2)如果其中一个集合是有穷集，另一个是无穷可数集，比如,Aa,0,a,1,a,n-1,，card B,0,如下构造双射,h：ABN,，,当,xA,时，,xa,i,，h(x)i,；,当,xB,时，,xb,j,，j0,1,，,那么,h(x)j+n,。,(3)如果,card,Acard,B,0,，,那么存在双射,f：AN,和,g：BN,。,如下构造函数,h：ABN,当,xA,且,f(x)i,时，,h(x)2i,当,xB,且,g(x)j,时，,h(x)2j+1,显然,h,为双射。,综上所述，,card(AB),0,。,