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

2019/11/26,集合论与图论第8讲,1,第8讲等价关系与序关系,内容提要等价关系,等价类,商集划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链,2019/11/26,集合论与图论第8讲,2,等价(equivalence)关系,定义同余关系等价类商集划分划分的加细Stirling子集数,2019/11/26,集合论与图论第8讲,3,等价(equivalence)关系定义,等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1=|x,yAx与y同年生R2=|x,yAx与y同姓R3=|x,yAx的年龄不比y小R4=|x,yAx与y选修同门课程R5=|x,yAx的体重比y重,2019/11/26,集合论与图论第8讲,4,例9(续),2019/11/26,集合论与图论第8讲,5,例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),2019/11/26,集合论与图论第8讲,6,例10(续),2019/11/26,集合论与图论第8讲,7,等价类(equivalenceclass),等价类:设R是A上等价关系,xA,令xR=y|yAxRy,称xR为x关于R的等价类,简称x的等价类,简记为x.等价类性质:xR;xRyxR=yR;xRyxRyR=;UxR|xA=A.,2019/11/26,集合论与图论第8讲,8,定理27,定理27:设R是A上等价关系,x,yA,(1)xR(2)xRyxR=yR;(3)xRyxRyR=;(4)UxR|xA=A.证明:(1)R自反xRxxxRxR.,x,2019/11/26,集合论与图论第8讲,9,定理27(证明(2),(2)xRyxR=yR;证明:(2)只需证明xRyR和xRyR.()z,zxRxRyzRxxRyzRyzyR.xRyR.()同理可证.,x,y,z,2019/11/26,集合论与图论第8讲,10,定理27(证明(3),(3)xRyxRyR=;证明:(3)(反证)假设z,zxRyR,则zxRyRzRxzRyxRzzRyxRy,这与xRy矛盾!xRyR=.,x,y,z,2019/11/26,集合论与图论第8讲,11,定理27(证明(4),(4)UxR|xA=A.证明:(4)A=Ux|xAUxR|xAUA|xA=A.UxR|xA=A.#,x,y,2019/11/26,集合论与图论第8讲,12,同余关系:设n2,3,4,x,yZ,则x与y模n同余(becongruentmodulon)xy(modn)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)关系,6,3,9,8,7,5,4,2,1,10,11,0,2019/11/26,集合论与图论第8讲,13,例11,例11:设A=1,2,3,4,5,8,求R3=|x,yAxy(mod3)的等价类,画出R3的关系图.解:1=4=1,4,2=5=8=2,5,8,3=3.#,1,4,2,5,8,3,2019/11/26,集合论与图论第8讲,14,商集(quotientset),商集:设R是A上等价关系,A/R=xR|xA称为A关于R的商集,简称A的商集.显然UA/R=A.例11(续):A/R3=1,4,2,5,8,3.,2019/11/26,集合论与图论第8讲,15,例12(1),例12(1):设A=a1,a2,an,IA,EA,Rij=IA,都是A上等价关系,求对应的商集,其中ai,ajA,ij.是A上等价关系吗?解:A/IA=a1,a2,anA/EA=a1,a2,anA/Rij=A/IAai,aj-ai,aj.不是A上等价关系(非自反).#,2019/11/26,集合论与图论第8讲,16,划分(partition),划分:设A,AP(A),若A满足(1)A;(2)x,y(x,yAxyxy=)(3)UA=A则称A为A的一个划分,A中元素称为划分块(block).,2019/11/26,集合论与图论第8讲,17,划分(举例),设A1,A2,AnE,则以下都是划分:Ai=Ai,Ai,(i=1,2,n)Aij=AiAj,AiAj,AiAj,AiAj-(i,j=1,2,nij)A12n=A1A2An,A1A2An-1An,A1A2An-.#,2019/11/26,集合论与图论第8讲,18,划分(举例,续),Ai,Ai,2019/11/26,集合论与图论第8讲,19,等价关系与划分是一一对应的,定理28:设A,则(1)R是A上等价关系A/R是A的划分(2)A是A的划分RA是A上等价关系,其中xRAyz(zAxzyz)RA称为由划分A所定义的等价关系(同块关系).#,2019/11/26,集合论与图论第8讲,20,例12(2),例12(2):A=a,b,c,求A上全体等价关系.解:A上不同划分共有5种:,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,R1=EA,R2=IA,R3=IA,R4=IA,R5=IA.#,2019/11/26,集合论与图论第8讲,21,Bell数(Bellnumber),问题:给n个对象分类,共有多少种分法?答案:Bell数Bn=(EricTempleBell,18831960)Stirling子集数(Stirlingsubsetnumber):把n个对象分成k个非空子集的分法个数.递推公式:,2019/11/26,集合论与图论第8讲,22,Stirling子集数,递推公式:,剔除一个,其余分k类,加入一类,其余分k-1类,自成一类,2019/11/26,集合论与图论第8讲,23,第一、二类Stirling数,第一类Stirling数(Stirlingnumberofthefirstkind):s(n,k)第二类Stirling数(Stirlingnumberofthesecondkind):S(n,k)=,2019/11/26,集合论与图论第8讲,24,Bell数表,2019/11/26,集合论与图论第8讲,25,第二类Stirling数表,2019/11/26,集合论与图论第8讲,26,例13,例13:问A=a,b,c,d上有多少种等价关系?解:#,2019/11/26,集合论与图论第8讲,27,划分的加细(refinement),划分的加细:设A和B都是集合A的划分,若A的每个划分块都包含于B的某个划分块中,则称A为B的加细.A为B的加细RARB,2019/11/26,集合论与图论第8讲,28,例14,例14:考虑A=a,b,c上的划分之间的加细.解:,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,加细,加细,加细,加细,加细,加细,#,2019/11/26,集合论与图论第8讲,29,序关系,偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链,2019/11/26,集合论与图论第8讲,30,偏序(partialorder)关系,偏序关系:设RAA且A,若R是自反的,反对称的,传递的,则称R为偏序关系通常用表示偏序关系,读作“小于等于”RxRyxy“严格小于”:xyxyxy偏序集(poset):,是A上偏序关系例子:,2019/11/26,集合论与图论第8讲,31,偏序集,AR=|x,yAxy,=|x,yAxy,AZ+=x|xZx0|=|x,yAx|y,2019/11/26,集合论与图论第8讲,32,偏序集,AP(A),=|x,yAxy设A=a,b,A1=,a,b,A2=a,a,b,A3=P(A)=,a,b,a,b,则1=IA1,2=IA23=IA3,2019/11/26,集合论与图论第8讲,33,偏序集,A,是由A的一些划分组成的集合加细=|x,yx是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,.#,2019/11/26,集合论与图论第8讲,34,哈斯图(Hassediagram),设是偏序集,x,yA可比(comparable):x与y可比xyyx覆盖(cover):y覆盖xxyz(zAxzy)哈斯图:当且仅当y覆盖x时,在x与y之间画无向边,并且x画在y下方,2019/11/26,集合论与图论第8讲,35,例16(1)(2),例16:画出下列偏序关系的哈斯图.(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解:,1,2,4,3,6,9,15,5,10,a,b,c,a,b,a,c,b,c,2019/11/26,集合论与图论第8讲,36,例16(3),例16:画出下列偏序关系的哈斯图.(3),=A1,A2,A3,A4,A5,A6,A=a,b,c,dA1=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解:,A1,A2,A5,A3,A4,A6,#,2019/11/26,集合论与图论第8讲,37,偏序关系中的特殊元素,最大元,最小元极大元,极小元上界,下界最小上界(上确界),最大下界(下确界),2019/11/26,集合论与图论第8讲,38,最大元,最小元,设为偏序集,BA,yB最大元(maximum/greatestelement):y是B的最大元x(xBxy)最小元(minimum/leastelement):y是B的最小元x(xByx),2019/11/26,集合论与图论第8讲,39,最大元,最小元举例(例16(1),例16(1):,A=1,2,3,4,5,6,9,10,15B1=1,2,3,B2=3,5,15,B3=A.B1的最大元是,B1的最小元是1B2的最大元是15,B2的最小元是B3的最大元是,B3的最小元是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2019/11/26,集合论与图论第8讲,40,极大元,极小元,设为偏序集,BA,yB极大元(maximalelement):y是B的极大元x(xByxx=y)极小元(minimalelement):y是B的极小元x(xBxyx=y),2019/11/26,集合论与图论第8讲,41,极大元,极小元举例(例16(1),例16(1):,A=1,2,3,4,5,6,9,10,15B1=1,2,3,B2=3,5,15,B3=A.B1的极大元是2,3,B1的极小元是1B2的极大元是15,B2的极小元是3,5B3的极大元是4,6,9,15,10,B3的极小元是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2019/11/26,集合论与图论第8讲,42,上界,下界,设为偏序集,BA,yA上界(upperbound):y是B的上界x(xBxy)下界(lowerbound):y是B的下界x(xByx),2019/11/26,集合论与图论第8讲,43,上界,下界举例(例16(1),例16(1):,A=1,2,3,4,5,6,9,10,15B1=1,2,3,B2=3,5,15,B3=A.B1的上界是6,B1的下界是1B2的上界是15,B2的下界是1B3的上界是,B3的下界是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2019/11/26,集合论与图论第8讲,44,最小上界,最大下界,设为偏序集,BA最小上界(leastupperbound):设C=y|y是B的上界,C的最小元称为B的最小上界,或上确界.最大下界(greatestlowerbound):设C=y|y是B的下界,C的最大元称为B的最大下界,或下确界.,2019/11/26,集合论与图论第8讲,45,最小上界,最大下界举例(例16(1),例16(1):,A=1,2,3,4,5,6,9,10,15B1=1,2,3,B2=3,5,15,B3=A.B1的最小上界是6,B1的最大下界是1B2的最小上界是15,B2的最大下界是1B3的最小上界是,B3的最大下界是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2019/11/26,集合论与图论第8讲,46,特殊元素比较,2019/11/26,集合论与图论第8讲,47,链(chain),反链(antichain),设为偏序集,BA,链(chain):B是A中的链xy(xByBx与y可比)|B|称为链的长度反链(antichain):B是A中的反链xy(xByBxyx与y不可比)|B|称为反链的长度,2019/11/26,集合论与图论第8讲,48,链,反链(举例),设偏序集如图所示,A=a,b,k.,a,b,c,d,e,f,g,h,i,j,k,B1=a,c,d,e是长为4的链上界e,f,g,h,上确界e下界a,下确界aB2=a,e,h是长为3的链B3=b,g是长为2的链B4=g,h,k是长为3的反链上界,下界,上确界,下确界:无B5=a是长为1的链和反链B6=a,b,g,h既非链,亦非反链,2019/11/26,集合论与图论第8讲,49,定理31,定理31:设为偏序集,A中最长链的长度为n,则(1)A中存在极大元(2)A存在n个划分块的划分,每个划分块都是反链(即A划分成n个互不相交的反链)推论:设为偏序集,若|A|=mn+1,则A中要么存在长度为m+1的反链,要么存在长度为n+1的链.,2019/11/26,集合论与图论第8讲,50,定理31(举例),a,b,c,d,e,f,g,h,i,j,k,最长链长度为6,如B1=a,c,d,e,f,h,B2=a,c,d,e,f,g,A=a,b,k可以划分为A1=a,b,i,c,j,d,e,f,g,h,k,A2=a,b,c,i,d,j,e,k,f,g,h|A|=11=25+1,A中既有长度为2+1=3的反链,也有长度为5+1=6的链,2019/11/26,集合论与图论第8讲,51,定理31(证明(1),定理31:设为偏序集,A中最长链的长度为n,则(1)A中存在极大元证明:(1)设B是A中长度为n的最长链,B有极大元(也是最大元)y,则y也是A的极大元,否则A中还有比y“大”的元素z,B就不是最长链.,2019/11/26,集合论与图论第8讲,52,定理31(证明(2),定理31:设为偏序集,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是满足要求的划分.,2019/11/26,集合论与图论第8讲,53,定理31(证明(2):举例),a,b,c,d,e,f,g,h,i,j,k,最长链长度为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,2019/11/26,集合论与图论第8讲,54,定理31(证明(2)续),证明(续):1A1=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确是所求划分.#,2019/11/26,集合论与图论第8讲,55,定理31推论(证明),推论:设为偏序集,若|A|=mn+1,则A中要么存在长度为m+1的反链,要么存在长度为n+1的链.证明:(反证)假设A中既没有长度为m+1的反链,也没有长度为n+1的链,则按照定理31(2)中要求来划分A,A至多划分成n块,每块至多m个元素,于是A中至多有mn个元素,这与|A|=mn+1矛盾!#,2019/11/26,集合论与图论第8讲,56,全序(totalorder)关系,全序关系:若偏序集满足xy(xAyAx与y可比)则称为全序关系,称为全序集全序关系亦称线序(linearorder)关系例:,2019/11/26,集合论与图论第8讲,57,拟序(quasi-order)关系,拟序关系:设RAA且