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

离散数学有限集与无限集课件§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是无限的。分析:∀xN,找到一一对应得函数f(x),且{y|y=f(x),∀xN}N证明:设函数f:N→N′定义为f(x)=2x,显然f就是一对一得,而且有f(N)N,所以N就是无限得。§4、1有限集与无限集基本概念定理4.2实数集R是无限的。分析:∀xR,找到一一对应得函数f(x),且{y|y=f(x),∀xR}R证明：设函数f：R→R′为这个函数f是一对一的，而显然有f(R)R，所以R是无限的。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，则有奇数项就是加,偶数项就是减。§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

英德法12

87§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:{m1m2

m3m4…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',即有n>m

与M~M'矛盾,推论得证。§4、3无限集得性质无限集定义定义4、5一个集合若存在与其等势得真子集称为无限集,否则称为有限集。§4、3无限集得性质可列集得定义定义4、6凡与自然数集N等势得集合叫可列集。即:能与自然数N建立一一对应关系得集合例:下列集合都就是可数集合:

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

3)P＝{x|xN,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:012

3…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:012

3…↕↕↕↕↕A':am0am1am2

am3…综合得证可列集得无限子集仍为一可列集。§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是可列集。分析:有理数得形式:,找出有理数得一定得排列规律,即得到一一对应得关系。§4、3无限集得性质证明：一切有理数均呈状，现将所有按下列次序排列正分数按其分子分母之和的大小顺序排列：从小到大正分数的分子分母之和相同者按分子大小顺序排列：从大到小与正分数具有相同形式的负分数排于正分数之后按上述规律可得一序列，即与N的一一对应关系：N：012345678910…↕↕↕↕↕↕↕↕↕↕↕↕Q:-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无限集得性质集合得大小问题集合得基数集合得基数可用|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|xR且0<x<1}∀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……只需证还能找到一个元素