第八章-形式语言与自动机课件.ppt

《第八章-形式语言与自动机课件.ppt》由会员分享，可在线阅读，更多相关《第八章-形式语言与自动机课件.ppt（69页珍藏版）》请在三一办公上搜索。

1、2023/4/3,1,4-1 函数的概念,定义4-1.1 设A和B是两个任意集合，而f是A到B的二元关系，如果对于A中的每一个元素x，B中都存在惟一元素y，使得x,yf，则称关系f是A到B的函数或映射。记为 f：AB 或 A B 假如x,yf，x称为自变元或像源，y称为在 f 作用下x的像或函数值。x,yf，常记为y=f(x)，且记f(X)=f(x)|xX。,2023/4/3,2,由函数的定义可以看出，函数是一种特殊的二元关系。若f是A到B的函数。它与一般二元关系的区别如下：函数的定义中强调A中的每一个元素x有像，所以A=dom f。这称为像的存在性。函数的定义域是A，而不是A的某个真子集。函

2、数的定义中还强调像y是惟一的，一个x A只能对应唯一的一个y，称做像的惟一性。像的惟一性可以描述为：设f(x1)=y1且f(x2)=y2。如果x1=x2，那么y1=y2。或者，如果y1y2，那么x1x2。,2023/4/3,3,【例4.1.1】设 N为自然数集合，下列N上的二元关系是否为函数？f=x,2x|xN g=x,2|xN 解：f和g都是从自然数集合N到自然数集合N的函数，常记为f：NN，f(x)=2x和g：NN，g(x)=2。,2023/4/3,4,定义 设A和B是两个任意的集合，f：AB，A1A，集合f(x)|xA1称为集合A1在 f 下的像，记为f(A1)。集合A在 f 下的像 f

