北大離散數(shù)學(xué)08

2024/11/5《集合論與圖論》第8講1第8講等價(jià)關(guān)系與序關(guān)系內(nèi)容提要等價(jià)關(guān)系,等價(jià)類,商集劃分,第二類Stirling數(shù)偏序,線序,擬序,良序哈斯圖特殊元素:最?元,極?元,?界,?確界(反)鏈2024/11/5《集合論與圖論》第8講2等價(jià)(equivalence)關(guān)系定義同余關(guān)系等價(jià)類商集劃分劃分的加細(xì)Stirling子集數(shù)2024/11/5《集合論與圖論》第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,y>|x,yAx與y同年生}R2={<x,y>|x,yAx與y同姓}R3={<x,y>|x,yAx的年齡不比y小}R4={<x,y>|x,yAx與y選修同門課程}R5={<x,y>|x,yAx的體重比y重}2024/11/5《集合論與圖論》第8講4例9(續(xù))定義自反對(duì)稱傳遞等價(jià)關(guān)系R1x與y同年生

R2x與y同姓

R3x的年齡不比y小

R4x與y選修同門課程

R5x的體重比y重

2024/11/5《集合論與圖論》第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)=rts(R)str(R)=srt(R)=rst(R)2024/11/5《集合論與圖論》第8講6例10(續(xù))tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反

對(duì)稱

傳遞

等價(jià)關(guān)系(等價(jià)閉包)

2024/11/5《集合論與圖論》第8講7等價(jià)類(equivalenceclass)等價(jià)類:設(shè)R是A

上等價(jià)關(guān)系,

xA,令[x]R={y|yAxRy},稱[x]R為x關(guān)于R的等價(jià)類,簡(jiǎn)稱x的等價(jià)類,簡(jiǎn)記為[x].等價(jià)類性質(zhì):[x]R;xRy[x]R=[y]R;xRy[x]R[y]R=;U{[x]R|xA}=A.2024/11/5《集合論與圖論》第8講8定理27定理27:設(shè)R是A

上等價(jià)關(guān)系,

x,yA,(1)[x]R

(2)xRy[x]R=[y]R;(3)xRy[x]R[y]R=;(4)U{[x]R|xA}=A.證明:(1)R自反xRxx

[x]R

[x]R.x2024/11/5《集合論與圖論》第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

zRyz[y]R

.

[x]R[y]R.(

)同理可證.xyz2024/11/5《集合論與圖論》第8講10定理27(證明(3))(3)xRy[x]R[y]R=;證明:(3)(反證)假設(shè)

z,z[x]R

[y]R,則z[x]R

[y]R

zRx

zRy

xRz

zRy

xRy,這與xRy矛盾![x]R[y]R=.xyz2024/11/5《集合論與圖論》第8講11定理27(證明(4))(4)U{[x]R|xA}=A.證明:(4)A=U{{x}|xA}U{[x]R

|xA}U{A

|xA}=A.

U{[x]R|xA}=A.#xy2024/11/5《集合論與圖論》第8講12同余關(guān)系:設(shè)n{2,3,4,…},x,yZ,則x與y模n同余(becongruentmodulon)

xy(modn)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}.同余(congruence)關(guān)系

639875421101102024/11/5《集合論與圖論》第8講13例11例11:設(shè)A={1,2,3,4,5,8},求R3={<x,y>|x,yAxy(mod3)}的等價(jià)類,畫出R3的關(guān)系圖.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832024/11/5《集合論與圖論》第8講14商集(quotientset)商集:設(shè)R是A

上等價(jià)關(guān)系,A/R={[x]R|xA}稱為A關(guān)于R的商集,簡(jiǎn)稱A的商集.顯然UA/R=A.例11(續(xù)):A/R3

={{1,4},{2,5,8},{3}}.2024/11/5《集合論與圖論》第8講15例12(1)例12(1):設(shè)A={a1,a2,…,an},IA,EA,Rij=IA{<ai,aj>,<aj,ai>}都是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/IA{{ai,aj}}-{{ai},{aj}}.

