北大离散数学08

2024/11/5《集合论与图论》第8讲1第8讲等价关系与序关系内容提要等价关系,等价类,商集划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2024/11/5《集合论与图论》第8讲2等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2024/11/5《集合论与图论》第8讲3等价(equivalence)关系定义等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):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(续)定义自反对称传递等价关系R1x与y同年生

R2x与y同姓

R3x的年龄不比y小

R4x与y选修同门课程

R5x的体重比y重

2024/11/5《集合论与图论》第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)2024/11/5《集合论与图论》第8讲6例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反

对称

传递

等价关系(等价闭包)

2024/11/5《集合论与图论》第8讲7等价类(equivalenceclass)等价类:设R是A

上等价关系,

xA,令[x]R={y|yAxRy},称[x]R为x关于R的等价类,简称x的等价类,简记为[x].等价类性质:[x]R;xRy[x]R=[y]R;xRy[x]R[y]R=;U{[x]R|xA}=A.2024/11/5《集合论与图论》第8讲8定理27定理27:设R是A

上等价关系,

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)(反证)假设

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同余关系:设n{2,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)关系

639875421101102024/11/5《集合论与图论》第8讲13例11例11:设A={1,2,3,4,5,8},求R3={<x,y>|x,yAxy(mod3)}的等价类,画出R3的关系图.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832024/11/5《集合论与图论》第8讲14商集(quotientset)商集:设R是A

上等价关系,A/R={[x]R|xA}称为A关于R的商集,简称A的商集.显然UA/R=A.例11(续):A/R3

={{1,4},{2,5,8},{3}}.2024/11/5《集合论与图论》第8讲15例12(1)例12(1):设A={a1,a2,…,an},IA,EA,Rij=IA{<ai,aj>,<aj,ai>}都是A上等价关系,求对应的商集,其中ai,ajA,ij.是A上等价关系吗?解:A/IA={{a1},{a2},…,{an}}A/EA={{a1,a2,…,an}}A/Rij=A/IA{{ai,aj}}-{{ai},{aj}}.

不是A上等价关系(非自反).#2024/11/5《集合论与图论》第8讲16划分(partition)划分:设A,AP(A),若A满足(1)

A;(2)x,y(x,yAxyxy=)(3)UA=A则称A为A的一个划分,A中元素称为划分块(block).2024/11/5《集合论与图论》第8讲17划分(举例)设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划分(举例,续)Ai~Ai2024/11/5《集合论与图论》第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

所定义的等价关系(同块关系).#2024/11/5《集合论与图论》第8讲20例12(2)例12(2):A={a,b,c},求A上全体等价关系.解: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数(Bellnumber)问题:给n个对象分类,共有多少种分法?答案:Bell数Bn=

(EricTempleBell,1883~1960)Stirling子集数(Stirlingsubsetnumber):把n个对象分成k个非空子集的分法个数.

递推公式:2024/11/5《集合论与图论》第8讲22Stirling子集数递推公式:剔除一个其余分k类加入一类其余分k-1类自成一类2024/11/5《集合论与图论》第8讲23第一、二类Stirling数第一类Stirling数(Stirlingnumberofthefirstkind):s(n,k)

第二类Stirling数(Stirlingnumberofthesecondkind):S(n,k)=2024/11/5《集合论与图论》第8讲24Bell数表nBn

nBn1184,14022921,1473510115,97541511678,570552124,213,59762031327,644,437787714190,899,3222024/11/5《集合论与图论》第8讲25第二类Stirling数表n\k0123456789011012011301314017615011525101601319065151701633013501402118011279661,1701,0502662819012553,0357,7706,9512,64646236110015119,33034,50142,52522,8275,880750452024/11/5《集合论与图论》第8讲26例13例13:问A={a,b,c,d}上有多少种等价关系?解:#2024/11/5《集合论与图论》第8讲27划分的加细(refinement)划分的加细:设A和B都是集合A的划分,若A的每个划分块都包含于B的某个划分块中,则称A为B的加细.

A为B的加细

RA

RB

2024/11/5《集合论与图论》第8讲28例14例14:考虑A={a,b,c}上的划分之间的加细.解:abcabcabcabcabc加细加细加细加细加细加细#2024/11/5《集合论与图论》第8讲29序关系偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2024/11/5《集合论与图论》第8讲30偏序(partialorder)关系偏序关系:设RAA且A,若R是自反的,反对称的,传递的,则称R为偏序关系通常用≼表示偏序关系,读作“小于等于”<x,y>RxRyx≼y“严格小于”:x≺yx≼y

x

