14.5等价关系与偏序关系等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应偏序关系偏序集与哈斯图偏序集中的特定元素2等价关系的定义与实例定义设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若∈R,称x等价于y,记做x～y.实例设A={1,2,…,8},如下定义A上的关系R：R={|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.3等价关系的验证验证模3相等关系R为A上的等价关系,因为x∈A,有x≡x(mod3)x,y∈A,若x≡y(mod3),则有y≡x(mod3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)自反性、对称性、传递性得到验证4A上模3等价关系的关系图设A={1,2,…,8},R={|x,y∈A∧x≡y(mod3)}5等价类定义设R为非空集合A上的等价关系,x∈A，令[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价类,简称为x的等价类,简记为[x].实例A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}6等价类的性质定理1设R是非空集合A上的等价关系,则(1)x∈A,[x]是A的非空子集.(2)x,y∈A,如果xRy,则[x]=[y].(3)x,y∈A,如果xy,则[x]与[y]不交.(4){[∪x]|x∈A}=A，即所有等价类的并集就是A.7实例A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}，[2]=[5]=[8]={2,5,8}，[3]=[6]={3,6}以上3类两两不交，{1,4,7}{2,5,8}{3,6}={1,2,…,8}8商集定义设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R|x∈A}实例A={1,2,…,8},A关于模3等价关系R的商集为A/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：A/IA={{1},{2},…,{8}}A/EA={{1,2,…,8}}9集合的划分定义设A为非空集合,若A的子集族π(πP(A))满足下面条件：(1)π(2)xy(x,y∈π∧x≠y→x∩y=)(3)∪π=A则称π是A的一个划分,称π中的元素为A的划分块.10例题例1设A＝{a,b,c,d},给定π1,π2,π3,π4,π5,π6如下：π1={{a,b,c},{d}}，π2={{a,b},{c},{d}}π3={{a},{a,b,c,d}},π4={{a,b},{c}}π5={,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}则π1和π2是A的划分,其他都不是A的划分.为什么？11等价关系与划分的一一对应商集A/R就是A的一个划分不同的商集对应于不同的划分任给A的一个划分π,如下定义A上的关系R：R={|x,y∈A∧x与y在π的同一划分块中}则R为A上的等价关系,且该等价关系确定的商集就是π.例2给出A＝{1,2,3}上所有的等价关系求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系.12等价关系与划分之间的对应π1,π2和π3分别对应等价关系R1,R2和R3.R1={<2,3>,<3,2>}∪IA，R2={<1,3>,<3,1>}∪IAR3={<1,2>,<2,1>}∪IAπ4对应于全域关系EA，π5对应于恒等关系IA13实例例3设A={1,2,3,4}，在AA上定义二元关系R：<,>Rx+y=u+v，求R导出的划分.解AA={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}14实例（续）根据的x+y=2,3,4,5,6,7,8将AA划分成7个等价类：(AA)/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}15偏序关系定义非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作≼.设为偏序≼关系,如果,∈≼则记作x≼y,读作x“小于或等于”y.实例集合A上的恒等关系IA是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.16相关概念x与y可比：设R为非空集合A上的偏序关系,x,yA,x与y可比x≼y∨y≼x.结论：任取两个元素x和y,可能有下述情况：x≺y(或y≺x),x＝y,x与y不是可比的.全序关系：R为非空集合A上的偏序,x,yA,x与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系17覆盖：设R为非空集合A上的偏序关系,x,y∈A,如果x≺y且不存在zA使得x≺z≺y,则称y覆盖x.实例：{1,2,4,6}集合上的整...