不是A上等價(jià)關(guān)系(非自反).#2024/11/5《集合論與圖論》第8講16劃分(partition)劃分:設(shè)A,AP(A),若A滿足(1)

A;(2)x,y(x,yAxyxy=)(3)UA=A則稱A為A的一個(gè)劃分,A中元素稱為劃分塊(block).2024/11/5《集合論與圖論》第8講17劃分(舉例)設(shè)A1,A2,…,AnE,則以下都是劃分:

Ai={Ai,~Ai},(i=1,2,…,n)

Aij={Ai

Aj,~Ai

Aj,Ai~Aj,

~Ai~Aj}-{

}(i,j=1,2,…,nij)……

A12…n={~A1~A2…~An,…,~A1~A2…~An-1

An,…A1

A2…An}-{

}.#2024/11/5《集合論與圖論》第8講18劃分(舉例,續(xù))Ai~Ai2024/11/5《集合論與圖論》第8講19等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的定理28:設(shè)A,則(1)R是A上等價(jià)關(guān)系

A/R是A的劃分(2)A是A的劃分

RA是A上等價(jià)關(guān)系,其中xRAy

z(z

A

x

z

y

z)RA稱為由劃分A

所定義的等價(jià)關(guān)系(同塊關(guān)系).#2024/11/5《集合論與圖論》第8講20例12(2)例12(2):A={a,b,c},求A上全體等價(jià)關(guān)系.解:A上不同劃分共有5種:abcabcabcabcabcR1=EA,R2=IA{<b,c><c,b>},R3=IA{<a,c><c,a>},R4=IA{<a,b><b,a>},R5=IA.#2024/11/5《集合論與圖論》第8講21Bell數(shù)(Bellnumber)問(wèn)題:給n個(gè)對(duì)象分類,共有多少種分法?答案:Bell數(shù)Bn=

(EricTempleBell,1883~1960)Stirling子集數(shù)(Stirlingsubsetnumber):把n個(gè)對(duì)象分成k個(gè)非空子集的分法個(gè)數(shù).

遞推公式:2024/11/5《集合論與圖論》第8講22Stirling子集數(shù)遞推公式:剔除一個(gè)其余分k類加入一類其余分k-1類自成一類2024/11/5《集合論與圖論》第8講23第一、二類Stirling數(shù)第一類Stirling數(shù)(Stirlingnumberofthefirstkind):s(n,k)

第二類Stirling數(shù)(Stirlingnumberofthesecondkind):S(n,k)=2024/11/5《集合論與圖論》第8講24Bell數(shù)表nBn

nBn1184,14022921,1473510115,97541511678,570552124,213,59762031327,644,437787714190,899,3222024/11/5《集合論與圖論》第8講25第二類Stirling數(shù)表n\k0123456789011012011301314017615011525101601319065151701633013501402118011279661,1701,0502662819012553,0357,7706,9512,64646236110015119,33034,50142,52522,8275,880750452024/11/5《集合論與圖論》第8講26例13例13:問(wèn)A={a,b,c,d}上有多少種等價(jià)關(guān)系?解:#2024/11/5《集合論與圖論》第8講27劃分的加細(xì)(refinement)劃分的加細(xì):設(shè)A和B都是集合A的劃分,若A的每個(gè)劃分塊都包含于B的某個(gè)劃分塊中,則稱A為B的加細(xì).

A為B的加細(xì)

RA

RB

2024/11/5《集合論與圖論》第8講28例14例14:考慮A={a,b,c}上的劃分之間的加細(xì).解:abcabcabcabcabc加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)#2024/11/5《集合論與圖論》第8講29序關(guān)系偏序,線序,擬序,良序哈斯圖特殊元素:最?元,極?元,?界,?確界(反)鏈2024/11/5《集合論與圖論》第8講30偏序(partialorder)關(guān)系偏序關(guān)系:設(shè)RAA且A,若R是自反的,反對(duì)稱的,傳遞的,則稱R為偏序關(guān)系通常用?表示偏序關(guān)系,讀作“小于等于”<x,y>RxRyx?y“嚴(yán)格小于”:x?yx?y

