离散数学有限集与无限集课件

离散数学有限集与无限集课件第1页，共38页，2023年，2月20日，星期一§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,…}两个集合的个数一样多。结论：无限集合无法用确切的个数来描述，有限集合的一些特征也不能任意推广到无限集合中去。第2页，共38页，2023年，2月20日，星期一§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的真子集。第3页，共38页，2023年，2月20日，星期一§4.1有限集与无限集基本概念例4.1一个有n个不同元素所组成的集合，它就是基数为n的有限集。例4.2自然数集N是无限集。例4.3实数集R是无限集。第4页，共38页，2023年，2月20日，星期一§4.1有限集与无限集基本概念定理4.1自然数N是无限的。分析：∀xN，找到一一对应的函数f(x)，且{y|y=f(x),∀xN}N证明：设函数f：N→N′定义为f(x)=2x，显然f是一对一的，而且有f(N)N，所以N是无限的。第5页，共38页，2023年，2月20日，星期一§4.1有限集与无限集基本概念定理4.2实数集R是无限的。分析：∀xR，找到一一对应的函数f(x)，且{y|y=f(x),∀xR}R证明：设函数f：R→R′为这个函数f是一对一的，而显然有f(R)R，所以R是无限的。01f(R)的范围第6页，共38页，2023年，2月20日，星期一§4.2有限集定义有限集的基数定义4.3有限集S的元素个数称为S的基数，记为|S|。例：设A={a，b，c，d}，则|A|=4第7页，共38页，2023年，2月20日，星期一§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|第8页，共38页，2023年，2月20日，星期一§4.2有限集定理4.6设有n个有限集合S1，S2，…Sn，则有奇数项是加，偶数项是减。第9页，共38页，2023年，2月20日，星期一§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第10页，共38页，2023年，2月20日，星期一§4.2有限集（2）由文氏图可计算仅学一种语言的各有多少人法语人数为：65-(12+8+17)=28德语人数为：45-(12+8+7)=18英语人数为：42-(17+8+7)=10

英德法12

87第11页，共38页，2023年，2月20日，星期一§4.3无限集的性质等势的定义定义4.4集合A，B的元素之间，如果存在一一对应的关系则称集合A，B是等势的，记为

A~B

注意：根据定义对有限集而言，两个集合等势即表示两个集合元素个数相同；对无限集而言，两个集合等势即表示两个集合元素之间存在一一对应关系；说明：要想证等势，必须找出一一对应的关系。第12页，共38页，2023年，2月20日，星期一§4.3无限集的性质例4.5自然数集

N={0,1,2,3……}与其子集S={1,3,5……}均为无限集，且N~SN：0123…n…↕↕↕↕↕↕↕S:1357…2n+1…此例说明了无限集的一个特性：一个无限集可以同它的一个真子集等势。第13页，共38页，2023年，2月20日，星期一定理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无限集的性质无限集的性质第14页，共38页，2023年，2月20日，星期一证明：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无限集的性质第15页，共38页，2023年，2月20日，星期一2、证明M~M'M：{m1m2

m3m4…mi…}∪M2↕↕↕↕↕↕↕↕M':{m2m3m4m5…mi+1…}∪M2§4.3无限集的性质因为无限，所以总能找到对应元素第16页，共38页，2023年，2月20日，星期一推论一集合为无限集的充分必要条件是它必含有与其等势的真子集。分析：充分性：M~M'且M⊃M'⇒M为无限集必要性：M为无限集⇒它必含有与其等式的真子集充分性利用反正法证，即假设M为有限集推出矛盾。必要性即为定理4.7。§4.3无限集的性质第17页，共38页，2023年，2月20日，星期一证明：设一集合M含有与其等势的真子集M'且M为有限集，设其元素个数为n个。

M'也为有限集，设其元素个数为m个根据条件有M⊃M'，即有n>m

与M~M'矛盾，推论得证。§4.3无限集的性质第18页，共38页，2023年，2月20日，星期一无限集定义定义4.5一个集合若存在与其等势的真子集称为无限集，否则称为有限集。§4.3无限集的性质第19页，共38页，2023年，2月20日，星期一可列集的定义定义4.6凡与自然数集N等势的集合叫可列集。即：能与自然数N建立一一对应关系的集合例：下列集合都是可数集合：

1)O＝{x|xN，x是奇数};2)E＝{x|xN，x是偶数};

