离散数学课件.ppt

《离散数学课件.ppt》由会员分享，可在线阅读，更多相关《离散数学课件.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于离散数学05.04.2023离散数学1现在学习的是第1页，共64页05.04.2023离散数学23.1 基本概念定义定义3.1.1：设A，B是两个集合，是A到B的二元关系，若对A中每个每个元素a，有唯一唯一的 bB，使得，则称为A到B的映射，记为：:AB 或 所谓从A到B的映射就是A中的每个人都向B中的人射了一箭，并且都射中了B中的一个人。既没有人偷懒不射，也没有人一箭双雕。这时，B中的人，有的可能身中数箭，有的可能一箭未中。当然也可能刚好每人中了一箭。现在学习的是第2页，共64页05.04.2023离散数学3几个概念映象：映象：若，则称b为a的映象。(被射中的人)象源：象源：若,则a为b

2、的象源,记为(a)=b。(射箭的人)映象集：映象集：(A)=bB|存在aA,使(a)=b 称为A的映象集。(全体被射中的人的集合。)显然，(A)B。变换：变换：A到A的映射称为变换。(窝里斗)现在学习的是第3页，共64页05.04.2023离散数学4下列关系是否构成映射？R1abcef gAB嗨！R1可不是映射喔。有人偷懒了。R2abcefgAB嗨！R2也不是映射喔。有人一箭双雕。R3abcefgAB啊哈！R3才是一个映射呢。现在学习的是第4页，共64页05.04.2023离散数学5满射、单射、双射定义定义3.1.2：若是A到B的映射，且对bB,aA,使得(a)=b，则称是A到B上上的映射，简

3、称满射满射。此时每个bB 必是A 中至少一个元素a 的映象，且(A)=B。糟糕！全被射中了。定义定义3.1.3：设是A到B的映射，若对a,bA,ab,均有(a)(b)，则称为A到B的单射单射或入射。此时|(A)|=|A|，B中每个元素最多是A中一个元素的映象。还好，只中了一箭。定义定义3.1.4：设是A到B的映射，若既是满射又是单射，则为A到B的双双射射或11映射映射。哼！你能射我，我也能射你。现在学习的是第5页，共64页05.04.2023离散数学6满射、单射和双射的例子设：N N，N 是自然数集，(n)=2n，nN。则是单射，但不是满射。设：0，0，1，()=sin()，0,。则是满射，但

4、不是单射。设：N E，N 是自然数集合，E是自然数中的所有偶数的集合，(n)=2n，n N。则是单射且是满射，所以是双射。现在学习的是第6页，共64页05.04.2023离散数学7判断下列映射是否单射，满射和双射。1、设：N N，N 是自然数集，(n)=2n，nN。（是变换）解：取b=2n+1，bN，由，由的定义知：(n)b，n,bN。不是满射。任取i，jN，且，且ij。若若(i)=(j)，即2i=2j，则i=j，此与ij矛盾。(i)(j)。故是单射。综上所述：是单射但不是满射。现在学习的是第7页，共64页05.04.2023离散数学82、：RR RR，R为实数集。(x,y)=解：(单射性)任

5、取(x,y),(u,v),假设(x,y)(u,v),若(x,y)=(u,v),即=则:x+y=u+v 得:x=u x-y=u-v y=v 从而(x，y)=(u，v),与假设矛盾.故是单射.(满射性)对任意RR,令:(x,y)=,即:x+y=u 解得:x=(u+v)/2 x-y=v y=(u-v)/2 显然(u+v)/2,(u-v)/2)RR,且满足(u+v)/2,(u-v)/2)=,故是满射.总之,是双射.现在学习的是第8页，共64页05.04.2023离散数学93、：NNN，N是自然数集(0N)，()=|x2-y2|解:取,NN ()=|1212|=0 ()=|2222|=0 故不是单射.又

