等价关系与等价类-集合与关系-离散数学

等价关系与等价类第1页等价关系是很重要的关系，它是我们遇到最多的关系，在分析离散结构中起到重要作用，与划分联系密切。知识点：等价关系定义、性质、证明等价类定义等价类与划分商集第2页一、等价关系1.定义3-10.1设R是集合A上的关系，若R是自反的、对称的和传递的，则称R是A上的等价关系。设R是一个等价关系，若x,yA，且x,yR，则称x等价于y。显然，若R是等价关系，则R=r(R)=s(R)=t(R)等价关系自反性对称性传递性第3页例3-10.1在全体中国人所组成的集合上定义的“同姓”关系三角形的相似关系非空集合上的完全关系“朋友”关系，“父子”关系整数集合上的“小于”关系是等价关系。是等价关系。是等价关系。不是等价关系。不是等价关系。第4页分析：R={x,y|x除以4与y除以4的余数相同}x,y∈Rx(mod4)=y(mod4)或x≡y(mod4)如：3(mod4)=7(mod4)3,7∈R7(mod4)=3(mod4)7,3∈R2(mod4)=6(mod4)2,6∈R6(mod4)=2(mod4)6,2∈R解：R={1,1,1,5,1,9,2,2,2,6,2,10,2,14,3,3,3,7,4,4,5,1,5,5,5,9,6,2,6,6,6,10,6,14,7,3,7,7,9,1,9,5,9,9,10,2,10,6,10,10,10,14,14,2,14,6,14,10,14,14}例3-10.2集合A={1,2,3,4,5,6,7,9,10,14}，R是A上的模4同余关系，试通过关系图说明R是等价关系。第5页关系图从图中可知：（1）R中每个结点都有自回路，即R是自反的；（2）R中两个结点x和y，若有从x指向y的边，则有y指向x的边，即R是对称的；（3）若有x指向y的边，y指向z的边，则有x指向z的边，即R是传递的。由（1）、（2）和（3）知，R是等价关系。159101426437第6页集合A={1,2,3,4,5,6,7,9,10,14}，R是A上的模4同余关系，试证明R是等价关系。证明：⑴证自反性：任取x∈A，(要证出x,xR)因x-x=0，0能被4整除，所以有x,x∈R，故R自反。⑵证对称性：任取x,y∈A，设x,y∈R，(要证出y,xR)由R定义得x-y能被4整除，即x-y=4n(n∈I)，y-x=-(x-y)=-4n=4(-n)，∵-n∈I，∴y,x∈R,所以R对称。⑶证传递性:任取x,y,z∈A,设x,y∈R,y,z∈R(要证出x,z∈R)由R定义得x-y=4m，y-z=4n(m,n∈I)x-z=(x-y)+(y-z)=4m+4n=4(m+n)，∵m+n∈I,所以x,z∈R,所以R传递。证毕。R是自反、对称和传递的，即R是等价关系。任意集合XI的模m同余关系，是一个等价关系。第7页等价关系R的有向图由若干个独立子图(R图的一部分)构成的，每个独立子图都是完全关系图。2、等价关系的有向图159101426437{1,5,9}{2,6,10,14}{3,7}{4}第8页R3,R4,R5是等价关系。A={1,2,3}，下面是A中的八个关系的关系图，判断哪些是等价关系。1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。333R2R1R3R4R5R6R7R8123第9页等价关系有向图等价类商集划分二元关系性质自反对称传递反对称反自反第10页二、等价类1、定义3-10.2:x的等价类R是A上的等价关系，对任何x∈A，集合[x]R称为由x生成的R等价类，简称x的等价类：[x]R={y|y∈A∧xRy}简化写法：y∈[x]RxRy讨论：（1）等价类[x]R是一个集合，且[x]RA。（2）[x]R中的元素是在等价关系R中，与x有等价关系R的所有元素组成的集合。（3）[x]RΦ，x∈[x]R。第11页总结：（1）集合中的10个元素都有一个等价类。（2）各等价类之间或者完全相等或者不相交。（3）所有等价类的并集就是A。二、等价类例3-10.2中，A={1,2,3,4,5,6,7,9,10,14}，R是A上的模4同余关系，求出由每个元素生成的R的等价类。R={1,1,1,5,1,9,2,2,2,6,2,10,2,14,3,3,3,7,4,4,5,1,5,5,5,9,6,2,6,6,6,10,6,14,7,3,7,7,9,1,9,5,9,9,10,2,10,6,10,10,10,14,14,2,14,6,14,10,14,14}=[5]R=[9]R=[6]R余数为1的等价类余数为2的等价类余数为3的等价类[1]R={1,5,9}[2]R={2,6,10,14}[3]R={3,7}[4]R={4}=[14]R=[10]R=[7]R余数为0的等价类第12页每个关系子图即为一个等价类，位于此子图中的元素的等价类相同，等于该子图中的所有元素构成的集合。159101426437[1]R=[5]R=[9]R={1,5,9}[2]R=[6]R=[10]R=[14]R={2,6,10,14}[3]R=[7]R={3,7}[4]R={4}第13页R是A上等价关系，任意x,y,z∈A⑴同一个等价类中的元素，彼此有等价关系R。即任意x,y∈[z]R，必有x,y∈R。⑵任意两个等价类[x]R、[y]R，要么[x]R=[y]R，要么[x]R∩[y]R=Φ。1)[x]R=[y]R，当且仅当x,y∈R。2)[x]R∩[y]R=Φ，当且仅当x,yR。(3)A中任何元素x必属于且仅属于一个等价类。(4)所有等价类的并集为A。2、等价类性质159101426437[1]R=[5]R=[9]R={1,5,9}[2]R=[6]R=[10]R=[14]R={2,6,10,14}[3]R=[7]R={3,7}[4]R={4}第14页R是A上等价关系，任意a,b,c∈A⑴同一个等价类中的元素，彼此有等价关系R。即任意x,y∈[z]R，必有x,y∈R。证明：任取x,y∈[z]R，由等价类定义得，z,x∈R，z,y∈R，由R的对称性得，x,z∈R，又由R的传递性得，x,y∈R。所以，同一个等价类中的元素，彼此有等价关系R。2、等价类性质的证明第15页(2)1)[x]R=[y]R当且仅当x,y∈R。证明：①设x,y∈R，证[x]R=[y]R。a)证[x]R[y]R设任何z∈[x]Rx,z∈Ry,x∈R（由x,y∈R和R的对称性得）y,z∈R（由y,x∈R、x,z∈R和R的传递性）z∈[y]R，所以[x]R[y]R。b)证[y]R[x]R采用类似[x]R[y]R的方法证[y]R[x]R。由a)和b)得[x]R=[y]R。②若[x]R=[y]R，证x,y∈R。由于有y,y∈R，所以y∈[y]R，由[x]R=[y]R，则y∈[x]R，即有x,y∈R。由①②可知[x]R=[y]R当且仅当x,y∈R。第16页⑵2)[x]R∩[y]R=Φ，当且仅当x,yR。证明:①设x,yR，证[x]R∩[y]R=Φ。反证法：假设[x]R∩[y]R≠Φ，则存在z∈[x]R∩[y]R，即z∈[x]R∧z∈[y]R，也即x,z∈R，y,z∈R，由y,z∈R和R的对称性得z,y∈R，又由x,z∈R、z,y∈R和R的传递性得x,y∈R，与x,yR矛盾。所以若x,yR，则[x]R∩[y]R=Φ②设[x]R∩[y]R=Φ，证x,yR。反证法：假设x,y∈R，则由等价类定义得y∈[x]R，又因为y,y∈R，所以y∈[y]R，所以y∈[x]R∩[y]R，与[x]R∩[y]R=Φ产生矛盾。所以若[x]R∩[y]R=Φ，则x,yR。由①②可知[x]R∩[y]R=Φ，当且仅当x,yR。第17页(3)A中任何元素x，x必属于且仅属于一个等价类。证明：A中任何元素x，由于有x,x∈R，所以x∈[x]R，若x∈[y]R，所以有y,x∈R。由性质(2)得[x]R=[y]R。(4)所有等价类的并集为A。即证明：①对任意x∈A，[x]RA，所以。②对任意x∈A，因R自反，所以x,x∈R，即x∈[x]R所以，即。由①和②得，即所有等价类的并集为A。第18页定义3-10.3R是A上等价关系，由R的所有等价类构成的集合，称为A关于R的商集。记作A/R。即A/R={[a]R|a∈A}例如A={1,2,3,4,5,6,7,9,10,14}，R上模4同余关系，则A/R={[1]R,[2]R,[3]R,[4]R}={{1,5,9},{2,6,10,14},{3,7},{4}}三、商集第19页A={1,2,3}，A上关系R1、R2、R3，如图所示。A/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}}A/R2={[1]R2,[2]R2}={{1},{2,3}}A/R3={[1]R3}={{1,2,3}}1。。。R21。。。R1。R3。。1232323例如第20页四、划分与等价关系等价关系集合的划分？？第21页证明：商集中的每一个元素是一个等价类。由等价类性质可得：1)因为A中每个元素都属于一个等价类。2)A/R中的任意两个等价类相交为空；3)所以所有等价类的并集必等于A。所以商集A/R是A的一个划分。1、由等价关系确定划分定理3-10.1:设R是集合A上的等价关系，则R的商集A/R为A的一个划分。第22页例：设A={a1,a2,……,an}(1)A集合中的全域关系，R1=A×A，是等价关系，[ai]R=A，|[ai]R|=|A|A按R1的商集A/R1={[x]R|xA},|A/R1|=1是A的一个最小划分。(2)A集合上的恒等关系IA，是等价关系，A/IA={[x]IA|xA}={[a1]IA,[a2]IA,……,[an]IA}，|A/IA|=n，是A的一个最大划分。例：A为全班同学的集合，|A|=n(1)同学关系R1是一个等价关系，A/R1={A}(2)指纹的相同关系R2是一个等价关系，A/R2={[x1]R2,[x2]R2,……,[xn]R2}。(3)同姓关系R3是一个等价关系；A/R3={[张]R3,[李]R3,……}。第23页2、由划分确定等价关系例如，A={1,2,3,4},S={{1,2},{3},{4}},S是A的一个划分，求A上一个等价关系R，使得A/R=S。2134R={1,2}×{1,2}∪{3}×{3}∪{4}×{4}={1,1,1,2,2,1,2,2,3,3,4,4}等价关系集合的划分A/R?第24页证明：假设S={S1,S2,...,Sn}是A的一个划分，构造S上的一个等价关系R:R=(S1×S1)∪(S2×S2)∪…∪(Sn×Sn)，下面证明R是等价关系。1)证R自反：即证x,x∈R？？？任取x∈A，因为S是X的划分，必存在SiS使xSi，于是x,x∈Si×Si，又因为Si×SiR，所以x,x∈R，即R是自反的。2)证R对称：由x,y∈R，证y,x∈R？？？任取x,y∈A，设x,y∈R，必存在SiS使得x,y∈Si×Si，于是y,xSi×Si，又因为Si×SiR，所以y,x∈R，即R是对称的。定理3-10.2：集合A的一个划分确定A上的一个等价关