離散數(shù)學(xué)第3章(12-13)(新教材)

1、 第十二節(jié)第十二節(jié)* 相容關(guān)系相容關(guān)系 從等價關(guān)系的三個條件中去掉第三個傳遞從等價關(guān)系的三個條件中去掉第三個傳遞性條件性條件,就得到我們下面要研究的相容關(guān)系就得到我們下面要研究的相容關(guān)系. 定義定義12.1(相容關(guān)系相容關(guān)系)設(shè)設(shè)R是集合是集合A上一個二元關(guān)系上一個二元關(guān)系,如果關(guān)系如果關(guān)系R同時具有同時具有(1)自反性自反性,(2)對稱性對稱性,那么就那么就稱稱R是集合是集合A上一個相容關(guān)系上一個相容關(guān)系. (注注)從相容關(guān)系的關(guān)系矩陣來看從相容關(guān)系的關(guān)系矩陣來看,由于它有自反性由于它有自反性,故而其關(guān)系矩陣的主對角線上所有元素均為故而其關(guān)系矩陣的主對角線上所有元素均為1;由由于它有對稱性于

2、它有對稱性,故而其關(guān)系矩陣還是一個對稱矩故而其關(guān)系矩陣還是一個對稱矩陣陣.從相容關(guān)系的關(guān)系圖來看從相容關(guān)系的關(guān)系圖來看,每個元素所在的頂每個元素所在的頂點必有一條自回路點必有一條自回路,且每兩個結(jié)點之間且每兩個結(jié)點之間,要么沒有要么沒有任何有向邊相連任何有向邊相連,要么恰有一對方向相反的有向要么恰有一對方向相反的有向邊相連邊相連. 例例1.設(shè)集合設(shè)集合B=a,b,c,d,則集合則集合B的冪集的冪集(B)是一是一個有個有16個元素的一個集合個元素的一個集合,取取(B)的一個如下的的一個如下的子集子集A A=a,d,a,b,b,c,b,c,d, 作集合作集合A上如下定義的關(guān)系上如下定義的關(guān)系R:

3、R當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x和和y含有含有B中至少一個相同的元素中至少一個相同的元素. 如果我們將集合如果我們將集合A中的元素簡記為中的元素簡記為: x1=a, x2=d, x3=a,b, x4=b,c, x5=b,c,d. 那么關(guān)系那么關(guān)系R可以用通常序偶的形式表示如下可以用通常序偶的形式表示如下: R=, , ,. 顯然顯然,這樣定義的關(guān)系是集合這樣定義的關(guān)系是集合A上的相容關(guān)系上的相容關(guān)系.定義定義12.2(相容類相容類)設(shè)設(shè)R是集合是集合A上的一個相容關(guān)系上的一個相容關(guān)系,B是是A的一個子集的一個子集.如果如果 x,y B R,那么就稱那么就稱B是由相容關(guān)系是由相容關(guān)系R產(chǎn)生的一個相容類產(chǎn)生的

4、一個相容類. 在上面的例在上面的例1中中,集合集合A的以下諸個子集都是所給的以下諸個子集都是所給相容關(guān)系的相容類相容關(guān)系的相容類 x1,x3,x2,x5,x3,x4,x3,x4,x5.在這幾個相容類中在這幾個相容類中, x1,x3,x2,x5以及以及x3,x4,x5這三這三個相容類不能再添加個相容類不能再添加A中的任何元素加以擴(kuò)大了中的任何元素加以擴(kuò)大了,而其中的而其中的x3,x4可以添加中的元素可以添加中的元素x5擴(kuò)大成一個新擴(kuò)大成一個新的更大的相容類的更大的相容類.為了區(qū)分這兩種情形為了區(qū)分這兩種情形,我們給出下我們給出下面的定義面的定義. 定義定義12.3(最大相容類最大相容類)設(shè)設(shè)B