6、取2N,因不存在自然数x,yN 满足:|x2y2|=2 故不是满射.既不是单射也不是满射.现在学习的是第9页，共64页05.04.2023离散数学10等势有限集合间的单射即满射定理定理3.1.1 设A，B是两个有限集，且|A|=|B|.于是，:AB是单射当且仅当是满射。证明：证明：(必要性)设是单射，则|A|=|(A)|,因为|A|=|B|,所以|(A)|=|B|,又因(A)B且B有限，所以(A)=B，从而是满射。(充分性)设是满射，则(A)=B，于是，|A|=|B|=|(A)|,即|A|=|(A)|。又因A有限，所以是单射。现在学习的是第10页，共64页05.04.2023离散数学113.2

7、 映射的运算逆映射的概念逆映射的概念定义定义3.2.1 设：AB，定义关系RBA为：R=|yB,xA,且(x)=y；如果R是B到A的映射，则称R为的逆映射。记为 1。例如：设：N E，N 是自然数集合，E是自然数中所有偶数的集合，(n)=2n，nN。则的逆映射-1为：-1：E N，-1(m)=m/2，mE。现在学习的是第11页，共64页05.04.2023离散数学12双射才有逆映射双射才有逆映射证明：必要性：证明：必要性：设-1存在，-1：BA。若不是满射，则yB,使得y不是A中任何元素的映象，即y没有象源。若不是单射，则 x1,x2A,x1x2且 (x1)=(x2)=y，则y的象源不唯一。不

8、论哪种情况，都说明的逆关系不是B到A的映射，此与假设矛盾。故是双射。充分性：充分性：设是双射，考虑的逆关系，易知，对于B中的每个元素y，都对应着A中唯一的一个在下以y为映象的元素x，因此，的逆关系是B到A的映射。定理定理3.2.1 设是A到B的映射，于是，存在逆映射当且仅当是双射。现在学习的是第12页，共64页05.04.2023离散数学13双射的逆也是双射显然，若是A到B的双射，则其逆映射 1也是B到A的双射，并且对任意的xA，均有：1(x)=x.现在学习的是第13页，共64页05.04.2023离散数学14复合映射定义定义3.2.2：设是A到B的映射，是B到C的映射，对任意xA,定义()(

9、x)=(x)，易知，是A到C的映射，称此映射为映射与映射的乘积乘积或复合映射复合映射。说明：说明：(1)是映射时，不一定不一定是映射；(2)假如 和 都是映射，不一定有 =，即映射的乘法不满足不满足交换律；(3)映射的乘法满足满足结合律。?现在学习的是第14页，共64页05.04.2023离散数学15 复合映射交换后不一定是映射12345678ACB因此，上例中 是映射，不是映射。(1)=(4)=7；(2)=(4)=7；(3)=(5)=8.而 (x)都不存在,其中，x B.令是A到B的映射，是B到C的映射，现在学习的是第15页，共64页05.04.2023离散数学16映射的乘法不满足交换律假如

10、 和 都是映射,如下所示：ABCxyzabxy (x)=(a)=x;(y)=(b)=y;(z)=(b)=y;(a)=(x)=a;(b)=(y)=b;所以，即映射的乘法不满足交换律。现在学习的是第16页，共64页05.04.2023离散数学17映射的乘法满足结合律映射的乘法满足结合律定理定理3.2.2 设是A到B的映射，是B到C的映射，是C到D的映射，于是 ()=()(式3.1)证明：对任意xA,有 ()(x)=()(x)=(x)()(x)=()(x)=(x)因此，(式3.1)成立。即映射的乘法满足结合律。现在学习的是第17页，共64页05.04.2023离散数学18双射两次求逆后不变双射两次求

