北大离散数学08.ppt

《北大离散数学08.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第8讲等价关系与序关系内容提要等价关系,等价类,商集划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2021/7/251《集合论与图论》第8讲等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2021/7/252《集合论与图论》第8讲等价(equivalence)关系定义等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1={

2、x,yAx与

3、y同年生}R2={

4、x,yAx与y同姓}R3={

5、x,yAx的年龄不比y小}R4={

6、x,yAx与y选修同门课程}R5={

7、x,yAx的体重比y重}2021/7/253《集合论与图论》第8讲例9(续)定义自反对称传递等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重2021/7/254《集合论与图论》第8讲例10例10:设RAA且A,对R依次求三种闭包共有6种不同顺序,

8、其中哪些顺序一定导致等价关系?rst(R),rts(R),str(R),srt(R),trs(R),tsr(R)=t(s(r(R)))解:st(R)ts(R),sr(R)=rs(R),…tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)2021/7/255《集合论与图论》第8讲例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)2021/7/256《集合论与图论》第8讲等价类(equivalencec

9、lass)等价类:设R是A上等价关系,xA,令[x]R={y

10、yAxRy},称[x]R为x关于R的等价类,简称x的等价类,简记为[x].等价类性质:[x]R;xRy[x]R=[y]R;xRy[x]R[y]R=;U{[x]R

11、xA}=A.2021/7/257《集合论与图论》第8讲定理27定理27:设R是A上等价关系,x,yA,(1)[x]R(2)xRy[x]R=[y]R;(3)xRy[x]R[y]R=;(4)U{[x]R

12、xA}=A.证明:(1)R自反xRxx[x

13、]R[x]R.x2021/7/258《集合论与图论》第8讲定理27(证明(2))(2)xRy[x]R=[y]R;证明:(2)只需证明[x]R[y]R和[x]R[y]R.()z,z[x]RxRyzRxxRyzRyz[y]R.[x]R[y]R.()同理可证.xyz2021/7/259《集合论与图论》第8讲定理27(证明(3))(3)xRy[x]R[y]R=;证明:(3)(反证)假设z,z[x]R[y]R,则z[x]R[y]RzRxzRyxRzzRyxRy,这与

14、xRy矛盾![x]R[y]R=.xyz2021/7/2510《集合论与图论》第8讲定理27(证明(4))(4)U{[x]R

15、xA}=A.证明:(4)A=U{{x}

16、xA}U{[x]R

17、xA}U{A

18、xA}=A.U{[x]R

19、xA}=A.#xy2021/7/2511《集合论与图论》第8讲同余关系:设n{2,3,4,…},x,yZ,则x与y模n同余(becongruentmodulon)xy(modn)n

20、(x-y)x-y=kn(kZ)同余关系是等价关系[0]={kn

21、kZ},[1]

22、={1+kn

23、kZ},[2]={2+kn

24、kZ},…,[n-1]={(n-1)+kn

25、kZ}.同余(congruence)关系639875421101102021/7/2512《集合论与图论》第8讲例11例11:设A={1,2,3,4,5,8},求R3={

26、x,yAxy(mod3)}的等价类,画出R3的关系图.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832021/7/2513《集合论与图论》第8讲商集(quotientset)商集:设R是A

27、上等价关系,A/R={[x]R

28、xA}称为A关于R的商集,简称A的商集.显然UA/R=A.例11(续):A/R3={{1,4},{2,5,8},{3}}.2021/7/2514《集合论与图论》第8讲例12(1)例12(1):设A={a1,a2,…,an},IA,EA,Rij=IA{,}都是A上等