第四章 有限集与无限集.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Company Logo,*,单击此处编辑母版标题样式,第四章 有限集与无限集,有限集与无限集基本概念,1,有限集,2,无限集的性质,3,Company Logo,4.1,有限集与无限集基本概念,问题：,1,2,3,与,2,4,6,哪个集合的元素更多？,因为,1,2,3,2,4,6,，所以,1,2,3,里的个数,多于,2,4,6,的个数。,因为两个集合可用函数,f(n,)=2n,表示，而,f(n,)=2n,是一一对应函数，所以,1,2,3,和,2,4,6,两个集合的个数,一样多,。,结论：,无限集合,无法用确切的个数来描述,，有限集合的一些特征也,不能任意推广,到无限集合中去。,Company Logo,4.1,有限集与无限集基本概念,定义,4.1,一个集合,S,与集合,N,n,=0,1,2(n-1),如果,存在一一,对应函数,f:,N,n,S,，则称,S,是,有限的,，并称其有,基数,n;,如果,S,不是有限的则称其为,无限的,。,定义,4.2,如果存在,一一对应函数,f:S S,，使得,f(S,),S,，即,f(S,),是,S,的真子集，则,S,是,无限的,，否则,S,是,有 限的,。,说明：,要证明一个集合是无限集，只需证明集合和它的它的,真,子集间,存在一一对应关系,。如：,2n,是,n,的真子集。,Company Logo,4.1,有限集与无限集基本概念,例,4.1,一个有,n,个不同元素所组成的集合，它就是基数为,n,的有限集。,例,4.2,自然数集,N,是无限集。,例,4.3,实数集,R,是无限集。,Company Logo,4.1,有限集与无限集基本概念,定理,4.1,自然数,N,是无限的。,分析：,x,N,，找到一一对应的函数,f(x,),，,且,y|y,=,f(x,),x,N,N,证明：设函数,f,：,N N,定义为,f(x,)=2x,，显然,f,是一对一的，而且有,f(N,),N,，所以,N,是无限的。,Company Logo,4.1,有限集与无限集基本概念,定理,4.2,实数集,R,是无限的。,分析：,x,R,，找到一一对应的函数,f(x,),，,且,y|y,=,f(x,),x,R,R,证明：设函数,f,：,RR,为,这个函数,f,是一对一的，而显然有,f(R,),R,，所以,R,是无限的。,0,1,f(R,),的范围,Company Logo,4.2,有限集,定义有限集的基数,定义,4.3,有限集,S,的,元素个数,称为,S,的基数，记为,|S|,。,例：设,A=a,，,b,，,c,，,d,，则,|A|=4,Company Logo,4.2,有限集,定理,4.3,如果,A,，,B,是,分离,的,有限,集合，则有,|AB|=|A|+|B|,定理,4.4,如果,A,，,B,是任意的,有限,集合，则有,|AB|=|A|+|B|-|AB|,定理,4.5,对任意三个,有限,集合,A,，,B,，,C,，则有,|AB C|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|AB C|,Company Logo,4.2,有限集,定理,4.6,设有,n,个有限集合,S,1,，,S,2,，,S,n,，则有,奇数项是加，偶数项是减。,Company Logo,4.2,有限集,例,4.4,假定有,120,个学生，其中,100,个学生至少要学德、法、英三种语言的一种，还假定,65,人学法语，,45,人学德语，,42,人学英语；,20,人学法语和德语，,25,人学法语和英语，,15,人学德语和英语。请问同时学三种语言的有多少人？仅学一种语言的各有多少人？,解：,（,1,）设,A,、,B,、,C,分别表示学法语、德语和英语的学生的集合，由题意和定理,4.5,有：,|AB C|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|AB C|,100=65+45+42-20-25-15+|AB C|,所以,|AB C|=8,Company Logo,4.2,有限集,（,2,）由,文氏图,可计算仅学一种语言的各有多少人,法语人数为：,65-(12+8+17)=28,德语人数为：,45-(12+8+7)=18,英语人数为：,42-(17+8+7)=10,英,德,法,12,8,7,Company Logo,4.3,无限集的性质,等势的定义,定义,4.4,集合,A,，,B,的元素之间，如果存在一一对应,的关系 则称集合,A,，,B,是,等势,的，记为,AB,注意,：根据定义,对,有限集,而言，两个集合等势即表示两个集合,元素个数相同,；,对,无限集,而言，两个集合等势即表示两个集合元素之间,存在一一对应关系,；,说明,：要想证等势，必须找出,一一对应,的关系。,Company Logo,4.3,无限集的性质,例,4.5,自然数集,N=0,1,2,3,与其子集,S=1,3,5,均为无限集，且,NS,N,：,0 1 2 3 n ,S:1 3 5 7 2n+1,此例说明了无限集的一个特性：,一个无限集可以同它的一个,真,子集等势。,Company Logo,定理,4.7,一个集合为无限集，则它必含有与其等势的真子集。,分析：,条件,是有一无限集,M,，,结论,是必存在无限集,M,有,M,M,且,MM,需要利用,构造法,，构造满足上述条件的,M,。,若无限集,M,是可以排列的，即,M=m,1,，,m,2,，,m,n,，,那么只需在,M,去掉元素,m,1,，即可得,M,。,若无限集,M,是不可以排列的，可在,M,中按一定规律找到一可以排列的,无限集,M,1,，使得,M,为,M,中去掉,M,1,中一元素。,4.3,无限集的性质,无限集的性质,Company Logo,证明：,1,、构造无限集,M,的一真子集,M,。,先从,M,中任取一个元素,m,1,，剩余部分为,M-m,1,无限集,再从,M-m,1,中任取一元素,m,2,，剩余部分为,M-m,1,，,m,2,继续下去，取出,m,3,，,m,4,，,，得到一个,无限集合,M,1,M,1,=m,1,，,m,2,，,，,，令,M,2,=M-M,1,(,若,M,可列，,M,2,为空,),M=M,1,M,2,=m,1,，,m,2,，,，,M,2,构造集合,M,M=m,2,，,m,3,，,，,M2,显然,M,M,4.3,无限集的性质,Company Logo,2,、证明,MM,M,：,m,1,m,2,m,3,m,4,m,i ,M,2,M:m,2,m,3,m,4,m,5,m,i+1,M,2,4.3,无限集的性质,因为无限，所以总能找到对应元素,Company Logo,推论,一集合为无限集的充分必要条件是它必含有与其等势的真子集。,分析：充分性：,MM,且,M,M,M,为无限集,必要性：,M,为无限集,它必含有与其等式的真子集,充分性利用反正法证，即假设,M,为有限集推出矛盾。,必要性即为定理,4.7,。,4.3,无限集的性质,Company Logo,证明：设一集合,M,含有与其等势的真子集,M,且,M,为有限集，设其元素个数为,n,个。,M,也为有限集，设其元素个数为,m,个,根据条件有,M,M,，即有,nm,与,MM,矛盾，推论得证。,4.3,无限集的性质,Company Logo,无限集定义,定义,4.5,一个集合若,存在与其,等势,的,真,子集,称为无限集，,否则称为有限集。,4.3,无限集的性质,Company Logo,可列集的定义,定义,4.6,凡与,自然数集,N,等势,的集合叫可列集。,即：能与自然数,N,建立一一对应关系的集合,例：下列集合都是可数集合：,1)O,x|x,N,，,x,是奇数,;,2)E,x|x,N,，,x,是偶数,;,3)P,x|x,N,，,x,是素数,;,4.3,无限集的性质,Company Logo,定理,4.8,一无限集必包含一可列集。,分析：,若无限集是可列集，定理显然成立。,若无限集不是可列集，需要,构造,其无限子集，使,无限子集与,N,等势,，即得无限子集为可列集。,4.3,无限集的性质,可列集的重要性质,Company Logo,证明：设,A,是一无限集,1,、构造无限集,A,的一子集,A,。,先从,A,中任取一个元素,a,0,，剩余部分为,A-a,0,再从,A-a,0,中任取一元素,a,1,，剩余部分为,A-a,0,，,a,1,继续下去，取出,a,2,，,a,3,，,，得到一个,无限集合,A,A=a,0,，,a,1,，,，,，显然,A,A,2,、证明,A N,N,：,0 1 2,3 i ,A:a,0,a,1,a,2,a,3,a,i,4.3,无限集的性质,A,为可列集，,因为,A,A,所以定理成立,Company Logo,定理,4.9,可列集的无限子集仍为一可列集。,分析：,构造可列集的无限子集。,证明其,无限子集与,N,等势,，即得无限子集为可列集。,4.3,无限集的性质,Company Logo,证明：设,A,是一可列集，,A=a,0,，,a,1,，,a,2,，,a,3,，,1,、构造可列集,A,的一子集,A,。,先从,A,中任取一个元素,a,m0,，剩余部分为,A-a,m0,再从,A-a,m0,中依次顺取一元素,a,m1,，剩余部分,A-a,m0,，,a,m1,依次顺取下去，取出,a,m2,，,a,m3,，,，得到一个,无限集合,A,A=a,m0,，,a,m1,，,，,，显然,A,A,2,、证明,A N,N,：,0 1 2,3 ,A :a,m0,a,m1,a,m2,a,m3,综合得证可列集的无限子集仍为一可列集。,4.3,无限集的性质,可列集,是,无限集中,的,最小元素,Company Logo,分析：,在整数集,I,和自然数集,N,之间构造一一对应关系。,证明：整数集,I,和自然数集,N,间的一一对应关系,N,：,0 1 2 3 4 5 6 2n-1 2n,I:0 1 -1 2 -2 3 -3 n -n,4.3,无限集的性质,定理,4.10,整数集,I,是可列集。,Company Logo,4.3,无限集的性质,分析：,有理数的形式：，找出有理数的一定的排列规律，即得到一一对应的关系。,定理,4.11,有理数集,Q,是可列集。,Company Logo,4.3,无限集的性质,证明：一切有理数均呈 状，现将所有 按下列次序,排列,正分数按其分子分母之和的大小顺序排列：从小到大,正分数的分子分母之和相同者按分子大小顺序排列：从大到小,与正分数具有相同形式的负分数排于正分数之后,按上述规律可得一序列，即与,N,的一一对应关系：,N,：,0 1 2 3 4 5 6 7 8 9 10,Q:,Company Logo,-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,PLAY,证明方法二：有理数和自然数的对应关系,Company Logo,4.3,无限集的性质,集合的大小问题,集合的基数,集合的基数可用,|A|,来表示。,对有限集,A,，,|A|=,集合,A,中元素的个数,；,对无限集,A,，,|A|,不能用有限集的方法来定义，规定自然数集,N,的基数为,0,(,阿列夫零,),，即,|N|=,0,Company Logo,4.3,无限集的性质,(2),集合大小的比较,有限集大小的比较，用“相等”、“不相等”,无限集大小的比较，用,“等势”、“不等势”,等势即为基数相同，由此立即可知：,所有可列集的基数均为,0,。,(3),可列集是最小的无限集,没有比基数,0,更小的无限集，但存在比基数,0,更大的无限集。如,实数集,。,Company Logo,4.3,无限集的性质,分析：,1,、证,(0,，,1),内的实数不可列，利用,反正法,，即假设其是可列的，当将其列出时总能找到一个元素不属于列出的集合。,2,、证,(0,，,1),内的实数与,R,等势，即,R,不可列。,定理,4.12,实数集是不可列的。,Company Logo,证明：,1,、定义在,(0,，,1),内的实数集,S=,x|x,R,且,0 x1,x,S,，可表示为,x=0.y,1,y,2,y,3,(,y,i,0,1,9,),假设,S,是可列的，则它的元素可依次排列：,x,0,，,x,1,，,x,2,，,且我们有,x,0,=0.a,00,a,01,a,02,a,0n,x,1,=0.a,10,a,11,a,12,a,1n,x,m,=0.a,m0,a,m1,a,m2,a,mn,只需证还能找到一个元素,r,S,，但,r,不在,x,0,，,x,1,，,x,2,，,中,4.3,无限集的性质,Company Logo,构造一,S,内的实数,r=0.b,0,b,1,b,2,b,n,其中当,a,ii,1,时，,b,i,=1,当,a,ii,=1,时，,b,i,=2,因为,b,0,a,00,，所以,r x,0,因为,b,1,a,11,，所以,r x,1,因为总有一位不同，所以,r x,i,，这与,r,S,矛盾，,即,(0,，,1),是不可列的。,2,、证明,SR,，即建立一一对应关系。设,R,中的元素为,y,，,S,中的元素为,x,，因为,S,不可列，所以只能建立关系式：,4.3,无限集的性质,Company Logo,4.3,无限集的性质,当,x,(0,，,1/2,，根据上式有,y(0,，,+),当,x,1/2,，,1),，根据上式有,y(,，,0),综上所述,x,(0,，,1),，有,y(,，,+),根据上式,还需证,y(,，,+),，有,x,(0,，,1),，才能证得上式试,R,和,S,之间满足一一对应关系。转变上式，得,Company Logo,4.3,无限集的性质,当,y(0,，,+),，根据上式有,x,(0,，,1/2,当,y(,，,0),，根据上式有,x,1/2,，,1),综上所述,y(,，,+),，有,x,(0,，,1),从而建立了一一对应关系，由此整个定理得证。,Company Logo,4.3,无限集的性质,结论,(1),实数集比可列集要“大”，它的基数不是阿列夫零，我们,用,(,阿列夫数,),表示,-,称为连续统的势；,(2),在无限集中除了阿列夫零和阿列夫数以外,还有更大基数的集合,；,(3),无限集也有大小，,可列集是最小的无限集,，其次是,实数集,；,(4),对于任意一个无限集，总存在一个基数大于这个集合的集合，即,无限集的大小也是无限的,。,Company Logo,小结,掌握有限集和无限集的概念。,掌握有限集的计数方法。,熟练掌握无限集的性质，无限集计数方法，根据势的定义对无限集进行分类。能够证明一个集合是无限集，可列集等。,Company Logo,习题,1,求下列集合的基数。,(1)A=0,2,4,6,50;(2)B=,x|x,R,并且,x,2,+1=0,；,(3)S=0,3,6,9,;(4)T=10,11,12,13,(,1)A,的基数,|A|=26,(2),B=,x|x,R,并且,x,2,+1=0,=,，故,|B|=0,；,(3),S=0,3,6,9,=3x|x,N,，,S,与,N,能够建立一一对应关系，,SN,，,|S|=,0,；,(4),T=10,11,12,13,=x+10|x,N,，,T,与,N,能够建立一一对应关系，,TN,，,|T|=,0,；,Company Logo,习题,2.,求,1,到,1000,之间（包含,1,和,1000,在内）既不能被,5,和,6,整,除，也不能被,8,整除的数有多少个？,解：设,1,到,1000,的整数构成全集,U,，用,A,，,B,，,C,分别表示能被,5,，,6,，,8,整除的数构成的集合,|U|=1000,|A|=,1000/5,=200,|B|=,1000/6,=166,|C|=,1000/8,=125,|A,B|=,1000/30,=33,|A,C|=,1000/40,=25,|B,C|=,1000/24,=41,|A,B,C|=,1000/120,=8,Company Logo,习题,|AB C|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|AB C|,=,200+166+125-33-25-41+8,=400,=|U|-,|AB C|=600,Company Logo,