11、逆后不变定理定理3.2.3 设是A到B的双射，则 (1)1=证明：证明：因为是双射，所以 1 是B到A的双射，从而(1)1是A到B的双射。对任意xA,设(x)=y,则 1(y)=x,由于 1也是双射，所以(1)1(x)=y,故(1)1=。现在学习的是第18页，共64页05.04.2023离散数学19复合双射的逆复合双射的逆先让我们来回忆一下复合关系的逆（定理2.2.3）：(RS)-1=S-1R-1。定理定理3.2.4 设是A到B的双射，是B到C的双射，于是 ()1=1 1 (式3.2)证明：证明：由假设不难知道，()1 和 1 1均是C到A的双射。对任意zC,因为 1也是双射，所以有唯一的yB

12、,使 1(z)=y.又因为 1也是双射，所以对y有唯一的xA,使 1(y)=x.于是，1 1(z)=1(1(z)=1(y)=x 又因()(x)=(x)=(y)=z,且 也是双射，所以()1(z)=x.从而对任意zC,有()1(z)=1 1(z)。因此，(式3.2)成立。注意：要使 为双射，不必要求和均是双射，只 须是单射，是满射即可，但要（3.2）成立，则和 必须为双射。现在学习的是第19页，共64页05.04.2023离散数学20第四章 可数集与不可数集 对于两个有限集，要比较这两个集合中元素的多少，只需分别数出它们的元素个数，再加以比较即可。但对于无限集，采用这种数数和比较元素个数的方法则

13、行不通。本章将利用“映射”的概念建立集合间的等势关系，并拓广集合中元素个数的概念，引进集合的基数的概念，最后讨论可数集与不可数集。现在学习的是第20页，共64页05.04.2023离散数学214.1 等 势 如何比较两个集合中元素的多少呢？引入等势的概念。定义定义4.1.1 设A和B是集合，若存在A到B的双射，则称A与B等势，记为A B。(可形象理解为A与B的元素一样多。)“”是一个等价关系。例例1 自然数集N与偶自然数集E是等势的，其中定义N到E的双射为：(n)=2n nN.现在学习的是第21页，共64页05.04.2023离散数学22证明“”是一个等价关系证明：设S=X|任意两个元素之间存

14、在双射，X是集合，是S上的二元关系：=|A,BS,存在双射:AB 1)对每个AS,存在恒等映射I:AA，I是双射,于是AA，故是自反的。2)对任意A,BS，若AB，则存在双射:AB，显然双射-1:BA存在，于是BA，故是对称的。3)对任意A,B,CS，若AB,BC,则存在双射:AB和:BC，而(A)=(A)=(B)=C，即双射:AC存在，于是AC，故是传递的。综上所述，是等价关系。现在学习的是第22页，共64页05.04.2023离散数学23有限与无限定义定义4.1.2：设Nn=0,1,n 1,n1,若集合A与Nn等势，则称A为有限集；否则称A为无限集。现在学习的是第23页，共64页05.04

15、.2023离散数学24无限多的自然数无限多的自然数 定理定理4.1.1 自然数集合N是无限集。证明：设nN，n 1,令是从Nn到N的映射，Nn=0,1,n1，下证不是双射。令k=1+max(0),(1),(n1),于是kN，但对任意xNn,均有(x)k,因此，不是满射，更不是双射。由定义4.1.2知，N为无限集。啊哈！这下我们知道有无限多个自然数了！现在学习的是第24页，共64页05.04.2023离散数学25抽屉原理（鸽巢原理）我们知道，若A，B均为有限集，且A与B之间存在双射，则A和B的元素个数相等，即AB。但是：定理定理4.1.2 任何有限集均不能和其真子集等势。此定理也称为抽屉原则：若

16、将n+1个物体放入n个抽屉中，则至少有一个抽屉中放了两个或两个以上的物体。抽屉原则对无限集并不总是成立，即无限集能够与其真子集等势。这是无限集合的一个非常重要的性质。我们已经看到自然数集等势于它的真子集偶数集合。下面我们再看几个例子。现在学习的是第25页，共64页05.04.2023离散数学26正实数和全体实数一样多例例2：令R和R+分别为实数集合和正实数集合，即R+=xR|x 0，显然，R+R，即R+是R的真子集。但是RR+证明：定义映射 f 如下：f(x)=ex ,xR 于是，对任意的xR，存在唯一的yR+,使 y=ex=f(x)；另一方面，对任意的yR+,存在唯一的 x=lnyR,使 f

