【正文】 是 R是循環(huán)關(guān)系和自反關(guān)系。 證明：必要性：若 R是等價(jià)關(guān)系； (1)R等價(jià) =R自反 (2) ， R等價(jià) ∴ R對(duì)稱 ∴ ，即 R是循環(huán)關(guān)系； 充分性：若 R自反且循環(huán) ： (1)自反性顯然； (2) ， R是自反，得 ，因 R是循環(huán)的 ，即 R是對(duì)稱的； ?RcbRcaRba ????????? , ，則有且RcaRbaAcba ???????? ,, 若RcbRcaRab ?????????? ,R, 傳遞，而Aba ?? , Raa ??? ,RabRba ?????? , 則若45/57 等價(jià)關(guān)系與劃分 (3) ，則由 R對(duì)稱得 ，由 R循環(huán)， ， ∴ R是傳遞的； ∴R 等價(jià)。 RcbRbaAcba ???????? , ，若Rab ??? , Rab ??? , Rcb ??? ,Rca ???? ,46/57 次序關(guān)系 在一些研究中，需要把研究的對(duì)象排出次序，因此，集合的元素之間還有一種重要關(guān)系，稱為“先后次序”關(guān)系，即偏序關(guān)系。 ?定義 ： (1)設(shè) R為非空集合 A上的關(guān)系，如果 R是自反的，反對(duì)稱的，傳遞的，則稱 R為 A上的偏序關(guān)系 (Partial Order relation)。記作“ ≤ ” ,讀作“小于等于”； (2)設(shè) R為非空集合 A上的關(guān)系，如果 R是反自反的，反對(duì)稱的，傳遞的，則稱R為 A上的擬序關(guān)系 (Quasi Order relation)。記作“ ”；讀作“小于”。 ?偏序關(guān)系的逆關(guān)系 也是一個(gè)偏序，用“ ≥ ”表示，讀作“大于等于”；擬序關(guān)系的逆關(guān)系 也是一個(gè)擬序，用“ ”表示，讀作“大于”。 1??1??47/57 次序關(guān)系 例： (1)集合 A上的冪集 ρ (A)上定義的“ ”和“ ”分別是偏序關(guān)系和擬序關(guān)系； (2)實(shí)數(shù)集合 R上定義的數(shù)的“小于等于”關(guān)系，“小于”關(guān)系，分別是偏序關(guān)系和擬序關(guān)系； (3)自然數(shù)集合 N上定義的“整除”關(guān)系，也是一個(gè)偏序集合。 ?定義 ： 設(shè) A, ≤ 是一個(gè)偏序集，對(duì) ，x ≤y 或 y ≤x ，則稱 x與 y是可比的 (Comparable),若 x與 y是可比的， xy，且不存在 ，使得xzy，則稱 y覆蓋 (Overlay)x。 ? ?Ayx ?? ,Az?48/57 次序關(guān)系 例： (1)集合 A={a， b， c}，則偏序集 ρ (A), ?中， {a}與 {a， b}是可比的； {a}與 {b， c}是不可比的； {a， b}覆蓋 {a}； {a， b， c}不覆蓋 {a}。 (2)偏序集 {R， ≤} ，對(duì) ， x與 y都是可比的，但 x不覆蓋 y， y也不覆蓋 x。 (3)偏序集 {Z， ≤} ，對(duì) ， x與 y都是可比的， x覆蓋 x1。 (4)偏序集 N， |中， 2與 3不是可比的， 2與 6是可比的，并且 6覆蓋 2,2與 8可比，但 8不覆蓋 2。 Ayx ?? ,Ayx ?? ,49/57 次序關(guān)系 ?：偏序集的哈斯圖 由于偏序關(guān)系本身具有自反，反對(duì)稱，傳遞的性質(zhì)，在用關(guān)系圖來描述偏序關(guān)系且不引起混淆，可以對(duì)其進(jìn)行簡(jiǎn)化，得到的圖叫做偏序圖或哈斯圖(Hasse)。 哈斯圖的作圖方法如下： (1):用小圓圈或點(diǎn)表示 A中的元素，省掉關(guān)系圖中的所有環(huán) (因自反性 )； (2):對(duì) ，若 xy則將 x畫在 y的下方，可省掉關(guān)系圖中所有邊的箭頭； (3):對(duì) ，若 y覆蓋 x，則在 x與 y之間連條線，否則無線相連。 Ayx ?? ,Ayx ?? ,50/57 次序關(guān)系 按 (1)， (2)， (3)所作成的圖稱為哈斯圖。 ?例 416： 設(shè) A={2,3,6,12,24,36}，“ ≤ ”是 A上的整除關(guān)系，畫出其一般關(guān)系圖和哈斯圖。 ?例 417： 設(shè)集合 A={a}， B={a， b}， C={a， b， c}分別畫出集合 A， B， C之冪集上定義的“ ”的哈斯圖。 ?51/57 次序關(guān)系 ?：偏序集中的特殊元素 ?定義 ： 設(shè) A, ≤ 為偏序集， ?最小元與極小元不一樣，最小元是 B中最小的元素，它與 B中其它元素都是可比的，而極小元不一定與 B中的元素都可比，只要沒有比它小的元素，它就是極小元； ?對(duì)于有窮集，極小元一定存在，但最小元不一定存在； ByAB ?? ,的極大元。為成立，則稱若的極小元；為成立，則稱若的最大元；為成立，則稱若的最小元；為成立，則稱若ByxyxyBxxByxyyxBxxByyxBxxByxyBxx)()4()()3()()2()()1(????????????????????52/57 次序關(guān)系 ?如果最小元存在，最小元唯一，但極小元可以有多個(gè)； ?b是 B的最小元 =b是 B中的唯一極小元； ?反之，極大元亦然。 ?定義 ： 設(shè) A, ≤ 為偏序集， AyAB ?? ,或下確界。的最大下界的最大元為，則稱的下界為令或上確界；的最小上界的最小元為，則稱的上界為令的下界；為成立，則稱若的上界；為成立，則稱若BByyDBByyCByxyBxxByyxBxxD}|{)4(C}|{)3()()2()()1(??????????53/57 次序關(guān)系 ?例 418： 設(shè)集合 A={a， b， c}，求偏序集 的子集的子集 的最大元，最小元，極大元，極小元，上界，下界，上確界，下確界。 解：畫圖 ??? ),( A?} } ,{},{},{{},},{},{},{},{{ 21 cacaBcbcbbaB ????)(3 AB ??集合 最大元 最小元 極大元 極小元 上界 下界 上確界 下確界 無 {a,b}，{b， c} {a， b，c} {a， b，c} {a， c} 無 {a， c} {a}，{c} {a,c}，{a， b，c} {a， c} {a， b，c} {a， b，c} {a， b，c} {a， b，c} 1B2B3B????????????????????54/57 次序關(guān)系 ?例 419： 設(shè) A={a， b， c， d}， A上定義偏序集 A， ≤ 的哈斯圖如圖所示，求 B={a， b}和 C={c， d}的最大元，最小元，極大元 ，極小元，上下 界，上下確界。 解： a dbc集合 最大元 最小元 極大元 極小元 上界 下界 上確界 下確界 B 無 無 a， b a， b 無 c， d 無 無 C 無 無 c， d c， d a， b 無 無 無 55/57 次序關(guān)系 ?上 (下 )界存在，并不一定存在最小上 (下 )界； ?b是 B的最大元 =b是 B的極大元，上界，上確界； ?b是 B的最小元 =b是 B的極小元，下界，下確界； ?a是 B的上確界 ∧ =a是 B的最大元； ?a是 B的下確界 ∧ =a是 B的最小元； ?若 B存在上確界，則其上確界唯一； ?若 B存在下確界，則其下確界唯一。 Ba?Ba?56/57 次序關(guān)系 ?：全序與良序 ?定義 ： 設(shè) A, ≤ 是一個(gè)偏序集，若對(duì) x與 y都是可比的，則稱關(guān)系“ ≤ ”為全序關(guān)系(Total Order Relation)，或稱線序關(guān)系，簡(jiǎn)稱全序或線序，稱 A, ≤ 為全序集或線序集或鏈。 例： (1)集合 A={a， b， c}，上定義的關(guān)系 ≤={a ，a， b， b， c， c， a， b， b， c， a， c}是一個(gè)全序關(guān)系； (2)實(shí)數(shù)集合 R上定義的“ ≤ ”是全序關(guān)系， R, ≤ 是全序集。 ?全序集中，任何兩個(gè)元素可比，存在一個(gè)次序，其哈斯圖為一鏈。 Ayx ?? ,57/57 次序關(guān)系 ?定義 ： 設(shè) A, ≤ 是一個(gè)偏序集，若 A的任何一個(gè)非空子集有最小元，則稱“ ≤ ”為良序關(guān)系(Well Order Relation)，簡(jiǎn)稱良序，此時(shí) A, ≤ 稱為良序集。 {a， b}有最小元，則 a ≤b 或 b ≤a ， ∴ 良序關(guān)系是一個(gè)全序關(guān)系。 ?“ ≤ ”是良序關(guān)系 =“ ≤ ”是全序關(guān)系 =“ ≤ ”是偏序關(guān)系； ?一般地，任何有限的全序集的每一個(gè)非空子集一定有最小元，所以，有限全序集一定是良序集，對(duì)與無窮的全序集則不一定。 Aba ??