这是I上的等价关系在R下,把I中所有与0有关系即与0等

1、 例：设整数集例：设整数集I上的模上的模2同余关系为同余关系为R,这这是是I上的等价关系。上的等价关系。 在在R下，把下，把I中所有与中所有与0有关系即与有关系即与0等价等价的整数划分为一类，记为的整数划分为一类，记为E； 与与1等价的所有整数划分为一类，记为等价的所有整数划分为一类，记为O 集合集合I中的元素或者属于中的元素或者属于E，或者属于或者属于O,且它们互不相交。且它们互不相交。 由关系由关系R把把I分为两类：分为两类：E和和O， 这就是这就是I的一个划分。的一个划分。 三、等价关系与划分三、等价关系与划分 定义定义 2.14：设：设R是是A上的等价关系上的等价关系, 对于对于每个每

2、个a A,与与a等价的元素全体所组成的集等价的元素全体所组成的集合称为由合称为由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，

3、其等价类为其等价类为0,1。 其中其中0=,-4,-2,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上的等价关系上的等价关系, 则则

4、 (1)对任一对任一a A,有有a a; (2)若若aRb, 则则a=b; (3)对对a,b A, 如果如果(a,b) R,则则ab=;AaAa)4(此定理的此定理的(1)说明说明A中每个元素所产生的等价类是非空的中每个元素所产生的等价类是非空的定理的定理的(2)、(3)说明：互相等价的元素属于同一个等价类，说明：互相等价的元素属于同一个等价类，而不等价的元素其所对应的等价类之间没有公共元素而不等价的元素其所对应的等价类之间没有公共元素定理的定理的(4)说明：说明：A上等价关系上等价关系R所对应的等价类的并就等于所对应的等价类的并就等于A.由此定理说明由此定理说明A上等价关系上等价关系R所对应

5、的等价类集合是所对应的等价类集合是A的的一个划分。一个划分。该定理告诉我们，给定一个等价关系就唯一确定一个划分。该定理告诉我们，给定一个等价关系就唯一确定一个划分。 证明：证明：(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= 采用反证法。假设采用反证法。假设

6、ab，则至少存则至少存在在x ab。AaAa)4(AaxAaaxAa, 使得必存在某个对任意的AaAa所以AaaxxAx,有又对任意的AaaA所以AaAa因此有 例：设例：设A=1,2,3,4，R=(1,1),(2,2), (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上划分上划

7、分 =A1,A2,An，定义定义A上二元关系上二元关系R：aRb当且仅当存在当且仅当存在Ai,使得使得a,b Ai。 即即R=(A1 A1)(A2 A2)(An An) 容易证明容易证明R是等价关系。是等价关系。 定理定理2.14：集合：集合A上的任一划分可以确定上的任一划分可以确定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上的等价关系上的等价关

8、系,R1=R2当且仅当当且仅当A/R1=A/R2。 定理定理 2.13 和定理和定理 2.15 说明集合说明集合A上的任一等上的任一等价关系可以唯一地确定价关系可以唯一地确定A的一个划分。的一个划分。 定理定理2.14和定理和定理 2.15说明集合说明集合A的任一划分的任一划分可以唯一地确定可以唯一地确定A上的一个等价关系。上的一个等价关系。 集合集合A上给出一个划分和给出一个等价关系上给出一个划分和给出一个等价关系是没有什么实质区别的。是没有什么实质区别的。 设集合设集合A上的等价关系为上的等价关系为R1和和R2,它们通过并它们通过并和交运算而得到的关系是不是等价关系和交运算而得到的关系是不

9、是等价关系? 若是若是,其对应的划分与原来的两个划分有何联其对应的划分与原来的两个划分有何联系。系。 四、划分的积与和四、划分的积与和 1.划分的积划分的积 定理定理 2.16：设：设R1和和R2是是A上的等价关系上的等价关系,则则R1R2是是A上的等价关系。上的等价关系。 定义定义 2.16：设：设R1和和R2是是A上的等价关系上的等价关系, 由由R1和和R2确定的确定的A的划分分别为的划分分别为 1和和 2,A上上的等价关系的等价关系R1R2所确定的所确定的A的划分的划分,称为称为 1与与 2划分的积划分的积,记为记为 1 2。 定义定义 2.17：设：设 和和 是是A的划分的划分, 若若

10、 的每的每一块包含在一块包含在 的一块中的一块中, 称称 细分细分 ,或称或称 加细加细 。 例：例： =1,2,3,4， =1,2, 3,4 因为因为1 1,2，2 1,2， 3,4 3,4， 所以所以 细分细分 若若 细分细分 ,则与它们对应的二元关系则与它们对应的二元关系R和和R它们之间有何联系？它们之间有何联系？ (1)若若 细分细分 ,则与它们对应的二元关系则与它们对应的二元关系R和和R满足满足R R。 证明：对任意证明：对任意(a,b) R，目标是目标是(a,b) R (2)若若R R，是否有是否有 细分细分 ？ 证明：对任意证明：对任意S,目标是目标是S S S 定理定理 2.1

11、7：设：设 , 是是A的划分的划分,它们确定它们确定A上的等价关系分别为上的等价关系分别为R,R,则则 细分细分 当当且仅当且仅当R R。 定理定理 2.18：设：设 1, 2是是A的划分的划分,则则 (1) 1 2细分细分 1与与 2。 (2)设设 是是A的划分的划分,若若 细分细分 1与与 2,则则 细分细分 1 2。 证明：证明：(1)设设 1和和 2分别对应的分别对应的A上关系是上关系是R1和和R2，则则 1 2对应的关系为对应的关系为R1R2。 (2) 设设 对应对应A上关系是上关系是R， 1和和 2分别对应的分别对应的A上关系是上关系是R1和和R2，则则 1 2对应的关系为对应的关

12、系为R1R2。 2.划分的和划分的和 设集合设集合A上的等价关系为上的等价关系为R1和和R2,容易证容易证明明R1R2是是A上的自反和对称关系上的自反和对称关系,但不但不是是A上的等价关系。然而上的等价关系。然而R1R2的传递的传递闭包是闭包是A上的等价关系。上的等价关系。 定理定理 2.19:设设R1和和R2是集合是集合A上的等价关上的等价关系系,则则(R1R2)+是是A上的等价关系。上的等价关系。 定义定义 2.18:设设R1和和R2是是A上的等价关系上的等价关系, R1和和R2确定确定A的划分分别为的划分分别为 1和和 2。 A上上的等价关系的等价关系(R1R2)+所确定所确定A的划分称

13、的划分称为为 1与与 2划分的和划分的和,记为记为 1+ 2。 定理定理 2.20：设：设 1, 2是是A的划分的划分, 则则 (1) 1与与 2细分细分 1+ 2； (2)设设 是是A的划分的划分,若若 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.7 次序关系次序关系 集合中还有

14、一种重要的关系：次序关系。集合中还有一种重要的关系：次序关系。它可用来比较集合中元素的次序它可用来比较集合中元素的次序,其中最其中最常用的是偏序关系和全序关系。常用的是偏序关系和全序关系。 1.偏序关系偏序关系 定义定义 2.19,2.20:设设R是集合是集合A上的二元关上的二元关系系, 若若R是自反的是自反的, 反对称的和传递的反对称的和传递的, 则则称称R是是A上的偏序关系。又记为上的偏序关系。又记为(注意注意,此此符号在这里并不意味着小于或等于符号在这里并不意味着小于或等于)。若。若集合集合A具有偏序关系具有偏序关系R,则称则称A为偏序集为偏序集,记记为为(A,R)。 实数集实数集R R

15、上的小于或等于关系上的小于或等于关系； 正整数集正整数集Z Z+ +上的整除关系；上的整除关系； 集合集合A A的幂集的幂集P(A)(A)上的包含关系上的包含关系 。 由于它们都是偏序关系，因此由于它们都是偏序关系，因此( (R,) R,) (Z(Z+ +,|), (,|), (P(A),(A), ) )都是偏序集。都是偏序集。 偏序集必须有一个具体给定的偏序集必须有一个具体给定的偏序关系偏序关系 例：例：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

16、),(,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是可比较的。是可比较的。 在上例中，在上例中，与与,1,2与与1,2都是可以比都是可以比较的，而较的，而1与与2无包含关系，故不可比较无包含关系，故不可比较 由此可见：偏序集合中任意两个元素不一由此可见：偏序集合中任意两个元素不一定可比较的。定可比较的。 但对于实数集上的小于或等于关系但

17、对于实数集上的小于或等于关系，对，对任意两个实数任意两个实数x,y,或者或者xy,或者或者yx，必有必有一个成立，故一个成立，故x和和y是可以比较的。是可以比较的。 全序关系全序关系 定义定义 2.22,2.23：设：设是集合是集合A上的二元关上的二元关系系, 如果对于如果对于A中任意两个元素中任意两个元素a,b A,必必有有ab或或ba, 则称则称是是A上的上的全序关系全序关系(或或称称线性次序关系线性次序关系)。而该集合称为。而该集合称为全序集全序集或或线性次序集线性次序集,记为记为(A,)。 整数集整数集I上的小于或等于关系上的小于或等于关系是全序关是全序关系系, 但但I上的整除关系上的

18、整除关系/不是全序关系。而不是全序关系。而前面给出的幂集前面给出的幂集P(A)上的上的 关系也不是全关系也不是全序关系。序关系。 2Hasse图图 偏序集偏序集(A,R)可以通过图形表示可以通过图形表示, 该图叫哈该图叫哈斯图。是对关系图的简化。斯图。是对关系图的简化。 (1)由于偏序关系是自反的，即对每个元素由于偏序关系是自反的，即对每个元素a,都有都有aRa，因此在图上省去自环因此在图上省去自环 (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,