等价关系与等价类

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3-10 等价关系与等价类,离散数学,复习,自反性,（ reflexive ）,定义：,设R为定义在集合A上的二元关系，如果,对于每个xA，,都有,R,即xRx，则称二元关系R是自反的。,对称性（ symmetric ）,定义：,设R为定义在集合A上的二元关系，如果对于每个x，yA，,每当R，就有R,，则称集合A上关系R是对称的。,传递性,（ transitive ）,定义:,设R为定义在集合A上的二元关系， 如果对于任意x，y，zA，,每当 R且 R，,就有, R,，称关系R在A上是传递的。,R,1,是对称的。,R,2,是自反的、对称的、传递的。,等价关系与等价类的基本概念,1,等价关系的基本性质,2,主要内容,商集与集合的划分,3,3,一、定义,定义1:,设R为定义在集合A上的一个关系，,若R是自反的，对称的和传递的,，则称R为集合A上的等价关系。,例如,平面上三角形集合中，三角形的相似关系；,同学集合A=a,b,c,d,e,f,g,A中的关系R：住在同一宿舍；,同性关系。,例1 设T1，2，3，4，,R1，1，1，4，4，1，,4，4，2，2，2，3，,3，2，3，3。,验证R是集合T上的等价关系。,例2 设A = 1, 2, 8 , 如下定义A上的关系R:,R = | x, y,A且xy（mod3) ,证明R为A上的等价关系。,证明:,x,A , 因为x-x=0=0,3,所以R;,x,y,A, 若x-y=3t(t为整数）, 则有: y-x=-3t,即 R;,x,y,z,A, 若x-y=3t, y-z=3s, 则有:,x-z=3(t+s),即 R.,关系图如下图所示.,等价类,定义2：,设R为集合A上的等价关系，对任意aA，集合,a,R,=x|x A,R,称为元素a关于R的等价类。,例2可求出三个不同的等价类,1,R,=4,R,=7,R,=1,4,7,2,R,=5,R,=8,R,=2,5,8,3,R,=6,R,=3,6,定义3:,集合A上的等价关系R，其等价类集合a,R,|a A称作A关于R的,商集(,quotient set),。记作A/R,(1) a a,R,(2),定理1:,设给定集合A上的等价关系R，对于a,bA，若R,iff a,R,=b,R,。,二、性质,(3)设R为集合A上的等价关系，则任意a,b A,若,R,则,证明,设集合A上的一个等价关系R，则a,R,是A的一个子集，则所有这样的子集可做成商集A/R,1、A/R=a,R,|a,A中,a,R,=A,2、 对任意a A，都有aRa，即aa,R，,即A中的每一个元素都属于一个分块。,3、A的每个元素只能属于一个分块,反证设ab,R,，ac,R,且b,R, c,R，,则bRa,cRa成立，所以有aRc,所以bRc，即b,R, c,R,所以A/R是A上对应于R的一个划分。,定理2：,集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。,三 商集与集合的划分,证明：,设集合A的一个划分SS1,S2Sm，现定义一个关系：aRb当且仅当a,b在同一个分块中。则R是一个等价关系。,、a与a在同一个分块中，则有aRa ，即自反性,、 a与b在同一个分块中，则b与a在同一个分块中，即若aRb，有bRa，故R是对称的。,、 a与b在同一个分块中， b与c在同一个分块中，而由划分的定义b只能属于且属于一个分块，故a与c必在同一分块中，即若有aRb,bRc则必有aRc，即传递性成立。,所以R是一个等价关系。SA/R,定理3,集合A的一个划分确定A的元素间的一个等价关系。,说明,等价关系,等价类,商集,划分,A上的等价关系与A的划分是一一对应的。,R1a,b,x,a,b=,R2=c,x,c=,R3= d,exd,e=,R=R1R2R3,例3A=a,b,c,d,e，,Sa,b,c,d,e，求由S确定的R,。,例4设A=a,b,c,d,e,R=a,a,a,b,a,c,b,b,b,a,b,c,c,c,c,a,c,b,d,d,d,e,e,e,e,d,其有向图如图所示,则R诱导的划分S=a,b,c,d,e.反之,若A的划分S=a,b,c,d,e,则所诱导的等价关系R=a,b,ca,b,cd,ed,e=a,a,a,b,a,c,b,b,b,a,b,c,c,c,c,a,c,b,d,d,d,e,e,e,e,d,证明,必要性：A/R1a,R1,|a A，A/R2 a,R2,|a A,R1R2，对任意a A, 有a,R1,x|x A,aR,1,x=x|x A,aR,2,x= a,R2,所以有a,R1,|a Aa,R2,|a A即有A/R1=A/R2,充分性：反之设a,R1,|a Aa,R2,|a A,对任意a,R1, A/R1则有c,R2, A/R2,使得a,R1,c,R2,所以, R1 a a,R1,b a,R1,a c,R2,b c,R2, R2,所以R1是R2的子集，同理可证R2也是R1的子集。,所以R1R2,定理4：设R1和R2为非空集合A上的等价,关系，则R1=R2当且仅当A/R1=A/R2。,