5、A是由相容關(guān)系是由相容關(guān)系R產(chǎn)生產(chǎn)生的一個相容類的一個相容類,且不存在集合且不存在集合A的任何其他子集的任何其他子集B1,使得使得B B1,B B1,且且B1也是相容關(guān)系也是相容關(guān)系R產(chǎn)生的一個產(chǎn)生的一個相容類相容類,則稱則稱B是一個最大相容類是一個最大相容類(或者極大相容類或者極大相容類). 在上面的例在上面的例1中中x1,x3,x2,x5以及以及x3,x4,x5這三個這三個相容類都是最大相容類相容類都是最大相容類,而而x3,x4不是最大相容類不是最大相容類. 由于集合由于集合A上的相容關(guān)系一定滿足自反性和對上的相容關(guān)系一定滿足自反性和對稱性稱性,因此對于集合因此對于集合A上給定的相容關(guān)系上

6、給定的相容關(guān)系,可以按照可以按照下述方法對它的關(guān)系圖加以簡化下述方法對它的關(guān)系圖加以簡化,為此我們進(jìn)一步為此我們進(jìn)一步給出以下的定義給出以下的定義.定義定義12.4(相容關(guān)系圖相容關(guān)系圖)設(shè)設(shè)R是給定集合是給定集合A上的一個相上的一個相容關(guān)系容關(guān)系,畫出畫出R的關(guān)系圖的關(guān)系圖,再作如下簡化再作如下簡化:1從它的關(guān)系圖中略去每個頂點處的自回路從它的關(guān)系圖中略去每個頂點處的自回路(環(huán)環(huán));2如果對某兩個元素如果對某兩個元素a,b A有有, R,則則在該關(guān)系圖中的頂點在該關(guān)系圖中的頂點a與與b之間只保留一條邊之間只保留一條邊(改畫改畫成無向邊成無向邊). 這樣簡化后得到的圖稱為這個相容關(guān)系的相這樣簡

7、化后得到的圖稱為這個相容關(guān)系的相容關(guān)系圖容關(guān)系圖. 從一個給定的相容關(guān)系的相容關(guān)系圖可以更從一個給定的相容關(guān)系的相容關(guān)系圖可以更清楚地看出所給相容關(guān)系的極大相容類清楚地看出所給相容關(guān)系的極大相容類.為此我們?yōu)榇宋覀兘o出下面的定義給出下面的定義.定義定義12.5(完全多邊形完全多邊形)一個多邊形一個多邊形,如果它的每兩個如果它的每兩個頂點之間恰有一邊相連頂點之間恰有一邊相連,稱之為一個完全多邊形稱之為一個完全多邊形.在在一個圖中一個圖中,一個不能包含在另外任何一個更大的完一個不能包含在另外任何一個更大的完全多邊形內(nèi)的完全多邊形稱為一個最大完全多邊全多邊形內(nèi)的完全多邊形稱為一個最大完全多邊形形.

8、例如例如,一個三角形總是一個完全多邊形一個三角形總是一個完全多邊形,一個四一個四邊形加上它的兩條對角線也是一個完全多邊形等邊形加上它的兩條對角線也是一個完全多邊形等等等.由此我們?nèi)菀卓闯鲇邢旅娴慕Y(jié)論成立由此我們?nèi)菀卓闯鲇邢旅娴慕Y(jié)論成立.定理定理12.1 在一個相容關(guān)系的相容關(guān)系圖中在一個相容關(guān)系的相容關(guān)系圖中,以下圖以下圖形中的頂點集合都是一個最大相容類形中的頂點集合都是一個最大相容類:(1)每個單獨的孤立頂點每個單獨的孤立頂點;(2)不包含在任何更大的完全多邊形內(nèi)的兩個頂點不包含在任何更大的完全多邊形內(nèi)的兩個頂點 以及連接這兩點的一條邊以及連接這兩點的一條邊;(3)任何一個最大完全多邊形任何

9、一個最大完全多邊形. 請讀者對例請讀者對例1作出它的相容關(guān)系圖來作出它的相容關(guān)系圖來,并利用此并利用此定理的結(jié)論判斷其中有哪些最大相容類定理的結(jié)論判斷其中有哪些最大相容類. 下面的定理給出了集合的覆蓋與相容關(guān)系之間下面的定理給出了集合的覆蓋與相容關(guān)系之間的部分聯(lián)系的部分聯(lián)系. 定理定理12.2 設(shè)設(shè)T=S1,Sm是集合是集合A的一個覆蓋的一個覆蓋,那么那么 就是集合就是集合A上的一個相容關(guān)系上的一個相容關(guān)系. 這個定理的證明很簡單這個定理的證明很簡單,我們把它留給讀者自己我們把它留給讀者自己去完成去完成. 定理定理12.2告訴我們告訴我們,對于集合對于集合A的每個完全覆蓋的每個完全覆蓋,都有一