3)P＝{x|xN，x是素数};§4.3无限集的性质第20页，共38页，2023年，2月20日，星期一定理4.8一无限集必包含一可列集。分析：若无限集是可列集，定理显然成立。若无限集不是可列集，需要构造其无限子集，使无限子集与N等势，即得无限子集为可列集。§4.3无限集的性质可列集的重要性质第21页，共38页，2023年，2月20日，星期一证明：设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：012

3…i…↕↕↕↕↕↕↕A':a0a1a2a3…ai…§4.3无限集的性质A'为可列集，因为A

A'所以定理成立第22页，共38页，2023年，2月20日，星期一定理4.9可列集的无限子集仍为一可列集。分析：构造可列集的无限子集。证明其无限子集与N等势，即得无限子集为可列集。§4.3无限集的性质第23页，共38页，2023年，2月20日，星期一证明：设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：012

3…↕↕↕↕↕A':am0am1am2

am3…综合得证可列集的无限子集仍为一可列集。§4.3无限集的性质※可列集是无限集中的最小元素第24页，共38页，2023年，2月20日，星期一分析：在整数集I和自然数集N之间构造一一对应关系。证明：整数集I和自然数集N间的一一对应关系N：0123456…2n-12n…↕↕↕↕↕↕↕↕↕↕↕I:01-12-23-3…n-n…§4.3无限集的性质定理4.10整数集I是可列集。第25页，共38页，2023年，2月20日，星期一§4.3无限集的性质定理4.11有理数集Q是可列集。分析：有理数的形式：，找出有理数的一定的排列规律，即得到一一对应的关系。第26页，共38页，2023年，2月20日，星期一§4.3无限集的性质证明：一切有理数均呈状，现将所有按下列次序排列正分数按其分子分母之和的大小顺序排列：从小到大正分数的分子分母之和相同者按分子大小顺序排列：从大到小与正分数具有相同形式的负分数排于正分数之后按上述规律可得一序列，即与N的一一对应关系：N：012345678910…↕↕↕↕↕↕↕↕↕↕↕↕Q:第27页，共38页，2023年，2月20日，星期一-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证明方法二：有理数和自然数的对应关系第28页，共38页，2023年，2月20日，星期一§4.3无限集的性质集合的大小问题集合的基数集合的基数可用|A|

来表示。对有限集A，|A|=集合A中元素的个数；对无限集A，|A|不能用有限集的方法来定义，规定自然数集N的基数为א0(阿列夫零)，即|N|=א0第29页，共38页，2023年，2月20日，星期一§4.3无限集的性质(2)集合大小的比较有限集大小的比较，用“相等”、“不相等”无限集大小的比较，用“等势”、“不等势”等势即为基数相同，由此立即可知：所有可列集的基数均为א0。(3)可列集是最小的无限集没有比基数א0更小的无限集，但存在比基数א0更大的无限集。如实数集。第30页，共38页，2023年，2月20日，星期一§4.3无限集的性质分析：1、证(0，1)内的实数不可列，利用反正法，即假设其是可列的，当将其列出时总能找到一个元素不属于列出的集合。2、证(0，1)内的实数与R等势，即R不可列。定理4.12实数集是不可列的。第31页，共38页，2023年，2月20日，星期一证明：1、定义在(0，1)内的实数集S={x|xR且0<x<1}∀xS，可表示为x=0.y1y2y3…(yi{0,1,…9})

假设S是可列的，则它的元素可依次排列：x0，x1，x2，…且我们有x0=0.a00a01a02…a0n…x1=0.a10a11a12…a1n……xm=0.am0am1am2…amn……只需证还能找到一个元素rS，但r不在x0，x1，x2，…中§4.3无限集的性质第32页，共38页，2023年，2月20日，星期一构造一S内的实数r=0.b0b1b2…bn…其中当aii≠1时，bi=1

当aii=1时，bi=2因为b0≠a00，所以r≠x0因为b1≠a11，所以r≠x1

…因为总有一位不同，所以r≠xi，这与rS矛盾，即(0，1)是不可列的。2、证明S~R，即建立一一对应关系。设R中的元素为y，S中的元素为x，因为S不可列，所以只能建立关系式：§4.3无限集的性质第33页，共38页，2023年，2月20日，星期一§4.3无限集的性质当x(0，1/2]，根据上式有y(0，+∞)当x[1/2，1)，根据上式有y(－∞，0)综上所述x(0，1)，有y(－∞，+∞)根据上式还需证y(－∞，+∞)，有x(0，1)，才能证得上式试R和S之间满足一一对应关系。转变上式，得第34页，共38页，2023年，2月20日，星期一§4.3无