x

y偏序集(poset):<A,?>,?是A上偏序關(guān)系例子:<A,>,<A,|>,<A,>,<,?加細(xì)>2024/11/5《集合論與圖論》第8講31偏序集<A,>,<A,

>,<A,|>

AR

={<x,y>|x,yAx

y},

={<x,y>|x,yAx

y},

AZ+={x|xZx>0}|={<x,y>|x,yAx|y}2024/11/5《集合論與圖論》第8講32偏序集<A,>AP(A),

={<x,y>|x,y

Ax

y}設(shè)A={a,b},A1={,{a},},A2={{a},{a,b}},A3=P(A)={,{a},,{a,b}},則

1=IA1{<,{a}>,<,>}

2=IA2{<{a},{a,b}>}

3=IA3{<,{a}>,<,>,<,{a,b}>,<{a},{a,b}>,<,{a,b}>}2024/11/5《集合論與圖論》第8講33偏序集<,?加細(xì)>A,是由A的一些劃分組成的集合?加細(xì)

={<x,y>|x,y

x是y的加細(xì)}設(shè)A={a,b,c},A1={{a,b,c}},A2={{a},{b,c}},A3={,{a,c}},A4={{c},{a,b}},A5={{a},,{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>}.#2024/11/5《集合論與圖論》第8講34哈斯圖(Hassediagram)設(shè)<A,?>是偏序集,x,yA可比(comparable):x與y可比

x?yy?x覆蓋(cover):y覆蓋x

x?y

z(zAx?z?y)哈斯圖:當(dāng)且僅當(dāng)y覆蓋x時(shí),在x與y之間畫無(wú)向邊,并且x畫在y下方2024/11/5《集合論與圖論》第8講35例16(1)(2)例16:畫出下列偏序關(guān)系的哈斯圖.(1)<A,|>,A={1,2,3,4,5,6,9,10,15}(2)<A,>,A={a,b,c},AP(A),A={,{a},,{c},{a,b},{b,c},{a,c}}解:12436915510

{a}{c}{a,b}{a,c}{b,c}2024/11/5《集合論與圖論》第8講36例16(3)例16:畫出下列偏序關(guān)系的哈斯圖.(3)<,?加細(xì)>,={A1,A2,A3,A4,A5,A6},A={a,b,c,d}A1={{a},,{c},qhzqbdq},A2={{a,b},{c,d}},A3={{a,c},{b,d}},A4={{a},{b,c,d}},A5={{a},,{c,d}},A6={{a,b,c,d}}解:A1A2A5A3A4A6#2024/11/5《集合論與圖論》第8講37偏序關(guān)系中的特殊元素最大元,最小元極大元,極小元上界,下界最小上界(上確界),最大下界(下確界)2024/11/5《集合論與圖論》第8講38最大元,最小元設(shè)<A,?>為偏序集,BA,yB最大元(maximum/greatestelement):y是B的最大元

x(xBx?y)最小元(minimum/leastelement):y是B的最小元

x(xBy?x)2024/11/5《集合論與圖論》第8講39最大元,最小元舉例(例16(1))例16(1):<A,|>,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的最小元是{1}12436915510124369155102024/11/5《集合論與圖論》第8講40極大元,極小元設(shè)<A,?>為偏序集,BA,yB極大元(maximalelement):y是B的極大元

x(xBy?xx=y)極小元(minimalelement):y是B的極小元

x(xBx?yx=y)2024/11/5《集合論與圖論》第8講41極大元,極小元舉例(例16(1))例16(1):<A,|>,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,5}B3的極大元是{4,6,9,15,10},B3的極小元是{1}12436915510124369155102024/11/5《集合論與圖論》第8講42上界,下界設(shè)<A,?>為偏序集,BA,yA上界(upperbound):y是B的上界

x(xBx?y)下界(lowerbound):y是B的下界