10、個相容關(guān)系與之對應(yīng)都有一個相容關(guān)系與之對應(yīng);反過來反過來,對于集合的每對于集合的每個相容關(guān)系個相容關(guān)系,利用與等價關(guān)系的討論中類似的方法利用與等價關(guān)系的討論中類似的方法也可證明有一個完全覆蓋與之對應(yīng)也可證明有一個完全覆蓋與之對應(yīng).但是集合的完但是集合的完全覆蓋與相容關(guān)系之間一般并不存在如同集合的全覆蓋與相容關(guān)系之間一般并不存在如同集合的分劃與等價關(guān)系那樣的一一對應(yīng)關(guān)系分劃與等價關(guān)系那樣的一一對應(yīng)關(guān)系.請看下面的請看下面的例子例子.1miiiRSS例例2.設(shè)給定集合設(shè)給定集合A=a,b,c,d上兩個不同的完全覆蓋上兩個不同的完全覆蓋 T1=a,b,a,c,d,T2=a,b,a,c,a,d,c,d

11、.試計算它們所產(chǎn)生的兩個相容關(guān)系試計算它們所產(chǎn)生的兩個相容關(guān)系.解解:(1)a,b a,b=, a,c,d a,c,d=, ,所以所以T1所產(chǎn)生的相容關(guān)系是所產(chǎn)生的相容關(guān)系是 R1=, ,.(2)a,b a,b=, a,c a,c=, a,d a,d=, c,d c,d=,所以所以T2所產(chǎn)生的相容關(guān)系是所產(chǎn)生的相容關(guān)系是 R2=, ,.由此可以看出由此可以看出:在本例中雖然在本例中雖然T1 T2,但卻有但卻有R1= R2.另一方面另一方面,如果我們反過來從這個例子中得到的相如果我們反過來從這個例子中得到的相容關(guān)系容關(guān)系 R=, , 出發(fā)去尋找它所對應(yīng)的完全覆蓋出發(fā)去尋找它所對應(yīng)的完全覆蓋.由于

12、由于 , R, 故而所有元素故而所有元素a,b,c,d均在同一個分塊之中均在同一個分塊之中,也就是也就是說說,這個相容關(guān)系這個相容關(guān)系R反過來對應(yīng)的是完全分劃反過來對應(yīng)的是完全分劃 T=a,b,c,d,然而然而T T1,T T2.第十三節(jié)第十三節(jié) 序關(guān)系序關(guān)系 在與實數(shù)這一重要的研究對象有關(guān)的數(shù)學(xué)問在與實數(shù)這一重要的研究對象有關(guān)的數(shù)學(xué)問題中題中,有一個極其重要的性質(zhì)是我們所一直關(guān)注的有一個極其重要的性質(zhì)是我們所一直關(guān)注的,這個性質(zhì)就是這個性質(zhì)就是實數(shù)之間有大小實數(shù)之間有大小.這個性質(zhì)可以視為這個性質(zhì)可以視為分析的基礎(chǔ)分析的基礎(chǔ),是與微積分有關(guān)的一系列數(shù)學(xué)課程的是與微積分有關(guān)的一系列數(shù)學(xué)課程的基

13、礎(chǔ)基礎(chǔ).我們來看實數(shù)的大小關(guān)系有哪些基本性質(zhì)我們來看實數(shù)的大小關(guān)系有哪些基本性質(zhì).以以“小于或者等于小于或者等于”(即即“”)為例為例:(1)對于任何實數(shù)對于任何實數(shù)x,都有都有xx成立成立,這就是自反性這就是自反性;(2)對于任意兩個實對于任意兩個實數(shù)數(shù)x,y,如果同時有如果同時有xy和和yx成立成立,則必有則必有x=y成立成立,這這就是反對稱性就是反對稱性;(3)對于任意三個實數(shù)對于任意三個實數(shù)x,y,z,如果同時如果同時有有xy和和yz成立成立,則必有則必有xz成立成立,這就是傳遞性這就是傳遞性.鑒鑒于實數(shù)的這些性質(zhì)的特殊重要性于實數(shù)的這些性質(zhì)的特殊重要性,我們將它們抽象我們將它們抽象出

