第3章二元关系.ppt

《第3章二元关系.ppt》由会员分享，可在线阅读，更多相关《第3章二元关系.ppt（154页珍藏版）》请在三一文库上搜索。

1、第3章 二元关系,3.1 基本概念 3.2 关系的合成 3.3 关系上的闭包运算 3.4 次序关系 3.5 等价关系和划分,3.1 基本概念,3.1.1 关系 关系的数学概念是建立在日常生活中关系的概念之上的.让我们先看两个例子 例1设A=a,b,c,d是某乒乓球队的男队员集合, B=e,f,g是女队员集合.如果A和B元素之间有混双配对关系的是a和g,d和e. 我们可表达为: R=a,g,d,e,这里R表示具有混双配对关系的序偶集合.所有可能具有混双配对关系的序偶 集合是: AB=x,y|xAyB =a,e,a,f,a,g,b,e,b,f,b,g, c,e,c,f,c,g,d,e,d,f,d,

2、g,例2设学生集合A1=a,b,c,d,选修课集合A2=日语,法语,成绩等级集合A3=甲,乙,丙.如果四人的选修内容及成绩如下: a 日 乙 b 法 甲 c 日 丙 d 法 乙 我们可表达为S=a,日,乙,b,法,甲,c,日,丙,d,法,乙,这里S表示学生和选修课及成绩间的关系.而可能出现的全部情况为,A1A2A3=x,y,z|xA1yA2zA3 =a,日,甲,a,日,乙,a,日,丙,a,法,甲,a,法,乙,=a,法,丙,b,日,甲,b,日,乙,b,日,丙,b,法,甲,=b,法,乙,b,法,丙,c,日,甲,c,日,乙,c,日,丙,=c,法,甲,c,法,乙,c,法,丙,d,日,甲,d,日,乙,=

3、d,日,丙,d,法,甲,d,法,乙,d,法,丙,定义 3.11 (1)AB的子集叫做A到B的一个二元关系. (2)A1A2An(n1)的子集叫做A1A2An上的一个n元关系. (3),的子集叫做A上的n元关系,从定义可看出,关系是一个集合,所有定义集合的方法,都可用来定义关系 例1,例2是列举法的例子一个谓词P(x1,x2,xn)可以定义一个n元关系R: R=x1,x2,xn|P(x1,x2,xn) 例如,实数R上的二元关系可定义如下: =x,y|xRyRxy 反之,一个n元关系也可定义一个谓词:,P(x1,x2,xn)=,1(真),当x1,x2,xnR时 0(假),当x1,x2,xnR时,当

4、n=1时,R=x|P(x)称为一元关系.它是一重组集合,表示论述域上具有性质P的元素集合,其意义与R=x|P(x)相同,仅记法不同而崐已例如,设P(x)表示“x是质数”,论述域是N,则质数集合可表示为 xP(x) 或 xP(x),关系也可归纳地定义.自然数上的小于关系可定义如下: (1) (基础)0,1 (2) (归纳)如果x,y,那么 (i)x,y+1 (ii)x+1,y+1 (3)(极小性)对一切x,yN,xy当且仅当x,y是由有限次应用条款(1)和(2)构成,定义3.12设R是 的子集,如果R=,则称R为空关系,如果 ,则称R为全域关系. 现在定义关系相等的概念,在关系相等的概念中不仅需

5、要n重组集合相等,还需其叉积扩集也相同. 定义3.13设R1是 上的n元关系,R2是 上的m元关系.那么R1=R2,当且仅当n=m,且对一切i,1in,Ai=Bi,并且R1和R2是相等的有序n重组集合,3.1.2 二元关系 最重要的关系是二元关系.本章主要讨论二元关系,今后术语“关系”都指二元关系.若非二元关系将用“三元”或“n元”一类术语指出. 二元关系有自己专用的记法和若干新术语 设 A=x1,x2,x7, B=y1,y2,y6 R=x3,y1,x3,y2,x4,y4,x6,y2,A到B的二元关系R可如图3.11那样形象地表示.x3,y1R,也可写成x3Ry1,称为中缀记法,读做x3和y1

