《北大离散数学》PPT课件.ppt

《《北大离散数学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《北大离散数学》PPT课件.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8讲 等价关系与序关系内容提要等价关系,等价类,商集 划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2023/1/111集合论与图论第8讲等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2023/1/112集合论与图论第8讲等价(equivalence)关系定义等价关系:设 RAA 且 A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1=|x,yAx与y同年生R2=|x,yAx与y同姓R3=|x,yAx的年龄不比y小R4=|x,yAx与y选修同门课

2、程R5=|x,yAx的体重比y重2023/1/113集合论与图论第8讲例9(续)定义自反对称 传递 等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重2023/1/114集合论与图论第8讲例10例10:设 RAA 且 A,对R依次求三种闭包共有6种不同顺序,其中哪些顺序一定导致等价关系?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)2023/1/115集合论与图论第

3、8讲例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)2023/1/116集合论与图论第8讲等价类(equivalence class)等价类:设R是A上等价关系,xA,令 xR=y|yA xRy,称xR为x关于R的等价类,简称x的等价类,简记为x.等价类性质:xR;xRy xR=yR;xRy xRyR=;U xR|xA =A.2023/1/117集合论与图论第8讲定理27定理27:设R是A上等价关系,x,yA,(1)xR(2)xRy xR=yR;(3)xRy xRyR=;(4)U xR|xA =A.证明:(1)R自反x

