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

會計(jì)學(xué)1等價(jià)關(guān)系與偏序關(guān)系2等價(jià)關(guān)系的驗(yàn)證驗(yàn)證模3相等關(guā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)自反性、對稱性、傳遞性得到驗(yàn)證第1頁/共24頁3A上模3等價(jià)關(guān)系的關(guān)系圖設(shè)A={1,2,…,8},

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

第2頁/共24頁4等價(jià)類定義設(shè)R為非空集合A上的等價(jià)關(guān)系,x∈A，令

[x]R={y|y∈A∧xRy}稱[x]R為x關(guān)于R的等價(jià)類,簡稱為x的等價(jià)類,簡記為[x].實(shí)例A={1,2,…,8}上模3等價(jià)關(guān)系的等價(jià)類：

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}第3頁/共24頁5等價(jià)類的性質(zhì)

定理1

設(shè)R是非空集合A上的等價(jià)關(guān)系,則

(1)x∈A,[x]是A的非空子集.

(2)x,y∈A,如果xRy,則[x]=[y].

(3)x,y∈A,如果xy,則[x]與[y]不交.

(4)∪{[x]|x∈A}=A，即所有等價(jià)類的并集就是A.

第4頁/共24頁6實(shí)例A={1,2,…,8}上模3等價(jià)關(guān)系的等價(jià)類：

[1]=[4]=[7]={1,4,7}，

[2]=[5]=[8]={2,5,8}，

[3]=[6]={3,6}

以上3類兩兩不交，

{1,4,7}{2,5,8}{3,6}={1,2,…,8}第5頁/共24頁7商集定義

設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集,記做A/R,A/R={[x]R

|x∈A}實(shí)例A={1,2,…,8}，A關(guān)于模3等價(jià)關(guān)系R的商集為

A/R={{1,4,7},{2,5,8},{3,6}}

A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：

A/IA

={{1},{2},…,{8}}

A/EA

={{1,2,…,8}}第6頁/共24頁8集合的劃分定義設(shè)A為非空集合,若A的子集族π(πP(A))滿足下面條件：

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

(3)∪π=A

則稱π是A的一個劃分,稱π中的元素為A的劃分塊.第7頁/共24頁9例題例1設(shè)A＝{a,b,c,d},

給定π1,π2,π3,π4,π5,π6如下：π1={{a,b,c},makza3m}，π2={{a,b},{c},f2acntf}

π3={{a},{a,b,c,d}},π4={{a,b},{c}}

π5={,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}

則π1和π2

是A的劃分,其他都不是A的劃分.

為什么？第8頁/共24頁10等價(jià)關(guān)系與劃分的一一對應(yīng)商集A/R就是A的一個劃分不同的商集對應(yīng)于不同的劃分任給A的一個劃分π,如下定義A上的關(guān)系R：

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

則R為A上的等價(jià)關(guān)系,且該等價(jià)關(guān)系確定的商集就是π.例2給出A＝{1,2,3}上所有的等價(jià)關(guān)系求解思路：先做出A的所有劃分,然后根據(jù)劃分寫出對應(yīng)的等價(jià)關(guān)系.第9頁/共24頁11等價(jià)關(guān)系與劃分之間的對應(yīng)π1,π2和π3分別對應(yīng)等價(jià)關(guān)系R1,R2和R3.

R1={<2,3>,<3,2>}∪IA，R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAπ4對應(yīng)于全域關(guān)系EA，π5對應(yīng)于恒等關(guān)系IA第10頁/共24頁12實(shí)例例3設(shè)A={1,2,3,4}，在AA上定義二元關(guān)系R：

<<x,y>,<u,v>>Rx+y=u+v，求R導(dǎo)出的劃分.

解AA={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}第11頁/共24頁13實(shí)例（續(xù)）根據(jù)<x,y>的x+y=2,3,4,5,6,7,8將AA劃分成7個等價(jià)類：

(AA)/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}

第12頁/共24頁14偏序關(guān)系定義非空集合A上的自反、反對稱和傳遞的關(guān)系，稱為A上的偏序關(guān)系，記作?.設(shè)?為偏序關(guān)系,如果<x,y>∈?,則記作x?y,讀作x“小于等于”y.

實(shí)例集合A上的恒等關(guān)系IA是A上的偏序關(guān)系.

小于等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.第13頁/共24頁15相關(guān)概念x與y可比：設(shè)R為非空集合A上的偏序關(guān)系,

x,yA,x與y可比x?y∨y?x.

結(jié)論：任取兩個元素x和y,可能有下述情況：

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

全序關(guān)系：

R為非空集合A上的偏序,x,yA,x與y都是可比的，則稱R為全序關(guān)系實(shí)例：數(shù)集上的小于等于關(guān)系是全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系第14頁/共24頁16蓋住：設(shè)R為非空集合A上的偏序關(guān)系,x,y∈A,如果x?y且不存在zA使得x?z?y,則稱y蓋住x.實(shí)例：{1,2,4,6}集合上的整除關(guān)系,2蓋住1,4和6蓋住2.4不蓋住1.

相關(guān)概念（續(xù)）第15頁/共24頁17偏序集與哈斯圖定義集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.

實(shí)例：整數(shù)集和小于等于關(guān)系構(gòu)成偏序集<Z,≤>，冪集P(A)和包含關(guān)系構(gòu)成偏序集<P(A),R>.哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關(guān)系圖特點(diǎn)：每個結(jié)點(diǎn)沒有環(huán)，兩個連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前，具有蓋住關(guān)系的兩個結(jié)點(diǎn)之間連邊第16頁/共24頁18哈斯圖實(shí)例例4<{1,2,3,4,5,6,7,8,9},R整除><P({a,b,c}),R>第17頁/共24頁19A={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

哈斯圖實(shí)例（續(xù)）例5已知偏序集<A,R>的哈斯圖如右圖所示,試求出集合A和關(guān)系R的表達(dá)式.

第18頁/共24頁20偏序集的特定元素定義設(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)成立,則稱y為B的極小元.

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

第19頁/共24頁21特殊元素的性質(zhì)

對于有窮集，極小元和極大元必存在，可能存在多個.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是極小元；最大元一定是極大元.

孤立結(jié)點(diǎn)既是極小元，也是極大元.第20頁/共24頁22定義設(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的最大下界或下確界.偏序集的特定元素(續(xù))第21頁/共24頁23下界、上界、最大下界、最小上界不一定存在下界、上界存在不一定惟一最大下界、最小上界如果存在，則惟一集合