6、有关系R.中缀记法常用来表示诸如“=”,“”,“”等关系,例如3,5,通常写作35.,图 3.11,A叫做关系R的前域,B叫做关系R的陪域 D(R)=xy(x,yR)叫做关系R的定义域 R(R)=yx(x,yR)叫做关系R的值域 关系是序偶的集合,对它可进行集合运算,运算结果定义一个新关系.设R和S是给定集合上的两个二元关系,则RS,RS,R-S, 等可分别定义如下: x(RS)y xRyxSy x(RS)y xRyxSy x(R-S)y xRyx$y x( )y xRy,例3平面上的几何图形是平面R2的子集,也是一种关系.设(参看图3.12) R1=x,yx,yR2x2+y29 R2=x,y

7、x,yR21x3) (0y3) R3=x,yx,yR2x2+y24 则 R1R2=x,yx,yR2(x2+y2 9(1x30y3),R1R3=x,yx,yR2(x2+y2 9x2+y24) R1-R3=x,yx,yR2(x2+y29 L (x2+y24) =x,yx,yR2L (x2+y24),图 3.12,3.1.3 关系矩阵和关系图 表达有限集合到有限集合的二元关系时,矩阵是一有力工具定义3.14给定集合A=a1,a2,am和B=b1,b2,bn,及一个A到B的二元关系R. 使.,rij=,1,如果aiRbj,0,如aiRbj,则称MR=rij矩阵是R的关系矩阵.,例4设A=a1,a2,B

8、=b1,b2,b3,R=a1,b1,a2,b1,a1,b3,a2,b2,则其关系矩阵为,b1 b2 b3 a1 1 0 1 a2 1 1 0,即,例5设A=1,2,3,4,A上的二元关系R=x,yxy,试求出关系矩阵 解R=4,1,4,2,4,3,3,1,3,2,2,1,图 3.13,例6设A=1,2,3,4,5,R=1,2,2,2,3,2,3,4,4,3,其图示如图3.13所示.图中结点5叫做孤立点利用关系R的图示,也可写出关系R.,3.1.4 关系的特性 在研究各种二元关系中,关系的某些特性扮演着重要角色,我们将定义这些特性,并给出它的图示和矩阵的特点 定义3.15设R是A上的二元关系,

9、(1)如果对A中每一x,xRx,那么R是自反的.即 A上的关系R是自反的 x(xAxRx) A=1,2,3,R1=1,1,2,2,3,3,1,2 是自反的.其关系图和关系矩阵的特点如图3.14所示.,图 3.14,(2)如果对A中每一x,xRx,那么R是反自反的.即 A上的关系R是反自反的 x(xAxRx) 例如,A=1,2,3,R2=2,1,1,3,3,2是反自反的,其关系图和关系矩阵的特点如图3.15所示.,图 3.15,有些关系既不是自反的,又不是反自反的(如图3.16),例如,R3=1,1,1,2,3,2,2,3,3,3,图 3.16,(3)如果对每一x,yA,xRy蕴含着yRx,那么

10、R是对称的.即A上的关系R是对称的 x y (xAyAxRyyRx) 例如,A=1,2,3,R4=1,2,2,1,1,3,3,1,1,1是对称的.其关系图和关系矩阵的特点如图3.17所示,图 3.17,(4)如果对每一x,yA,xRy,yRx蕴含着x=y,那么R是反对称的.即A上的关系R是反对称的 x y(xAyAxRyyRxx=y) 例如,A=1,2,3,R5=1,2,2,3是反对称的,其关系图和关系矩阵的特点如图3.18所示.,图 3.18,(5)如果对每一x,y,zA,xRy,yRz蕴含着xRz,那么R是传递的.即A上的关系R是传递的 x y z(xAyAz=AxRyyRzxRz) 例如

11、,A=1,2,3,4,R5=4,1,4,3,4,2,3,2,3,1,2,1是传递的.其关系图和关系矩阵如图3.110所示.,图 3.19,图 3.110,例7 (a)任何集合上的相等关系是自反的,对称的,反对称的和传递的,但不是反自反的 (b)整数集合I上,关系是自反的,反对称的,可传递的.但不是反自反的和对称的.关系是反自反的,反对称的,可传递的,但不是自反的和对崐称的 (c)设=a,b,试考察上的下列关系: (i)关系“与有同样长度”是自反的,对称的,可传递的,但不是反自反的和反对称的,(ii)“xRy”当且仅当x是y的真词头”,这里R是反自反的,反对称的,可传递的,但不是自反的和对称的

12、(iii)“xRy”当且仅当x的某真词头是y的一个真词尾”,这里R既不是自反的又不是反自反的,因为aaRaa,但abRab,既不是对称的也不是反对称的,并且不是传递的 (d)非空集合上的空关系是反自反的,对称的,反对称的和传递的,但不是自反的.空集合上的空关系则是自反的,反自反的,对称的,反对称的和可传递的,(e)基数大于1的集合上的全域关系是自反的,对称的和传递的,但不是反自反的和反对称的.例如图3.111所示的关系,图 3.111,3.2 关系的合成,3.2.1 关系的合成 前边已经指出,关系是序偶的集合,因此可以进行集合运算.本节介绍一种对关系来说,更为重要的运算合成运算.假设R1是A到

13、B的关系,R2是B到C的关系(参看图3.21).合成关系R1R2是一个A到C的关系:如果在关系图上,从aA到cC有一长度(路径中弧的条数)为2的路径,其第一条弧属于R1,其第二条弧属于R2,那么a,cR1R2.合成关系R1R2就是由a,c这样的序偶组成的集合.,图 3.21,定义3.21设R1是从A到B的关系,R2是从B到C的关系,从A到C的合成关系记为R1R2,定义为 R1R2=a,caAcCbbBa,b R1b,cR2 例1 (a)如果R1是关系“是的兄弟”,R2是关系“是的父亲”,那么R1R2是关系“是的叔伯”.R2R2是关系“是的祖父”,(b)给定集合A=1,2,3,4,B=2,3,4

14、,C=1,2,3,设R是A到B的关系;S是B到C的关系. R=x,yx+y=6=2,4,3,3,4,2 S=y,zy-z=1=2,1,3,2,4,3 则RS=2,3,3,2,4,1.如图3.22所示.,图 3.22,(c)设A=1,2,3,4,5,R和S都是A上二元关系.如果 R=1,2,3,4,2,2, S=4,2,2,5,3,1,1,3 则RS=1,5,3,2,2,5 SR=4,2,3,2,1,4 (RS)R=3,2 R(SR)=3,2 RR=1,2,2,2 SS=4,5,3,3,1,1,(d)设R是A到B的二元关系,IA,IB分别是A和B上的相等关系,则 IAR=RIB=R (e)如果关

15、系R的值域与关系S的定义域的交集是空集,则合成关系RS是空关系.下边介绍合成关系的性质,定理3.21设R1是从A到B的关系,R2和R3是从B到C的关系,R4是从C到D的关系,那么 (a) R1(R2R3)=R1R2R1R3 (b) R1(R2R3) R1R2R1R3 (c) (R2R3)R4=R2R4R3R4 (d) (R2R3)R4 R2R4R3R4 (a),(c),(d)部分的证明留作练习,我们仅证明(b)部分,证先证明公式.因为 a,cR1(R2R3) ba,bR1(b,cR2R3) ba,bR1(b,cR2b,cR3) b(a,bR1b,cR2)(a,bR1b,c R3) ba,bR1

16、b,cR2ba,bR1b,cR3 a,cR1R2a,cR1R3 a,cR1R2R1R3 即a,cR1(R2R3)a,cR1R2R1R3 所以,R1(R2R3)R1R2R1R3,再证包含可能是真包含.举反例证明 如果A=a,B=b1,b2,b3,C=c A到B的关系R1=a,b1,a,b2 B到C的关系R2=b1,c,b3,c B到C的关系R3=b2,c,b3,c 那么,R1(R2R3)= ,R1R2R1R3=a,c.此时R1( R2R3)R1R2R1R3.证毕,定理3.22 设R1,R2和R3分别是从A到B,B到C和C到D的关系,那么(R1R2)R3=R1(R2R3)证先证(R1R2)R3R1

17、(R2R3) 设a,d(R1R2)R3,那么对某cC,a,cR1R2和c,d崐R3.因为a,cR1R2,存在bB使a,bR1和b,cR2.因为b,cR2和c,dR3,得b,dR2R3,所以a,dR1(R2R3).这样,就证明了(R1R2)R3R1(R2R3).R1(R2R3)(R1R2)R3的证明是类似的,留给读者自证.上述证明也可用等价序列表达,3.2.2 关系R的幂 当R是A上的一个关系时,R可与自身合成任意次而形成A上的一个新关系.在这种情况下,RR常表示为R2,RRR表示为R3等等,我们能归纳地定义这一符号如下 定义3.22 设R是集合A上的二元关系,nN,那么R的n次幂记为Rn,定义

18、如下: (1) R0是A上的相等关系,R0=x,xxA (2) Rn+1=RnR,定理3.23设R是A上的二元关系,并设m和n是N的元素,那么 (a)RmRn=Rm+n (b)(Rm)n=Rmn 可用归纳法证明.请读者自证.,定理3.24设A=n,R是集合A上的一个关系,那么存在i和j使Ri=Rj而0ij 证A上的每一二元关系是AA的子集,因为AA=n2,(AA)= ,因此A上有 个不同关系.所以,R的不同的幂不会超过 个.但序列R0,R1, 有 +1项,因此R的这些幂中至少有两个是相等的.证毕,定理3.25设R是集合A上的一个二元关系.若存在i和j,ij,使Ri=Rj.记d=j-i,那么 (

19、a) 对所有k0,Ri+k=Rj+k (b) 对所有k,m0,Ri+md+k=Ri+k (c) 记S=R0,R1,R2,Rj-1,那么R的每一次幂是S的元素,即对nN,RnS,证(a)和(b)部分用归纳法证明,留作练习 对于(c),设nN,如果nj,那么根据S的定义,RnS.假设nj,那么我们能将n表示为i+md+k,这里kd,根据(b)部分,得Rn=Ri+k,因为i+kj,这证明了RnS. 定理中的i,j,在实用时宜取最小的非负整数,以保证S中无重复元素.,图 3.23,例2 设A=a,b,c,d,R=a,b,c,b, b,c,c,d,其关系图如图3.23所示,则 R0=a,a,b,b,c,

20、c,d,d R2=a,c,b,b,b,d,c,c R3=a,b,a,d,b,c,c,b,c,d R4=a,c,b,b,b,d,c,c 它们的关系图如图3.24所示,图 3.24,由于R4=R2,根据定理3.25(c),对所有nN,RnR0,R1,R2,R3,可见不必再算了.事实上易证R5=R3,R6=R4=R2,用归纳法可得R2n+1=R3和R2n=R2,这里n1,3.2.3 合成关系的矩阵表达 定理3.26设X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是X到Y的关系,MR=aij是mn矩阵,S是Y到Z的关系,MS=bij是np矩阵.则MRS=cij=MRMS,这里,证

21、因为如果存在某k使aik和bki都等于1,则cij=1.但aik和bkj都等于1意味着xiRyk和ykSzj.所以xi(RS)zj.可见如此求得的MRS确实表达了RS的关系.因此上述等式是正确的. 如果不仅存在一个k使aik和bki都是1,此时cij仍为1,只是从xi到zj不止一条长度为2的路径,但等式仍然正确.上段的论证,已隐含了不止一个k的情况. 本定理说明合成关系矩阵可用关系矩阵(布尔矩阵)的乘法表达.,例3设X=1,2,Y=a,b,c,Z=,R=1,a,1,b,2,c,S=a,b,则,图 3.25,定理3.27 关系矩阵的乘法是可结合的 证利用关系合成的可结合性证明. (MRMS)MT

22、 =MRSMT=M(RS)T=MR(ST)=MRMST =MR(MSMT). 不仅合成关系可用关系矩阵表达,而且关系的集合运算也可用关系矩阵表达.设R和S是X到Y上的二元关系,MR=aij,MS=bij,cij是运算后所得新关系之关系矩阵的元素,则,MRS=MRMS cij=aijbij MRS=MRMS cij=aijbij cij=L aij MR-S=MR cij=aij(L bij),3.3 关系上的闭包运算,3.3.1 逆关系 在讨论闭包运算时,要用到逆关系的概念,因此我们先介绍逆关系 定义3.31设R是从A到B的二元关系,关系R的逆(或叫R的逆关系)记为 ,是一从B到A的二元关系,

23、定义如下:,例1 (a) I上的关系 (b) 集合族上的关系的逆是关系 (c) 空关系的逆是空关系 (d) =BA,即AB的全域关系的逆等于BA的全域关系. 定理3.31设R是从A到B的关系,而S是从B到C 的关系,则,定理3.32 设R,R1和R2都是从A到B的二元关系,那么下列各式成立:,这里,表示,3.3.2 关系的闭包运算 关系的闭包运算是关系上的一元运算,它把给出的关系R扩充成一新关系R,使R具有一定的性质,且所进行的扩充又是最“节约”的定义3.32设R是A上的二元关系,R的自反(对称,传递)闭包是关系R,使 (i)R是自反的(对称的,传递的) (ii)RR (iii)对任何自反的(

24、对称的,传递的)关系R,如果 RR,那么RR,R的自反,对称和传递闭包分别记为r(R),s(R)和t(R).由定义可以看出,R的自反(对称,传递)闭包是含有R并且具有自反(对称,传递)性质的最小关系.如果R已经是自反的(对称的,传递的),那么,具有该性质并含有R的最小关系就是R自身.下一定理说明这一点. 定理3.34设R是集合A上的二元关系,那么 (a) R是自反的当且仅当r(R)=R (b) R是对称的当且仅当s(R)=R (c) R是传递的当且仅当t(R)=R,证 (a)如果R是自反的,那么R具有定义3.32对R所要求的性质,因此r(R)=R.反之,如果r(R)=R.那么,根据定义3.32

25、的性质(i),R是自反的. (b)和(c)的证明是类似的,略. 构造R的自反,对称和传递闭包的方法就是给R补充必要的序偶,使它具有所希望的特性.下面我们用关系图来说明如何实现这一点.,定理3.35 设R是集合A上的二元关系.那么,r(R)=RE(这里E是A上相等关系,在本节中均如此.) 证 设R =RE.显然,R 是自反的且RR.余下只需证明最小性,现假设R是A上的自反关系且RR.因R是自反的,所以RE,又RR,所以RRE=R.这样,定义3.32都满足.所以,R=r(R).证毕,定理3.37 设R是集合A上的二元关系,那么,证 证明分两部分,(1) (基础)从定义3.32第(ii)条,立即得到

26、Rt(R) (2) (归纳)假设Rnt(R),n1.设a,bRn+1.因为Rn+1=RnR,存在cA,使a,cRn和c,bR.根据归纳前提和基础步骤,a,ct(R)和c,bt(R).因为t(R)是传递的,得a,bt(R).这证明了Rn+1 t(R).,例2 (a)整数集合I上的关系的自反闭包是,对称闭包是关系,传递闭包是关系自身 (b)整数集合I上的关系的自反闭包是自身,对称闭包是全域关系,传递闭包是自身 (c)E的自反闭包,对称闭包和传递闭包都是E (d)的自反闭包是全域关系,对称闭包是,的传递闭包是全域关系 (e)空关系的自反闭包是相等关系,对称闭包和传递闭包是自身 (f)设R是I上的关系

27、,xRy当且仅当y=x+1,那么t(R)是关系,定理3.38设R是集合A上的二元关系,这里A有n个元素,那么 证 设x,yt(R),于是必存在最小的正整数k,使x,yRk.现证明kn.若不然,存在A的元素序列x=a0,a1,a2,ak-1,ak=y使xRa1,a1Ra2,ak-1Ry.因kn,a0,a1,ak中必有相同者,不妨设ai=aj,0ijk.于是 xRa1,a1Ra2,ai-1Rai,ajRaj+1,ak-1Ry 成立.即x,yRs,这里s=k-(j-i).但这与k是最小的假设矛盾,于是kn,又x,y是任意的,故定理得证,例3设A=a,b,c,d,R如图3.31(a)所示,则t(R)=

28、RR2R3R4,如图3.31(b)所示.(本例即是3.2 节例2.) 定理3.39 (a)如果R是自反的,那么s(R)和t(R)都是自反的 (b)如果R是对称的,那么r(R)和t(R)都是对称的 (c)如果R是传递的,那么r(R)是传递的,图 3.31,定理3.310 设R是集合A上的二元关系,那么 (a)rs(R)=sr(R) (b)rt(R)=tr(R) (c)ts(R) st(R),证,(b)注意到ER=RE=R和对一切nN,En=E,可得,于是,(c)不难证明如果R1R2,那么s(R1)s(R2)和t(R1) t(R2).现相继地应用这一结论于对称闭包的性质:s(R) R. 得 ts(

29、R) t(R)和sts(R) st(R),3.4 次序关系,3.4.1 偏序集合 定义3.41 如果集合A上的二元关系R是自反的,反对称的和传递的,那么称R为A上的偏序,称序偶A,R为偏序集合.,如果R是偏序,A,R常记为A, 是偏序符号,由于难以书写,通常写作,读做“小于或等于”,因为“小于或等于”也是一种偏序,故不会产生混乱.R是偏序时,aRb就记成ab. 如果R是集合A上的偏序,则 也是A上的偏序;如果用表示 ,可用表示R.A,和A,都是偏序集合,并互为对偶.,例1 (a)I, 是偏序集合,这里表示整数中的“小于或等于”关系 (b)(A), 是偏序集合,这里是集合间的包含关系 (c)A=

30、2,4,6,8,D代表整除关系,M代表整倍数关系,则 D=2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,8 M=2,2,4,4,6,6,8,8,4,2,6,2,8,2,8,4 A,D,A,M都是偏序集合,且互为对偶,图 3.41,例2 (a)P=1,2,3,4,P,的哈斯图为图3.42 (b)A=2,3,6,12,24,36,A,整除的哈斯图为图3.43 (c)A=1,2,12,A,整除的哈斯图为图3.44,图 3.42,图 3.43,图 3.44,定义3.42 设A,是一偏序集合,B是A的子集 (a)元素bB是B的最大元素,如果对每一元素xB,xb (b)元素bB是B的最小元素

31、,如果对每一元素xB,bx 例3考虑在偏序“整除”下整数1到6的集合,其哈斯图为图3.45 (a)如果B=1,2,3,6,那么1是B的最小元素,6是B的最大元素 (b)如果B=2,3,因为2和3互相不能整除,那么B没有最小元素和最大元素 (c)如果B=4,那么4是B的最大元素,也是B的最小元素,图 3.45,定理3.41 设A,是一偏序集合且BA,如果B有最大(最小)元素,那么它是唯一的证假设a和b都是B的最大元素,那么ab和ba.从的反对称性得到a=b.当a和b都是B的最小元素时,证明是类似的定义3.43设A,是一偏序集合,B是A的子集 (a) 如果bB,且B中不存在元素x,使bx且bx,那

32、么元素bB叫做B的极大元素. (b)如果bB,且B中不存在元素x,使bx且xb,那么元素bB叫做B的极小元素,定义3.44设A,是一偏序集合,B是A的子集 (a)如果对每一bB,ba,那么元素aA叫做B的上界;如果对每一bB,ab,那么元素aA叫做B的下界. (b)如果a是一上界并且对每一B的上界a有aa,那么元素aA叫做B的最小上界,记为lub;如果a是一下界并且对每一B的下界a有aa,那么元素aA叫做B的最大下界,记为glb .,例4 (a)考虑偏序集合1,1,1,0,0,1,0,0,这里按 a,bc,dacbd 规定,其哈斯图如图3.46 如果B=1,0,那么1,0是B的最小和最大元素,

33、也是B的极大和极小元素.B的上界是1,0和1,1,1,0是最小上界.B的下界是0,0和1,0,1,0是最大下界.,(b)考虑偏序集合I,设B=2iiN,那么B既没有最大元素和极大元素,也没有上界和最小上界.B的最小元素和极小元素是0,B的下界集合是iiIi0,0是最大下界. (c)考虑在偏序集合2,5,6,10,15,30,整除,其哈斯图如图3.47设B是全集合2,5,6,10,15,30,那么2和5都是B的极小元素,但B没有最小元素.集合B没有下界,所以没有最大下界.元素30是B的最大元素,极大元素,上界,最小上界.,图 3.46,图 3.47,定理3.42 如果A,是非空有限的偏序集合,则

34、A的极小(大)元素常存在最大下界和最小上界也可能存在或不存在,但如果它们存在,则是唯一的. 定理3.43设A,是偏序集合且B A, 如果B的最小上界(最大下界)存在,那么是唯一的.,下述定理描述了存在于诸特异元素之间的某些关系 定理3.44设A,是偏序集合,B是A的子集 (a)如果b是B的最大元素,那么b是B的极大元素 (b)如果b是B的最大元素,那么b是B的lub (c)如果b是B的一个上界且bB,那么b是B的最大元素 证明 可由最大元素,极大元素和lub的定义直接得出,故略去.另外,读者不难给出表达最小元素,极小元素和glb间关系的定理,3.4.2 拟序集合 定义3.45如果集合A上的二元

35、关系R是传递的和反自反的,那么R叫做A上的拟序.A,R称为拟序集合. 常借用符号表示拟序拟序是反对称的,虽然定义中没有明确指出,但容易证明这一点.因为如果xRy和yRx,由R的传递性得xRx,但这与R的反自反性矛盾,所以xRyyRx常假,于是 xRyyRxx=y 常真,即R是反对称的.,例5 (a) 实数集合中的是拟序关系 (b) 集合族中的真包含是拟序关系 拟序集合和偏序集合是紧密相关的,唯一区别是相等关系E.下述定理将说明这一点 定理3.45在集合A上, (a) 如果R是一拟序,那么r(R)=RE是偏序 (b) 如果R是一偏序,那么R-E是一拟序,3.4.3 线序集合和良序集合 如果是一偏

36、序,或ab或ba,我们说a和b是可比较的.偏序集合中的元素不一定都可比较,所以叫“偏”序.下面介绍的都是可比较的情况. 定义3.46在偏序集合A,中.如果每一a,bA,或者ab,或者ba.那么叫做A上的线序(或全序),这时的序偶A,叫做线序集合或链.,例6 (a)P=,a,a,b,a,b,c,P,是线序集合,其哈斯图如图3.48所示 (b)I,是线序集合,其哈斯图(不完全)如图3.49所示 (c)设S是区间套的集合0,a)aR+,则S,是线序集合 (d)1,2,3,6,整除不是线序集合;如果A是多于一个元素的集合,那崐么(A),不是线序集合.,图3.48 图3.49,定义3.47如果A上的二元

37、关系R是一线序,且A的每一非空子集都有一最小元素,那么R叫做A上的良序,序偶A,R叫做良序集合 定理3.46N,是良序集合 证我们必须证明N的每一非空子集S,在关系之下,都有一最小元素.因为S非空,所以在S中可以取一个数n,显然,S中所有不大于n的数形成非空集TS.如果T有最小数,那么这最小数就是S中的最小数,但从0到n只有n+1个自然数,于是T中所含的数最多是n+1个,所以T有最小数.因此定理成立.,例7 (a)每一有限线序集合是良序的 (b)线序集合I,不是良序集合,因为I的某些子集(诸如I自身)不包含最小元素 (c)关系是实数R的线序,但不是良序.例如子集A=(0,1无最小元素.如果A中

38、的a是最小元素,那么 也在A中,而 a且不相等.这与假设a是线序关系下A的最小元素矛盾,3.4.4 词典序和标准序 由已知的线序和良序集合可以诱导出新集合S上的线序和良序.常见的有以下几种方法 (1)首先,使集合S上的每个元素与集合N(也可选其它已知的良序或线序集合)的唯一不同的元素对应,然后应用N上的良序定义S上的良序R定义方法如下: 如果a,bS,且a对应于n1,b对应于n2,那么aRb n1n2,(2) 应用N上的良序定义出Nn上的良序 例如n=2时,N2上的次序关系可如下定义: a,bc,dac(a=cbd)N2,是良序集合.关系“严格小于”可如下定义:a,bc,da,bc,da,bc

39、,d类似地,应用I上的线序能定义出线序集合In, (3) 应用字母表上的线序,可定义出上的通常叫词典序的线序.,定义3.48设是一有限字母表,指定了字母表序(线序).如果x,y, (a)x是y的词头,或 (b)x=zu和y=zv,这里z*是x和y的最长公共词头,且在字母表序中u的第一个字符前于v的第一个字符,那么xy.叫做词典序 (4)由于N, 和有限线序集合都是良序集合,可应用它们定义出上的一个良序,通常叫标准序,定义3.49设是一有限字母表,指定了字母表序,x表示x的长度,如果x,y*, (a)xy,或. (b)x=y且在的词典序中x前于y.那么xy, 叫做标准序.,不论在词典序和标准序下

40、,的每一元素都有直接后继者.设=a,b,c且abc,x*.在标准序下 xa和xb的直接后继者分别是xb和xc, xc的直接后继者是ya,这里y是x的直接后继者.在词典序下x的直接后继者是xa在标准序下 xb和xc的直接前趋分别是xa和xb, xa的直接前趋是yc,这里y是x的直接前趋.在词典序下 xa的直接前趋是x,非a结尾的串都无直接前趋,例如b,ab,aab,但有无限个前趋,3.4.5 数学归纳法的推广 前章我们把数学归纳法第一,第二原理看作是自然数域上的一个推理规则,本小节我们把它推广到一般的良序集合对任一个自然数n,我们先取0,如果n0,取0的后继者1,如果n1,再取1的后继者2,如此

41、进行下去,最终会得出n. 给定一个良序集合,如果对它的任一元素x,我们先取该集合的最小元素m0,如果xm0,取m0的后继者m1,如果xm1,再取m1的后继者m2,如此以往,最终会得出x,那么就称这样的良序集合是“像自然数”的.,例 8 (a) 设=a,b,良序集合*,标准序是像自然数的.因为定长的串的个数有限,给定任一个串x,在x之前的串的个数有限,所以从开始,反复取后继者,终可得出x. (b)良序集合NN,不像自然数,这里按上一小节规定.因为有许多元素没有直接前趋,例如5,0就是这样,因而有无限个元素前于5,0,所以,从0,0开始,反复地取后继者,不可能取得5,0.,像自然数的良序集合,可以

42、应用数学归纳法第一原理.因为第一原理是建立在后继运算上,而这种良序集合的每一元素都可通过重复地取后继者得到,设m0是该良序集合S,的最小元素,S(x)是元素x的后继者,则推理规则如下:,这样,如果我们能证明m0有性质P,和当x有性质P时, 则S(x)有同样性质,那么我们能得出S的每一元素有性质P.,对不像自然数的良序集合,不能应用数学归纳法第一原理,因为这种良序集合的有些元素不能由后继运算得到.但对它可应用数学归纳法第二原理.第二原理是建立在良序集合上的,适用于一切良序集合.设S,是良序集合,表示-E(即xy表示xy且xy),则推理规则如下:,这样,若每一小于x的元素有性质P,如果我们能证明任

43、意元素x有性质P,那么我们能得出S的每一元素有性质P. 下面证明良序集合上这个推理规则是有效的 假设我们能证明前提,并假设T是S的子集,由S中没有性质P的所有元素组成.因为S是良序的,如果T ,那么T必有最小元素m;这得出对所有xm,P(x)是真.可是,前提断言如果对所有xm,P(x)是真,那么P(m)是真,导致矛盾,我们得出T必须是空.因此,第二原理结论xP(x)是真,这得出对任意良序集合S,数学归纳法第二原理是有效的推理规则 .,例9Q+,是线序集合.现说明在此线序集合中第二原理不是有效推理规则设谓词P(x)表示“x小于或等于5”. (i)当x5时, yyxP(y)是真,P(x)也真. 所以,(ii)当x5时, 由于x5,所以存在有理数y0,使5y0x.这样P(y0) 是假,因而,是真 综合(i)和(ii),得: 在论述域Q+上, x y(yxP(y)P(x)是真,但结论 x P(x)是假.这说明第二原理不能应用于线序集合Q+,是假,所以,3.5 等价关系和划分,3.5.1 等价关系 二元关系的另一重要类型是等价关系,其定义如下: 定义3.51如果集合A上的二元关系R是自反的,对称的和传递的,那么称R是等价关系设R是A上的等价关系,a,b,c是A的任意元素.如果aRb(即a,bR),通常我们记作ab,读做“a等价于b”.,定义3.52设k是一正整