（3）留作练习请读者自证。
3.9 等价关系与相容关系
本节讨论两类特殊关系—等价关系与相容关系。在讨论之前，我们先引进两个概念—集合的
划分与覆盖。
3.9.1 集合的划分和覆盖
设A是某一所综合性大学本科学生全体组成的集合，Si是对A的某种分类的集合（i?1,2,3）。若按文理科分类，则有S1?{S11,S12}，其中S11表示理科学生全体的集合、S12表示文科学生全体的集合；若按年级分类，则有S2?{S21,S22,S23,S24}，其中S2j(j?1,2,3,4)表示该大学j年级学生全体的集合；若按系分类，则有S3?{S31,S32,S33,S34,S35,S36}，这说明这所大学有六个系。分类法尽管给出了三种，但是它们有个共同的特点：(1) Si的元素都是A的非空子集；(2) Si的元素求交是空集、求并就是A。 此时，我们就说Si是集合A的一个划分。
定义3.9.1 设A是非空集合，A的子集的集合S?{A1,A2,?,Am}，如果满足： （1）A1,A2,?,Am都是非空集合；
m （2）?Ai?A
i?1则称集合S是集合A的覆盖(Cover)，称Ai是覆盖S的分块。
如果除以上条件外，另有Ai?Aj??（i?j），则称S是A的划分（或分划）(Partition)。 显然，若是划分则必是覆盖，其逆不真。
若A?{a1,a2,?,an}，则A有两个简单的划分：一是{{a1},{a2},?,{an}}，称为A的最大划分(分块最多)；二是A?{{a1,a2,?,an}}，称为A的最小划分(分块最少)。
例如，A?{a,b,c,d}，考虑下列子集：
S?{{a,b},{b,c},{d}}，Q?{{a},{a,b},{a,c,d}} D?{{a,d},{b,c}}，G?{{a,b,c,d}}， E?{{a},{b},{c},{d}}，F?{{a,b},{a,c}}
则S,Q是A的覆盖；D,G,E是A的划分，其中G是最小划分，E是最大划分；F既不是划 分也不是覆盖。
定义3.9.2 若S1?{A1,A2,?,Ar}与S2?{B1,B2,?,Bt}是同一集合X的两种划分，则 其中所有Ai?Bj(??)组成的集合，称为S1和S2的交叉划分，即
{Ai?BjAi?S1,Bj?S2,Ai?Bj??(i?1,2,?,r;j?1,2,?,t)}
注意：S1和S2的交叉划分一般不是S1?S2，而是以S1与S2元素之间的所有非空交集作元素的集合。
例如，所有生物的集合X，可分割成{P,Q}，其中P表示所有植物的集合，Q表示所 有动物的集合；又X也可分割成{E,F}，其中E表示史前生物，F表示史后生物。则其交 叉划分为{P?E,P?F,Q?E,Q?F}，其中P?E表示史前植物，P?F表示史后植物， Q?E表示史前动物，Q?F表示史后动物。
定理3.9.1 设S1?{A1,A2,?,Ar}与S2?{B1,B2,?,Bt}是同一集合X的两种划分，则
99
其交叉划分也是原集合X的一种划分。 证明 S1和S2的交叉划分是：
{A1?B1,A1?B2,?,A1?Bt,A2?B1,A2?B2,?,A2?Bt,
?,Ar?B1,Ar?B2,?,Ar?Bt}
在交叉划分中，任取两元素Ai?Bk和Aj?Bh，（i,j?1,2,叉划分中所有元素的并为
;?r,kh1,2,?t?），因为
Ai?Aj??，Bk?Bh??，所以 (Ai?Bk)?(Aj?Bh)?Ai?Bk?Aj?Bh??；其次，交
(A1?B1)?(A1?B2)???(A1?Bt)?(A2?B1)?(A2?B2)?
??(A2?Bt)???(Ar?B1)?(Ar?B2)???(Ar?Bt)
?(A1?(B1?B2???Bt))?(A2?(B1?B2???Bt))?
??(Ar?(B1?B2???Bt)) ?(A1?A2??Ar)?(B1?B2???Bt))
?X?X?X
所以，S1和S2的交叉划分也是X的一种划分。
定义3.9.3 给定X的任意两个划分S1?{A1,A2,?,Ar}与S2?{B1,B2,?,Bt}，若对于每一个Ai均有Bk，使Ai?Bk（i?1,2,?r;k?1,2,?t），则S1称为S2的加细。若还有S1?S2，则S1称为S2的真加细。
定理3.9.2 任何两种划分的交叉划分，都是原来各划分的一种加细。
证明 设S1?{A1,A2,?,Ar}与S2?{B1,B2,?,Bt}的交叉划分为T，对T中任意元素
Ai?Bj必有Ai?Bj?Ai和Ai?Bj?Bj，则T分别是S1和S2的加细。
3.9.2 等价关系与等价类
1. 等价关系
定义3.9.4 设R为定义在集合A上的一个关系，若R是自反的、对称的和传递的，则R称为等价关系(Equivalence Relation)。
例 3 . 9. 1 （1） 平面上三角形集合中，三角形的相似关系是等价关系。 （２） 数的相等关系是任何数集上的等价关系。 （3）一群人的集合中姓氏相同的关系也是等价关系。
（4）设A是任意非空集合，则A上的恒等关系IA和全域关系EA均是A上的等价关系。
例3.9.2 设集合A?{a,b,c,d,e}，
R?{a,a,a,b,b,a,b,b,c,c,c,d,c,e,
d,c,d,d,d,e,e,c,e,d,e,e}
验证R是A上的等价关系。
证明 R的关系矩阵：
?1?1???0??0?0?1100000111001110??0?1? ?1?1??MR 100
关系图如图3-9所示。
图3-9
关系矩阵中，对角线上的所有元素都是1，关系图上每个结点都有自环，说明R是自反的。关系矩阵是对称的，关系图上任意两结点间或没有弧线连接，或有成对弧出现，故R是对称的。从R的序偶表示式中，可以看出R是传递的。故R是A上的等价关系。
例3.9.3 设I为整数集，R?{x,yx?I,y?I,x?y(modk)}，其中x?y(modk)当且仅当?m?I，使得x?y?km，证明R是等价关系。
证明 设任意a,b,c?I
（1）a?a?k?0，所以，a,a?R，R是自反的；
（2）若a?b(modk)，a?b?kt(t为整数)，则 b?a??kt，所以，b?a(modk)，R是对称的；
（3）若a?b(modk)，b?c(modk)，则a?b?kt，b?c?ks (t,s为整数)， a?c?a?b?b?c?k(t?s)，所以，a?c(modk)，R是传递的。
因此，R是等价关系。我们称之为整数集I上的模k同余关系(Congruence Modulo k)。 2．等价类
定义3.9.5 设R是集合A上的等价关系，对任何a,b?A，若aRb，则称a与b等价。对任何a?A，集合A中等价于a的所有元素组成的集合称为以a为代表元的（A关于等价关系R的）等价类(Equivalence Class)，记作?a?R。即
?a?R?{xx?A,aRx}
由等价类的定义可知?a?R是非空的，因为aRa，a??a?R。因此，任给集合A及其上的等价关系R，必可写出A上各个元素的等价类。例如，在例3.9.2中，A的各个元素的等价类为：
?a?R?{xx?A,aRx}?{a,b}?{xx?A,bRx}??b?R；
?c?R?{xx?A,cRx}?{c,d,e}?{xx?A,dRx}??d?R?{xx?A,eRx}??e?R
可见，A上的等价关系R的不同的等价类有两个。
例3.9.4 设I是整数集合，R是模3同余关系，即
R?{x,yx?I,y?I,x?y(mod3)}，
确定由I的元素所产生的等价类。
解 例3.9.3已证明整数集合上的模k同余的关系是等价关系，故本例中由I的元素所产生的等价类是
?0?R?1?R?{?,?6,?3,0,3,6,?} ?{?,?5,?2,1,4,7,?}
101
?2?R?0?R?1?R?2?R?{?,?4,?1,2,5,8,?}
从本例可以看到，在集合I上模3同余等价关系R所构成的等价类有：
??3?R???3?R????3k?R ??4?R???2?R????3k?1?R ??5?R???1?R????3k?2?R
k???2,?1,0,1,2?
定理3.9.3 设给定集合A上的等价关系R，对于a,b?A有aRb当且仅当?a?R??b?R。 证明 若 ?a?R??b?R，因为 a??a?R，故a??b?R，即 bRa，则aRb。
若aRb ，则?c??a?R?aRc?cRa?cRb?bRc?c??b?R，即 ?a?R??b?R；
?c??b?R?bRc?aRc?c??a?R，即 ?b?R??a?R。
所以，?a?R??b?R。
定义3.9.6 集合A上的等价关系R，其所有等价类的集合称作A关于R的商集(Quotient Set )，记作AR，即
AR?{?a?Ra?A}
例如，例3.9.2中，商集：
AR?{{a,b},{c,d,e}}
例3.9.4中商集：
IR?{?0?R,?1?R,?2?R}}。
R我们注意到商集I下述重要定理。
中，?0?R??1?R??2?R?I，且任意两个等价类的交为?，于是我们有
。
定理3.9.4 集合A上的等价关系R，决定了A的一个划分，该划分就是商集AR为证定理，我们需要证明非空集合A在其上的等价关系R下形成的等价类的全体的集合－商集满足：
(1) 每一等价类都是A的子集， A中任一元素均属于某一等价类， 即等价类全体的并集是A；
(2) 不同的等价类之间交是空集。
证明 ?a?A，因为 ?a?R?{xx?A,aRx}，所以，?a?R?A，从而??a?R?A；
a?A因为R自反，即aRa，所以，a??a?R，则 A?(1) 得证。
为证明（2），用反证法：
??a?a?AR；故
??a?a?AR?A。
设?a,b?A，?a?R??b?R，且?a?R??b?R?? 则 ?c??a?R??b?R?A，使aRc,bRc成立，
由对称性得 cRb，再由传递性得 aRb，据定理3.9.3，必有 ?a?R??b?R，这与题设矛盾，（2）
102
得证。所以，AR是A的对应于R的一个划分。
定理3.9.5设S?{S1,S2,?,Sm}是集合A的一个划分，则存在A上的一个等价关系R，使得S是A关于R的商集。
证明 在集合A上定义关系R，对任意a,b?A，aRb当且仅当a,b在同一分块中。可以证明这样定义的关系R是一个等价关系。因为：
（1）a与a在同一分块中，故必有aRa，即R是自反的。 （2）若a与b在同一分块中，b与a也必在同一分块中，即 aRb?bRa，故R是对称的。 （3）若a与b在同一分块中，b与c在同一分块中，因为 Si?Sj??，即b属于且仅属于一个分块，故a与c必在同一分块中，即 (aRb)?(bR?c)所以，R是等价关系。
由R的定义可知： S?ARa，故RcR是传递的。
。
由定理3.9.5可知：由集合A的划分S?{S1,S2,?,Sm}所确定的A上的等价关系R为：
R?S1?S1?S2?S2???Sm?Sm
定理3.9.4和定理3.9.5说明：非空集合A上的等价关系与A的划分一一对应。
例3.9.5 设A?{a,b,c,d,e}的划分S?{{a,b},{c},{d,e}}，试由划分S确定A上的一个等价关系R。
解 R1?{a,b}?{a,b}?{a,a,a,b,b,a,b,b}
R2?{c}?{c}?{c,c} } R3?{d,e}?{d,e??R2? R?R1R3?{{d,d,aa,,d,e,ab,,e,d,ba,, e,e,bb,},cc,,dd,,de,,e d,,ee}显然，S?AR。
定理3.9.6 设R1和R2为非空集合A上的等价关系，则
R1?R2?AR1?AR2。
证明 AR1?{?a?Ra?A}，A11R2?{?a?Ra?A}。
22若R1?R2 ，?a?A，?a?R?{xx?A,aR1x}?{xx?A,aR2x}??a?R，故
{?a?Ra?A}?{?a?Ra?A}，即A12R1?AR2；
若AR1?AR1R2，即{?a?Ra?A}?{?a?Ra?A}，则对
12??a?R?A1，必有?c?R?A2R2，使得?a?R??c?R，故
12? a,b?R1a???aR1?b???Ra1??a??R2c??b??R2c?,a2c?R,?c2 b?R ?a,b?R 2所以， R1?R2；类似地有R2?R1 ，因此，R1?R2。
3.9.3 相容关系
定义3.9.4 给定集合A上的关系R，若R是自反的、对称的，则称R是A上的相容关系
103