离散数学：第10讲 基数.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基数,*,2025/5/17 周六,基数,1,计数,(counting),问题,设,|A|=n,|B|=m,问,A,B,中有多少单射,满射,双射,?,nm,时,A,B,中无单射和双射,满射个数为,2025/5/17 周六,基数,2,有穷集计数定理,设,X,、,Y,是,有穷集,，则：,若存在单射,f:XY,，则,|X|Y|,；,若存在满射,f:XY,，则,|X|Y|,；,若存在双射,f:XY,，则,|X|=|Y|,。,无穷集是否具有同样的性质,?,2025/5/17 周六,基数,3,有穷集,无穷集,有穷集,(finite set):,不能与自身真子集建立双射的集合,无穷集,(infinite set),:,可以与自身真子集建立双射的集合,Bernhard Bolzano(17811848),捷克,1851,“,paradoxes of the infinite,”,首次使用,“,set,”,一词,给出无穷集的上述定义,2025/5/17 周六,基数,4,有穷集和无穷集,定义：如果有一个从集合,0,1,.,n-1,到,A,的双射函数，那么称集合,A,是,有穷集,；如果集合,A,不是有穷集，则它是,无穷集,。,2025/5/17 周六,基数,5,定义,8.10,定义,8.10,：给定集合,A,，其后继集定义为集合：,A,+,=AA,若,A,为空集，则其后继集为,=,，,顺次写下去为,、,、,、,命名集合,为,0,，并依次命名,+,=0,+,=1,，,1,+,=,=2.,得到自然数集合,0,1,2,3,.,2025/5/17 周六,基数,6,G.Peano,公理：,0N(,其中,0=),如果,nN,，那么,n,+,N(,其中,n,+,=nn),如果一个子集,S,N,具有性质：,0S,如果,nS,，则,n,+,S,，那么,S=N,2025/5/17 周六,基数,7,自然数的三歧性,定理,:,m,nN,下面三式成立且仅成立一式,.,mn,m=n,nm,2025/5/17 周六,基数,8,自然数集合,N,是无穷集,定理：自然数集合,N,是无穷集,.,证：,n,N,，任取,f,是从,0,1,.,n-1,到,N,的函数。设,k=1+maxf(0),f(1),.,f(n-1),，那么,kN,，但对每一个,x0,1,.,n-1,，有,f(x)k,。因此,f,不能是满射函数，即,f,也不是双射函数。因为,n,和,f,都是任意的，故,N,是,无穷集,。,2025/5/17 周六,基数,9,无穷集间的,映射,函数,f:NN,，,f(n)=2n,单射但非满射,函数,f:NN,，,f(2n)=n,，,f(2n+1)=n,满射但非单射,有穷与无穷的区别！,2025/5/17 周六,基数,10,无穷之迷,许多关于无穷的悖论,无穷是否,“,存在,”,?,人是否,“,理解,”,无穷,?,极限,有穷与无穷的区别,?,高斯拒绝实际的无穷,2025/5/17 周六,基数,11,芝诺悖论,(Zeno,s paradox),芝诺悖论,:,阿基里斯,(Achilles),追不上乌龟,阿基里斯比乌龟快一倍,乌龟在阿基里斯前面起跑,2025/5/17 周六,基数,12,无穷集的大小,对有穷集的大小概念易理解，对无穷集的度量要考虑到集合的等势关系。,设有集合,A,，一切与该集合等势的集合，其元素之间可一一对应，若以此作为度量标准，有如下定义：,2025/5/17 周六,基数,13,定义,8.8,定义,8.8,：当且仅当集合,A,的元素与集合,B,的元素之间存在着,一一映射,，集合,A,与集合,B,称为是等势的记作,A,B,等势,:A,B,双射,f:AB,2025/5/17 周六,基数,14,证明等势,构造双射,(1),自然数集,N,与非负偶数集合,M,是等势的,NMf:n2n,2025/5/17 周六,基数,15,N,与其子集,N,N-0,1,2,-2,-1NN,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,-1,-2,2025/5/17 周六,基数,16,更多,举例,(1)Z,N,f(x)=2x,x0;f(x)=-2x-1,x0;f(0)=0,(2)N,N,N,f()=(m+n+1)(m+n)/2+m,(3)Q,N,2025/5/17 周六,基数,17,R(0,1),实数集,R,与其子集,S=x|xR0 x1,RS,f:x(arc tgx)/,+1/2,2025/5/17 周六,基数,18,关于实数区间,(1)(0,1),0,1,取一个与,N,等势的子集,M,构造双射,M,0,1,M,2025/5/17 周六,基数,19,0,1(0,1),分出一个,可数子集,，然后利用上述对应,2025/5/17 周六,基数,20,关于实数区间,(2)(0,1),(a,b),f(x)=(b-a)x+a,2025/5/17 周六,基数,21,实数区间的双射构造法,若,A,，,B,是实数区间，可以采用直线方程作为从,A,到,B,的双射函数。,例如,A=1,2,，,B=2,6,是实数区间。如图所示，先将,A,，,B,区间分别标记在直角坐标系的轴和轴上。过,(1,，,2),和,(2,，,6),两点的直线方程将,A,中的每个数映到,B,中的每个数，因此，该直线方程所代表的一次函数就是从,A,到,B,的双射函数。由解析几何的知识可以得到双射函数,f:A,B,，,f(x)=4x-2,。,2025/5/17 周六,基数,22,关于实数区间,(1)(0,1),0,1,取一个与,N,等势的子集,M,构造双射,M,0,1,M,(2)(0,1),(a,b),f(x)=(b-a)x+a,(3)R,(0,1),(a,b)0,1,2025/5/17 周六,基数,23,等势关系是等价关系,自反,:AA,I,A,:AA,双射,对称,:AB BA,f,:AB,双射,f,-1,:BA,双射,传递,:AB BC AC,f,:AB,g:BC,双射,g,f:AC,双射,2025/5/17 周六,基数,24,N,R?,N,S=0,1?,假设存在,N,到,S,的双射,f,，设,s,i+1,=,f,(i),，,i=0,1,，其中,0s,i,1,设,s,i,=0.yyy.,，其中,y0,1,2,.,9,s,1,=0.a,11,a,12,a,13,.a,1n,.,s,2,=0.a,21,a,22,a,23,.a,2n,.,.,构造一个实数,r=0.b,1,b,2,b,3,b,i,a,ii,i=1,，,则,r,与所有,s,1,s,2,.,不同，从而有,r,S,，与,f,是双射矛盾。,2025/5/17 周六,基数,25,无穷集的分类,无,穷集,之中也有分类,自然数集,N,是无,穷集,并非所有无穷集都可与自然数集建立一一对应,无穷集之间也有大小关系,2025/5/17 周六,基数,26,无穷集之间的比较,定义,8.9,：,若从集合,A,到集合,B,存在一个单射，则称,B,优势于,A,，记作,A,B,。,若从,A,到,B,存在一个单射，但不存在双射，则称,B,真优势于,A,，记作,A,B,。如果,B,不是,真优势于,A,，记作,A,B,2025/5/17 周六,基数,27,无穷集之间的比较,n,N,N,R,N,R,2025/5/17 周六,基数,28,基数,(cardinality),基数,:,满足,5,条约定,(,公理,),1,.cardA=cardB,A B,2,.A,为有穷集,则,cardA,=n,其中,A n,(n,是唯一的,),3,.cardN=,0,4,.,cardR=,阿列夫,5,.0,1,2,0,都是基数,0,1,2,是有穷基数,2025/5/17 周六,基数,29,可数集,定义：若集合,A,的基数小于等于,0,，则称,A,为可数集。,(,可数集又称为可枚举集，可列集,),eg1.,2N=0,2,4,6,.,A=1,4,9,.,n,.,B=2,4,6,.,2025/5/17 周六,基数,30,基数的比较,定义：若从集合,A,到集合,B,存在一个单射，则称,A,的基数不大于,B,的基数，记作,cardA,cardB,。若从,A,到,B,存在一个单射，但不存在双射，则称,A,的基数小于,B,的基数，记作,cardAcardB,。,2025/5/17 周六,基数,31,Zermelo,定理,Zermelo,定理：设,A,、,B,为任意两个集合，则以下三条中恰有一条成立：,a).cardAcardB,b).cardBcardA,c).cardA=cardB,2025/5/17 周六,基数,32,C-S-B,定理,Cantor-Schr,der-Bernstein,定理,:,cardA,cardB,cardB,cardA,AB,在两个集合间构造双射，较复杂。,构造单射较简单。,2025/5/17 周六,基数,33,相同基数的判定,eg1.0,1,与,(0,1),有相同基数,f:(0,1)0,1,x,|,x,g:0,1(0,1),x,|,(x/2)+(1/4),eg2.A=N,，,B=(0,1),，则,cardA,B=,f:A,BR,+,f,|,n+x,cardA,B,g,：,(0,1)A,B,x,|,cardA,B,2025/5/17 周六,基数,34,n,0,定理：设,A,是有穷集合，则,cardA,0,证：由,”,自然数集合,N,是无穷集,.,”,及,”,N,与,R,不等势,”,知只需证明,“,”,即可。,设,cardA=n,，,A0,1,2,.,n-1,f:0,1,.,n-1N,x|x,g:N0,1,n|1/(n+1),2025/5/17 周六,基数,35,作业,P163,习题八,24,