14、來單獨加以研究出來單獨加以研究,這就是我們在本節(jié)中要研究的這就是我們在本節(jié)中要研究的偏序關(guān)系偏序關(guān)系.定義定義13.1(偏序關(guān)系和偏序集偏序關(guān)系和偏序集) 設(shè)設(shè)A是一個集合是一個集合, 如果如果A上的一個關(guān)系上的一個關(guān)系R滿足自反性滿足自反性, 反對稱性反對稱性和傳遞性和傳遞性, 則稱則稱R是集合是集合A上的一個上的一個偏序關(guān)系偏序關(guān)系, 記作記作“”, 稱序偶稱序偶為為偏序集偏序集.例例1.取實數(shù)集合取實數(shù)集合 和它上面通常定義的實數(shù)之間的和它上面通常定義的實數(shù)之間的小于等于關(guān)系小于等于關(guān)系“”,顯然它是實數(shù)集合上的一個偏顯然它是實數(shù)集合上的一個偏序關(guān)系序關(guān)系, 也就是一個偏序集也就是一個偏

15、序集.例例2.給定集合給定集合B=1,2,3,4,取集合取集合A=(B),在集合在集合A上取如下的二元關(guān)系上取如下的二元關(guān)系: S1,S2 A=(B), R S1 S2. 容易驗證容易驗證,這個關(guān)系就是集合這個關(guān)系就是集合A上的一個偏序關(guān)系上的一個偏序關(guān)系.故可以用符號故可以用符號來表示這個偏序關(guān)系來表示這個偏序關(guān)系,并將并將 R 改寫成改寫成S1S2.R R,R R例例3.取集合取集合A=1,2,3,4,5,6和如下定義的二元關(guān)系和如下定義的二元關(guān)系R: x,y A, R x|y. 這里這里x|y表示表示x整除整除y.容易驗證容易驗證,這個關(guān)系就是集合這個關(guān)系就是集合A上的一個偏序關(guān)系上的一

16、個偏序關(guān)系.故可以用符號故可以用符號來表示這個偏來表示這個偏序關(guān)系序關(guān)系,并將并將 R(也就是也就是x|y)改寫成改寫成xy.例例4.取集合取集合A=1,2,3,4,5和如下定義的二元關(guān)系和如下定義的二元關(guān)系R: R=, ,. 容易驗證容易驗證,這個關(guān)系就是集合上的一個偏序關(guān)系這個關(guān)系就是集合上的一個偏序關(guān)系.故故可以用符號可以用符號來表示這個偏序關(guān)系來表示這個偏序關(guān)系,并將并將 R改寫成改寫成xy. 比較上面四個例子比較上面四個例子: 在例在例1中中,任取集合任取集合A中兩個元素中兩個元素x,y,關(guān)系式關(guān)系式xy和和yx中必至少有一個成立中必至少有一個成立. 而在例而在例2中中,取取S1=1

17、以及以及S2=2,易見易見S1S2以以及及S2S1都不成立都不成立(也就是也就是S1 S2和和S2 S1都不成立都不成立). 在例在例3中中,取取x=3和和y=5易見易見,xy以及以及yx都不都不成立成立(也就是也就是3|5和和5|3都不成立都不成立). 在例在例4中中,取取x=1和和y=4易見易見,xy以及以及yx都不都不成立成立(也就是也就是 R且且 R). 為了區(qū)分這兩類不同性質(zhì)的偏序關(guān)系為了區(qū)分這兩類不同性質(zhì)的偏序關(guān)系,我們給我們給出下面的定義出下面的定義. 定義定義13.2(全序關(guān)系和全序集全序關(guān)系和全序集)設(shè)設(shè)是一個偏序是一個偏序集集,如果對于集合如果對于集合A中任何兩個元素中任何

