1、2020/9/28,集合論與圖論第8講,1,第8講 等價(jià)關(guān)系與序關(guān)系,內(nèi)容提要 等價(jià)關(guān)系,等價(jià)類,商集 劃分, 第二類Stirling數(shù) 偏序,線序,擬序,良序 哈斯圖 特殊元素: 最?元,極?元,?界,?確界 (反)鏈,2020/9/28,集合論與圖論第8講,2,等價(jià)(equivalence)關(guān)系,定義 同余關(guān)系 等價(jià)類 商集 劃分 劃分的加細(xì) Stirling子集數(shù),2020/9/28,集合論與圖論第8講,3,等價(jià)(equivalence)關(guān)系定義,等價(jià)關(guān)系: 設(shè) RAA 且 A, 若R是自反的, 對(duì)稱的, 傳遞的,則稱R為等價(jià)關(guān)系 例9: 判斷是否等價(jià)關(guān)系(A是某班學(xué)生): R1=|x,

2、yAx與y同年生 R2=|x,yAx與y同姓 R3=|x,yAx的年齡不比y小 R4=|x,yAx與y選修同門課程 R5=|x,yAx的體重比y重,2020/9/28,集合論與圖論第8講,4,例9(續(xù)),2020/9/28,集合論與圖論第8講,5,例10,例10: 設(shè) RAA 且 A, 對(duì)R依次求三種閉包共有6種不同順序, 其中哪些順序一定導(dǎo)致等價(jià)關(guān)系? 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

3、 )=rts( R ) str( R )=srt( R )=rst( R ),2020/9/28,集合論與圖論第8講,6,例10(續(xù)),2020/9/28,集合論與圖論第8講,7,等價(jià)類(equivalence class),等價(jià)類: 設(shè)R是A上等價(jià)關(guān)系,xA,令 xR= y | yA xRy , 稱xR為x關(guān)于R的等價(jià)類, 簡(jiǎn)稱x的等價(jià)類, 簡(jiǎn)記為x. 等價(jià)類性質(zhì): xR ; xRy xR=yR ; xRy xRyR= ; U xR | xA =A.,2020/9/28,集合論與圖論第8講,8,定理27,定理27:設(shè)R是A上等價(jià)關(guān)系,x,yA, (1) xR (2) xRy xR=yR ;

