SG08离散数学大全-集合与图论

2020/11/2《集合论与图论》第8讲1第8讲等价关系与序关系内容提要等价关系,等价类,商集划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2020/11/2《集合论与图论》第8讲2等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2020/11/2《集合论与图论》第8讲3等价(equivalence)关系定义等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1={x,y|x,yAx与y同年生}R2={x,y|x,yAx与y同姓}R3={x,y|x,yAx的年龄不比y小}R4={x,y|x,yAx与y选修同门课程}R5={x,y|x,yAx的体重比y重}2020/11/2《集合论与图论》第8讲4例9(续)定义自反对称传递等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重2020/11/2《集合论与图论》第8讲5例10例10:设RAA且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)2020/11/2《集合论与图论》第8讲6例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)2020/11/2《集合论与图论》第8讲7等价类(equivalenceclass)等价类:设R是A上等价关系,xA,令[x]R={y|yAxRy},称[x]R为x关于R的等价类,简称x的等价类,简记为[x].等价类性质:[x]R;xRy[x]R=[y]R;xRy[x]R[y]R=;U{[x]R|xA}=A.2020/11/2《集合论与图论》第8讲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|xA}=A.证明:(1)R自反xRxx[x]R[x]R.x2020/11/2《集合论与图论》第8讲9定理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.()同理可证.xyz2020/11/2《集合论与图论》第8讲10定理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,这与xRy矛盾![x]R[y]R=.xyz2020/11/2《集合论与图论》第8讲11定理27(证明(4))(4)U{[x]R|xA}=A.证明:(4)A=U{{x}|xA}U{[x]R|xA}U{A|xA}=A.U{[x]R|xA}=A.#xy2020/11/2《集合论与图论》第8讲12同余关系:设n{2,3,4,…},x,yZ,则x与y模n同余(becongruentmodulon)xy(modn)n|(x-y)x-y=kn(kZ)同余关系是等价关系[0]={kn|kZ},[1]={1+kn|kZ},[2]={2+kn|kZ},…,[n-1]={(n-1)+kn|kZ}.同余(congruence)关系639875421101102020/11/2《集合论与图论》第8讲13例11例11:设A={1,2,3,4,5,8},求R3={x,y|x,yAxy(mod3)}的等价类,画出R3的关系图.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832020/11/2《集合论与图论》第8讲14商集(quotientset)商集:设R是A上等价关系,A/R={[x]R|xA}称为A关于R的商集,简称A的商集.显然UA/R=A.例11(续):A/R3={{1,4},{2,5,8},{3}}.2020/11/2《集合论与图论》第8讲15例12(1)例12(1):设A={a1,a2,…,an},IA,EA,Rij=IA{ai,aj,aj,ai}都是A上等价关系,求对应的商集,其中ai,ajA,ij.是A上等价关系吗?解:A/IA={{a1},{a2},…,{an}}A/EA={{a1,a2,…,an}}A/Rij=A/IA{{ai,aj}}-{{ai},{aj}}.不是A上等价关系(非自反).#2020/11/2《集合论与图论》第8讲16划分(partition)划分:设A,AP(A),若A满足(1)A;(2)x,y(x,yAxyxy=)(3)UA=A则称A为A的一个划分,A中元素称为划分块(block).2020/11/2《集合论与图论》第8讲17划分(举例)设A1,A2,…,AnE,则以下都是划分:Ai={Ai,~Ai},(i=1,2,…,n)Aij={AiAj,~AiAj,Ai~Aj,~Ai~Aj}-{}(i,j=1,2,…,nij)……A12…n={~A1~A2…~An,…,~A1~A2…~An-1An,…A1A2…An}-{}.#2020/11/2《集合论与图论》第8讲18划分(举例,续)Ai~Ai2020/11/2《集合论与图论》第8讲19等价关系与划分是一一对应的定理28:设A,则(1)R是A上等价关系A/R是A的划分(2)A是A的划分RA是A上等价关系,其中xRAyz(zAxzyz)RA称为由划分A所定义的等价关系(同块关系).#2020/11/2《集合论与图论》第8讲20例12(2)例12(2):A={a,b,c},求A上全体等价关系.解:A上不同划分共有5种:abcabcabcabcabcR1=EA,R2=IA{b,cc,b},R3=IA{a,cc,a},R4=IA{a,bb,a},R5=IA.#2020/11/2《集合论与图论》第8讲21Bell数(Bellnumber)问题:给n个对象分类,共有多少种分法?答案:Bell数Bn=(EricTempleBell,1883~1960)Stirling子集数(Stirlingsubsetnumber):把n个对象分成k个非空子集的分法个数.递推公式:.211nnnnknnkkn.1,1,122,11,0021nnCnnnnnnn.111knknkkn2020/11/2《集合论与图论》第8讲22Stirling子集数递推公式:.111knknkkn剔除一个其余分k类加入一类其余分k-1类自成一类2020/11/2《集合论与图论》第8讲23第一、二类Stirling数第一类Stirling数(Stirlingnumberofthefirstkind):s(n,k)第二类Stirling数(Stirlingnumberofthesecondkind):S(n,k)=kn.)1()2)(1(),(0kknkxkxxxxxkns.),()1()2)(1(),(00knknknxknSkxxxxknSx2020/11/2《集合论与图论》第8讲24Bell数表nBnnBn1184,14022921,1473510115,97541511678,570552124,213,59762031327,644,437787714190,899,3222020/11/2《集合论与图论》第8讲25第二类Stirling数表n\k0123456789011012011301314017615011525101601319065151701633013501402118011279661,1701,0502662819012553,0357,7706,9512,64646236110015119,33034,50142,52522,8275,880750452020/11/2《集合论与图论》第8讲26例13例13:问A={a,b,c,d}上有多少种等价关系?解:#.1516711)12(1443424142434CB2020/11/2《集合论与图论》第8讲27划分的加细(refinement)划分的加细:设A和B都是集合A的划分,若A的每个划分块都包含于B的某个划分块中,则称A为B的加细.A为B的加细RARB2020/11/2《集合论与图论》第8讲28例14例14:考虑A={a,b,c}上的划分之间的加细.解:abcabcabcabcabc加细加细加细加细加细加细#2020/11/2《集合论与图论》第8讲29序关系偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2020/11/2《集合论与图论》第8讲30偏序(partialorder)关系偏序关系:设RAA且A,若R是自反的,反对称的,传递的,则称R为偏序关系通常用≼表示偏序关系,读作“小于等于”x,yRxRyx≼y“严格小于”:x≺yx≼yxy偏序集(poset):A,≼,≼是A上偏序关系例子:A,,A,|,A,,,≼加细2020/11/2《集合论与图论》第8讲31偏序集A,,A,,A,|AR={x,y|x,yAxy},={x,y|x,yAxy},AZ+={x|xZx0}|={x,y|x,yAx|y}2020/11/2《集合论与图论》第8讲32偏序集A,AP(A),={x,y|x,yAxy}设A={a,b},A1={,{a},{b}},A2={{a},{a,b}},A3=P(A)={,{a},{b},{a,b}},则1=IA1{,{a},,{b}}2=IA2{{a},{a,b}}3=IA3{,{a},,{b},,{a,b},{a},{a,b},{b},{a,b}}2020/11/2《集合论与图论》第8讲33偏序集,≼加细A,是由A的一些划分组成的集合≼加细={x,y|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,A5}≼1=I1{A2,A1},≼2=I2,≼3=I3{A2,A1,A3,A1,A4,A1,A5,A1,A5,A2,A5,A3,A5,A4}.#2020/11/2《集合