离散数学课件章集合的基数.pptx

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学课件章集合的基数,9、1,集合得等势与优势,9、2,集合得基数,本章小结,习题,作业,本章内容,定义9、1 设,A,B,就是集合,如果存在着从,A,到,B,得双射函数,就称,A,与,B,就是等势(,same cardinality,)得,记作,AB。,如果,A,不与,B,等势,则记作,A B。,9、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)，,2,等势集合得实例(6),(6)对任何,a,b,R,a,b,0,1,a,b,。,双射函数,f,:0,1,a,b,f,(,x,)b,a,),x,+,a。,例9、2,设,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,。,例9、2,证明,复习,定理9、1 设,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,中不存在原像。,或者使用反证法。,定理9、2,康托定理,(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,“,更大,”,的集合。,定义9、2,(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,定理9、3 设,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、1010111,应按规定记为,0、1011000,。,对于,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,即,f,(,x,),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、0111,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,),9、2 集合得基数,上一节我们只就是抽象地讨论了集合得等势与优势。,本节将进一步研究度量集合得势得方法。,最简单得集合就是有穷集。尽管前面已经多次用到,“,有穷集,”,这一概念,当时只就是直观地理解成含有有限多个元素得集合,但一直没有精确地给出有穷集得定义。为解决这个问题我们需要先定义自然数与自然数集合。,定义9、3 设,a,为,集合,称,a,a,为,a,得后继,记作,a,+,即,a,+,=,a,a,。,例9、3,考虑空集得一系列后继。,+,=,=,+,=,+,=,=,=,+,+,=,+,=,=,=,+,+,后继,说明,前边得集合都就是后边集合得元素。,前边得集合都就是后边集合得子集。,利用后继得性质,可以考虑以构造性得方法用集合来给出自然数得定义,即,0=,1=0,+,+,0,2=1,+,+,0,1,32,+,+,0,1,2 ,n,0,1,n,1,说明,自然数得定义,这种定义没有概括出自然数得共同特征。,定义9、4 设,A,为,集合,如果满足下面得两个条件:,(1),A,(2),a,(,a,A,a,+,A,),称,A,就是归纳集。,例如:下面得集合,+,+,+,+,+,+,a,a,+,a,+,a,+,都就是归纳集。,归纳集,定义9、5 自然数,(1)一个自然数,n,就是属于每一个归纳集得集合。,(2)自然数集,N,就是所有归纳集得交集。,说明,:,根据定义9、5得到得自然数集,N,恰好由,+,+,+,等集合构成。而这些集合正就是构造性方法所定义得全体自然数。,例如:,自然数都就是集合,集合得运算对自然数都适用。,2,50,1,0,1,2,3,40,1,2,3,45,3,40,1,2,0,1,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,若,mn,则,m,n,。,(4),对任何自然数,n,与,m,以下三个式子:,m,n,m,n,n,m,必成立其一且仅成立其一。,(5),自然数得相等与大小顺序,对任何自然数,m,与,n,有,m,=,n,m,n m,n,m,n,自然数得性质,定义9、6 有穷集、无穷集,(1)一个集合就是有穷得当且仅当她与某个自然数等势;,(2)如果一个集合不就是有穷得,就称作无穷集。,例如:,a,b,c,就是有穷集,因为30,1,2,且,a,b,c,0,1,23,N,与,R,都就是无穷集,因为没有自然数与,N,与,R,等势。,任何有穷集只与唯一得自然数等势。,说明,有穷集与无穷集,定义9、7,(1)对于有穷集合,A,称与,A,等势得那个唯一得自然数为,A,得基数,记作,card,A,即,card,A,n,A,n,(,对于有穷集,A,card,A,也可以记作,|,A,|,),(2),自然数集合,N,得基数记作,0,即,card,N,=,0,(3),实数集,R,得基数记作,(读作阿列夫),即,card,R,=,基数(,cardinality,),定义9、8 设,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,0card,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,),等。,可数集,定义9、9,设,A,为集合,若,card,A,0,则称,A,为可数集(,enumerable),或可列集。,例如:,a,b,c,、5、,整数集,Z,、,有理数集,Q,、,N,N,等都就是可数集。,实数集,R,不就是可数集,与,R,等势得集合也不就是可数集。,对于任何得可数集,都可以找到一个,“,数遍,”,集合中全体元素得顺序。回顾前边得可数集,特别就是无穷可数集,都就是用这种方法来证明得。,说明,(1)可数集得任何子集都就是可数集。,一个集合得无限子集若不可数,则该集合也不可数。,(2)两个可数集得并就是可数集。,(3)两个可数集得笛卡儿积就是可数集。,(4)可数个可数集得笛卡儿积仍就是可数集。,(5)无穷集,A,得幂集,P,(,A,),不就是可数集。,可数集得性质,例9、4 求下列集合得基数。,(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。,解答,例9、4,方法一,由,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,。,例9、5,解答,例9、5,设,A,B,为集合,且,card,A,0,card,B,n,n,就是自然数,n,0。,求,card,A,B,。,例9、5,方法二,因为,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,Acard,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,。,解答,