7.6 等价关系与划分

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.6 等价关系与划分,1,等价关系是一类重要的关系。,定义7.15(等价关系),设,R,非空集合上的关系，如果,R,是自反的、对称的和传递的，则称,R,为,A,上的等价关系。,设,R,是一个等价关系，若,R,，,称,x,等价于,y,，,记作,x,y,。,例,设,A=1,2,3，R1，R2，R3,是,A,上的关系,R1=,R2=,，,R3=,2,例 设,A,为某班学生的集合，讨论下列关系是否为等价关系。,R1=|x, y,A x,与,y,同年生,R2=|x, y,A x,与,y,同姓,R3=|x, y,A x,的年龄比,y,小,解：,R1,是等价关系；,R2,是等价关系；,R3,不是等价关系；,3,如,tsr(R),必,为一个等价关系,例,A=1,2,3，A,上的关系,R=,tsr(R)=,通过闭包运算将任意的关系,R,构造成为一个等价关系,4,对,R,求三种闭包共有6种顺序，问每种顺序的运算结果是否一定为等价关系？,不一定。,由于对称闭包不一定保持关系的传递性，因此先求传递闭包后求对称闭包得到的关系不一定是等价关系,例,A=1,2,3，,A,上的关系,R=,str(R)=I,A,显然,str(R),不是等价关系,用闭包运算去构造等价关系时，传递闭包运算应该放在对称闭包运算的后面,5,例 设,A,N,，R=|x, y,Axy (mod 3),为,A,上的关系，其中,xy (mod 3),叫做,x,与,y,模3相等，其含义为,x,除以3的余数与,y,除以3的余数相等。证明,R,为,A,上的等价关系。,证明,:,x,A，,有,xx (mod 3),，即,R,，所以,R,是自反的。,x,y,A，,若,xy (mod 3)，,则有,yx (mod 3)。,所以,R,是对称的。,x,y,z,A,，若,xy (mod 3),，,yz (mod 3),，则有,xz (mod 3),。所以,R,是传递的。,综上,R,为,A,上的等价关系。,6,例：已知,A=P(X), C,X,x, y,A, ,R, xyC,。,证明,R,为,A,上的等价关系,.,证明：,（,1,）,x,A,，由于,xx=C,R,所以,R,是自反的。,（,2,）,x,y,A,，,R,xy,C,yx,C,R,所以,R,是对称的。,（,3,）,x,y,zA,，若R，R，,则有,xyC,，,yzC,。,xz=(xy)(yz)C,R.,所以,R,是传递的。,综上所证，,R,是,A,上的等价关系。,7,画出等价关系,R=|x,y,Axy(mod 3),的关系图,，,其中,A=1,2,8,。,不难看出，上述关系图被分为三个,分离（,互不连通）的部分。每部分中的数两两都有关系,(,模,3,相等,),，位于不同部分中的数之间则没有关系。,称每一部分中的顶点构成了一个,等价类,。,8,定义7.16（等价类）,设,R,为非空集合上的等价关系，,x,A,，,令,x,R,=y|y,AxRy,，,称,x,R,为,x,关于,R,的等价类，简称为,x,的等价类，简记为,x,。,说明：,x,的等价类是,A,中所有与,x,等价的元素构成的集合。,9,集合,A=1,2,8,上的,等价关系,R=|x, y,Axy（mod 3）,等价类是：,1=4=7=1，4，7,2=5=8=2，5，8,3=6=3，6,10,将模3的等价关系加以推广，可以得到整数集合,Z,上的模,n,等价关系。,对于任意的整数,x,和,y,，,定义模,n,相等关系,：,x,y,xy（mod n）,易证,是整数集合,Z,上的等价关系。,11,将,Z,中所有的整数根据它们除以,n,的余数分类如下：,余数为0的数，其形式为,nz，z,Z,余数为1的数，其形式为,nz+1，z,Z,余数为,n-1,的数，其形式为,nz+n-1，z,Z,以上构成了,n,个等价类：,i=n+i=2n+i=nz+i|z,Z，i=0,1,n-1,12,定理7.14（等价类的性质）,设,R,为非空集合,A,上的等价关系，则,（1）,x,是,A,的非空子集,（2）,x，y,A,，,如果,xRy,，,则,x=y,（3）,x，y,A,，,如果,xRy,，,则,x,与,y,不交,（4）,x|x,A =A,定理的含义：,（1）：任何等价类都是集合,A,的非空子集,（2）和（3）：在,A,中任何两个元素，它们的等价类相等或不相交，不能部分相交。,（4）：所有等价类的并集就是,A,（3）,和（4）：等价关系将,A,划分成若干个互不相交的子集,13,例集合,A=1,2,8,上的等价关系,R=|x, y,Axy（mod 3）,等价类是,1, 4, 7,、2, 5, 8,、3, 6,14,定义7.17（商集）,设,R,为非空集合,A,上的等价关系，以,R,的所有等价类为元素的集合叫做,A,在,R,下的商集，记作,A/R,，,即,A/R=x,R,|x,A ,例 集合,A=1,2,8,上的等价关系,R=|x, y,Axy（mod 3）,等价类是,1, 4, 7,、2, 5, 8,、3, 6,。,所以,A,在,R,下的商集为,1, 4, 7, 2, 5, 8, 3, 6,。,A,在,R,下的商集也可写成,1, 2, 3,。,整数集,Z,在模,n,等价关系下的商集是,nz+i|z,Z | i=0,1,n-1,或,0, 1, ., n-1,15,定义7.18（划分）,设,A,为非空集合，若,A,的子集族,（,P(A),，,是,A,的子集构成的集合,）,满足以下的条件：,（1）,（2）,x,y（x，y,x,y x,y=,）,即,中任意两个集合不相交,（3）,=A,，,即,中所有集合的并集等于,A,则称,是,A,的一个,划分,，称,中的元素为,A,的划分块,16,例,设,A=a,b,c,d,，,给定,1,2,3,4,5,6,如下，判别它们是否为,A,的划分。,1,= a，b，c ， d ,2,= a，b ， c ， d ,3,= a ， a，b，c，d ,4,= a，b ， c ,5,=,， a，b ， c，d ,6,= a， a ， b，c，d ,其中,1,2,是,A,的划分,，,3,4,5,6,不是,A,的划分,17,集合,A,的等价关系与集合,A,的划分一一对应,（1）,每个,A,上的等价关系所产生的商集是一个划分,（2）,每个,A,的划分,决定一个,A,上等价关系,R,通过,A,的一个划分来确定等价关系,R,的方法是：对任意的,x,y,A,，,R,当且仅当,x,和,y,在,的同一划分块中。,例,A=a,b,c,d,的一个划分为,=a,b,c,d,则,对应的等价关系为：,R=, I,A,18,a b,c,d,a b,d,c,划分的图形表示,一般用“圆”来表示一个划分，将圆划分成若干份来表示划分块。,例如:,1= a，b，c ， d ,2= a，b ， c ， d ,19,例7.18,给出,A=1，2，3,上所有的等价关系,解：,利用图形对,A,进行划分。,这些划分与,A,上的等价关系之间是一一对应的：,1,：,R1,对应于全域关系,E,A,2,：R2=,I,A,3,；R3=,I,A,4,：R4=,I,A,5,：,R5,对应于恒等关系,I,A,20,思考题,求出四元集上可定义多少个不同的等价关系?,21,