17、(x)=ex=elny=y,这说明 f 是R到R+的一个双射。因此，RR+。现在学习的是第26页，共64页05.04.2023离散数学27例3：A=0,1）,B=0,1,A,BR.显然 A B.构造一A到B的双射,说明AB.解:令 A1=0,1/2,1/3,1/n,.作f:AB为:任取x1,x2A,x1x2,显然,f(x1)f(x2),且对 任意yB:若y=0,则取x=0,有f(0)=0若y=1,则取x=1/2A1,于是f(1/2)=1/(2-1)=y若y=1/n,取x=1/(n+1)A1,故f(1/(n+1)=1/n=y若yBA1,则取x=y,于是f(x)=x=y 综上所述f是A到B的双射,

18、于是AB.f(0)=0 f(1/n)=1/(n-1)(n1,1/nA1,nN)f(x)=x (x0,1)A1)现在学习的是第27页，共64页05.04.2023离散数学284.2 集合的基数几个记号：同有限集合中元素的个数的记法一样，集合A的基数用|A|表示。每个有限集合都恰与某个集合Nn=0,1,n1等势，其中n 0,N0=。如果A Nn,则A中有n个元素，即|A|=n;若A为无限集，则用一个特殊的符号i(读作阿列夫i，i是一个正整数)来表示它的基数。例如，对于自然数集合N，令|N|=0(读作“阿列夫零”)。现在学习的是第28页，共64页05.04.2023离散数学29如何比较集合的大小(1

19、)若AB,则称A的基数与B的基数相等,记为|A|=|B|，否则记为|A|B|。(2)若存在A到B的单射，则称A的基数小于或等于B的基数，记为|A|B|；或称B的基数大于或等于A的基数，记为|B|A|。(3)若|A|B|，且|A|B|，则称A的基数小于B的基数，记为|A|A|。根据集合的基数来比较它们的大小。定义定义4.2.1 令A、B为两个集合，由定义，|A|=|B|可形象地理解为A中的元素与B中的元素一样多。现在学习的是第29页，共64页05.04.2023离散数学30集合大小是可比的 定理定理4.2.1 设A和B为两个集合，总有|A|B|或者|B|A|。即任意两个集合总可比较大小。像实数一

20、样，任何两个基数都可以比较大小，所以有现在学习的是第30页，共64页05.04.2023离散数学31基数之间的相等关系是等价关系定理定理4.2.2 基数之间的相等关系“=”是一个等价关系,即对任何集合A,B和C,有:(1)|A|=|A|;(2)若|A|=|B|,则|B|=|A|;(3)若|A|=|B|且|B|=|C|,则|A|=|C|.现在学习的是第31页，共64页05.04.2023离散数学32基数间的是偏序关系定理定理4.2.3 基数之间的小于或等于关系“”是一个偏序关系,即对任何集合A,B和C,有:(1)|A|A|;(2)若|A|B|且|B|A|,则|A|=|B|;(3)若|A|B|且|

21、B|C|,则|A|C|.现在学习的是第32页，共64页05.04.2023离散数学33几个关于基数的问题我们知道自然数有无限多个。那么自然数集合是不是就是最大集合的呢？如果自然数集合不是最大的，那么比它更大的集合是什么样的呢？是不是存在最大的基数呢？不！不存在最大的集合。山外有山，天外有天。我们的口号是：只有更大，没有最大！现在学习的是第33页，共64页05.04.2023离散数学34山外青山楼外楼 定理定理4.2.4 对任意集合A,均有|A|(A)|,其中(A)为A的幂集。证明：证明：令 f:A(A)。f(a)=a，aA。显然，f 是单射,于是|A|(A)|.显然，象集 a|aA 是(A)的