x(xBy?x)2024/11/5《集合論與圖論》第8講43上界,下界舉例(例16(1))例16(1):<A,|>,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}12436915510124369155102024/11/5《集合論與圖論》第8講44最小上界,最大下界設(shè)<A,?>為偏序集,BA最小上界(leastupperbound):設(shè)C={y|y是B的上界},C的最小元稱為B的最小上界,或上確界.最大下界(greatestlowerbound):設(shè)C={y|y是B的下界},C的最大元稱為B的最大下界,或下確界.2024/11/5《集合論與圖論》第8講45最小上界,最大下界舉例(例16(1))例16(1):<A,|>,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}12436915510124369155102024/11/5《集合論與圖論》第8講46特殊元素比較存在(B非空有窮)存在(B無(wú)窮)唯一

B最大元

(表示不一定)

最小元

極大元

(表示一定)

<Z,>,B=Z

極小元

上界

下界

上確界

下確界

2024/11/5《集合論與圖論》第8講47鏈(chain),反鏈(antichain)設(shè)<A,?>為偏序集,BA,鏈(chain):B是A中的鏈

xy(

xByBx與y可比)|B|稱為鏈的長(zhǎng)度反鏈(antichain):B是A中的反鏈

xy(

xByBxy

x與y不可比)

|B|稱為反鏈的長(zhǎng)度2024/11/5《集合論與圖論》第8講48鏈,反鏈(舉例)設(shè)偏序集<A,?>如圖所示,A={a,b,…,k}.abcdefghijkB1={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的反鏈上界,下界,上確界,下確界:無(wú)B5={a}是長(zhǎng)為1的鏈和反鏈B6={a,b,g,h}既非鏈,亦非反鏈2024/11/5《集合論與圖論》第8講49定理31定理31:設(shè)<A,?>為偏序集,A中最長(zhǎng)鏈的長(zhǎng)度為n,則(1)A中存在極大元(2)A存在n個(gè)劃分塊的劃分,每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈)推論:設(shè)<A,?>為偏序集,若|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈,要么存在長(zhǎng)度為n+1的鏈.2024/11/5《集合論與圖論》第8講50定理31(舉例)abcdefghijk最長(zhǎng)鏈長(zhǎng)度為6,如B1={a,c,d,e,f,h},B2={a,c,d,e,f,g},A={a,b,…,k}可以劃分為A

1={{a,b,i},{c,j},rcfuitv,{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的鏈2024/11/5《集合論與圖論》第8講51定理31(證明(1))定理31:設(shè)<A,?>為偏序集,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)鏈.2024/11/5《集合論與圖論》第8講52定理31(證明(2))定理31:設(shè)<A,?>為偏序集,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}是滿足要求的劃分.2024/11/5《集合論與圖論》第8講53定理31(證明(2):舉例)abcdefghijk最長(zhǎng)鏈長(zhǎng)度為6,A1={g,h,k},A2={f,j},A3={e,i},A4=fyxhcip,A5={c},A6={a,b},A={{a,b},{c},tqbsfig,{e,i},{f,j},{g,h,k}}2024/11/5《集合論與圖論》第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è)z

A-A1-…-An,則最長(zhǎng)鏈上的元素加上z就是長(zhǎng)度為n+1的鏈,矛盾!所以A=A1

A2

…

An.綜上所述,A={A1,A2,…,An}確是所求劃分.#2024/11/5《集合論與圖論》第8講55定理31推論(證明)推論:設(shè)<A,?>為偏序集,若|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈,要么存在長(zhǎng)度為n+1的鏈.證明:(反證)假設(shè)A中既沒(méi)有長(zhǎng)度為m+1的反鏈,也沒(méi)有長(zhǎng)度為n+1的鏈,則按照定理31(2)中要求來(lái)劃分A,A至多劃分成n塊,每塊至多m個(gè)元素,于是A中至多有mn個(gè)元素,這與|A|=mn+1矛盾!#2024/11/5《集合論與圖論》第8講56全序(totalorder)關(guān)系全序關(guān)系:若偏序集<A,?>滿足xy(xAyAx與