18、兩個元素x,y,xy和和yx中都至少有一個成立中都至少有一個成立,則稱它是一個則稱它是一個全序集全序集(也稱為也稱為線序集線序集),稱稱是該集合上的一個是該集合上的一個全序關(guān)系全序關(guān)系(也稱為也稱為線線序關(guān)系序關(guān)系).定義定義13.3(不可比較的元素不可比較的元素)設(shè)設(shè)是一個偏序集是一個偏序集,如果集合如果集合A中存在某兩個元素中存在某兩個元素x,y,使得使得xy和和yx都不成立都不成立,則稱這兩個元素是不可比較的元素則稱這兩個元素是不可比較的元素. 由定義由定義13.2可知可知,全序集中任何兩個元素都是可全序集中任何兩個元素都是可以比較的以比較的.定義定義4.(鏈與反鏈鏈與反鏈)設(shè)設(shè)是一個偏

19、序集是一個偏序集,如果集合如果集合B是集合是集合A的一個子集的一個子集,且且B中不存在不可比較的元中不存在不可比較的元素素,也即也即是一個全序集是一個全序集,則稱則稱B是一個鏈?zhǔn)且粋€鏈;顯然顯然,偏序集偏序集是一個全序集的充要條件是是一個全序集的充要條件是A是一個是一個鏈鏈.如果如果B中任何兩個元素都是不可比較的中任何兩個元素都是不可比較的,則稱則稱B是是一個反鏈一個反鏈.如果子集如果子集B中只有一個元素中只有一個元素,我們約定既我們約定既把把B視為一個鏈視為一個鏈,也把也把B視為一個反鏈視為一個反鏈. 根據(jù)定義根據(jù)定義,上面只有例上面只有例1中的偏序集才是全序集中的偏序集才是全序集,其余三個

20、例子中的偏序集均不是全序集其余三個例子中的偏序集均不是全序集.在例在例2中中,子集子集B1=,1,1,2,1,2,4就是一個鏈就是一個鏈,而子集而子集B2=1,2,1,3,2,3,4則是一個反鏈則是一個反鏈. 既然偏序關(guān)系仍然是集合上的二元關(guān)系既然偏序關(guān)系仍然是集合上的二元關(guān)系,我們我們就可以用關(guān)系圖來表示它們就可以用關(guān)系圖來表示它們.但是在用關(guān)系圖來表但是在用關(guān)系圖來表示一個偏序集的時候示一個偏序集的時候,往往因為圖中的有向邊過于往往因為圖中的有向邊過于復(fù)雜而使我們難以看清該偏序集的有別于其他偏復(fù)雜而使我們難以看清該偏序集的有別于其他偏序集的特殊的重要特征序集的特殊的重要特征.為此我們需要對

21、它的關(guān)系為此我們需要對它的關(guān)系圖加以必要的簡化圖加以必要的簡化:例如例如,去掉每個結(jié)點處的自回路去掉每個結(jié)點處的自回路(鑒于每個偏序關(guān)系都有自反性鑒于每個偏序關(guān)系都有自反性,這樣的自回路在任這樣的自回路在任何偏序關(guān)系的關(guān)系圖中都會出現(xiàn)何偏序關(guān)系的關(guān)系圖中都會出現(xiàn),這并不是給定的這并不是給定的偏序關(guān)系的重要的特殊特征偏序關(guān)系的重要的特殊特征,因而略去這樣的自回因而略去這樣的自回路不會對偏序關(guān)系的研究造成任何損害路不會對偏序關(guān)系的研究造成任何損害,而只會使而只會使它自身的特點更加突出它自身的特點更加突出,以便于深入研究以便于深入研究);此外如下此外如下形狀的有向邊也可略去形狀的有向邊也可略去:設(shè)設(shè)

