《等价关系与划分》PPT课件.ppt

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