y偏序集(poset):<A,≼>,≼是A上偏序关系例子:<A,>,<A,|>,<A,>,<,≼加细>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}设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}>}2024/11/5《集合论与图论》第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>}.#2024/11/5《集合论与图论》第8讲34哈斯图(Hassediagram)设<A,≼>是偏序集,x,yA可比(comparable):x与y可比

x≼yy≼x覆盖(cover):y覆盖x

x≺y

z(zAx≺z≺y)哈斯图:当且仅当y覆盖x时,在x与y之间画无向边,并且x画在y下方2024/11/5《集合论与图论》第8讲35例16(1)(2)例16:画出下列偏序关系的哈斯图.(1)<A,|>,A={1,2,3,4,5,6,9,10,15}(2)<A,>,A={a,b,c},AP(A),A={,{a},{b},{c},{a,b},{b,c},{a,c}}解:12436915510

{a}{b}{c}{a,b}{a,c}{b,c}2024/11/5《集合论与图论》第8讲36例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#2024/11/5《集合论与图论》第8讲37偏序关系中的特殊元素最大元,最小元极大元,极小元上界,下界最小上界(上确界),最大下界(下确界)2024/11/5《集合论与图论》第8讲38最大元,最小元设<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极大元,极小元设<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上界,下界设<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最小上界,最大下界设<A,≼>为偏序集,BA最小上界(leastupperbound):设C={y|y是B的上界},C的最小元称为B的最小上界,或上确界.最大下界(greatestlowerbound):设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无穷)唯一

B最大元

(表示不一定)

最小元

极大元

(表示一定)

<Z,>,B=Z

极小元

上界

下界

上确界

下确界

2024/11/5《集合论与图论》第8讲47链(chain),反链(antichain)设<A,≼>为偏序集,BA,链(chain):B是A中的链

xy(

xByBx与y可比)|B|称为链的长度反链(antichain):B是A中的反链

xy(

xByBxy

x与y不可比)

|B|称为反链的长度2024/11/5《集合论与图论》第8讲48链,反链(举例)设偏序集<A,≼>如图所示,A={a,b,…,k}.abcdefghijkB1={a,c,d,e}是长为4的链上界{e,f,g,h},上确界{e}

下界{a},下确界{a}B2={a,e,h}是长为3的链B3={b,g}是长为2的链B4={g,h,k}是长为3的反链上界,下界,上确界,下确界:无B5={a}是长为1的链和反链B6={a,b,g,h}既非链,亦非反链2024/11/5《集合论与图论》第8讲49定理31定理31:设<A,≼>为偏序集,A中最长链的长度为n,则(1)A中存在极大元(2)A存在n个划分块的划分,每个划分块都是反链(即A划分成n个互不相交的反链)推论:设<A,≼>为偏序集,若|A|=mn+1,则A中要么存在长度为m+1的反链,要么存在长度为n+1的链.2024/11/5《集合论与图论》第8讲50定理31(举例)abcdefghijk最长链长度为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},{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的链2024/11/5《集合论与图论》第8讲51定理31(证明(1))定理31:设<A,≼>为偏序集,A中最长链的长度为n,则(1)A中存在极大元证明:(1)设B是A中长度为n的最长链,B有极大元(也是最大元)y,则y也是A的极大元,否则A中还有比y“大”的元素z,B就不是最长链.2024/11/5《集合论与图论》第8讲52定理31(证明(2))定理31:设<A,≼>为偏序集,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}是满足要求的划分.2024/11/5《集合论与图论》第8讲53定理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}}2024/11/5《集合论与图论》第8讲54定理31(证明(2)续)证明(续):[1]

A1={x|x是A中的极大元},极大元互相之间不可比,所以A1是反链,同理A2,…,An都是反链.

[2]

显然A1,A2,…,An互不相交.

[3]最长链上的元素分属A1,A2,…,An,所以A1,A2,…,An都非空.

[4]假设z

A-A1-…-An,则最长链上的元素加上z就是长度为n+1的链,矛盾!所以A=A1

A2

…

An.综上所述,A={A1,A2,…,An}确是所求划分.#2024/11/5《集合论与图论》第8讲55定理31推论(证明)推论:设<A,≼>为偏序集,若|A|=mn+1,则A中要么存在长度为m+1的反链,要么存在长度为n+1的链.证明:(反证)假设A中既没有长度为m+1的反链,也没有长度为n+1的链,则按照定理31(2)中要求来划分A,A至多划分成n块,每块至多m个元素,于是A中至多有mn个元素,这与|A|=mn+1矛盾!#2024/11/5《集合论与图论》第8讲56全序(totalorder)关系全序关系:若偏序集<A,≼>满足xy(xAyAx与