22、x,y,z是集合中某三個元是集合中某三個元素素,如果有如果有xy和和yz成立成立,那么由傳遞性就必然也那么由傳遞性就必然也有有xz成立成立. 這就是說這就是說,只要從結(jié)點只要從結(jié)點x到結(jié)點到結(jié)點y有一條有向邊有一條有向邊,且從結(jié)點且從結(jié)點y到結(jié)點到結(jié)點z也有一條有向邊也有一條有向邊,那么從結(jié)點那么從結(jié)點x到到結(jié)點結(jié)點z必然也有一條有向邊必然也有一條有向邊,因而從結(jié)點因而從結(jié)點x到結(jié)點到結(jié)點z的的這條有向邊是不必畫出來的這條有向邊是不必畫出來的.這樣的簡化導(dǎo)致與原這樣的簡化導(dǎo)致與原來的關(guān)系圖本質(zhì)上完全相同、結(jié)構(gòu)上更為簡潔的來的關(guān)系圖本質(zhì)上完全相同、結(jié)構(gòu)上更為簡潔的Hasse圖圖.Hasse圖保留

23、了原來關(guān)系圖中所有重要的圖保留了原來關(guān)系圖中所有重要的特征特征.為了敘述為了敘述Hasse圖方便起見圖方便起見,我們先給出下面我們先給出下面的定義的定義.定義定義13.5(偏序集的蓋偏序集的蓋)設(shè)設(shè)是一個偏序集是一個偏序集,x,y是是A中兩個元素中兩個元素,x y,如果不存在元素如果不存在元素z A,z x,x y,使得同時有使得同時有xz和和zy成立成立,則稱元素則稱元素y蓋住了元素蓋住了元素x.稱偏序關(guān)系稱偏序關(guān)系的如下子集合的如下子集合 |x,y A,y蓋住蓋住x為偏序集的蓋為偏序集的蓋,記為記為CovA,也就是也就是 CovA=|x,y A,y蓋住蓋住x.定義定義13.6(Hasse圖

24、圖)按照下面程序畫出的圖稱為給定按照下面程序畫出的圖稱為給定偏序集偏序集的的Hasse圖圖:(1)求出求出CovA;(2)用小圓圈代表每個元素用小圓圈代表每個元素;(3)將所有元素所代表的小圓圈畫到圖上將所有元素所代表的小圓圈畫到圖上,如果如果xy 且且x y,就將代表就將代表x的小圓圈畫在代表的小圓圈畫在代表y的小圓圈的小圓圈 的下面的下面;(4)如果如果 CovA,就在代表就在代表x的小圓圈與代表的小圓圈與代表y的的 小圓圈之間連一無向線段小圓圈之間連一無向線段.以上面的例以上面的例3為例為例,容易算出有容易算出有CovA=,. 故而它的故而它的Hasse圖如下圖所示圖如下圖所示.定義定義

25、13.7(極大元和極小元極大元和極小元)設(shè)設(shè)是一個偏序是一個偏序集集,B是是A的一個子集的一個子集.我們稱元素我們稱元素x0是是B的一個極大的一個極大元元,如果如果:(1) x0 B;(2) ( x)(x B) (x x0 ) (x0 x). 我們稱元素我們稱元素y0是是B的一個極小元的一個極小元,如果如果:(3) y0 B;(4) ( y)(y B) (y y0 ) (yy0).定義定義13.8(最大元和最小元最大元和最小元)設(shè)設(shè)是一個偏序是一個偏序集集,B是是A的一個子集的一個子集.我們稱元素我們稱元素x0是是B的一個最大的一個最大元元,如果如果:(1) x0 B;(2) ( x)(x B

26、) (xx0). 我們稱元素我們稱元素y0是是B的一個極小元的一個極小元,如果如果:(3) y0 B;(4) ( y)(y B) (y0y).(注注)B的最大元和最小元通常用符號的最大元和最小元通常用符號maxB和和minB 來表示來表示.以上面的例以上面的例3為例為例,分別考慮集合的如下幾個子集分別考慮集合的如下幾個子集:1B1=2,3,4,5,6有三個極大元有三個極大元4,5,6;有三個極小元有三個極小元 2,3,5.但它既無最大元但它既無最大元,也無最小元也無最小元.2B2=1,2,3,4,6有兩個極大元有兩個極大元4,6;有一個極小元有一個極小元1. 它沒有最大元它沒有最大元,但有最小