4、(3) xRy xRyR= ; (4) U xR | xA =A. 證明: (1) R自反xRxxxRxR.,x,2020/9/28,集合論與圖論第8講,9,定理27(證明(2),(2) xRy xR=yR ; 證明: (2) 只需證明xRyR和xRyR. () z, zxRxRy zRxxRy zRy zyR . xRyR. () 同理可證.,x,y,z,2020/9/28,集合論與圖論第8講,10,定理27(證明(3),(3) xRy xRyR= ; 證明: (3) (反證) 假設(shè)z, zxRyR, 則 zxRyR zRxzRy xRzzRy xRy, 這與xRy矛盾! xRyR=.,x,

5、y,z,2020/9/28,集合論與圖論第8講,11,定理27(證明(4),(4) U xR | xA = A. 證明: (4) A=U x | xA U xR | xA U A | xA =A. U xR | xA = A. #,x,y,2020/9/28,集合論與圖論第8講,12,同余關(guān)系: 設(shè)n2,3,4, x,yZ,則 x與y模n同余(be congruent modulo n) xy(mod n) n|(x-y) x-y=kn (kZ) 同余關(guān)系是等價(jià)關(guān)系 0 = kn|kZ, 1 = 1+kn|kZ, 2 = 2+kn|kZ, n-1=(n-1)+kn|kZ.,同余(congrue

6、nce)關(guān)系,6,3,9,8,7,5,4,2,1,10,11,0,2020/9/28,集合論與圖論第8講,13,例11,例11: 設(shè) A=1,2,3,4,5,8, 求 R3 = | x,yA xy(mod 3) 的等價(jià)類, 畫出R3的關(guān)系圖. 解: 1=4=1,4, 2=5=8=2,5,8, 3=3. #,1,4,2,5,8,3,2020/9/28,集合論與圖論第8講,14,商集(quotient set),商集: 設(shè)R是A上等價(jià)關(guān)系, A/R = xR | xA 稱為A關(guān)于R的商集, 簡(jiǎn)稱A的商集. 顯然 U A/R = A. 例11(續(xù)): A/R3 = 1,4, 2,5,8, 3 .,2

7、020/9/28,集合論與圖論第8講,15,例12(1),例12(1): 設(shè)A=a1,a2,an, IA, EA, Rij=IA, 都是A上等價(jià)關(guān)系, 求對(duì)應(yīng)的商集, 其中ai,ajA, ij. 是A上等價(jià)關(guān)系嗎? 解: A/IA= a1, a2, an A/EA= a1,a2,an A/Rij= A/IAai,aj - ai,aj. 不是A上等價(jià)關(guān)系(非自反). #,2020/9/28,集合論與圖論第8講,16,劃分(partition),劃分: 設(shè)A, AP(A),若A滿足 (1) A ; (2) x,y( x,yA xy xy= ) (3) UA = A 則稱A為A的一個(gè)劃分, A中元素

8、稱為劃分塊(block).,2020/9/28,集合論與圖論第8講,17,劃分(舉例),設(shè) 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-. #,2020/9/28,集合論與圖論第8講,18,劃分(舉例,續(xù)),Ai,Ai,2020/9/28,集合論與圖論第8講,19,等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的,定理28: 設(shè)A, 則 (1) R是A上等價(jià)關(guān)系 A/R是A的劃分 (2) A是A的劃分 RA

9、是A上等價(jià)關(guān)系,其中 xRAy z(zA xz yz) RA稱為由劃分A 所定義的等價(jià)關(guān)系(同塊關(guān)系). #,2020/9/28,集合論與圖論第8講,20,例12(2),例12(2): A=a,b,c, 求A上全體等價(jià)關(guān)系. 解: 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. #,2020/9/28,集合論與圖論第8講,21,Bell數(shù)(Bell number),問題: 給n個(gè)對(duì)象分類, 共有多少種分法? 答案: Bell數(shù) Bn= (Eric Temple Bell, 1883196

10、0) Stirling子集數(shù)(Stirling subset number) : 把n個(gè)對(duì)象分成k個(gè)非空子集的分法個(gè)數(shù). 遞推公式:,2020/9/28,集合論與圖論第8講,22,Stirling子集數(shù),遞推公式:,剔除一個(gè),其余分k類,加入一類,其余分k-1類,自成一類,2020/9/28,集合論與圖論第8講,23,第一、二類Stirling數(shù),第一類Stirling數(shù)(Stirling number of the first kind): s(n,k) 第二類Stirling數(shù)(Stirling number of the second kind): S(n,k)=,2020/9/28,集

11、合論與圖論第8講,24,Bell數(shù)表,2020/9/28,集合論與圖論第8講,25,第二類Stirling數(shù)表,2020/9/28,集合論與圖論第8講,26,例13,例13: 問A=a,b,c,d上有多少種等價(jià)關(guān)系? 解: #,2020/9/28,集合論與圖論第8講,27,劃分的加細(xì)(refinement),劃分的加細(xì): 設(shè)A和B都是集合A的劃分, 若A的每個(gè)劃分塊都包含于B的某個(gè)劃分塊中, 則稱A為B的加細(xì). A為B的加細(xì) RARB,2020/9/28,集合論與圖論第8講,28,例14,例14: 考慮A=a,b,c上的劃分之間的加細(xì). 解:,a,b,c,a,b,c,a,b,c,a,b,c,a

12、,b,c,加細(xì),加細(xì),加細(xì),加細(xì),加細(xì),加細(xì),#,2020/9/28,集合論與圖論第8講,29,序關(guān)系,偏序,線序,擬序,良序 哈斯圖 特殊元素: 最?元, 極?元, ?界, ?確界 (反)鏈,2020/9/28,集合論與圖論第8講,30,偏序(partial order)關(guān)系,偏序關(guān)系: 設(shè) RAA 且 A, 若R是自反的, 反對(duì)稱的, 傳遞的, 則稱R為偏序關(guān)系 通常用表示偏序關(guān)系,讀作“小于等于” R xRy xy “嚴(yán)格小于”: xy xy xy 偏序集(poset): , 是A上偏序關(guān)系 例子: , , , ,2020/9/28,集合論與圖論第8講,31,偏序集, , ,AR = |

13、 x,yA xy , = | x,yA xy , AZ+= x | xZ x0 | = | x,yA x|y ,2020/9/28,集合論與圖論第8講,32,偏序集,AP(A), = | x,yA xy 設(shè)A=a,b, A1=,a,b, A2=a,a,b, A3=P(A)=,a,b,a,b,則 1 = IA1 , 2 = IA2 3 = IA3 , , , ,2020/9/28,集合論與圖論第8講,33,偏序集,A, 是由A的一些劃分組成的集合 加細(xì) = | x,y x是y的加細(xì) 設(shè)A=a,b,c, A1=a,b,c,A2=a,b,c, A3=b,a,c,A4=c,a,b,A5=a,b,c 取

14、1=A1,A2,2=A2,A3,3=A1,A2,A3,A4,A5 1 = I1 , 2 = I2, 3 = I3 , , ,. #,2020/9/28,集合論與圖論第8講,34,哈斯圖(Hasse diagram),設(shè)是偏序集, x,yA 可比(comparable): x與y可比 xy yx 覆蓋(cover): y覆蓋x xy z( zA xzy ) 哈斯圖: 當(dāng)且僅當(dāng)y覆蓋x時(shí),在x與y之間畫無向邊, 并且x畫在y下方,2020/9/28,集合論與圖論第8講,35,例16(1)(2),例16: 畫出下列偏序關(guān)系的哈斯圖. (1) , A=1,2,3,4,5,6,9,10,15 (2) ,

15、 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,2020/9/28,集合論與圖論第8講,36,例16(3),例16: 畫出下列偏序關(guān)系的哈斯圖. (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 解:,A1,A2,A5,A3,A4,A6,#,2020/9/28,集合論與圖論第

16、8講,37,偏序關(guān)系中的特殊元素,最大元, 最小元 極大元, 極小元 上界, 下界 最小上界(上確界), 最大下界(下確界),2020/9/28,集合論與圖論第8講,38,最大元, 最小元,設(shè)為偏序集, BA, yB 最大元(maximum/greatest element): y是B的最大元 x( xB xy ) 最小元(minimum/least element): y是B的最小元 x( xB yx ),2020/9/28,集合論與圖論第8講,39,最大元, 最小元舉例(例16(1),例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15,

17、B3=A. B1的最大元是, B1的最小元是1 B2的最大元是15, B2的最小元是 B3的最大元是, B3的最小元是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2020/9/28,集合論與圖論第8講,40,極大元,極小元,設(shè)為偏序集, BA, yB 極大元(maximal element): y是B的極大元 x( xB yx x=y ) 極小元(minimal element): y是B的極小元 x( xB xy x=y ),2020/9/28,集合論與圖論第8講,41,極大元,極小元舉例(例16(1),例16(1): , A=1,2,3,4,5,6,

18、9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的極大元是2,3, B1的極小元是1 B2的極大元是15, B2的極小元是3,5 B3的極大元是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,2020/9/28,集合論與圖論第8講,42,上界, 下界,設(shè)為偏序集, BA, yA 上界(upper bound): y是B的上界 x( xB xy ) 下界(lower bound): y是B的下界 x( xB yx ),2020/9/28,集合論與圖論第8講,43,上界, 下界舉例(例16(1),

19、例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的下界是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2020/9/28,集合論與圖論第8講,44,最小上界, 最大下界,設(shè)為偏序集, BA 最小上界(least upper bound): 設(shè) C = y | y是B的上界 , C的最小元稱為B的最小上界, 或上確界. 最大下界(greatest lower bound): 設(shè) C = y | y是B

20、的下界 , C的最大元稱為B的最大下界, 或下確界.,2020/9/28,集合論與圖論第8講,45,最小上界,最大下界舉例(例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的最大下界是1,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2020/9/28,集合論與圖論第8講,46,特殊元素比較,2020/9/28,集合論與圖論第8講,47,鏈(chain), 反鏈(ant

21、ichain),設(shè)為偏序集, BA, 鏈(chain): B是A中的鏈 xy( xByB x與y可比 ) |B|稱為鏈的長(zhǎng)度 反鏈(antichain): B是A中的反鏈 xy( xByBxy x與y不可比 ) |B|稱為反鏈的長(zhǎng)度,2020/9/28,集合論與圖論第8講,48,鏈, 反鏈(舉例),設(shè)偏序集如圖所示, A=a,b,k.,a,b,c,d,e,f,g,h,i,j,k,B1=a,c,d,e是長(zhǎng)為4的鏈 上界e,f,g,h, 上確界e 下界a, 下確界a B2=a,e,h是長(zhǎng)為3的鏈 B3=b,g是長(zhǎng)為2的鏈 B4=g,h,k是長(zhǎng)為3的反鏈 上界,下界,上確界,下確界: 無 B5=a是

22、長(zhǎng)為1的鏈和反鏈 B6=a,b,g,h既非鏈,亦非反鏈,2020/9/28,集合論與圖論第8講,49,定理31,定理31: 設(shè)為偏序集, A中最長(zhǎng)鏈的長(zhǎng)度為n, 則 (1) A中存在極大元 (2) A存在n個(gè)劃分塊的劃分, 每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈) 推論: 設(shè)為偏序集, 若|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈, 要么存在長(zhǎng)度為n+1的鏈.,2020/9/28,集合論與圖論第8講,50,定理31(舉例),a,b,c,d,e,f,g,h,i,j,k,最長(zhǎng)鏈長(zhǎng)度為6, 如 B1=a,c,d,e,f,h, B2=a,c,d,e,f,g, A=a,b,k可以劃分為

23、 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中既有長(zhǎng)度為2+1=3的反鏈, 也有長(zhǎng)度為5+1=6的鏈,2020/9/28,集合論與圖論第8講,51,定理31(證明(1),定理31: 設(shè)為偏序集, A中最長(zhǎng)鏈的長(zhǎng)度為n, 則 (1) A中存在極大元 證明: (1) 設(shè)B是A中長(zhǎng)度為n的最長(zhǎng)鏈, B有極大元(也是最大元)y, 則y也是A的極大元, 否則A中還有比y“大”的元素z, B就不是最長(zhǎng)鏈.,2020/9/28,集合論與圖論第8講,52,定理31(證明(2),定理31: 設(shè)為

24、偏序集, A中最長(zhǎng)鏈的長(zhǎng)度為n, 則 (2) A存在n個(gè)劃分塊的劃分, 每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈) 證明: (2) A1 = x | x是A中的極大元 , A2 = x | x是(A-A1)中的極大元 , An = x | x是(A-A1-An-1)中的極大元 , 則 A = A1, A2, An 是滿足要求的劃分.,2020/9/28,集合論與圖論第8講,53,定理31(證明(2):舉例),a,b,c,d,e,f,g,h,i,j,k,最長(zhǎng)鏈長(zhǎng)度為6, A1 = g, h, k , A2 = f, j , A3 = e, i , A4 = d , A5 = c , A6

25、 = a, b , A = a,b, c, d, e,i, f,j, g,h,k ,2020/9/28,集合論與圖論第8講,54,定理31(證明(2)續(xù)),證明(續(xù)): 1 A1 = x | x是A中的極大元 , 極大元互相之間不可比, 所以A1是反鏈, 同理A2,An都是反鏈. 2 顯然A1,A2,An互不相交. 3 最長(zhǎng)鏈上的元素分屬A1,A2,An, 所以A1,A2,An都非空. 4 假設(shè)zA-A1-An,則最長(zhǎng)鏈上的元素加上z就是長(zhǎng)度為n+1的鏈, 矛盾! 所以A=A1A2An. 綜上所述, A= A1,A2,An 確是所求劃分. #,2020/9/28,集合論與圖論第8講,55,定理

26、31推論(證明),推論: 設(shè)為偏序集, 若|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈, 要么存在長(zhǎng)度為n+1的鏈. 證明: (反證)假設(shè)A中既沒有長(zhǎng)度為m+1的反鏈, 也沒有長(zhǎng)度為n+1的鏈, 則按照定理31(2)中要求來劃分A, A至多劃分成n塊, 每塊至多m個(gè)元素, 于是A中至多有mn個(gè)元素, 這與|A|=mn+1矛盾! #,2020/9/28,集合論與圖論第8講,56,全序(total order)關(guān)系,全序關(guān)系: 若偏序集滿足 xy( xAyA x與y可比) 則稱為全序關(guān)系, 稱為全序集 全序關(guān)系亦稱線序(linear order)關(guān)系 例: , ,2020/9/28,集合論與圖論第8講,57,擬序(quasi-order)關(guān)系,擬