离散数学――有限集与无限集(课件)

第四章有限集与无限集有限集与无限集基本概念1有限集2无限集的性质3§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,…}两个集合的个数一样多。结论：无限集合无法用确切的个数来描述，有限集合的一些特征也不能任意推广到无限集合中去。§4.1有限集与无限集基本概念定义4.1一个集合S与集合Nn={0,1,2…(n-1)}如果存在一一对应函数f:Nn→S，则称S是有限的，并称其有基数n;如果S不是有限的则称其为无限的。定义4.2如果存在一一对应函数f:S→S′，使得f(S)S，即f(S)是S的真子集，则S是无限的，否则S是有限的。说明：要证明一个集合是无限集，只需证明集合和它的它的真子集间存在一一对应关系。如：2n是n的真子集。§4.1有限集与无限集基本概念例4.1一个有n个不同元素所组成的集合，它就是基数为n的有限集。例4.2自然数集N是无限集。例4.3实数集R是无限集。§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是无限的。§4.1有限集与无限集基本概念定理4.2实数集R是无限的。分析：∀xR，找到一一对应的函数f(x)，且{y|y=f(x),∀xR}R证明：设函数f：R→R′为这个函数f是一对一的，而显然有f(R)R，所以R是无限的。1xx0f(x)=xx001f(R)的范围§4.2有限集定义有限集的基数定义4.3有限集S的元素个数称为S的基数，记为|S|。例：设A={a，b，c，d}，则|A|=4§4.2有限集定理4.3如果A，B是分离的有限集合，则有|A∪B|=|A|+|B|定理4.4如果A，B是任意的有限集合，则有|A∪B|=|A|+|B|-|A∩B|定理4.5对任意三个有限集合A，B，C，则有|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|§4.2有限集定理4.6设有n个有限集合S1，S2，…Sn，则有niij12ni=11ijnijk1ijknn-112n|S∪S∪…S|=||-|∩|SSS+|∩∩|+…SSS+(-1)|∩…∩|SSS奇数项是加，偶数项是减。§4.2有限集例4.4假定有120个学生，其中100个学生至少要学德、法、英三种语言的一种，还假定65人学法语，45人学德语，42人学英语；20人学法语和德语，25人学法语和英语，15人学德语和英语。请问同时学三种语言的有多少人？仅学一种语言的各有多少人？解：（1）设A、B、C分别表示学法语、德语和英语的学生的集合，由题意和定理4.5有：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|100=65+45+42-20-25-15+|A∩B∩C|所以|A∩B∩C|=8§4.2有限集（2）由文氏图可计算仅学一种语言的各有多少人法语人数为：65-(12+8+17)=28德语人数为：45-(12+8+7)=18英语人数为：42-(17+8+7)=10英德法121787§4.3无限集的性质等势的定义定义4.4集合A，B的元素之间，如果存在一一对应的关系则称集合A，B是等势的，记为A~B注意：根据定义对有限集而言，两个集合等势即表示两个集合元素个数相同；对无限集而言，两个集合等势即表示两个集合元素之间存在一一对应关系；说明：要想证等势，必须找出一一对应的关系。§4.3无限集的性质例4.5自然数集N={0,1,2,3……}与其子集S={1,3,5……}均为无限集，且N~SN：0123…n…↕↕↕↕↕↕↕S:1357…2n+1…此例说明了无限集的一个特性：一个无限集可以同它的一个真子集等势。定理4.7一个集合为无限集，则它必含有与其等势的真子集。分析：条件是有一无限集M，结论是必存在无限集M'有M'M且M'~M需要利用构造法，构造满足上述条件的M'。若无限集M是可以排列的，即M={m1，m2…，mn，…},那么只需在M去掉元素m1，即可得M'。若无限集M是不可以排列的，可在M中按一定规律找到一可以排列的无限集M1，使得M'为M中去掉M1中一元素。§4.3无限集的性质无限集的性质证明：1、构造无限集M的一真子集M'。先从M中任取一个元素m1，剩余部分为M-{m1}—无限集再从M-{m1}中任取一元素m2，剩余部分为M-{m1，m2}…继续下去，取出m3，m4，…，得到一个无限集合M1M1={m1，m2，…，}，令M2=M-M1(若M可列，M2为空)M=M1∪M2={m1，m2，…，}∪M2构造集合M'M'={m2，m3，…，}∪M2显然M'M§4.3无限集的性质2、证明M~M'M：{m1m2m3m4…mi…}∪M2↕↕↕↕↕↕↕↕M':{m2m3m4m5…mi+1…}∪M2§4.3无限集的性质因为无限，所以总能找到对应元素推论一集合为无限集的充分必要条件是它必含有与其等势的真子集。分析：充分性：M~M'且M⊃M'⇒M为无限集必要性：M为无限集⇒它必含有与其等式的真子集充分性利用反正法证，即假设M为有限集推出矛盾。必要性即为定理4.7。§4.3无限集的性质证明：设一集合M含有与其等势的真子集M'且M为有限集，设其元素个数为n个。M'也为有限集，设其元素个数为m个根据条件有M⊃M'，即有nm与M~M'矛盾，推论得证。§4.3无限集的性质无限集定义定义4.5一个集合若存在与其等势的真子集称为无限集，否则称为有限集。§4.3无限集的性质可列集的定义定义4.6凡与自然数集N等势的集合叫可列集。即：能与自然数N建立一一对应关系的集合例：下列集合都是可数集合：1)O＝{x|xN，x是奇数};2)E＝{x|xN，x是偶数};3)P＝{x|xN，x是素数};§4.3无限集的性质定理4.8一无限集必包含一可列集。分析：若无限集是可列集，定理显然成立。若无限集不是可列集，需要构造其无限子集，使无限子集与N等势，即得无限子集为可列集。§4.3无限集的性质可列集的重要性质证明：设A是一无限集1、构造无限集A的一子集A'。先从A中任取一个元素a0，剩余部分为A-{a0}再从A-{a0}中任取一元素a1，剩余部分为A-{a0，a1}…继续下去，取出a2，a3，…，得到一个无限集合A'A'={a0，a1，…，}，显然AA'2、证明A'~NN：0123…i…↕↕↕↕↕↕↕A':a0a1a2a3…ai…§4.3无限集的性质A'为可列集，因为AA'所以定理成立定理4.9可列集的无限子集仍为一可列集。分析：构造可列集的无限子集。证明其无限子集与N等势，即得无限子集为可列集。§4.3无限集的性质证明：设A是一可列集，A={a0，a1，a2，a3，…}1、构造可列集A的一子集A'。先从A中任取一个元素am0，剩余部分为A-{am0}再从A-{am0}中依次顺取一元素am1，剩余部分A-{am0，am1}…依次顺取下去，取出am2，am3，…，得到一个无限集合A'A'={am0，am1，…，}，显然AA'2、证明A'~NN：0123…↕↕↕↕↕A':am0am1am2am3…综合得证可列集的无限子集仍为一可列集。§4.3无限集的性质※可列集是无限集中的最小元素分析：在整数集I和自然数集N之间构造一一对应关系。证明：整数集I和自然数集N间的一一对应关系N：0123456…2n-12n…↕↕↕↕↕↕↕↕↕↕↕I:01-12-23-3…n-n…§4.3无限集的性质定理4.10整数集I是可列集。§4.3无限集的性质定理4.11有理数集Q是可列集。分析：有理数的形式：，找出有理数的一定的排列规律，即得到一一对应的关系。nm§4.3无限集的性质证明：一切有理数均呈状，现将所有按下列次序排列(1)正分数按其分子分母之和的大小顺序排列：从小到大(1)正分数的分子分母之和相同者按分子大小顺序排列：从大到小(1)与正分数具有相同形式的负分数排于正分数之后按上述规律可得一序列，即与N的一一对应关系：N：012345678910…↕↕↕↕↕↕↕↕↕↕↕↕Q:nmnm...1122113322110------111122112233-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/23/2[12]0/21/2[2]-2/3[6]-1/3[7]-3/32/3[9]3/30/31/3[8]-2/4-1/4[15]-3/4[16]2/43/4[13]0/41/4[14]……………………PLAY证明方法二：有理数和自然数的对应关系§4.3无限集的性质集合的大小问题(1)集合的基数集合的基数可用|A|来表示。对有限集A，|A|=集合A中元素的个数；对无限集A，|A|不能用有限集的方法来定义，规定自然数集N的基数为א0(阿列夫零)，即|N|=א0§4.3无限集的性质(2)集合大小的比较有限集大小的比较，用“相等”、“不相等”无限集大小的比较，用“等势”、“不等势”等势即为基数相同，由此立即可知：所有可列集的基数均为א0。(3)可列集是最小的无限集没有比基数א0更小的无限集，但存在比基数א0更大的无限集。如实数集。§4.3无限集的性质分析：1、证(0，1)内的实数不可列，利用反正法，即假设其是可列的，当将其列出时总能找到一个元素不属于列出的集合。2、证(0，1)内的实数与R等势，即R不可列。定理4.12实数集是不可列的。证明：1、定义在(0，1)内的实数集S={x|xR且0x1}∀xS，可表示为x=0.y1y2y3…(yi{0,1,…9})假设S是可列的，则它的元素可依次排列：x0，x1，x2，…且我们有x0=0.a00a01a02…a0n…x1=0.a10a11a12…a1n……xm=0.am0am1am2…amn……只需证还能找到一个元素rS，但r不在x0，x1，x2，…中§4.3无限集的性质构造一S内的实数r=0.b0b1b2…bn…其中当aii≠1时，bi=1当aii=1时，bi=2因为b0≠a00，所以r≠x0因为b1≠a11，所以r≠x1…因为总有一位不同，所以r≠xi，这与rS矛盾，即(0，1)是不可列的。2、证明S~R，即建立一一对应关系。设R中的元素为y，S中的元素为x，因为S不可列，所以只能建立关系式：§4.3无限集的性质§4.3无限集的性质y11-1,0x2x211+1,x12(x-1)2当x(0，1/2]，根据上式有y(0，+∞)当x[1/2，1)，根据上式有y(－∞，0)综上所述x(0，1)，有y(－∞，+∞)根据上式还需证y(－∞，+∞)，有x(0，1)，才能证得上式试R和S之间满足一一对应关系。转变上式，得§4.3无限集的性质x01,y02(y+1)1+1,y2(y-1)当y(0，+∞)，根据上式有x(0，1/2]当y(－∞，0)，根据上式有x[1/2，1)综上所述y(－∞，+∞)，有x(0，1)从而建立了一一对应关系，由此整个定理得证。§4.3无限集的性质结论(1)实数集比可列集要“大”，它的基数不是阿列夫零，我们用א(阿列夫数)表示---称为连续统的势；(2)在无限集中除了阿列夫零和阿列夫数以外还有更大基数的集合；(3)无限集也有大小，可列集是最小的无限集，其次是实数集；(4)对于任意一个无限集，总存在一个基数大于这个集合的集合，即无限集的大小也是无限的。小结掌握有限集和无限集的概念。掌握有限集的计数方法。熟练掌握无限集的