27、元但有最小元1.3B3=1,3,6有一個極大元有一個極大元6和一個極小元和一個極小元1,有最大有最大 元元6和最小元和最小元1.4B4=A有三個極大元有三個極大元4,5,6;有一個極小元有一個極小元1.它沒有它沒有 最大元最大元,但有最小元但有最小元1.從上面的例子看出從上面的例子看出,偏序集的子集必有極大元偏序集的子集必有極大元,也必有極小元也必有極小元;且有可能有多個極大元或者多且有可能有多個極大元或者多個極小元個極小元(極大元必在極大元必在Hasse圖該子集合的最圖該子集合的最上面元素之中上面元素之中,極小元必在極小元必在Hasse圖的該子集圖的該子集合的最下面元素之中合的最下面元素之中

28、,不同的極大元之間都是不同的極大元之間都是不可比較的不可比較的,不同的極小元之間也都是不可比不同的極小元之間也都是不可比較的較的).但是給定子集合的最大元和最小元卻但是給定子集合的最大元和最小元卻不一定存在不一定存在.定理定理13.1 最大最大(最小最小)元如果存在元如果存在,則必定是唯一的則必定是唯一的.證明證明:僅以最大元為例證明之僅以最大元為例證明之.設(shè)設(shè)B是偏序集是偏序集的一個子集的一個子集.如果如果x1和和x2都是都是B的最大元的最大元,那么由最大那么由最大元的定義必同時有元的定義必同時有x1x2和和x2x1成立成立,由于偏序關(guān)由于偏序關(guān)系滿足反對稱性系滿足反對稱性,從而必有從而必有

29、x1= x2成立成立,這正是所要這正是所要證明的證明的.定義定義13.9(上界和下界上界和下界)設(shè)設(shè)是一個偏序集是一個偏序集,B是是A的一個子集的一個子集.我們稱元素我們稱元素x0是是B的一個上界的一個上界,如果如果:(1) x0 A;(2) ( x)(x B) (xx0). 我們稱元素我們稱元素y0是是B的一個下界的一個下界,如果如果:(3) y0 A;(4) ( y)(y B) (y0y).定義定義13.10(上確界和下確界上確界和下確界)設(shè)設(shè)是一個偏序是一個偏序集集,B是是A的一個子集的一個子集.我們稱元素我們稱元素x0是是B的一個上確的一個上確界界(或稱為最小上界或稱為最小上界),如果

30、如果:(1)x0是是B的一個上界的一個上界;(2)如果如果x也是也是B的一個上界的一個上界,那么必有那么必有x0 x. 我們稱元素我們稱元素y0是是B的一個下確界的一個下確界(或稱為最大下或稱為最大下界界),如果如果:(3)y0是是B的一個下界的一個下界;(4)如果如果y也是也是B的一個下界的一個下界,那么必有那么必有yy0.(注注)由定義容易看出由定義容易看出:上確界就是諸個上界中最小上確界就是諸個上界中最小的那個上界的那個上界,而下確界就是諸個下界中最大的那個而下確界就是諸個下界中最大的那個下界下界.B的上確界常記為的上確界常記為lubB(least upper bound),B的下確界常

31、記為的下確界常記為glbB(greatest lower bound).也有的也有的書上把的上確界和下確界分別記為書上把的上確界和下確界分別記為supB以及以及infB.例例5. 改取集合改取集合A=2,3,12,18,仍取通常的整除關(guān)系仍取通常的整除關(guān)系作為該集合上的偏序關(guān)系作為該集合上的偏序關(guān)系: x,y A,xy x|y.在這個例子的集合在這個例子的集合A中選取如下五個子集分別討論中選取如下五個子集分別討論相應(yīng)的子集合的極大極小元、最大最小元、上界相應(yīng)的子集合的極大極小元、最大最小元、上界和下界以及上確界和下確界和下界以及上確界和下確界:1B1=2,3有兩個極大元有兩個極大元2和和3以及