22、真子集，所以，f 不是满射，从而不是双射。于是我们有|A|(A)|。错！错！错！错！错！错！错误是：虽然f不是双射，但不能说明A与(A)之间不存在其它的映射是双射。正确的作法是证明A与(A)存在任何的双射都是不可能的。现在学习的是第34页，共64页05.04.2023离散数学35山外青山楼外楼 假设|A|=|(A)|，则存在A到(A)的双射g.令B=aA|a g(a)(g(a)是a所对应的A的子集)，显然B(A)。bA,使g(b)=B。但是 (1)若bB，则由B之定义有bg(b)，即bB;(2)若bB，即bg(b)，则由B之定义有bB。总之有bB当且仅当b B，矛盾。故|A|(A)|。综合以上

23、，定理得证。定理定理4.2.4 对任意集合A,均有|A|(A)|,其中(A)为A的幂集。证明：证明：令f：A(A)。f(a)=a，aA。显然，f 是单射，于是|A|(A)|。讨论B的存在性：双射g：A(A)，aA，g(a)(A)即：g(a)是A的子集。又：作集合D=AA，AA，显然，D A，即D(A)。令：aA，g(a)=D，于是，aD，即a g(a)，但aA A。现在学习的是第35页，共64页05.04.2023离散数学36无限集也分大小，且无最大者 定理4.2.4说明：对任意无限集，它的幂集就比它大。因此对任意无限集都存在更大的集合。我们记自然数集合N的幂集的基数为1，也就是|(N)|=1

24、，由定理4.2.4知，0 1。可以证明|R|=|(N)|,其中R为实数集，于是，|N|R|。实际上N是最小的无限集。依次可以推得实数集合的幂集的基数为2，现在学习的是第36页，共64页05.04.2023离散数学374.3 可数集与不可数集定义定义4.3.1：设A是一个集合，若A与N等势，则称A为可数无限集；若A是有限集，则称A为可数集。有时也将可数无限集简称为可数集。（遇到讨论可数集的问题时要注意区分无限和有限两种情况。）不是可数集的集合就称为不可数集。现在学习的是第37页，共64页05.04.2023离散数学38整数集是可数集例例1：整数集Z是可数集。证明：可定义N到Z的映射如下：(n)=

