等价关系与等价类.ppt

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上是传递的。,R1 是对称的。,R2 是自反的、对称的、传递的。,主要内容,一、定义,定义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, yA且xy（mod3) 证明R为A上的等价关系。,证明: xA , 因为x-x=0=03,所以R; x,yA, 若x-y=3t(t为整数）, 则有: y-x=-3t,即 R; x,y,zA, 若x-y=3t, y-z=3s, 则有: x-z=3(t+s),即 R.,关系图如下图所示.,等价类,定义2：设R为集合A上的等价关系，对任意aA，集合 aR=x|x A,R 称为元素a关于R的等价类。,例2可求出三个不同的等价类,1R=4R=7R=1,4,7 2R=5R=8R=2,5,8 3R=6R=3,6,定义3:集合A上的等价关系R，其等价类集合aR|a A称作A关于R的商集(quotient set) 。记作A/R,(1) a aR (2)定理1:设给定集合A上的等价关系R，对于a,bA，若R,iff aR=bR。,二、性质,(3)设R为集合A上的等价关系，则任意a,b A,若,R,则,证明 设集合A上的一个等价关系R，则aR是A的一个子集，则所有这样的子集可做成商集A/R 1、A/R=aR|a A中, aR=A 2、 对任意a A，都有aRa，即aaR，即A中的每一个元素都属于一个分块。 3、A的每个元素只能属于一个分块 反证设abR ，acR,且bR cR，则bRa,cRa成立，所以有aRc,所以bRc，即bR cR 所以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,bxa,b= R2=c xc= R3= d,exd,e= R=R1R2R3,例3 A=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/R1aR1|a A，A/R2 aR2|a A R1R2，对任意a A, 有aR1x|x A,aR1x=x|x A,aR2x= aR2 所以有aR1|a AaR2|a A即有A/R1=A/R2 充分性：反之设aR1|a AaR2|a A 对任意aR1 A/R1则有cR2 A/R2,使得aR1cR2 所以 R1 a aR1 b