32、兩個極小元以及兩個極小元2和和3;它沒有最大元它沒有最大元,也沒有最小元也沒有最小元;它有兩個上界它有兩個上界12和和18,但是沒有上確界但是沒有上確界;它沒有下界它沒有下界,當(dāng)然也沒有下確界當(dāng)然也沒有下確界.2B2=12,18有兩個個極大元有兩個個極大元12和和18;也有兩個極也有兩個極小元小元12和和18.它沒有最大元它沒有最大元,也沒有最小元也沒有最小元.它沒有上它沒有上界界,但是有兩個下界但是有兩個下界2和和3.但是既沒有上確界但是既沒有上確界,也沒有也沒有下確界下確界.3B3=2,3,12有一個極大元有一個極大元12和兩個極小元和兩個極小元2和和3.有最大元有最大元12,但沒有最小元

33、但沒有最小元.它有一個上界它有一個上界12,當(dāng)然當(dāng)然12也是它的上確界也是它的上確界;它沒有下界它沒有下界,也沒有下確界也沒有下確界.4B4=2,12,18有兩個極大元有兩個極大元12和和18,有一個極小元有一個極小元2.它沒有最大元它沒有最大元,但有最小元但有最小元2.它沒有上界它沒有上界,當(dāng)然也當(dāng)然也沒有上確界沒有上確界;它有一個下界它有一個下界2,顯然顯然2也是它的下確界也是它的下確界.5B5=A=2,3,12,18 ,它有兩個個極大元它有兩個個極大元12和和18,也也有兩個極小元有兩個極小元2和和3.但是既沒有最大元但是既沒有最大元,也沒有最小也沒有最小元元.它沒有上界它沒有上界,也沒

34、有下界也沒有下界;當(dāng)然它既沒有上確界當(dāng)然它既沒有上確界,也沒有下確界也沒有下確界. 根據(jù)上述定義根據(jù)上述定義,顯然有下面的定理成立顯然有下面的定理成立:定理定理13.2 設(shè)設(shè)是一個偏序集是一個偏序集,B是是A的一個子集的一個子集.那么有以下結(jié)論成立那么有以下結(jié)論成立:(1)如果如果B有最大元有最大元,那么最大元必也是它的極大元那么最大元必也是它的極大元,也是它的上界也是它的上界,也是它的上確界也是它的上確界.(2)如果如果B有最小元有最小元,那么最小元必也是它的極小元那么最小元必也是它的極小元,也是它的下界也是它的下界,也是它的下確界也是它的下確界.(3)如果如果B有上確界有上確界x0,且且x

35、0 B,那么那么x0必也是必也是B的最大的最大元和極大元元和極大元.(4)如果如果B有下確界有下確界y0,且且y0 B,那么那么y0必也是必也是B的最小的最小元和極小元元和極小元.(5)如果如果還是一個全序集還是一個全序集,那么那么B的極大元必的極大元必也是也是B的最大元的最大元.(6)如果如果還是一個全序集還是一個全序集,那么那么B的極小元必的極小元必也是的最小元也是的最小元.(7)如果如果還是一個全序集還是一個全序集,且它有上界且它有上界,那么它那么它必有上確界必有上確界.(8)如果如果還是一個全序集還是一個全序集,且它有下界且它有下界,那么它那么它必有下確界必有下確界.定義定義13.11

36、(良序集良序集)設(shè)設(shè)是一個偏序集是一個偏序集,如果如果A的的任何一個非空子集都必有最小元任何一個非空子集都必有最小元,則稱則稱是一是一個良序集個良序集.例例6. 取實數(shù)集合取實數(shù)集合 與實數(shù)的與實數(shù)的關(guān)系作成的偏關(guān)系作成的偏序集序集.根據(jù)關(guān)系的定義可知根據(jù)關(guān)系的定義可知,對于對于 的任何非空的任何非空子集合子集合B,B的最小元就是的最小元就是B中最小的那個實數(shù)中最小的那個實數(shù).特別地特別地,如果取如果取 的非空子集為的非空子集為(0,1中所有實中所有實數(shù)組成的集合數(shù)組成的集合,那么顯然它沒有最小元存在那么顯然它沒有最小元存在.從從而而僅僅是個偏序集僅僅是個偏序集,但卻不是良序集但卻不是良序集. 注意到注意到還是一個全序集還是一個全序集,從而上面這從而上面這個例子表明個例子表明:并非每個全序集都是良序的并非每個全序集都是良序的.然然而可以證明而可以證明,任何有限的全序集都是良序的任