等價(jià)關(guān)系與偏序關(guān)系

等價(jià)關(guān)系與偏序關(guān)系第一頁，共二十二頁，2022年，8月28日2實(shí)例設(shè)A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}R的關(guān)系圖如：例1設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.不難驗(yàn)證R為A上的等價(jià)關(guān)系,因?yàn)?/p>

x∈A,有x≡x(mod3)

x,y∈A,若x≡y(mod3),則有y≡x(mod3)

x,y,z∈A,若x≡y(mod3),y≡z(mod3),則有x≡z(mod3)第二頁，共二十二頁，2022年，8月28日3定理4.8

設(shè)R是非空集合A上的等價(jià)關(guān)系，則有下面的結(jié)論成立：1)對(duì)xA，[x]R≠Φ；2)對(duì)x,y∈A，如果y∈[x]R，則有[x]R=[y]R3)對(duì)x,y∈A，如果y[x]R，則有[x]R∩[y]R＝Φ4)＝A；定義4.20

設(shè)R是非空集合A上的等價(jià)關(guān)系，對(duì)任意x∈A，稱集合[x]R＝{y|y∈A∧<x,y>∈R}(也即A中與x等價(jià)的全體元素構(gòu)成的子集)為x關(guān)于R的等價(jià)類.等價(jià)類第三頁，共二十二頁，2022年，8月28日4集合的劃分定義4.21

設(shè)A為非空集合,若A的子集族

(

P(A))滿足下面條件：

(1)

(2)xy(x,y∈∧x≠y→x∩y=)

(3)∪

=A

則稱是A的一個(gè)劃分,稱

中的元素為A的劃分塊.

第四頁，共二十二頁，2022年，8月28日5商集定義4.22

設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R

的商集,記做A/R,A/R={[x]R

|x∈A}第五頁，共二十二頁，2022年，8月28日6等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)(1)

商集A/R就是A的一個(gè)劃分,不同的商集對(duì)應(yīng)于不同的劃分(2)

任給A的一個(gè)劃分

,如下定義A上的關(guān)系R：

R={<x,y>|x,y∈A∧x與y在的同一劃分塊中}

則R為A上的等價(jià)關(guān)系,且該等價(jià)關(guān)系確定的商集就是.第六頁，共二十二頁，2022年，8月28日7總結(jié)1、熟記等價(jià)關(guān)系的定義；2、利用等價(jià)關(guān)系的定義證明一個(gè)關(guān)系是等價(jià)關(guān)系；3、給定A上的等價(jià)關(guān)系R，會(huì)求所有的等價(jià)類和商集A/R；并求出對(duì)應(yīng)的集合的劃分；4、給定集合A上的劃分，會(huì)求對(duì)應(yīng)的等價(jià)類。第七頁，共二十二頁，2022年，8月28日8判定下列關(guān)系具有哪些性質(zhì)1、對(duì)任何非空集合A，A上的恒等關(guān)系；2、多邊形的“相似關(guān)系”、“全等關(guān)系”；3、集合A的冪集P(A)上定義的“包含關(guān)系”；4、集合A的冪集P(A)上定義的“真包含關(guān)系”。解：1，2都具有自反性，對(duì)稱性和傳遞性，是等價(jià)關(guān)系；

3具有自反性，反對(duì)稱性和傳遞性；

4具有反自反性，反對(duì)稱性，傳遞性。偏序關(guān)系擬序關(guān)系第八頁，共二十二頁，2022年，8月28日94.7偏序關(guān)系定義4.22

非空集合A上的自反、反對(duì)稱和傳遞的關(guān)系，稱為A上的偏序關(guān)系，記作?.設(shè)?為偏序關(guān)系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.并將集合A與偏序關(guān)系R一起叫做偏序集，用序偶<A，R>或者<A，?>表示。不指數(shù)的大小，而指在偏序關(guān)系中的順序性第九頁，共二十二頁，2022年，8月28日【實(shí)例】試判斷下列關(guān)系是否為偏序關(guān)系：（1）集合A的冪集P(A)上的包含關(guān)系“”（2）實(shí)數(shù)集合R上的小于等于關(guān)系“≤”（3）自然數(shù)集合N上的模m同余關(guān)系；（4）自然數(shù)集合N上的整除關(guān)系“|”；根據(jù)偏序關(guān)系的定義知(1)，(2)，(4)，所對(duì)應(yīng)的關(guān)系同時(shí)具有自反性，反對(duì)稱性和傳遞性，所以都是偏序集；(3)所對(duì)應(yīng)的關(guān)系不具有反對(duì)稱性，所以不是偏序集。第十頁，共二十二頁，2022年，8月28日11相關(guān)概念定義4.24

x與y可比

設(shè)R為非空集合A上的偏序關(guān)系,

x,yA,x與y可比x?y∨y?x.x,y∈A,如果x?y且不存在zA使得x?z?y,則稱y覆蓋x.結(jié)論：x,yA，下述幾種情況發(fā)生其一且僅發(fā)生其一：x?y,

y?x,x＝y(tǒng),x與y不是可比的

定義4.25

R為非空集合A上的偏序,x,yA,x與y都可比，則稱R為全序.