25、n/2 (n为偶数）(n)=(1-n)/2 (n为奇数）不难验证为双射,故NZ,则Z是可数集。说明：映射 将 10，偶数正整数，奇数（除1外）负整数。现在学习的是第38页，共64页05.04.2023离散数学39定理定理4.3.1 A是可数无限集当且仅当A的所有元素可以如下编号排出：a1,a2,a3,an,此定理告诉我们，任何集合只要它的元素可以排序，就是可数的。如何判别一集合是可数的现在学习的是第39页，共64页05.04.2023离散数学40可数集的子集仍是可数的定理定理4.3.2 可数集的子集仍是可数集。证明：设A是可数集，若A是有限集，则它的子集仍是有限集，当然也是可数集。若A是无限集

26、，则由定理4.3.1知，A的元素可排列成：a1,a2,a3,an,(3.3)显然，A的无限子集可如下得到：从左向右看式(3.3)，可以依据子集中元素出现的次序将该子集的元素排列为：ai1,ai2,ai3,ain,由定理4.3.1知，该子集是可数集。现在学习的是第40页，共64页05.04.2023离散数学41有理数集Q是可数集。例2：有理数集是可数集。证明：已知任何非零有理数均可表示成确定的既约分数，故把全体有理数按如下方式排列：(1)0排在最前面；(2)对正分数，按它的分子与分母的和数由小到大排列，若和数相等，则分子小的排前面；(3)对负分数，把它紧排在相应的正分数后面。显然，任意有理数总会

27、排入此序列中。由定理4.3.1知，Q是可数集。这种排序的方法称为字典排序法。现在学习的是第41页，共64页05.04.2023离散数学42三角形方法有理数还可以按下表排序：显然用此方法可将所有的有理数排序。分子分母 1 2 3 4 5 6 1234.此方法称为三角形方法，是很有用的方法。现在学习的是第42页，共64页05.04.2023离散数学43符号串的集合是可数的令为一字母表，上的符号串为+：+=1+2+3+4+=i i=1 这里i为长度为i的符号串的集合。+为可数集。事实上，若|=k，则每一个符号串就是一个 k 进制的数，显然它们是可以按序排列起来。所以+为可数集。现在学习的是第43页，

28、共64页05.04.2023离散数学44不是所有的集合都能排序如果一个集合的元素可以排序，那么我们就可以一个一个地去数。是不是所有的集合的元素都能排序呢？不！不是所有的集合都能排序。比如0，1中实数的集合。让我们来设想一下将它的元素排一个序：0理所当然排在第一位。但是0之后应该排哪个呢？0.1？不！0.01？不！0.001？不！.？你会发现第二个就不知道排哪个好了。这样看来实数集合是没法去数了！?现在学习的是第44页，共64页05.04.2023离散数学45实数集是不可数的定理定理4.3.3 实数集是不可数的。证明：取R的子集(0,1)=xR|0 x 1,由定理4.3.2知，只需证明(0,1)

29、是不可数集即可。若(0,1)可数，则可将(0,1)中的数排成序列：1：0.a11 a12 a13 2：0.a21 a22 a23 3：0.a31 a32 a33 考虑数r=0.r1 r2 rk，其中当akk1则rk=1;当akk=1则 rk=2，k=1,2,。这样就保证了r不等于序列中任何数，因为对任意k，r的第k位rk与序列中第k号数的第k位akk不相等。因为r不在序列中，所以，(0,1)是不可数集。现在学习的是第45页，共64页05.04.2023离散数学46对角线方法定理4.3.3中所使用的方法称为对角线方法。a11a22a33r1r2r31 2 3 对角线方法是一种非常有用的方法。现在

30、学习的是第46页，共64页05.04.2023离散数学47连续统问题连续统问题已知N是可数集，而|N|R|.能否找到一个实数集R的子集A，使得：NAR,但又不存在A到R的双射？这个问题称为这个问题称为“连续统问题连续统问题”。现已证明：在现有公理系统中，证明它成立与否都不可能。现在学习的是第47页，共64页05.04.2023离散数学48新春晓信息时代到，处处有电脑。夜来打字声，程序知多少？答曰：诗中的问题是计算机上所有程序有多少？为何如此？有诗为证：计算机，靠程序，它的本事知底细。程序都是符号串，理应是个可数集。程序时时新，落花处处飘。它们同为0，数数便知道。现在学习的是第48页，共64页0

31、5.04.2023离散数学49第一篇的总结集合；关系；映射；可数集与不可数集。本篇内容有：现在学习的是第49页，共64页05.04.2023离散数学50集合基本概念：集合、子集、幂集。集合之间的关系：(真)含于(/)，相等()。集合的基本运算：并()、交()、差()和对称差()。笛卡尔直积：n个集合的笛卡尔直积是它们的 n元有序组的集合。它仍然是个集合。集合的表示：列举法和描述法。现在学习的是第50页，共64页05.04.2023离散数学51关系关系的概念：A到B的二元关系R是笛卡尔直积AB的子集。关系仍然是集合。关系的表示：仍然可以采用集合的表示方法。若A、B是有限集合，或者说R是有限集上的

32、关系，则R的表示还可以采用：关系矩阵 和 关系图。现在学习的是第51页，共64页05.04.2023离散数学52关系的性质自反性：x A xRx。反自反性：x A (xRx)。对称性：x，yA，若xRy yRx。反对称性：x，yA，若xRy且yRx x=y。传递性：x，y，zA，若xRy且yRz xRz。令R是定义在集合A上的关系。现在学习的是第52页，共64页05.04.2023离散数学53关系的运算关系是集合，可具有集合的各种运算。复合运算：RS=x，z|yB：xRy 且ySz，其中，R，S分别为A到B和B到C的关系。逆关系：R-1=y，x|x，y R。注意复合运算的逆：(RS)1=S-1

33、R-1。在一个集合A上的关系的幂运算：R0=x，x|x A,Rk=Rk-1R。现在学习的是第53页，共64页05.04.2023离散数学54关系的闭包某关系的具有某种性质的闭包是：包含该关系的最小的有此性质的关系。依据关系的性质有：r(R)、s(R)和t(R)，即自反闭包、对称闭包和传递闭包。r(R)=RR0。s(R)=RR-1。t(R)=Ri。i=1现在学习的是第54页，共64页05.04.2023离散数学55用关系矩阵实现关系的运算MRS=MR MS。MR0为R0的关系矩阵。显然R-1的关系矩阵就是MRT。显然的Rk关系矩阵是MRk=MRk-1 MR。R的自反闭包为MRMR0。R的对称闭包

34、为MRMRT。nR的传递闭包为 MRk。k=1令R、S为有限集上的关系，关系矩阵为MR 和 MS：现在学习的是第55页，共64页05.04.2023离散数学56等价、划分和商集集合A上的等价关系是具有自反性、对称性和传递性的关系。集合A的划分是将A中所有元素分成若干非空的两两互不相交的集合。集合A上的等价关系R可将A中的元素划分成等价类。这些等价类的集合称为A关于R的商集，记为A/R。集合A上的关系R是等价关系当且仅当A/R是一个划分。所以A上的等价关系和A的划分是一一对应的。现在学习的是第56页，共64页05.04.2023离散数学57序关系集合A上的序关系是具有自反性、反对称性和传递性的关

35、系。称A，为偏序集任何两个元素均有序关系的偏序集为全序集。极大(极小)元，最大(最小)元，上/下(确)界。有限集上的序关系可用Hasse图表示。任何非空子集均有最小元的偏序集为良序集。良序集一定是全序集，但反之不然。现在学习的是第57页，共64页05.04.2023离散数学58映射映射是每个象源都对应唯一映象的二元关系。满射、单射和双射。等势有限集之间的单射即满射，也就是双射。映射的逆不一定还是映射。只有双射才存在逆映射。映射的复合运算(乘法)仍是映射。乘法只满足结合律，不满足交换律。现在学习的是第58页，共64页05.04.2023离散数学59有限与无限集合A、B间若存在双射，则A，B等势，

36、AB。与确定数目n个元素构成的集合Nn等势的集合是有限集，否则是无限集。任何有限集均不能与其真子集等势(抽屉原理)。存在无限集，自然数集合就是无限集。无限集可以与其真子集等势。现在学习的是第59页，共64页05.04.2023离散数学60基数基数是集合中元素的数量，记为|A|。若AB，则|A|=|B|。若存在A到B的单射，则|A|B|。若|A|B|且|A|B|，则|A|B|。基数之间的是等价关系，而是偏序关系。对任何集合A，均有|A|(A)|。所以基数有无限多个，且无最大者。自然数集合的基数记为0，其幂集的基数记为1，依次类推。现在学习的是第60页，共64页05.04.2023离散数学61可数

37、集与自然数集合或其子集等势的集合是可数集，否则是不可数集。集合是可数集当且仅当其中的元素可排序。可数集的子集仍是可数集。有理数集，符号串的集合，所有程序的集合，等等，都是可数集。排序的方法：字典法，三角形法。现在学习的是第61页，共64页05.04.2023离散数学62不可数集存在不可数集，实数集就是不可数集。实数集中的元素无法排序。一种证明实数集中的元素无法排序的方法：对角线方法。现在学习的是第62页，共64页05.04.2023离散数学63集合篇到此结束，谢谢大家的合作。再见再见，让我们相逢在 图论的奇妙世界！现在学习的是第63页，共64页05.04.2023感感谢谢大大家家观观看看现在学习的是第64页，共64页