等价关系与等价类幻灯片.ppt

3-10等价关系与等价类,离散数学,1,复习,自反性（reflexive）定义：设R为定义在集合A上的二元关系，如果对于每个xA，都有R,即xRx，则称二元关系R是自反的。,2,对称性（symmetric）,定义：设R为定义在集合A上的二元关系，如果对于每个x，yA，每当R，就有R，则称集合A上关系R是对称的。,3,传递性（transitive）,定义:设R为定义在集合A上的二元关系，如果对于任意x，y，zA，每当R且R，就有R，称关系R在A上是传递的。,4,R1是对称的。,5,R2是自反的、对称的、传递的。,6,主要内容,7,一、定义,定义1:设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为集合A上的等价关系。,8,例如,平面上三角形集合中，三角形的相似关系；同学集合A=a,b,c,d,e,f,g,A中的关系R：住在同一宿舍；同性关系。,9,例1设T1，2，3，4，,R1，1，1，4，4，1，4，4，2，2，2，3，3，2，3，3。验证R是集合T上的等价关系。,10,11,例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.,12,关系图如下图所示.,13,等价类,定义2：设R为集合A上的等价关系，对任意aA，集合aR=x|xA,R称为元素a关于R的等价类。,14,例2可求出三个不同的等价类,1R=4R=7R=1,4,72R=5R=8R=2,5,83R=6R=3,6,15,定义3:集合A上的等价关系R，其等价类集合aR|aA称作A关于R的商集(quotientset)。记作A/R,16,(1)aaR(2)定理1:设给定集合A上的等价关系R，对于a,bA，若R,iffaR=bR。,二、性质,17,(3)设R为集合A上的等价关系，则任意a,bA,若,R,则,18,证明设集合A上的一个等价关系R，则aR是A的一个子集，则所有这样的子集可做成商集A/R1、A/R=aR|aA中,aR=A2、对任意aA，都有aRa，即aaR，即A中的每一个元素都属于一个分块。3、A的每个元素只能属于一个分块反证设abR，acR,且bRcR，则bRa,cRa成立，所以有aRc,所以bRc，即bRcR所以A/R是A上对应于R的一个划分。,定理2：集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。,三商集与集合的划分,19,证明：设集合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的元素间的一个等价关系。,20,说明,等价关系等价类商集划分A上的等价关系与A的划分是一一对应的。,21,R1a,bxa,b=R2=cxc=R3=d,exd,e=R=R1R2R3,例3A=a,b,c,d,e，Sa,b,c,d,e，求由S确定的R。,22,例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,23,证明必要性：A/R1aR1|aA，A/R2aR2|aAR1R2，对任意aA,有aR1x|xA,aR1x=x|xA,aR2x=aR2所以有aR1|aAaR2|aA即有A/R1=A/R2充分性：反之设aR1|aAaR2|aA对任意aR1A/R1则有cR2A/R2,使得aR1cR2所以R1aaR