3、(A)=f(x)|xA称为函数f的像。显然，函数 f 的像f(A)就是二元关系 f 的值域，即f(A)=ran f B。有时也记作Rf，即Rf=y|(x)(xA)(y=f(x)，集合B称为f的共域，ran f 亦称为函数的像集合。【例4.1.2】设f：1,2,3 a,b，f=1,a,2,a,3,b，A1=1,2，试求A1在f下的像f(A1)和函数f的像f(A)。解：f(A1)=f(x)|xA1=f(1),f(2)=a f(A)=f(x)|xA=f(1),f(2),f(3)=a,b,2023/4/3,5,定义4-1.2 设函数f：AB，g：CD，若A=C，B=D且xA和xC，有f(x)=g(x)

4、，则称函数 f 和g相等，记为f=g。例如，函数f：NN，f(x)=x3 函数g：1,2,3 N，g(x)=x3 虽然函数f和g有相同的表达式x3，但是它们是两个不同的函数。如果把f和g看成二元关系，fNN，用列举法表示为：0,0,1,1,2,8,3,27,4,64,g1,2,3 N，用列举法表示为：0,0,1,1,2,8,3,27 按二元关系相等的条件衡量，它们也是不等的。函数相等和二元关系相等是一致的。,2023/4/3,6,设A和B是两个任意集合，AB任意子集是A到B的二元关系，但不一定是A到B的函数。当A和B是有限集时，A到B的二元关系共有2|A|B|个，A到B的函数有多少个呢？以下研

5、究这个问题。设A和B是两个任意的有限集合，分别由m个和n个不同的元素，由于从A到B的任意一个函数的定义域是A，在这些函数中每一个恰有m个序偶。另外任何元素x A，可以有Y的n个元素中的任何一个作为他的像，故共有nm个不同的函数。f|f：AB是A到B的所有函数构成的集合，常记为BA。读作B上A。,2023/4/3,7,【例4.1.3】设 A=1,2,3，B=a,b，求BA。解：由A到B的函数有以下8个：f0=1,a,2,a,3,a f1=1,a,2,a,3,b f2=1,a,2,b,3,a f3=1,a,2,b,3,b f4=1,b,2,a,3,a f5=1,b,2,a,3,b f6=1,b,2

6、,b,3,a f7=1,b,2,b,3,b BA=f0,f1,f2,f3,f4,f5,f6,f7 A到B的函数共8个，8=23=|B|A|。当A和B都是有限集时，这个结论可以推广。一般地说，若|A|=m，|B|=n，则|BA|=nm=|B|A|。,2023/4/3,8,定义4-1.3 设f：AB，若f的值域ran f=B，即B的每一个元素是A中一个或多个元素的象点，则称这个映射f为满射（或到上映射）。设f是A到B的函数，由定义不难看出，如果yB，都存在xA，使得f(x)=y，则f是满射函数。例如，A=a,b,c,d，B=1,2,3，f是由A到B的函数，定义为：f=a,1,b,1,c,3,d,2

7、 因为ran f=f(A)=1,2,3=B，所以f是满射。图4.1.1是f的示意图。由图4.1.1可得出如下的结论：若A、B是有限集，f：AB是满射，在f的示意图中，B中每个元素至少是一个有向边的终点且|A|B|,2023/4/3,9,定义4-1.4 设f：AB，若yran f，存在惟一的xA，使得f(x)=y，则称f为入射。即A中没有两个元素有相同的象，则称这个映射为入射（或一对一映射）。设f是A到B的函数，由定义不难看出，如果对于x1A，x2A，f(x1)=y1，f(x2)=y2。当y1=y2时，一定有x1=x2，则f是入射函数。当x1x2时，一定有y1y2，则f是入射函数。,2023/4

8、/3,10,【例4.1.4】设f：a,b2,4,6，定义 f=a,2,b,6 函数f是否为入射？f是否为满射？,解：因为f(a)=2，f(b)=6，所以f是入射。因为 f 的值域ran f=2,62,4,6，所以f不是满射。图4.1.2是 f 的示意图。由图4.1.2可得出如下的结论：若A、B是有限集，f：AB是入射，在 f 的示意图中，B中每个像点是且仅是一条有向边的终点且|A|B|,2023/4/3,11,定义4-1.5 设f：AB，若f既是入射，又是满射，则称f为双射。例如：A=1,2,3，B=a,b,c，f=1,a,2,c,3,b，f是A到B的双射函数，图4.1.3是f的示意图。,20

9、23/4/3,12,若A、B是有限集，f：AB是双射，则 f 一定是满射。故B中每个元素至少是一个有向边的终点；f 也是单射，故B中每个像点是且仅是一条有向边的终点。所以，在双射函数的示意图中，B中每一个元素是且仅是一条有向边的终点。若A、B是有限集，f：AB是双射，则 f 一定是满射，所以|A|B|；f 也是入射，所以|A|B|。于是|A|=|B|。,2023/4/3,13,2023/4/3,14,解：f(x)=-x2+2x-1=-(x-1)2，f 是开口向下的抛物线，不是单调函数，所以不是入射。在 x=1处取得极大值0，所以f 不是满射。f 既不是入射也不是满射。f 是单调增加函数。因此是

10、入射，但不是满射，因为ran f=ln 1，ln 2，R f是满射，但不是入射，例如f(1.5)=1.5=1，而f(1.2)=1.2=1 f是单调增加函数且ran f=R，它既是入射，也是满射，因此它是双射。f 不是入射也不是满射。当x0时，f(x)；而当x时，f(x)。在x=1处函数f(x)取得极小值f(1)=2。因此它既不是入射也不是满射。,2023/4/3,15,定理4-1.1 令X和Y为有限集，若X和Y的元素个数相同，即|X|=|Y|，则f：XY是入射的，当且仅当他是一个满射。证明：a 若f是入射，则|X|=|f(X)|，因此|f(X)|=|Y|，从f 的定义我们有f(X)Y，而|f(

11、X)|=|Y|，又因为|Y|是有限的，故f(X)=Y，因此f是一个入射推出f是满射。b 若f是一个满射，根据满射的定义f(X)=Y，于是|X|=|Y|=|f(X)|。因为|X|=|f(X)|和|X|是有限的，故f是一个入射，因此f是满射推出f是一个入射。这个定理必须在有限集情况下才能成立，在无限集上不一定有效，如f：II是f(X)=2x，在这种情况下整数映射到偶整数，显然这是一个入射，但不是满射。,2023/4/3,16,4-2 逆函数和复合函数,定理4.2.1设 f：AB是双射函数，则 f 的逆关系f C是B A的双射函数。证明：先证逆关系 f C是B到 A的函数。因为 f 是函数，所以 f

12、 C是B到 A的二元关系。以下证明B到 A的二元关系f C是B到 A的函数。yB，因为 f：AB是满射，所以，yB必有xA，使x,y f，由逆关系的定义得，y,x f C。设y1,x1 fC，y2,x2 fC，y1=y2，由逆关系的定义知，x1,y1 f，x2,y2 f，因为f是入射，所以x1=x2 故 f C是B到 A的函数。,2023/4/3,17,再证 f C是满射。因为ran f C=dom f。又因为 f 是A到B的函数，所以dom f=A。于是ran f C=A。所以f C是B到 A的满射。最后证f C是入射。设y1,x1 f C，y2,x2 f C且x1=x2，由逆关系的定义有x

13、1,y1 f，x2,y2 f，又因为f是函数，必有y1=y2。所以 f C是入射。这就证明了f C是双射函数。,2023/4/3,18,定义4.2.1 设f：AB是双射函数，称BA 的双射函数f C为 f 的逆函数，记为：f-1。例如，设A=1,2,3，B=a,b,c。f=1,a,2,c,3,b 显然，f是A到B的双射函数。f的逆关系 f C=a,1,c,2,b,3是B到A的双射函数，记为f-1，f 1是 f 的逆函数。又如 g=1,a,2,a,3,b也是A到B的函数，但g不是满射，也不是入射，因而不是双射。逆关系 gC=a,1,a,2,b,3不是B到 A的函数。,2023/4/3,19,二元

14、关系的复合关系定义为：设X，Y，Z是集合，R XY，SYZ，集合 x,zxXzZ(y)(yYx,yRy,zS)叫做R和S的复合关系。记为RS。即 RS=x,zxXzZ(y)(yYx,yRy,zS)将RS=x,zxXzZ(y)(yYx,yRy,zS)记为SR，即 SR=x,zxXzZ(y)(yYx,yRy,zS),前者叫做R和S的复合关系。为了与前者区别，后者叫做二元关系S在二元关系R左边的复合关系，简称为S和R的左复合关系。,2023/4/3,20,前面已经讲过，函数是满足一定条件的二元关系，当然它可以进行左复合运算。函数的左复合关系描述为：设f：AB，g：CD，若f(A)C，集合 gf=a,

15、d|aAdD(b)(bBa,bfb,dg)=a,d|aAdD(b)(bBb=f(a)d=g(b),定义4.2.2 设f：AB，g：CD，若f(A)C，集合 gf=a,d|aAdD(b)(bBb=f(a)d=g(b)称函数g在函数 f 左边可复合。记为gf。,2023/4/3,21,定理4.2.2 两个函数的复合是一个函数。证明 设g：W Z，f：X Y为左复合，即f(X)W。a 对于任意xX，因为f为函数，故必有唯一的序偶x,y使y=f(x)成立，而f(x)f(X)即f(x)W，又因为g是函数，故必有唯一序偶y,z使z=g(y)成立，根据复合定义，x,z gf，即X中每个x对应Z中某个z。,2

16、023/4/3,22,b 假定gf中包含序偶x,z1 和x,z2 且 z1z2，这样在Y中必存在y1和y2，使得在f中有x,y1 和x,y2 在g中有y1,z1 和y2,z2。因为f是一个函数，故y1=y2。于是g中有y,z1 和y,z2，但g是一个函数，故 z1=z2，即每个xX只能有唯一的x,z gf。由 a，b可知gf 是一个函数。在定义4-2.2中，当W=Y时，则函数f：X Y，g：Y Z。gf=x,z|xXzZ(y)(yYy=f(x)z=g(y)称为复合函数，或称gf 为g 对f 的左复合。根据复合函数的定义，显然有gf(x)=g(f(x)。,2023/4/3,23,定理 设f：AB

17、，g：CD，f(A)C，则函数g在函数f左边的复合关系gf是A到D的函数。证明：aA，因为f是A到B函数，必存在惟一的bB，使得a,bf。即b=f(a)。而b=f(a)f(A)C，故bC。又因为g是C到D函数，必存在惟一的dD，使得b,dg。即d=g(b)。故由定义4.2.2，a,dgf，即gf(a)=d。所以gf是A到D的函数。,2023/4/3,24,定义 设f：AB，g：CD，若f(A)C，函数g在函数f左边的复合关系gf称为函数 g在函数f左边可复合函数，简称为g和f的左复合函数或g和f的复合函数。仍然记为gf。gf是A到D的函数。推论 设f：AB，g：CD，f(A)C，则gf(x)=

18、g(f(x)。证明：由前面定理的证明过程可以看出，aA，b=f(a)且d=g(b)，gf(a)=d，于是，gf(a)=d=g(b)=g(f(a)。所以，gf(x)=g(f(x)。,2023/4/3,25,定理4.2.3 设f：AB，g：BC，gf：AC。如果f 和g 都是满射，则gf 也是满射。如果f 和g 都是入射，则gf 也是入射。如果f 和g 都是双射，则gf 也是双射。证明：cC，因为g是B到C的满射，所以cC必有bB，使c=g(b)。又因为f是A到B满射，所以bB必有aA，使b=f(a)。于是，gf(a)=g(f(a)=g(b)=c，所以gf是满射。设a1A且a2A，a1a2，因为f

19、是A到B入射，所以f(a1)f(a2)，f(a1)B，f(a2)B。又因为g是B到C入射，所以g(f(a1)g(f(a2)，即gf(a1)gf(a2)，故gf是入射。f和g都是双射，则f和g都是满射和入射，由和知，gf是满射和入射，故gf是双射。,2023/4/3,26,定义4.2.3 函数f：AB叫做常函数，如果存在某个y0 Y，对于每个x X都有f(x)=y0，即f(X)=y0。定义4.2.4 如果Ix=|xX则称函数Ix：XX为恒等函数。,定义设A是任意集合，AA，xA，定义：A0,1如下：叫做A的特征函数。设R是A上的等价关系，xR是 x形成的R等价类，A/R是A关于R的商集，f：AA

20、/R，定义为：f(x)=xR，称f为A到商集A/R的自然函数或自然映射。,2023/4/3,27,在二元关系的复合运算，介绍了复合运算性质。这些性质有：设RXY，SYZ，T ZW。(RS)T=R(ST)RIY=IXR=R RRC=IX，RCR=IY(RS)C=SCRC 函数的复合运算也有类似的性质。以下几个定理介绍了这些性质。,2023/4/3,28,定理 设f：AB，g：BC，h：CD，则 h(gf)=(hg)f 证明：由定义可知，gf：AC，h(gf)：AD。类似地 hg：BD，(hg)f：AD。令f(x)=y，g(y)=z，h(z)=u。由前面定理可知，gf(x)=g(f(x)=g(y)

21、=z，hg(y)=h(g(y)=h(z)=u h(gf)(x)=h(gf)(x)=h(z)=u=hg(y)=hg(f(x)=(hg)f(x)所以 h(gf)=(hg)f 因为函数的复合运算满足结合律，所以可略去函数复合运算中的括号，即用hgf记h(gf)=(hg)f，另外，还可以定义函数的幂：f 2=ff，f 3=fff，,2023/4/3,29,【例4.2.1】设R是实数集合，下面是R到R的函数f(x)=x+2，g(x)=x-2，h(x)=3x 先求g和f的复合函数gf，h和g的复合函数hg。再验证h(gf)=(hg)f 解：显然h(gf)：RR(hg)f：RR gf(x)=g(f(x)=g

22、(x+2)=(x+2)-2=x hg(x)=h(g(x)=h(x-2)=3(x-2)=3x-6 h(gf)(x)=h(gf(x)=h(x)=3x(hg)f(x)=hg(f(x)=hg(x2)=3(x2)-6=3x所以 h(gf)(x)=(hg)f(x)故 h(gf)=(hg)f,2023/4/3,30,定理4.2.4 设f：AB，IA是A上的恒等函数，IB是B上的恒等函数，则IBf=fIA=f 证明：先证fIA=f fIA：AB，又 fIA(x)=f(IA(x)=f(x)所以 fIA=f 类似地可以证明IBf=f,2023/4/3,31,定理4.2.5设f：AB为双射函数，f1：BA是f的逆函

23、数，则f-1f=IA，ff-1=IB 证明：先证明f-1 f=IA f-1f：AA。IA：AA。xA，设f(x)=y，则f-1(y)=x。f-1 f(x)=f-1(f(x)=f-1(y)=x=IA(x)所以 f-1 f=IA 类似地可以证明ff-1=IB,2023/4/3,32,【例4.2.2】设 A=0,1,2，B=a,b,c，f：AB，定义为：f=0,c,1,a,2,b，求f 1、f-1f和ff-1，验证 f-1f=IA和ff-1=IB 解：f-1=a,1,b,2,c,0 f-1f=0,0,1,1,2,2 ff-1=a,a,b,b,c,c f-1f：AA，IA：AA f-1f(0)=0=I

24、A(0)，f-1f(1)=1=IA(1)，f-1f(2)=2=IA(2)所以f-1 f=IA ff-1：BB，IB：BB ff-1(a)=a=IB(a)，ff-1(b)=b=IB(b)，ff-1(c)=c=IB(c)所以ff-1=IB,2023/4/3,33,定理4.2.6 设f：AB，是一一对应的函数，则(f-1)-1=f。证明：a 因f：AB是一一对应的函数，故f-1：BA也是一一对应的函数，因此(f-1)-1：AB又为一一对应的函数，显然 dom f=dom(f-1)-1=A b xA f：xf(x)f-1：f(x)x(f-1)-1：xf(x)。由 a，b可知(f-1)-1=f。,202

25、3/4/3,34,定理4.2.7 设f：AB，g：BC且 f 和g均为双射函数，则(gf)-1=f-1g-1 证明：因为f和g均为双射函数，f-1和g-1存在且 f-1：BA，g-1：CB 所以 f-1g-1：CA 另一方面，gf：AC。所以(gf)-1：CA。zC，因为g为双射函数，yB 使g(y)=z，又因为f为双射函数，xA，使f(x)=y，于是，gf(x)=g(f(x)=g(y)=z 故(gf)-1(z)=x。另一方面，f-1(y)=x，g-1(z)=y。于是，f-1g-1(z)=f-1(g-1(z)=f-1(y)=x 所以(gf)-1=f-1 g-1,2023/4/3,35,4-3

26、特征函数与模糊子集,定义4.3.1令E是全集，A是E的子集，AE，由定义的函数：E 0,1，称为集合A的特征函数。,2023/4/3,36,设A和B是全集E的任何两个子集，对于xE，特征函数有如下一些性质。,2023/4/3,37,对于特征函数进行推广可以导出模糊子集的概念。设E=x1,x2,xn,我们可以将E的任何一个子集A表示为：当,我们将 的取值范围不局限于0和1，而是取0和1之间的任何数，例如 其中0.2，0.3.0.8.分别称为该集合中对应元素的隶属程度。,2023/4/3,38,定义4.3.2给定论域E，指定E上的一个模糊子集 是指对任意xE 都有一个隶属程度 与它对应，称 为 的

27、隶属函数。从模糊子集的定义可以看出，当 只取0，1两值时，便成为普通子集。,2023/4/3,39,4-4 基数的概念,定义4.4.1 给定集合A的后继集定义为集合：A+=AA。若A为空集，则后继集为+，(+)+,(+)+)+,.这些集合可写成如下形式：，,.可简化为，,.若我们命名集合为0，那么，+=0+=1 1+=22+=3这就得到了自然数集合0,1,2,3,.这个集合也可以概括为如下公理形式（G.Peano公理）。,2023/4/3,40,G.Peano公理1、0N(其中0=)。2、如果nN，那么n+N(其中 n+=nn).3、如果一个子集SN具有性质：a 0S。b 如果nS，有n+S，

28、则S=N。性质3称极小性质，它指明了自然数系统的最小性，即自然数系统是满足公理1和2的最小集合。,2023/4/3,41,定义4.4.2 给定两个集合P与Q，如果我们对P中每个不同元素，与Q中每个不同元素，可以分别两两成对，那么我们说P的元素与Q的元素间存在着一一对应。定义4.4.3 当且仅当集合A的元素与集合B的元素之间存在着一一对应，集合A与集合B称为是等势的(或称同浓的)。记作AB。,关于等势的定义：设A和B是集合，如果存在A到B的双射函数，则称集合A和集合B等势。记作AB。设A和B是有限集合，AB，则存在A到B的双射函数，根据双射的性质，|A|=|B|。即A和B中元素的个数相等。,20

29、23/4/3,42,【例4.4.1】设I是整数集，N是自然数集。试证明IN。证明：设f：IN，定义为：,按照这个定义将I中的元素如下排列与N中的元素对应：I 0-1 1-2 2-3 3-4 4 N 0 1 2 3 4 5 6 7 8,2023/4/3,43,以下证明f是I到N的双射函数。任取nN，若n是偶数，有 I且 0，使f()=2=n；若n是奇数，有 I且 0，使f()=-2()-1=n。所以f是满射。,2023/4/3,44,若有n1I，n2I且n1n2。分下列4种情况讨论：假定n10且n20，则f(n1)-f(n2)=2n1-2n2=2(n1-n2)0，所以f(n1)f(n2)。假定n

30、10且n20，则f(n1)-f(n2)=(-2n1-1)-(-2n2-1)=2(n2-n1)0，所以f(n1)f(n2)。假定n10且n20，则f(n1)-f(n2)=2n1-(-2n2-1)=2(n1n2)+10(因为一个偶数与1的和或差永远不能为0)，所以f(n1)f(n2)。假定n10且n20，类似，同样有f(n1)f(n2)。所以f是入射。于是f是I到N的双射函数。IN,2023/4/3,45,定理4.4.1 设A，B，C是任意三个集合。则集合的等势有下列性质。（在集合族上等势关系是一个等价关系。）自反性:即AA。对称性:即若AB，则BA。传递性:即若AB，BC，则AC。证明：仅证明。

31、因为AB，BC，由等势的定义知，存在双射函数f：AB和双射函数g：BC，因为gf是A到C的双射函数。所以AC。,2023/4/3,46,定义4.4.4 如果集合A与集合0,1,2,n-1(n是某个自然数)等势，即存在双射函数，则称A为有限集，如果集合A不是有限集，则称A为无限集。定理4.4.2 自然数集N是无限集。证明：nN，设f是任意集合0,1,2,n-1到N的函数，令k=1+maxf(0),f(1),f(n-1)，kN。x0,1,2,n-1,f(x)k。因此，f不是从0,1,2,n-1到N的满射函数。当然不是从0,1,2,n-1到N的双射函数。因为n和 f 都是任意的，所以，自然数集N不是

32、有限集，而是无限集。,2023/4/3,47,定义4.4.5 将相互等势的集合归于同一类，对这样的每一类集合规定一个记号，称这个记号是这一类集合中每一个集合的基数或者势。集合A的势记为KA(或 或|A|)。根据定义，任何等势的集合具有相同的基数；而不等势的集合基数也不相同。规定有限集的势是该集合中元素的个数，空集的势为0。可以看到，如果两个集合能够建立双射函数，则两个集合元素间必一一对应，从基数的定义可以知道，该两集合应具有相同的基数。,2023/4/3,48,4-5 可数集与不可数集,定义4.5.1 设N是自然数集合，凡与N等势的集合称为可数集或可列集，也叫无限可数集或无限可列集。通常记可数

33、集的基数为0。读作“阿列夫零”。根据此定义，可知自然数集合N和整数集I都是可数集，|N|=|I|=0。有时我们把有限集和可数集统称为至多可数集。,2023/4/3,49,定理4.5.1 集合A是可数集的充分必要条件是A的全部元素可以排成一个无限序列A=a0,a1,。证明：设A是可数集，下证A的全部元素可以排成一个无限序列a0,a1,。因为A是可数集，由可数集的定义有NA。由等势的定义知，存在N到A的双射函数。设f：NA是双射函数，令an=f(n)A。则A可写成一个无限序列a0,a1,。设A的全部元素可以排成一个无限序列a0,a1,，下证A是可数集。因为A的全部元素可以排成一个无限序列a0,a1

34、,，所以可定义N到A一个双射函数f(n)=an，故A是可数集。该定理说明一个能用自然数编号的无限集是可数集。,2023/4/3,50,【例4.5.1】设N为自然数集，证明集合 M=x|x=10nnN是可数集。证明：令ai=10i，则集合M可用列举法表示为：M=0,10,20,30,=a0,a1,M是能用自然数编号的无限集，所以M是可数集。,定理 有限集不与它的任何真子集等势。证明：设A为任一有限集，BA，则C=A-B。|B|=|A|-|C|A|，即|A|B|，根据双射的性质，A与B之间不存在双射函数。A与B不等势。,2023/4/3,51,定理4.5.2 任何无限集必含有可数子集。证明：设A为

35、无限集，则A，在A中任取一个元素，记为a0。因为集合A是无限集，显然，集合A-a0不空。再从A-a0中取一个元素a1。同样A-a0,a1不空。可以继续做下去，从A中取出一系列元素a0,a1,令A=a0,a1,A是可数集。显然AA。,2023/4/3,52,定理4.5.3 无限集必与其某个真子集等势。证明：首先证明在任何一个无限集A中，一定能取出一系列元素a1,a2,。在A中任取一个元素，记为a1。因为集合A是无限集，显然，集合A-a1不空。再从A-a1中取一个元素，记为a2。同样，集合A-a1,a2不空。继续做下去，可从A中取出一系列元素a1,a2,。记=A-a1,a2,，令=a2,a3,，显

36、然A。f：A，定义为：f(ai)=ai+1 i=1,2,f(x)=x x 显然，f是A到的双射。A可以给出有限集与无限集的另外一个定义如下：不能和自己的任何真子集等势的集合称作有限集。能与自己的某个真子集等势的集合称作无限集。,2023/4/3,53,这个定理可以用图4.5.1所示。设线段AB，其上有线段CD，则线段AB与CD上所有的点，可以做成一一对应。做法：把CD移出与AB平行，联AC、BD延长交于G，则AB上任意点E与G的联线EG必与CD相交于F。反之，CD上任意点F，与G的联线FG延长必交AB于E，上述E，F的对应做法，即说明ABCD。,2023/4/3,54,定理4.5.4 可数集的

37、无限子集仍为可数集。证明：设A为可数集，它的元素编号如下：a0,a1,an,任取A的无限子集B，在A的元素中，从a0开始逐个检查，将遇到的第一个B的元素记为，第二个记为，。因为B是无限集，所以B中的元素可排为，。因此B是可数集。,2023/4/3,55,定理4.5.5 可数个两两不相交可数集的并集仍为可数集。证明：设可数个可数集分别为：A0=a00,a01,a02,a03,a04,A1=a10,a11,a12,a13,a14,A2=a20,a21,a22,a23,a24,A3=a30,a31,a32,a33,a34,p+q=h称为元素apq(p,q=0,1,2,)的高度。对上述集合的所有元素，

38、先按高度大小编号，在同一高度中按q的值由小到大编号。这样就可以把并集A0A1A2中所有的元素按下列顺序(箭头所指顺序)编成一列：,2023/4/3,56,a00，a01，a02，a03，a04,a10，a11，a12，a13，a14,a20，a21，a22，a23，a24,a30，a31，a32，a33，a34,将各斜线上的元素排列为 a00;a10,a01;a20,a11,a02;所以并集A=A0A1A2是可数集。,2023/4/3,57,【例4.5.2】在直角坐标系下，两坐标x，y均为整数的点(x,y)称为格点。证明全体格点构成可数集。证明：对每个固定的整数n，An=n,m|m是整数中的元

39、素可排列为：n,0，n,1，n,-1，n,2，n,-2，所以An是可数集。显然，右半平面上的格点全体构成的集合就是并集A0A1A2，这是可数个可数集的并，因而是可数集。左半平面上的格点全体构成的集合就是并集A-1A-2A-3，这也是可数个可数集的并，因而是可数集。因为可数集的并是可数集，所以平面上的格点全体构成的集合A0A1A2A-1A-2A-3是可数集。,2023/4/3,58,定理4.5.6 设自然数集合N，则NN是可数集。证明省略。,定理4.5.7 有理数的全体组成的集合是可数集。证明：有理数r可写成分数，其中q0，p,q为互质的整数。把分数 记为序偶p,q，就成为平面上的格点。在平面上

40、的全体格点构成的集合中删除q=0和p,q不互质的序偶得集合S，S就是有理数集合,它是平面上的全体格点构成的集合的无限子集，而平面上的全体格点构成的集合是可数集。因此，有理数全体是可数集。,2023/4/3,59,定理4.5.8 设R为实数集，则集合x|xR0 x1是不可数集。同样R也为不可数集。证明：因为f:(0,1)R是双射函数，令S=x|xR0 x1，如果S是不可数集，则R也必为不可数集。所以先证x|xR0 x1是不可数集。如果x|xR0 x1是可数集，那么，其中所有实数可排成一数列：t1,t2,tn,，将这些实数用十进制无限小数表示为(0.2可表示为0.19999.，0.123可表示为0

41、.12299999.)：t1=0.t11t12t13t14 t2=0.t21t22t23t24 t3=0.t31t32t33t34,2023/4/3,60,其中所有tij都是0，1，2，9十个数字中的一个，并且对每一个i，ti=0.ti1ti2ti3ti4中无限项后不全为0。作十进制小数 a=0.a1a2a3a4 于是所作成的数a应该在集合x|xR0 x1中，但不会在数列t1,t2,tn,中，因为对于每个n，antnn，所以atn，这和ti|i=1,2,是区间x|xR0 x1中实数全体的假设相矛盾。因此x|xR0 x1是不可数集。从而R也是不可数集。定义 集合x|xR0 x1的基数称为连续点集

42、的基数或称作连续统的势。记为kR=。读作“阿列夫”。,2023/4/3,61,4-6 基数的比较,定义4.6.1 若集合A到集合B存在一个入射，则称A的基数不大于B的基数或称A的基数小于等于B的基数，记为KAKB。若集合A到集合B存在一个入射，但不存在双射，则称A的基数小于B的基数，记为KAKB。,定理4.6.1(Zermelo定理)设A和B是集合，则以下三条中恰有一条成立。a KAKBb KBKA c KA=KB证明从略。,2023/4/3,62,定理4.6.2(Cantor-Schroder-Bernstein定理)设A和B是集合，如果KAKB且KBKA，则KA=KB。证明从略。这个定理对

43、证明集合的基数相同提供了有效方法。如果我们能够构造一入射函数f：AB，即说明有KAKB。另外，如能够构造入射函数f：BA，即有KBKA。根据本定理就得到 KA=KB。,2023/4/3,63,【例4.6.1】证明区间0,1与(0,1)有相同的基数。证明：作入射函数 f：(0,1)0,1，f(x)=x|(0,1)|0,1|g：0,1(0,1)，f(x)=+|0,1|(0,1)|所以|(0,1)|=|0,1|【例4.6.2】实数集R的基数是。证明：先证集合R1=x|xR0 x1和实数集R等势。作R1到R的函数f：R1R f(x)=因为正切函数tg x在R1中是单调递增的，所以f是R1到R的双射函数

44、。因此，R1R，因此，|R|=。,2023/4/3,64,【例4.6.3】设A是自然数集合，B=(0,1)，|A|N|=0，|B|=，求证|AB|=。证明：设R是实数集合。定义一个从AB到R的函数。f(n,x)=nx 显然f是从AB到R的入射函数，所以|AB|R|，而|R|=，故|AB|此外，作函数 g：(0,1)AB，g(x)=0,x因为g是入射的，|(0,1)|AB|，而|(0,1)|=，故|AB|。所以|AB|=。,2023/4/3,65,定理4.6.3 设A是有限集合，则KA0。证明：设|A|=n，则A0,1,2,n-1。定义函数 f：0,1,2,n-1N(N为自然数)，f(x)x。f

45、是入射函数，故|A|N|=0 已证得0,1,2,n-1到N之间不存在双射函数，所以|A|N|=0，即|A|0。又作函数 g：N0,1，g(n)=，g是入射函数，故|N|。因为N与0,1间不存在双射函数，所以|N|，因此0。|A|0成立。,2023/4/3,66,定理4.6.4 设A是无限集合，则0|A|。证明：因为A是无限集合，故A必包含一个可数无限子集A，作函数f：AA，f(x)=x，显然f是A到A入射函数，所以|A|A|而|A|=0，从而0|A|我们已经证明了0。在本定理中证明了，当A是无限集合时，0|A|。但是直到目前为止还没有人能够证明：有一个无限集的基数严格介于0与之间。假定是大于0

46、的最小基数，即不存在任何基数KS,使得0KS 成立，这就是著名的连续统假设。,2023/4/3,67,下面定理说明，没有最大的基数，也没有最大的集合。定理4.6.5(Cantor定理)设A是集合，P(A)是A的幂集合，则KAKP(A)证明：先证明KAKP(A)作函数f：AP(A)，f(a)=a，f是A到P(A)入射，故KAKP(A)再证明KA KP(A)设KA=KP(A)，则必存在A到P(A)双射函数，设为g：AP(A)。对于任意aA，必有P(A)中惟一的g(a)与之对应。,2023/4/3,68,如果ag(a)，称a是A的内部元素；若ag(a)，称a是A的外部元素。令S=a|aAag(a)，即S是A的外部元素集合。显然SA，故SP(A)。因为g是双射函数，故必有一个元素bA，使g(b)=S。若bS，则由S(外部元素的集合)的定义，b是A的外部元素；又因为g(b)=S，bS=g(b)，此时，由A的内部元素的定义，b是A的内部元素。得出矛盾。若bS，则由S(外部元素的集合)的定义，b是A的内部元素；又因为g(b)=S，bS=g(b)，此时，由A的外部元素的定义，b是A的外部元素。又得出矛盾。故KA KP(A)由和得KA KP(A),2023/4/3,69,