《等价关系与划分课件》由会员分享，可在线阅读，更多相关《等价关系与划分课件（26页珍藏版）》请在金锄头文库上搜索。
1、例例：设设整整数数集集I上上的的模模2同同余余关关系系为为R,这这是是I上的等价关系。上的等价关系。在在R下下，把把I中中所所有有与与0有有关关系系即即与与0等等价价的整数划分为一类，记为的整数划分为一类，记为E；与与1等价的所有整数划分为一类，记为等价的所有整数划分为一类，记为O集集合合I中中的的元元素素或或者者属属于于E，或或者者属属于于O,且它们互不相交。且它们互不相交。由关系由关系R把把I分为两类：分为两类：E和和O，这就是这就是I的一个划分。的一个划分。三、等价关系与划分三、等价关系与划分定定义义 2.14：设设R是是A上上的的等等价价关关系系, 对对于于每每个个a A,与与a等等价
2、价的的元元素素全全体体所所组组成成的的集集合合称称为为由由a生生成成的的关关于于R的的等等价价类类,记记为为aR, 即即aR=x|x A,xRa,a称称为为该该等等价价类的代表元。类的代表元。在在不不会会引引起起误误解解的的情情况况下下,可可把把aR简简记记为为a。定定义义 2.15：设设R是是A上上的的一一个个等等价价关关系系, 关关于于R的的等等价价类类全全体体所所组组成成的的集集合合族族称称为为A上上 关关 于于 R的的 商商 集集 ,记记 为为 A/R, 即即A/R=a|a A。例例：整整数数集集I上上的的模模2同同余余关关系系R，其其等等价价类类为为0,1。其其中中0=,-4,-2,
3、0,2,4,=2=4=-2=-4=1=,-3,-1,1,3,=3=-1=-3=因此因此A/R=0,1例例:整整数数集集I上上的的模模n同同余余关关系系是是I上上的的等等价价关关系系。I上关于上关于R的等价类为：的等价类为：0=,-2n,-n,0,n,2n,1=,-2n+1,-n+1,1,n+1,2n+1,n-1=,-n-1,-1,n-1,2n-1,3n-1,这些类又称这些类又称I上模上模n同余类。同余类。I上关于上关于R的商集的商集I/R=0,1,n-1 定理定理 2.13：设：设R是是A上的等价关系上的等价关系, 则则(1)对任一对任一a A,有有a a;(2)若若aRb, 则则a=b;(3
4、)对对 a,b A, 如如 果果 (a,b) R,则则ab=;此定理的此定理的(1)说明说明A中每个元素所产生的等价类是非空的中每个元素所产生的等价类是非空的定定理理的的(2)、(3)说说明明：互互相相等等价价的的元元素素属属于于同同一一个个等等价价类类，而不等价的元素其所对应的等价类之间没有公共元素而不等价的元素其所对应的等价类之间没有公共元素定定理理的的(4)说说明明：A上上等等价价关关系系R所所对对应应的的等等价价类类的的并并就就等等于于A.由由此此定定理理说说明明A上上等等价价关关系系R所所对对应应的的等等价价类类集集合合是是A的的一一个划分。个划分。该定理告诉我们，给定一个等价关系就
5、唯一确定一个划分。该定理告诉我们，给定一个等价关系就唯一确定一个划分。 证明：证明：(1)对任一对任一a A，因为因为R是是A上的上的等价关系，所以有等价关系，所以有aRa(R自反自反)，则，则a a。(2)对对a,b A, aRb,分分别别证证明明a b，b a。对任意对任意x a(目标证明目标证明x b，即即xRb)。下面证明下面证明b a对任意对任意x b(目标证明目标证明x a，即即xRa)。(3)对对a,b A, 如果如果(a,b) R,则则ab=采用反证法。假设采用反证法。假设ab，则至则至少存在少存在x ab。例例 ： 设设 A=1,2,3,4， R=(1,1),(2,2), (
6、3,3),(4,4),(1,3),(2,4),(3,1), (4,2)为为等等价价关关系。系。其等价类为其等价类为1=1,3 2=2,4 3=1,3 4=2,4划分划分 =1,2前前面面是是给给定定等等价价关关系系唯唯一一确确定定划划分分，反反过过来来，给给定定一一个个划划分分，也也可可唯唯一一确确定定一一个等价关系。个等价关系。设设非非空空集集A上上划划分分 =A1,A2,An，定定义义A上上二二元元关关系系R：aRb当当且且仅仅当当存存在在Ai,使使得得a,b Ai。即即R=(A1 A1)(A2 A2)(An An)容易证明容易证明R是等价关系。是等价关系。定定理理2.14：集集合合A上上
7、的的任任一一划划分分可可以以确确定定A上的一个等价关系上的一个等价关系R。例例：设设A=a,b,c的的一一个个划划分分 =a,b,c,由由 确定确定A上的一个等价关系上的一个等价关系R：R=(a,b a,b)(c c)=(a,a),(a,b),(b,a),(b,b), (c,c)定定理理 2.15:设设R1和和R2是是A上上的的等等价价关关系系,R1=R2当且仅当当且仅当A/R1=A/R2。定定理理 2.13 和和定定理理 2.15 说说明明集集合合A上上的的任任一一等等价关系可以唯一地确定价关系可以唯一地确定A的一个划分。的一个划分。定定理理2.14和和定定理理 2.15说说明明集集合合A的
8、的任任一一划划分分可以唯一地确定可以唯一地确定A上的一个等价关系。上的一个等价关系。集集合合A上上给给出出一一个个划划分分和和给给出出一一个个等等价价关关系系是没有什么实质区别的。是没有什么实质区别的。设设集集合合A上上的的等等价价关关系系为为R1和和R2,它它们们通通过过并并和交运算而得到的关系是不是等价关系和交运算而得到的关系是不是等价关系?若若是是,其其对对应应的的划划分分与与原原来来的的两两个个划划分分有有何何联系。联系。四、划分的积与和四、划分的积与和1.划分的积划分的积定定理理 2.16：设设R1和和R2是是A上上的的等等价价关关系系,则则R1R2是是A上的等价关系。上的等价关系。
9、定定义义 2.16：设设R1和和R2是是A上上的的等等价价关关系系, 由由R1和和R2确确定定的的A的的划划分分分分别别为为 1和和 2,A上上的的等等价价关关系系R1R2所所确确定定的的A的的划划分分,称称为为 1与与 2划分的积划分的积,记为记为 1 2。定定义义 2.17：设设 和和 是是A的的划划分分, 若若 的的每每一一块块包包含含在在 的的一一块块中中, 称称 细细分分 ,或或称称 加细加细 。例例 ： =1,2,3,4， =1,2, 3,4因因 为为 1 1,2， 2 1,2，3,4 3,4，所以所以 细分细分 若若 细细分分 ,则则与与它它们们对对应应的的二二元元关关系系R和和
10、R它们之间有何联系？它们之间有何联系？(1)若若 细细分分 ,则则与与它它们们对对应应的的二二元元关关系系R和和R满足满足R R。证证 明明 ： 对对 任任 意意 (a,b) R， 目目 标标 是是(a,b) R(2)若若R R，是否有是否有 细分细分 ？证明：对任意证明：对任意S,目标是目标是SS S定理定理 2.17：设：设 , 是是A的划分的划分,它们确定它们确定A上的等价关系分别为上的等价关系分别为R,R,则则 细分细分 当且仅当当且仅当R R。定理定理 2.18：设：设 1, 2是是A的划分的划分,则则(1) 1 2细分细分 1与与 2。(2)设设 是是A的的划划分分,若若 细细分分
11、 1与与 2,则则 细细分分 1 2。证证明明：(1)设设 1和和 2分分别别对对应应的的A上上关关系系是是R1和和R2，则则 1 2对应的关系为对应的关系为R1R2。(2) 设设 对对应应A上上关关系系是是R， 1和和 2分分别别对对应应的的A上上关关系系是是R1和和R2，则则 1 2对对应应的的关关系系为为R1R2。2.划分的和划分的和设设集集合合A上上的的等等价价关关系系为为R1和和R2,容容易易证证明明R1R2是是A上上的的自自反反和和对对称称关关系系,但但不不是是A上上的的等等价价关关系系。然然而而R1R2的的传传递递闭闭包是包是A上的等价关系。上的等价关系。定定理理 2.19:设设
12、R1和和R2是是集集合合A上上的的等等价价关关系系,则则(R1R2)+是是A上的等价关系。上的等价关系。定定义义 2.18:设设R1和和R2是是A上上的的等等价价关关系系, R1和和R2确确定定A的的划划分分分分别别为为 1和和 2。 A上上的的等等价价关关系系(R1R2)+所所确确定定A的的划划分分称称为为 1与与 2划分的和划分的和,记为记为 1+ 2。定理定理 2.20：设：设 1, 2是是A的划分的划分, 则则(1) 1与与 2细分细分 1+ 2；(2)设设 是是A的的划划分分,若若 1与与 2细细分分 ,则则 1+ 2细分细分 。证证明明：(1)设设 1和和 2分分别别对对应应的的A
13、上上关关系系是是 R1和和 R2， 则则 1+ 2对对 应应 的的 关关 系系 为为(R1R2)+ 。(2) 设设 对应对应A上关系是上关系是R， 1和和 2分分别对应的别对应的A上关系是上关系是R1和和R2，则则 1+ 2对应的关系为对应的关系为(R1R2)+ 。2.7 次序关系次序关系集集合合中中还还有有一一种种重重要要的的关关系系：次次序序关关系系。它它可可用用来来比比较较集集合合中中元元素素的的次次序序,其其中中最最常用的是偏序关系和全序关系。常用的是偏序关系和全序关系。1.偏序关系偏序关系定定义义 2.19,2.20:设设R是是集集合合A上上的的二二元元关关系系, 若若R是是自自反反
14、的的, 反反对对称称的的和和传传递递的的, 则则称称R是是A上上的的偏偏序序关关系系。又又记记为为(注注意意,此此符符号号在在这这里里并并不不意意味味着着小小于于或或等等于于)。若若集集合合A具具有有偏偏序序关关系系R,则则称称A为为偏偏序序集集,记记为为(A,R)。实数集实数集R R上的小于或等于关系上的小于或等于关系；正整数集正整数集Z Z+ +上的整除关系；上的整除关系；集合集合A A的幂集的幂集P(A)(A)上的包含关系上的包含关系 。由由于于它它们们都都是是偏偏序序关关系系，因因此此( (R,) R,) (Z(Z+ +,|), (,|), (P(A),(A), ) )都是偏序集。都是
15、偏序集。偏序集必须有一个具体给定的偏序集必须有一个具体给定的偏序关系偏序关系例例：A=1,2,A=1,2,P(A)=(A)=,1,2,1,2,1,2,1,2,则则 A A的幂集的幂集P(A)(A)上的包含关系上的包含关系(, ,),(),(,1),(,1),(,2),(,2),(,1,2), ,1,2), (1,1),(1,1,2),(2,2), (1,1),(1,1,2),(2,2), (2,1,2),(1,2,1,2)(2,1,2),(1,2,1,2)定定义义：对对于于集集合合A上上的的偏偏序序关关系系R, 如如果果A中中两个元素两个元素a,b有有aRb,则称则称a与与b是可比较的。是可比
16、较的。在在上上例例中中，与与,1,2与与1,2都都是是可可以以比比较较的的，而而1与与2无无包包含含关关系系，故故不不可比较可比较由由此此可可见见：偏偏序序集集合合中中任任意意两两个个元元素素不不一一定可比较的。定可比较的。但但对对于于实实数数集集上上的的小小于于或或等等于于关关系系，对对任任意意两两个个实实数数x,y,或或者者xy,或或者者yx，必必有有一个成立，故一个成立，故x和和y是可以比较的。是可以比较的。全序关系全序关系定定义义 2.22,2.23：设设是是集集合合A上上的的二二元元关关系系, 如如果果对对于于A中中任任意意两两个个元元素素a,b A,必必有有ab或或ba, 则则称称
17、是是A上上的的全全序序关关系系(或或称称线线性性次次序序关关系系)。而而该该集集合合称称为为全全序序集集或或线性次序集线性次序集,记为记为(A,)。整整数数集集I上上的的小小于于或或等等于于关关系系是是全全序序关关系系, 但但I上上的的整整除除关关系系/不不是是全全序序关关系系。而而前前面面给给出出的的幂幂集集P(A)上上的的 关关系系也也不不是是全全序关系。序关系。2Hasse图图偏偏序序集集(A,R)可可以以通通过过图图形形表表示示, 该该图图叫叫哈哈斯图。是对关系图的简化。斯图。是对关系图的简化。(1)由由于于偏偏序序关关系系是是自自反反的的，即即对对每每个个元元素素a,都有都有aRa，
18、因此在图上省去自环因此在图上省去自环(2)由由于于偏偏序序关关系系是是传传递递的的，即即若若有有aRb, bRc则必有则必有aRc,因此省去因此省去a与与c之间的连线之间的连线(3)对对于于aRb,规规定定b在在a的的上上方方，则则可可省省去去箭箭头。头。这样的图称为哈斯图。这样的图称为哈斯图。A=1,2,A=1,2,画画出出A A的的幂幂集集P(A)(A)上上的的包包含含关关系的哈斯图系的哈斯图P(A)=(A)=,1,2,1,2,1,2,1,2例例A=2, 3, 6, 12, 24, 36, 画画出出偏偏序序集集(A, /)的哈斯图。的哈斯图。设设A上上的的小小于于等等于于关关系系,A=1,
19、 2, 3, 4, 5, 6,画出偏序集画出偏序集(A,)的哈斯图。的哈斯图。3.拟序关系拟序关系定定义义 2.21:集集合合A上上的的二二元元关关系系R是是反反自自反反的的和和传传递递的的, 称称R为为A上上的的拟拟序序关关系系。称称(A, R)为为拟拟序序集集,或或记记为为(A,)(注注意意, 此此符号符号在这里也不意味着小于在这里也不意味着小于)。常常见见的的拟拟序序关关系系有有：实实数数集集R上上的的小小于于关关系系；集集合合A的的幂幂集集P(A)上上的的真真包包含含关关系系 。定定理理 2.22:集集合合A上上的的二二元元关关系系R是是拟拟序序的的, 则则R必为反对称的。必为反对称的。证明：假设证明：假设R不是反对称的不是反对称的由由此此定定理理, 我我们们可可知知拟拟序序关关系系实实际际上上是是满满足足反自反的反自反的, 反对称的和传递的。反对称的和传递的。定理定理 2.23：设：设R是是A上的二元关系上的二元关系,则则(1)若若R是是A上上的的拟拟序序关关系系, 则则r(R)=RIA是是A上的偏序关系。上的偏序关系。(2)若若R是是A上上的的偏偏序序关关系系, 则则R-IA是是A上上的的拟序关系。拟序关系。作业作业:p42 19,25(2),26,28,35,38, 39
