集合论与图论2.4

1、2.6 等价关系与划分*等价关系是一类重要的二元关系: 设R是非空集合A上的关系.如果R是自反的,对称的和传递的,则称R为A上的等价关系.若R,则称x等价于y,记作xy.例1:设A=1,2,8,定义A上的关系R: R=|x,yAxy(mod3)证明:xA,有xx(mod3).x,yA,若xy(mod3),则有yx(mod3).x,y,zA,若xy(mod3),yz(mod3),则有xz(mod3).关系图如下: (见图2.6.1): 设R为非空集合A上的等价关系,xA,令xR=y|yAxRy.称xR为x关于R的等价类,简称为x的等价类,简记为x或 .例如:例1中关系R的等价类有: 1=4=7=

2、1,4,7 2=5=8=2,5,8 3=6=3,6 .*对上述等价关系的推广,可得整数集合Z上模n同余的等价关系.xZ, x=qn+r , 0rn1.*例如: n=3, x=8, 8=23+2, r=2n=3, x=8, 8=(3)3+1, r=1定义: xyxy(mod n)该关系将Z中的数划分为等价类如下:余数为0的数, nz, zZ余数为1的数, nz+1, zZ 余数为n-1的数, nz+(n-1), zZ构成的等价类: i=nz+i|zZ, i=0,1,2,n-1.*下面给出等价类的性质(对一般的等价类而言).:设R为非空集合A上的等价关系,则(1)xA,x是A的非空子集;(2)x,

3、yA,如果xRy,则x=y;(3)x,yA,如果,则x与y不相交.(4)x | xA = A .证明: (1)由等价类的定义,有xA, xRx, 故xx, 因而x.(2)任取z,则有zxxRzzRx (由对称性)又有zRxxRyzRy (由R的传递性) yRz (由对称性)从而证明了zy,因而有xy.同理可证yx.因而有x=y.(3)假设xy,则存在zxy,即有zxzy. 故RR, 由对称性,R, 再由传递性, 有R, 这与R矛盾.(4)先证x| xAA.任取y,yx| xAx(xAyx)yA (因为xA)从而有x|xAA.再证:Ax|xA.任取y,yAyyyAyx|xA.从而有Ax|xA成立

4、.综上所述,A=x|xA.*由非空集合A和A上的等价关系R可以构造一个新的集合商集.:设R是非空集合A上的一个等价关系,以R的所有等价类作为元素的集合称为A关于R的商集A/R=xR | xA.例如:以例1中的集合A和关系R,得到商集:A/R=1,4,7,2,5,8,3,6:设A为非空集合,若A的子集族(P(A)满足下面的条件:(1) ;(2) ;(3) =A则称是A的一个划分,称中的元素为A的划分块.例2:设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

5、是A的划分,其它都不是A的划分.*设R是非空集合A上的一个等价关系,则商集A/R是A的一个划分.*反之,任给A的一个划分,定义A上的关系R如下:R=|x,yAx与y在的同一划分块中.不难证明R是一个等价关系,且该等价关系所确定的商集就是.*A上的等价关系与A的划分是一一对应的.2.7 偏序关系: 设R是非空集合A上的关系.如果R是自反的,反对称的和传递的,则称R为A上的偏序关系,记作. 如果, 则记为xy,读作x小于或等于y.例如: 集合A的幂集P(A)上也是偏序关系.*一般说来,全域关系EA不是A上的偏序关系.: 设R为非空集合A上的偏序关系,定义(1)(2)x,yA, x与y可比xyyx

6、.*xy读作x小于y.*由以上定义:在具有偏序关系的集合A中,任取两个元素x和y,只有以下三种情形之一发生:xy (或yx), x=y, x与y是不可比的.例如:A=1,2,3, 是A上的整除关系,则有 1 2 , 1 3 1=1 , 2=2, 3=3 2和3不可比.: 设R为非空集合A上的偏序关系,如果x,yA,x与y都是可比的,则称R为A上的全序关系(或线序关系).例如: 整数集合上的关系. 设A是至少有两个元素的集合, 则不是P(A)上的线序关系.: 集合A和A上的偏序关系一起叫做偏序集, 记做 .例如: , .*哈斯图: 设为偏序集. x,yA, 如果xy且不存在zA使得xzy, 则称

7、y覆盖x .例3: 画出偏序集 (R为整除关系) 和的哈斯图 . (见图2.7.1)例4: 已知偏序关系的哈斯图如图2.7.2, 试求出集合A和关系R的表达式.解:A=a,b,c,d,e,f,g,h. R=,IA .: 设为偏序集, BA, yB.(1) 若成立,则称y为B的最小元;(2) 若成立,则称y为B的最大元;(3) 若成立,则称y为B的极小元;(4) 若成立,则称y为B的极大元.例5: 见上例. A的极小元: a,b,c,g . A的极大元: a,f,h . A没有最小元和最大元. B1=b,c,d,e,f有最大元f,但没有最小元. B2=b,d,e,f有最大元f和最小元b.: 设为

8、偏序集, BA, yA .(1) 若成立, 则称y为B的上界;(2) 若成立, 则称y为B的下界;(3) 令C=y|y为B的上界,则称C的最小元为B的最小上界或上确界;(4) 令D=y|y为B的下界,则称D的最大元为B的最大下界或下确界.例如: 例5中,B1=b,c的上界为d,e,f, 但没有最小上界.B2=b,d,e有最小上界f.B3=b,c,d,e,f有最小上界f.B4=f,e,d有下界b,c, 但没有最大下界.B5=h有下界h和g, 其中h为B5的最大下界.作业:1. 对于给定的A和R,判断R是否为A的等价关系:(1) A为实数集,x,yA, xRyxy=2. 不是(2) A=Z+,即正整数集,x,yA, xRyxy是奇数. 不是(3) A=P(X), |X|2, x,yA, xRyxyyx . 是2. 设A=a,b,c,d, A上的等价关系R=,IA,画出R的关系图,并求出A中各元素的等价类.a = bb = ac = dd = c3. 设R是A上的自反的和传递的关系,如下定义A上的关系T,使得x,