實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系{1,2,4,6}集合上的整除關(guān)系,2覆蓋1,4和6覆蓋2.但4不覆蓋1.第十一頁，共二十二頁，2022年，8月28日12偏序集與哈斯圖定義：集合A和A上的偏序關(guān)系?一起叫做偏序集,

記作<A,?>.

實(shí)例：整數(shù)集和數(shù)的小于等于關(guān)系構(gòu)成偏序集

<Z,≤>

冪集P(A)和包含關(guān)系構(gòu)成偏序集

<P(A),R>.第十二頁，共二十二頁，2022年，8月28日

利用偏序自反、反對(duì)稱、傳遞性簡(jiǎn)化的關(guān)系圖：（1）由偏序關(guān)系是自反的，故關(guān)系圖上每個(gè)節(jié)點(diǎn)都有環(huán)，用小圓圈或點(diǎn)表示A中的元素，省掉關(guān)系圖中的所有的環(huán)；（因自反性)（2）對(duì)任意x,y∈A，若x＜y，則將x畫在y的下方，可省掉關(guān)系圖中所有邊的箭頭；（因反對(duì)稱性）（3）具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊.即對(duì)任意x,y∈A(x≠y)，若x＜

y，且x與y之間不存在z∈A，使得x＜

z＜

y，則x與y之間用一條線相連，否則無線相連。（因傳遞性）哈斯圖：第十三頁，共二十二頁，2022年，8月28日14哈斯圖實(shí)例例

<{1,2,3,4,5,6,7,8,9},R整除>

例<P({a,b,c}),R>第十四頁，共二十二頁，2022年，8月28日練習(xí)115設(shè)A={2,3,6,12,24,36}，“≤”是A上的整除關(guān)系R，畫出其一般的關(guān)系圖和哈斯圖。解

由題意可得R={<2,2>,<2,6>,<2,12>,<2,24>,<2,36>,<3,3>,<3,6>,<3,12>,<3,24>,<3,36>,<6,6>,<6,12>,<6,24>,<6,36>,<12,12>,<12,24>,<12,36>,<24,24>,<36,36>}，從而得出該偏序集<A,≤>的一般關(guān)系圖和哈斯圖如下：哈斯圖236123624關(guān)系圖236123624第十五頁，共二十二頁，2022年，8月28日16練習(xí)2

已知偏序集<A,R>的哈斯圖如右圖所示,試求出集合A和關(guān)系R的表達(dá)式.

解：A={a,b,c,d,e,f,g,h}

R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

第十六頁，共二十二頁，2022年，8月28日174.7.2極值與最值定義4.26

設(shè)<A,?>為偏序集,BA,y∈B.

(1)若x(x∈B→y?x)成立,則稱y為B的最小元.

(2)若x(x∈B→x?y)成立,則稱y為B的最大元.

(3)若x(x∈B∧x?y→x=y)成立,則稱y為B的極小元.

(4)若x(x∈B∧y?x→x=y)成立,則稱y為B的極大元.

第十七頁，共二十二頁，2022年，8月28日【性質(zhì)】對(duì)于有窮集，極小元和極大元必存在，可能存在多個(gè).最小元和最大元不一定存在，如果存在一定惟一.最小元一定是極小元；最大元一定是極大元.【特定元素與哈斯圖】如果圖中有孤立結(jié)點(diǎn)，那么這個(gè)結(jié)點(diǎn)既是極小元，也是極大元，并且圖中既無最小元，也無最大元(除了圖中只有唯一孤立結(jié)點(diǎn)的特殊情況)。除了孤立結(jié)點(diǎn)以外，其他的極小元是圖中所有向下通路的終點(diǎn)，其他的極大元是圖中所有向上通路的終點(diǎn)。圖中唯一的極小元是最小元，唯一的極大元是最大元；否則最小元和最大元不存在。第十八頁，共二十二頁，2022年，8月28日19定義4.27

設(shè)<A,?>為偏序集,BA,yA.

（1）若x(x∈B→x?y)成立,則稱y為B的上界.

（2）若x(x∈B→y?x)成立,則稱y為B的下界.

（3）令C＝{y|y為B的上界},則稱C的最小元為B的最小上界或上確界.

（4）令D＝{y|y為B的下界},則稱D的最大元為B的最大下界或下確界.由定義4.27可知以下性質(zhì)：下界、上界、下確界、上確界不一定存在于集合B中下界、上界存在不一定惟一下確界、上確界如果存在，則惟一子集B的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì).偏序集的特定元素第十九頁，共二十二頁，2022年，8月28日20實(shí)例練3

設(shè)偏序集<A,?>如下圖所示，求A的極小元、最小元、極大元、最大元.設(shè)B＝{b,c,d},求B的下界、上界、下確界、上確界.解：A的極小元：a,b,c,g；極大元：a,f,h；沒有最小元與最大元.B的下界不存在,上界有d和f下確界不存在,上確界為d.第二十頁，共二十二頁，2022年，8月28日實(shí)例21練4A={x1,x2,x3,x4}，A上定義偏序集<A,≤>的哈斯圖如圖所示。求B={x1,x2}和C={x3,x4}上界、下界、上確界和下確界。【解】

B、C的各種特殊元見下表。集合上界下界上確界下確界B無x3,x4無無Cx1,x2無無無x1x3x2x4第二十一頁，共二十二頁