离散数学-等价关系与偏序关系

离散数学集合论2/68主要内容集合代数二元关系函数集合的基本概念集合的运算有穷集合的计数集合恒等式有序对与笛卡儿积二元关系关系的运算关系的性质关系的闭包等价关系与划分偏序关系函数的定义与性质函数的复合与反函数双射函数与集合的基数3/68§7.6等价关系与划分例7.16设A={1,2…,8},定义A上的关系R如下:验证R是A上的等价关系.)}3(mod,,{yxAyxyxR一.等价关系定义7.15设R为非空集合A上的关系.如果R是自反的,对称的和传递的,则称R为A上的等价关系.对等价关系R,若x,yR,则称x等价于y,记为x～yorxRy.x)3(modxx解:∵xA,有,故R是自反的.)3(modyx)3(modxyx,yA,若,则,故R是对称的.)3(modyx)3(modzy)3(modzxx,y,zA,若,则,故R是传递的.∴R是A上的一个等价关系.4/68等价类定义7.16设R为非空集合A上的等价关系,xA,令称xR为x在R下的等价类(简称为x的等价类),有时简记为x.x称为该等价类的代表元.注:一个等价类是A中在等价关系R下彼此等价的所有元素的集合,等价类中各元素的地位是平等的,每个元素都可以作为其所在等价类的代表元.例如,在上例中的等价关系R下,A中元素形成了三个等价类:1=4=7={1,4,7};2=5=8={2,5,8};3=6={3,6}.)}({][xRyAyyxR1,1,1,4,1,7,4,1,4,4,4,7,7,1,7,4,7,72,2,2,5,2,8,5,2,5,5,5,8,8,2,8,5,8,83,3,3,6,6,3,6,65/68等价类的性质定理7.14设R为非空集合A上的等价关系,则（1）xA,x是A的非空子集.（2）x,yA,如果xRy,则x=y（3）x,yA,如果x与y不具有关系R,则x与y不相交.（4）∪{[x]|x∈A}=A证：(1)显然.(2)∵zxx,zRz,xR（R是对称的）∴z,xR∧x,yRz,yRy,zR∴zy,从而xy同理可得,yx.故x=y6/68等价类的性质(3)反证法.假设x∩y,则存在zx∩y.因而zx且zy,即x,zR∧y,zR.根据R的对称性和传递性,必有x,yR.这与前提条件矛盾.故原命题成立.AAxx][AAxx][)][(])[(][AxAyxyAxxAxxyAAxx][AxxyAyyyAy][][AxxA][AAxx][(4)先证∵∴再证∵∴因此7/68商集与划分定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素,形成的集合称为A关于R的商集,记为A/R,即:例如:例7.16中等价关系形成的商集为:A/R＝{{1,4,7},{2,5,8},{3,6}}AxxRAR][/定义7.18设A为非空集合,若A的子集族(P(A),是由A的一些子集形成的集合)满足下列条件:(1)¬(2)xy(x,y∧x≠y→x∩y=)(3)则称是A的一个划分,而称中的元素为A的划分块或类.五.集合的划分xAx8/68等价关系与划分例7.17设A={a,b,c,d},则1={{a,b,c},{d}}和2={{a,b},{c},{d}}都是A的划分,而3={{a},{a,b,c,d}}和4={,{a,b},{c}}都不是A的划分.注:给定非空有限集A上的一个等价关系R,在R下彼此等价的元素构成的子集便形成了A的一个划分,它其实就是商集A/R,其每个类(等价块)就是R的一个等价类;反之,任给A的一个划分,可定义A上的关系R如下:R={x,yx,yA∧x与y在的同一个类中}可以验证R是A上的一个等价关系.可见A上的等价关系与A的划分是一一对应的.9/68例例7.18求A={1,2,3}上所有的等价关系.解先求出A的所有划分:1={{1,2,3}};2={{1},{2,3}}；3={{2},{1,3}};4={{3},{1,2}};5={{1},{2},{3}}.与这些划分一一对应的等价关系是:1:→全域关系EA2:→R2={2,3,3,2}∪IA3:→R3={1,3,3,1}∪IA4:→R4={1,2,2,1}∪IA5:→恒等关系IA10/68§7.7偏序关系一.偏序关系与偏序集定义7.19设R为非空集合A上的关系.如果R是自反的,反对称的和传递的,则称R为A上的偏序关系,记为≼.对一个偏序关系≼,如果x,y≼,则记为x≼y.注:1.集合A上的恒等关系IA和空关系都是A上的偏序关系,但全域关系EA一般不是A上的偏序关系.2.实数域上的小于等于关系（大于等于关系）,自然数域上的整除关系,集合的包含关系等都是偏序关系.11/68可比与不可比注:在具有偏序关系的集合A中任二元素x和y之间必有下列四种情形之一:x≺y,y≺x,x=y,x与y不可比.例设A={1,2,3}(1)≼是A上的整除关系,则:1≺2,1≺3,1＝1,2＝2,3＝3,2和3不可比;(2)≼是A上的大于等于关系,则:2≺1,3≺1,3≺2,1＝1,2＝2,3＝3.定义7.20设R为非空集合A上的偏序关系,定义(1)x,yA,x≺y当且仅当x≼y且x≠y(2)x,yA,x与y可比当且仅当x≼y或y≼x12/68偏序集定义7.21设R为非空集合A上的偏序关系,如果x,yA,x与y都是可比的,则称R为A上的全序关系.例如大于等于关系(小于等于关系)是全序集,但整除关系一般不是全序集.定义7.22带有某种指定的偏序关系≼的集合A称为偏序集,记为A,≼.例如整数集Z和数的小于等于关系≤构成偏序集z,≼;集合A的幂集P(A)和集合的包含关系构成偏序集P(A),.定义7.23设A,≼为偏序集,x,yA,如果x≺y且不存在zA,使得x≺z≺y,则称y覆盖x.例如A={1,2,4,6}上的整除关系,有2覆盖1,4和6都覆盖2,但4不覆盖1,6不覆盖4.13/68哈斯图利用偏序关系的自反性,反对称性和传递性可简化偏序关系的关系图,得到偏序集的哈斯图.设有偏序集A,≼,其哈斯图的画法如下:(1)以A的元素作为顶点,适当排列各顶点的顺序,使得对x,yA,若x≺y,则将x画在y的下方.(2)对A中两个不同元素x和y,如果y覆盖x,则用一条线段连接x和y.例7.19画出偏序集{1,2,3,…,9},R整除}和P({a,b,c},R的哈斯图.解:它们的哈斯图分别为图A,图B表示如下:847236951图A{a,b}{a,b,c}{a}{b}{b,c}{c}{a,c}图B14/68例例7.20已知偏序集A,R的哈斯图如下:求集合A和关系R的表达式.aedfhgbc解A={a,b,c,d,e,f,g,h},R={b,d,b,e,b,f,c,d,c,e,c,f,d,f,e,f,g,h}∪IA.15/68特殊元素定义7.24设A,≼为偏序集,BA,yB.(1)若x(xB→y≼x)成立,则称y是B的最小元;(2)若x(xB→x≼y)成立,则称y是B的最大元;(3)若x(xB∧x≼y→x=y)成立,则称y是B的极小元;(4)若x(xB∧y≼x→x=y)成立,则称y是B的极大元.注:(1)极大(极小)元未必是最大(最小)元.极大(极小)元未必与B中任何元素都可比;(2)对有限集B,极大(极小)元一定存在,但最大(最小)元不一定存在;(3)最大(最小)元如果存在,必定是唯一的;而极大(极小)元一般不唯一.但如果B中只有一个极大(极小)元,则它一定是B的最大(最小)元.16/68例解:极大元:a,f,h;极小元:a,b,c,g;无最大元和最小元.例7.21求上例中A的极大元,极小元,最大元,最小元例7.22设x为集合,A=P(x)-{}-{x},且A≠,若|x|=n,问:(1)偏序集A,R是否有最大元?(2)偏序集A,R是否有最小元?(3)偏序集A,R中极大元和极小元的一般形式是什么?解:首先,因A≠,故n≥2,x中单个元素构成的子集都在A中,他们在R下互相不可比,因此A中无最大元和最小元.例x={1,2,3},A={{1},{2},{3},{1,2},{1,3},{2,3}}∅和x不是A中元素,故A中无最小元和最大元{1},{2},{3}都是极小元;{1,2},{1,3},{2,3}都是极大元17/68例其次考察(P(x),R)的哈斯图.其最低层是空集,记为第0层,由底向上,第1层是单元集,第2层是二元子集,…,第n-1层是x的所有n-1元子集,最顶层即第n层,只有一个顶点x.偏序集A,R的哈斯图是由P(x),R⊆的哈斯图去掉第0层与第n层得到的,故x的所有单元集都是A,R的极小元,x的所有n-1元子集都是A,R的极大元.18/68特殊元素定义7.25设A,≼为偏序集,BA,yA.(1)若x(xB→x≼y)成立,则称y为B的上界;(2)若x(xB→y≼x)成立,则称y为B的下界;(3)令C＝{y|y为B的上界},则称C的最小元为B的最小上界或上确界;(4)令D＝{y|y为B的下界},则称D的最大元为B的最大下界或下确界.注:1.B的最大元(最小元)必定是B的上界(下界),也是B的上确界(下确界).2.B的上界和上确界都未必是B的最大元,因它们可能不在B中.同理,下界和下确也未必是B的最小元.3.B的上界,上确界,下界,下确界都可能不存在.但如果上确界(下确界)存在,则它是唯一的.