4、RxxxRxR.x2023/1/118集合论与图论第8讲定理27(证明(2)(2)xRy xR=yR;证明:(2)只需证明xRyR和xRyR.()z,zxRxRy zRxxRy zRy zyR.xRyR.()同理可证.xyz2023/1/119集合论与图论第8讲定理27(证明(3)(3)xRy xRyR=;证明:(3)(反证)假设z,zxRyR,则 zxRyR zRxzRy xRzzRy xRy,这与xRy矛盾!xRyR=.xyz2023/1/1110集合论与图论第8讲定理27(证明(4)(4)U xR|xA =A.证明:(4)A=U x|xA U xR|xA U A|xA=A.U xR|xA

5、 =A.#xy2023/1/1111集合论与图论第8讲同余关系:设n2,3,4,x,yZ,则x与y模n同余(be congruent modulo n)xy(mod n)n|(x-y)x-y=kn(kZ)同余关系是等价关系0 =kn|kZ,1 =1+kn|kZ,2 =2+kn|kZ,n-1=(n-1)+kn|kZ.同余(congruence)关系 639875421101102023/1/1112集合论与图论第8讲例11例11:设 A=1,2,3,4,5,8,求R3=|x,yA xy(mod 3)的等价类,画出R3的关系图.解:1=4=1,4,2=5=8=2,5,8,3=3.#14258320

6、23/1/1113集合论与图论第8讲商集(quotient set)商集:设R是A上等价关系,A/R=xR|xA 称为A关于R的商集,简称A的商集.显然 U A/R=A.例11(续):A/R3=1,4,2,5,8,3.2023/1/1114集合论与图论第8讲例12(1)例12(1):设A=a1,a2,an,IA,EA,Rij=IA,都是A上等价关系,求对应的商集,其中ai,ajA,ij.是A上等价关系吗?解:A/IA=a1,a2,an A/EA=a1,a2,an A/Rij=A/IAai,aj-ai,aj.不是A上等价关系(非自反).#2023/1/1115集合论与图论第8讲划分(partit

7、ion)划分:设A,AP(A),若A满足 (1)A;(2)x,y(x,yA xy xy=)(3)UA=A 则称A为A的一个划分,A中元素称为划分块(block).2023/1/1116集合论与图论第8讲划分(举例)设 A1,A2,AnE,则以下都是划分:Ai=Ai,Ai,(i=1,2,n)Aij=AiAj,AiAj,AiAj,AiAj-(i,j=1,2,n ij)A12n=A1A2 An,A1A2 An-1An,A1A2 An-.#2023/1/1117集合论与图论第8讲划分(举例,续)AiAi2023/1/1118集合论与图论第8讲等价关系与划分是一一对应的定理28:设A,则(1)R是A上等

8、价关系 A/R是A的划分(2)A是A的划分 RA是A上等价关系,其中xRAy z(zA xz yz)RA称为由划分A 所定义的等价关系(同块关系).#2023/1/1119集合论与图论第8讲例12(2)例12(2):A=a,b,c,求A上全体等价关系.解:A上不同划分共有5种:abcabcabcabcabcR1=EA,R2=IA,R3=IA,R4=IA,R5=IA.#2023/1/1120集合论与图论第8讲Bell数(Bell number)问题:给n个对象分类,共有多少种分法?答案:Bell数 Bn=(Eric Temple Bell,18831960)Stirling子集数(Stirlin

9、g subset number):把n个对象分成k个非空子集的分法个数.递推公式:2023/1/1121集合论与图论第8讲Stirling子集数递推公式:剔除一个其余分k类加入一类其余分k-1类自成一类2023/1/1122集合论与图论第8讲第一、二类Stirling数第一类Stirling数(Stirling number of the first kind):s(n,k)第二类Stirling数(Stirling number of the second kind):S(n,k)=2023/1/1123集合论与图论第8讲Bell数表 nBn nBn1184,14022921,1473510

10、115,97541511678,570552124,213,59762031327,644,437787714190,899,3222023/1/1124集合论与图论第8讲第二类Stirling数表nk01 23456789011012011301314017615011525101601319065151701633013501402118011279661,1701,050266281901255 3,0357,7706,9512,64646236110015119,33034,50142,52522,8275,880750452023/1/1125集合论与图论第8讲例13例13:问A=a

11、,b,c,d上有多少种等价关系?解:#2023/1/1126集合论与图论第8讲划分的加细(refinement)划分的加细:设A和B都是集合A的划分,若A的每个划分块都包含于B的某个划分块中,则称A为B的加细.A为B的加细 RARB 2023/1/1127集合论与图论第8讲例14例14:考虑A=a,b,c上的划分之间的加细.解:abcabcabcabcabc加细加细加细加细加细加细#2023/1/1128集合论与图论第8讲序关系偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链 2023/1/1129集合论与图论第8讲偏序(partial order)关系偏序关系:设

12、RAA 且 A,若R是自反的,反对称的,传递的,则称R为偏序关系通常用表示偏序关系,读作“小于等于”R xRy xy“严格小于”:xy xy xy偏序集(poset):,是A上偏序关系例子:,2023/1/1130集合论与图论第8讲偏序集,AR=|x,yA xy,=|x,yA xy,AZ+=x|xZ x0|=|x,yA x|y 2023/1/1131集合论与图论第8讲偏序集AP(A),=|x,yA xy 设A=a,b,A1=,a,b,A2=a,a,b,A3=P(A)=,a,b,a,b,则1=IA1 ,2=IA2 3=IA3 ,2023/1/1132集合论与图论第8讲偏序集A,是由A的一些划分组

13、成的集合加细=|x,y x是y的加细 设A=a,b,c,A1=a,b,c,A2=a,b,c,A3=b,a,c,A4=c,a,b,A5=a,b,c取1=A1,A2,2=A2,A3,3=A1,A2,A3,A4,A51=I1 ,2=I2,3=I3 ,.#2023/1/1133集合论与图论第8讲哈斯图(Hasse diagram)设是偏序集,x,yA可比(comparable):x与y可比 xy yx覆盖(cover):y覆盖x xy z(zA xzy)哈斯图:当且仅当y覆盖x时,在x与y之间画无向边,并且x画在y下方2023/1/1134集合论与图论第8讲例16(1)(2)例16:画出下列偏序关系的

14、哈斯图.(1),A=1,2,3,4,5,6,9,10,15(2),A=a,b,c,AP(A),A=,a,b,c,a,b,b,c,a,c解:12436915510abca,ba,cb,c2023/1/1135集合论与图论第8讲例16(3)例16:画出下列偏序关系的哈斯图.(3),=A1,A2,A3,A4,A5,A6,A=a,b,c,d A1=a,b,c,d,A2=a,b,c,d,A3=a,c,b,d,A4=a,b,c,d,A5=a,b,c,d,A6=a,b,c,d 解:A1A2A5A3A4A6#2023/1/1136集合论与图论第8讲偏序关系中的特殊元素最大元,最小元极大元,极小元上界,下界最小

15、上界(上确界),最大下界(下确界)2023/1/1137集合论与图论第8讲最大元,最小元设为偏序集,BA,yB最大元(maximum/greatest element):y是B的最大元 x(xB xy)最小元(minimum/least element):y是B的最小元 x(xB yx)2023/1/1138集合论与图论第8讲最大元,最小元举例(例16(1)例16(1):,A=1,2,3,4,5,6,9,10,15 B1=1,2,3,B2=3,5,15,B3=A.B1的最大元是,B1的最小元是1 B2的最大元是15,B2的最小元是 B3的最大元是,B3的最小元是1124369155101243

16、69155102023/1/1139集合论与图论第8讲极大元,极小元设为偏序集,BA,yB极大元(maximal element):y是B的极大元 x(xB yx x=y)极小元(minimal element):y是B的极小元 x(xB xy x=y)2023/1/1140集合论与图论第8讲极大元,极小元举例(例16(1)例16(1):,A=1,2,3,4,5,6,9,10,15 B1=1,2,3,B2=3,5,15,B3=A.B1的极大元是2,3,B1的极小元是1 B2的极大元是15,B2的极小元是3,5B3的极大元是4,6,9,15,10,B3的极小元是11243691551012436

17、9155102023/1/1141集合论与图论第8讲上界,下界设为偏序集,BA,yA上界(upper bound):y是B的上界 x(xB xy)下界(lower bound):y是B的下界 x(xB yx)2023/1/1142集合论与图论第8讲上界,下界举例(例16(1)例16(1):,A=1,2,3,4,5,6,9,10,15 B1=1,2,3,B2=3,5,15,B3=A.B1的上界是6,B1的下界是1 B2的上界是15,B2的下界是1 B3的上界是,B3的下界是112436915510124369155102023/1/1143集合论与图论第8讲最小上界,最大下界设为偏序集,BA最小

18、上界(least upper bound):设 C=y|y是B的上界,C的最小元称为B的最小上界,或上确界.最大下界(greatest lower bound):设 C=y|y是B的下界,C的最大元称为B的最大下界,或下确界.2023/1/1144集合论与图论第8讲最小上界,最大下界举例(例16(1)例16(1):,A=1,2,3,4,5,6,9,10,15 B1=1,2,3,B2=3,5,15,B3=A.B1的最小上界是6,B1的最大下界是1 B2的最小上界是15,B2的最大下界是1 B3的最小上界是,B3的最大下界是112436915510124369155102023/1/1145集合论

19、与图论第8讲特殊元素比较存在(B非空有穷)存在(B无穷)唯一 B最大元(表示不一定)最小元 极大元 (表示一定),B=Z 极小元 上界下界上确界 下确界 2023/1/1146集合论与图论第8讲链(chain),反链(antichain)设为偏序集,BA,链(chain):B是A中的链 xy(xByB x与y可比)|B|称为链的长度反链(antichain):B是A中的反链 xy(xByBxy x与y不可比)|B|称为反链的长度2023/1/1147集合论与图论第8讲链,反链(举例)设偏序集如图所示,A=a,b,k.abcdefghijkB1=a,c,d,e是长为4的链 上界e,f,g,h,上

20、确界e 下界a,下确界aB2=a,e,h是长为3的链B3=b,g是长为2的链B4=g,h,k是长为3的反链 上界,下界,上确界,下确界:无B5=a是长为1的链和反链B6=a,b,g,h既非链,亦非反链2023/1/1148集合论与图论第8讲定理31定理31:设为偏序集,A中最长链的长度为n,则 (1)A中存在极大元 (2)A存在n个划分块的划分,每个划分块都是反链(即A划分成n个互不相交的反链)推论:设为偏序集,若|A|=mn+1,则A中要么存在长度为m+1的反链,要么存在长度为n+1的链.2023/1/1149集合论与图论第8讲定理31(举例)abcdefghijk最长链长度为6,如B1=a

21、,c,d,e,f,h,B2=a,c,d,e,f,g,A=a,b,k可以划分为A 1=a,b,i,c,j,d,e,f,g,h,k,A 2=a,b,c,i,d,j,e,k,f,g,h|A|=11=25+1,A中既有长度为2+1=3的反链,也有长度为5+1=6的链2023/1/1150集合论与图论第8讲定理31(证明(1)定理31:设为偏序集,A中最长链的长度为n,则 (1)A中存在极大元证明:(1)设B是A中长度为n的最长链,B有极大元(也是最大元)y,则y也是A的极大元,否则A中还有比y“大”的元素z,B就不是最长链.2023/1/1151集合论与图论第8讲定理31(证明(2)定理31:设为偏序

22、集,A中最长链的长度为n,则 (2)A存在n个划分块的划分,每个划分块都是反链(即A划分成n个互不相交的反链)证明:(2)A1=x|x是A中的极大元,A2=x|x是(A-A1)中的极大元,An=x|x是(A-A1-An-1)中的极大元,则 A=A1,A2,An 是满足要求的划分.2023/1/1152集合论与图论第8讲定理31(证明(2):举例)abcdefghijk最长链长度为6,A1=g,h,k,A2=f,j,A3=e,i,A4=d,A5=c,A6=a,b,A=a,b,c,d,e,i,f,j,g,h,k 2023/1/1153集合论与图论第8讲定理31(证明(2)续)证明(续):1 A1=

23、x|x是A中的极大元,极大元互相之间不可比,所以A1是反链,同理A2,An都是反链.2 显然A1,A2,An互不相交.3 最长链上的元素分属A1,A2,An,所以A1,A2,An都非空.4 假设zA-A1-An,则最长链上的元素加上z就是长度为n+1的链,矛盾!所以A=A1A2An.综上所述,A=A1,A2,An 确是所求划分.#2023/1/1154集合论与图论第8讲定理31推论(证明)推论:设为偏序集,若|A|=mn+1,则A中要么存在长度为m+1的反链,要么存在长度为n+1的链.证明:(反证)假设A中既没有长度为m+1的反链,也没有长度为n+1的链,则按照定理31(2)中要求来划分A,A

24、至多划分成n块,每块至多m个元素,于是A中至多有mn个元素,这与|A|=mn+1矛盾!#2023/1/1155集合论与图论第8讲全序(total order)关系全序关系:若偏序集满足xy(xAyA x与y可比)则称为全序关系,称为全序集全序关系亦称线序(linear order)关系例:,2023/1/1156集合论与图论第8讲拟序(quasi-order)关系拟序关系:设 RAA 且 A,若R是反自反的,传递的,则称R为拟序关系通常用表示拟序关系(对比:“严格小于”)反自反性与传递性蕴涵反对称性拟序集:,是A上拟序关系例子:设AR,BZ+A,|=|x,yB x|y xy2023/1/115

25、7集合论与图论第8讲定理29定理29:设是非空集合A上偏序关系,是A上拟序关系,则 (1)是反对称的;(2)-IA是A上拟序关系;(3)IA是A上偏序关系.证明:(1)xy yx xx,矛盾!(2)(3)显然.2023/1/1158集合论与图论第8讲定理30定理30:设是非空集合A上拟序关系,则 (1)xy,x=y,yx中至多有一式成立;(2)(xy x=y)(yx x=y)x=y.证明:(1)两式以上成立导致 xx,矛盾!(2)xy (xy)(yx),(由已知条件)与(1)矛盾!#2023/1/1159集合论与图论第8讲三歧性(trichotomy)三歧性:设是非空集合A上拟序关系,若xy,

26、x=y,yx中有且仅有一式成立,则称具有三歧性.拟全序关系:设是非空集合A上拟序关系,若具有三歧性,则称为拟全序关系,或拟线序关系,称为拟线序集.2023/1/1160集合论与图论第8讲良序(well-order)良序关系:设为拟全序集,若A的任何非空子集B均有最小元,则称为良序关系,为良序集例:N,是良序集,Z,不是良序集良序原理(well-ordering principle):每一个集合都可以良序化(建立良序关系)良序原理等价于选择公理良序集可做超限(transfinite)归纳证明2023/1/1161集合论与图论第8讲总结等价关系,等价类,商集,划分偏序,线序,拟序,良序哈斯图,特殊元素,(反)链2023/1/1162集合论与图论第8讲作业(#6)p84,习题二,35,39,47,50,522023/1/1163集合论与图论第8讲