1、第二節(jié) 關 系(relations),的基本概念及其性質 1.2.2等價關系 1.2.3部分序關系,1.2.1 關系的基本概念及其性質,定義1.2.1 設A1,A2,An是n個集合， 集合A1A2 An的一個子集F稱為A1,A2,An上的一個n元關系。特別地，集合AB中的一個子集R，稱為集合A與B上的一個二元關系(binary relation)，簡稱為關系。 對于xA，yB，若(x,y)R則稱x，y有關系R，記為xRy；若(x,y)R，則稱x，y沒有關系R，記為xRy。 若B=A，則R稱為A上的二元關系。,關系的特點,AA上的任一子集都是A上的一個關系； 若A=n，則A上的關系有 個。 A上

2、的三個特殊關系，即空關系；全域關系EA=AA；相等關系IA=(x,x)xA。 有序偶(a,b)=(c,d)的充要條件是a=c，b=d。,關系的補充說明,為了便于關系定義的理解并且與我們頭腦中不夠清晰嚴密的關系相區(qū)分，我們首先給出下列問題描述。 例假設目前中國乒乓球對男子隊員集合是A=馬琳，王勵勤，馬龍，王皓，郝帥，陳杞，閆森，女隊員集合B=張怡寧，郭躍，郭炎，李曉霞，丁寧，牛劍鋒，劉詩雯?，F(xiàn)在要出征乒乓球世界杯賽，如果按照上面關系的定義，對男子雙打，女子雙打和混合雙打分別可以構造出249個關系，但實際上這里的很多關系是沒有實際意義的。假設教練組根據(jù)個人狀態(tài)和實際情況確定雙打和混雙組合如下：男子

3、雙打關系R1=(馬琳,陳杞)，(王勵勤,馬龍)，(王皓，郝帥)，(陳杞, 馬琳)，(馬龍,王勵勤)，(郝帥，王皓) ； 女子雙打關系R2=(張怡寧,丁寧)，(郭躍,李曉霞)，(郭炎,牛劍鋒)，（丁寧, 張怡寧)，(李曉霞, 郭躍)，(牛劍鋒,郭炎)； 男女混雙關系R3=(馬龍, 張怡寧)，(王皓, 郭躍)，(郝帥, 劉詩雯)，(張怡寧, 馬龍)，(郭躍,王皓)，(劉詩雯, 郝帥)。,從上述三個關系我們可以清晰地看出那些隊員之間構成所需確切關系，并且把人們頭腦中模糊的對稱關系也顯示地表達出來，而不是人們頭腦中僅需要前三個二元有序對的關系能夠確切表達的,這也是人與計算機理解問題的差異。這也是我們書

4、中的關系與我們日常所說關系的區(qū)別。 實際上關系還可以用坐標系來描述，例如二元關系可以用平面上的離散點坐標系來描述，兩個坐標上的離散點集對應我們討論的兩個集合，這兩個集合可以不同也可以相同，不如用坐標描述男子雙打組合關系時這兩個集合相同，而男女混雙時不同，對于三元及以上關系可以用三維及以上坐標系表示。坐標系中不同點的組合就構成了不同的關系。,關系的補充說明,例,設A=a,b,c,d,e,f為學生集合，B=,為選修課程集合，C=2,3,4,5為學習成績集合，學生與課程之間存在著一種關系即“選修關系”；學生、課程和成績之間也存在著一種叫做“學習成績關系”。設用R表示選修關系，S表示學習成績關系，那么

5、R為A與B上的二元關系，S為A，B和C上的三元關系。,R=(a,),(a,),(b,),(b,),(c,),(c,),(e,),(f,) 表示學生a選修課程，；學生b選修課程，；學生c選修課程，；學生e 選修課程；學生f選修課程；而學生d沒有選修任何課程。 S=(a,5), (a, ,5), (b, , 3), (c, ,4), (f, ,2) 表示學生a所選的兩門課程成績都是5分；學生b所選課程的成績是3分；學生c所選課程的成績是4分；學生f所選課程的成績是2分。,關系是集合，因此集合的方法對關系都是有效的。因而有子關系，關系的并、交、差、余等運算。 例：R，S是集合A上的兩個關系，若RS，

6、則稱R為S的子關系； 對任意x，yA，有 x(RS)y當且僅當xRy或者xSy x(R S)y當且僅當xRy并且xSy x(R-S)y當且僅當xRy并且xSy x y當且僅當xR y,定義1.2.2 逆關系(inverse relation),設R是集合A上的一個關系。令R-1 =(y, x)xA, yA, 并且有xRy，則稱關系R-1為關系R的逆。 例如，小于關系的逆關系是大于關系，大于關系的逆關系是小于關系，相等關系的逆關系仍是相等關系。 例：R=(a,b),(b,c),(a,c),(b,d),則R-1 = (b,a),(c,b),(c,a),(d,b),定義1.2.3 自反關系(refl

7、exive),集合A 上的關系R稱為是自反的(反身的)，如果對每一個xA，都有xRx。 例：A=a, b, c, A 上的關系R1=(a,b),(b,b),(b,c) R2=(a,a),(a,b),(b,b),(b,c),(c,c) R是自反的當且僅當IAR，R是自反的當且僅當R-1是自反的 。,定義1.2.4 反自反關系(irreflexive),集合A上的關系R稱為反自反的，如果對任意的xA，xRx均不成立。或者說對任意的xA，都有xRx。 例：A=a, b, c, A上的關系R1=(a,b),(b,b),(b,c) R2=(a,b),(b,c),(a,c) 顯然，R是反自反的當且僅當 I

8、AR=。,討論：,是否存在既具有自反性，又具有反自反性的關系？ 是否存在既不具有自反性，又不具有反自反性的關系？ 空關系 、全域關系EA、相等關系IA是否具有自反性，或反自反性？,定義1.2.4 對稱關系(symmetric),集合A上的關系R稱為對稱的，如果xRy，則yRx。其中xA，yA。 例：A=a, b, c, A上的關系R1=(a,a),(a,b),(b,a),(b,c) R2=(a,a),(b,b),(c,b),(b,c),(a,c),(c,a) R是對稱的當且僅當R-1=R 。,定義1.2.4反對稱關系(antisymmetric),集合A上的關系R稱為反對稱的,如果xRy,則y

9、 Rx,除非x=y時成立。 其中xA,yA。 。 例：A=a, b, c, A上的關系R1=(a,a),(a,b),(b,c) R2=(a,a),(b,b),(c,b),(b,c),(c,a) R是反對稱的當且僅當RR-1IA 。,討論：,是否存在既具有對稱性，又具有反對稱性的關系？ 是否存在既不具有對稱性，又不具有反對稱性的關系？ 空關系 、全域關系EA、相等關系IA是否具有對稱性，或反對稱性？,定義1.2.4 傳遞關系(transitive),集合A上的關系R稱為是傳遞的，如果xRy，yRz，則xRz。 其中xA，yA，zA。 例：A=a, b, c, A上的關系R1=(a,a),(a,b

10、),(b,c),(a,c) ， R2=(a,b),(a,c), R3=(a,a),(c,b),(b,c),(c,a)數(shù)的相等關系、大于關系、小于關系都具有傳遞性。,定義1.2.4 關系的乘積(composite),設R，S是集合A上的兩個關系，令RS=(x, y)xA, yA且存在一個zA使得xRz，zSy。稱關系RS為關系R和S的乘積或合成(composite) 。 例：兄弟關系和父子關系的乘積是叔侄關系，而姐妹關系和母子關系的乘積是姨與外甥關系。,例：,A=a, b, c, d, A上的關系 R和S ，R=(a, a),(b,a),(c,d)，S= (a,c),(a,d),(b,c),(c

11、,b)，則RS = (a,c),(a,d),(b,c),(b,d)SR = (a,d), (b,d),(c,a) 顯然，RSSR，關系的乘法不滿足交換率。,關系的乘法滿足結合率,設R，S和T是集合A上的三個關系，證明： (RS)T= R(ST)。 分析：因為關系的乘積仍是集合，要證明集合相等，就要證明集合互為包含，我們首先證明(RS)TR(ST)，再證明R(ST) ( RS)T 。,證明(RS)TR(ST),任取(x, y)(RS)T，即x(RS)Ty，由關 系乘積的定義知，存在zA使得x(RS)z， zTy，同樣對x(RS)z，必存在zA使得 xRz，zSz。故由zSz 和zTy知z(ST)

12、y， 再有xRz得xR(ST)y，即(x, y) R(ST), 從而證得了(RS)TR(ST),證明R(ST) (RS)T,任取(x, y)R(ST), 即xR(ST)y，由關 系乘積的定義知，存在zA使得xRz， z(ST)y，同樣對z(ST)y，必存在zA使得 zSz，zTy 。故由xRz和zSz知x(RS)z， 再有zTy，得x(RS)Ty ，即(x,y)(RS)T， 從而證得了R(ST) (RS)T。 因此， (RS)T=R(ST)得證。,對A上任意的關系R，有RIA= IA R= R,由于關系的乘法運算滿足結合律，因此我們可以用“冪”表示集合A上同一個關系的乘積，即 規(guī)定，R0=IA

13、。,綜合思考題,設A表示工人的集合,B表示工作的集合. R1 表示A到B的二元關系,R1=(a,b)aA,bB, a分配去做工作b.設R2表示A到A的二元關系,R2=(a1,a2)a1,a2A,a1和a2不能友好相處.請你用R1和R2表示關系 R,使得xRy表示 x,y分配去做同樣工作且能友好相處.,因為R1是A到B的二元關系,故R1-1表示B到A的二元關系, 則R1R1-1表示從A到A的二元關系,即由分配做同一樣工作的兩個人構成的序偶的全體.因此R=R1R1-1-R2,定理1.2.1,設R是A上的關系，m，n為任意的自然數(shù)，那么，(1) RmRn=Rm+n；(2) (Rm)n=Rmn。 證明

14、：(1)任給m，對n作歸納法。n=0時，Rm R0=Rm IA= Rm = Rm+0。假設Rm Rn=Rm+n，那么RmRn+1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。,(2)任給m，對n作歸納法。n=0時，(Rm)0=IA= R0 = Rm0。假設(Rm)n=Rmn。那么(Rm)n+1= (Rm)n Rm = Rmn Rm= Rmn+m= Rm(n+1) 。,定理1.2.2,設集合A的元素數(shù)為n，R是A上二元關系，那么存在自然數(shù)i，j(0ij )使得Ri=Rj。 證明：由關系的特點知道，若A=n，則A上的關系有 個，因此，在 R0，R1

15、，R2，這 +1個關系中，至少有兩個是相同的（鴿巢原理），即有i,j(0ij )使得Ri=Rj。,定理1.2.3,設R是集合A上的關系，若存在自然數(shù)i，j(ij)，使得Ri=Rj，則有 (1)Ri+k=Rj+k，kN；(2)Ri+kp+m=Ri+m，其中k，mN，p=j-i。 證明： (1) Ri+k= Ri Rk =Rj Rk =Rj+k；,證明,(2),根據(jù)(1),根據(jù)(1),根據(jù)(1),定理1.2.4,集合A上的關系R具有傳遞性的充要條件是R2 R。 證明：必要性。若R具有傳遞性，任取 (x,y)R2，于是存在zA，使得xRz，zRy， 因為R是傳遞的，所以有xRy，即(x,y) R,故

16、R2 R。 充分性。如果xRy，yRz，則xR2z。 因為R2 R，故xRz。所以具有傳遞性的。,二元關系的表示方法,1列舉法:列出關系R中的所有序偶; 2關系矩陣;給定兩個有限 集合A=a1,a2,B=b1,b2,R為A到B的一個二元關系,則可以用下列關系矩陣MR=rijmn來表示R: r11 r12 r1n MR= r21 r22 r2n ： ： ： rm1 rm2 rmn 其中rij=1,若(ai,bj)R;否則rij=0,若(ai,bj)R 關系的矩陣表示與矩陣的行列對應的集合A和B上的元素順序是相關的,不同的排序會得到不同的關系矩陣.,二元關系的表示方法,3關系圖:給定兩個有限集合A

17、=a1,a2, am,B=b1,b2,bn,R為A到B的一個二元關系. 首先在平面上作m個結點代表a1,a2, am,然后作另外n結點代表b1,b2,bn.如果aiRbj,則畫一條從ai到 bj的有向弧,這樣的圖稱為R的關系圖.,關系的性質總結,定義1.2.9 關系的閉包(closure),設A是非空集合，R是A上的二元關系。稱R 是R的自反閉包(對稱閉包，傳遞閉包)，如果R滿足： （1）R是自反的(對稱的，傳遞的)； （2）RR； （3）對A上任意關系R， 若R R，且R是自反的(對稱的，傳遞的)，必有RR。,R 的自反閉包、對稱閉包和傳遞閉包分別記為r(R)，s(R)，t(R) ，也稱r，

18、s，t為閉包運算，它們作用于關系R后，產(chǎn)生包含R的最小的自反、對稱、傳遞的關系。,定理1.2.5,設R是集合A上的關系，那么， (1) r(R)=IAR； (2) s(R)=RR-1； (3) t(R)=,（1）證明 r(R)=IAR,因為IA IAR，所以IAR具有自反性； 顯然，R IAR 對A上任意關系R， 若R R，且R是自反的，往證IAR R。因為R是自反的，所以IA R ，又R R，所以IAR R。,（2）證明 s(R)=RR-1, 任取(x,y) RR-1 ，則(x,y) R或 (x,y)R-1 ，若(x,y)R，則有(y,x)R-1， 所以(y,x)RR-1；若(x,y)R-1

19、 ，則有 (y,x)R，所以(y,x)RR-1 ， RR-1具有對稱性； 顯然，R RR-1,對A上任意關系R， 若R R，且R是對稱的，往證RR-1 R。 任取(x,y)RR-1 ，則(x,y)R或(x,y)R-1 ， 若(x,y)R，因為R R，則(x,y)R ； 若(x,y)R-1 ，則有(y,x)R，則(y,x)R， 因為R是對稱的，所以(x,y)R ， 因此，RR-1 R。,（3）證明 t(R)=,對于任意x,y,zA，若(x,y) ， (y,z) , 則存在自然數(shù)j, k，使得(x,y) Rj，(y,z) Rk ，故(x,z) Rj Rk = Rj+k，從而(x，z) ，所以， 具

20、有傳遞性； 顯然，R ,對A上任意關系R， 若R R，且R是傳遞的，往證 R。為此只要證對任意正整數(shù)n，Rn R 。對n采用歸納法，n=1時，顯然有R1 R 。假設n=k時有Rk R ，任取(x, y)Rk+1，那么有z使(x,z)Rk，(z,y)R。根據(jù)歸納假設及題設，有(x,z)R ，(z,y)R。又R是傳遞的，故(x,y)R ，所以Rk+1 R；因此， R。證畢。,設R是有窮集合A上的關系，|A|=n，則 t(R)=,推論,1.2.2等價關系(equivalence relation),定義1.2.10設A是一個非空集合，R是A上二元關系。如果R具有自反性，對稱性，傳遞性，則稱R是一個等

21、價關系。 通常，用“ ”表示等價關系。 例：整數(shù)的同余關系，幾何圖形的面積相等關系，人群中的同姓關系、同齡關系等。,定義1.2.11 等價類(equivalence class),設A是一個非空集合，R是A上的等價關系。A的一個非空子集M叫做A關于R的一個等價類，如果,通常，用aR表示包含元素a的等價類，則 aR=x|(x,a)R ,a稱為該等價類代表元。,例：,設集合A=1,2,3,10，R是模3同余關系，則3R=6R=9R=3,6,9, 1R= 4R= 7R= 10R=1,4,7,10 , 2R= 5R= 8R= 2, 5, 8都是等價類。 設A是本教室中的所有人集合，在同姓關系下，則本教

22、室中所有姓“張”的人構成的集合是一個等價類,所有姓“王”的人構成的集合是一個等價類, 。,定理1.2.6,設是集合A上的等價關系，于是等價類是存在的。 證明: (1)任取aA，令Mx|xA并且xa，顯然，M非空。 (2)任取x1M，x2M，根據(jù)M的定義，則有x1a，x2a，而具有對稱性，傳遞性，所以x1x2。 (3)任取x1M，若x1y，則x1a，而具有對稱性，傳遞性，所以ya，故yM。 因此，M是一個等價類。,定理1.2.7,設是集合A上的等價關系，M1, M2 , ，是A中關于的所有等價類。于是AM1 M2 并且MiMj=(ij)，亦即，集合A上的等價關系把A分成了互不相交的等價類。,證明

23、：,任取Mi，Mj，ij。假設MiMj ，則必存在xMiMj，則任取aMi，b Mj，都有ax，bx，所以ab, 故MiMj，矛盾。 任取aA， 令MxxA并且xa，由定理1.2.6知，M是等價類，故有k，使得MMk，因為aM，所以，aM1M2Mk。顯然有M1 M2 A。故AM1 M2 。,定義1.2.12 劃分(partition),稱集合A的子集族C為A的劃分，如果：（1）若BC，則B；（2） ；（3）對任意的B，BC，若BB，則BB=。稱C中元素為劃分的單元，或劃分塊。 規(guī)定，A=時只有劃分，,例：,設A=1,2,3,4,5,6,7,8,9,10， C1=1,2,3,4,5,6,7,8,

24、9,10 C2=1,3,2,4,5,6,7,8,9,10 C3=1,4,7,10,2,5,8,3,6,9,定義1.2.13 商集(quotient set),設R是非空集合A上的等價關系，以R的所有不同等價類為元素作成的集合稱為A的商集，簡稱A的商集，記作A/R。 A/R恰是集合的一個劃分。 設集合A=1,2,3,10，R是模3同余關系，則A/R 1R，2R ，3R，這里 1R=1,4,7,10, 2R= 2, 5, 8, 3R=3,6,9,例1.2.3,設A=a1,a2, , an，n1。 (1)驗證EA，IA，Rij=IA(ai，aj)，(aj，ai)都是A上的等價關系，并求它們對應的商集

25、，其中ai，ajA，且ij。是A上的等價關系嗎？ (2)A=a,b,c，試求出A上的全體等價關系及其對應的商集。,解,(1)EA，IA，Rij是等價關系(證明略)。A/IA=a1,a2,an；A/EA=a1,a2,an；A/Rij=ai,aj,ak1,ak2,akn-2，其中k1,k2,kn-2均不等于i或j，共有C2n個。因為無自反性，所以不是A上的等價關系。,(2)按(1)中n=3的情況，A=a,b,c上有5種不同的等價關系： EA，其商集為A/EA=a,b,c； IA，其商集為A/IA=a,b,c； R12=IA(a,b),(b,a)，A/R12=a,b,c； R13=IA(a,c),(

26、c,a)，A/R13=a,c,b； R23=IA(b,c),(c,b)，A/R23=b,c,a；,定理1.2.8,設A為一個非空集合。(1)設R為A上的任意一個等價關系，則對應R的商集A/R為A的一個劃分。(2)設C為A的任一個劃分，令RC=(x,y)|x,yA并且x, y屬于C的同一劃分塊，則RC為A上的等價關系。,(1)證明：A/R是A的一個劃分,設商集A/R M1, M2 , ，則i (i=1,2, )是A關于R的等價類，根據(jù)等價類的定義知，i (i=1,2,3, );又根據(jù)定理1.2.7知，AM1 M2 ，并且MiMj=(ij) ，所以，A/R是A的一個劃分。,(2)證明：RC為A上的

27、等價關系,自反性；對任意的xA，有x和x屬于C的同一劃分塊，所以(x,x) RC，則RC 具有自反性； 對稱性；對任意的x,yA，若(x, y)RC，即x,y屬于C的同一劃分塊，亦即y, x 屬于C的同一劃分塊，所以(y,x) RC，則RC 具有對稱性；,(2)證明：RC為A上的等價關系,傳遞性；對任意的x, y, zA，若(x, y)RC， (y, z)RC，即x與y屬于同一劃分塊，y與z屬于同一劃分塊，則x與z也屬于同一劃分塊，所以(x,z) RC，則RC 具有傳遞性； 因此， RC為A上的等價關系。證畢。,第二類Stirling數(shù),將n個不同的球放入r個相同的盒中去，并且要求無空盒，有多

28、少種不同的放法？這里要求nr。 不同的放球方法數(shù)即為n元集合A的不同的劃分數(shù)，,設 表示將n個不同的球放入r個相同的盒中的方案數(shù)，稱 為第二類Stirling數(shù) 。,第二類Stirling數(shù)的性質,(1),(2)滿足如下的遞推公式:,例1.2.4,集合A=a，b，c，d上有多少不同的等價關系？ 解：不同的劃分個數(shù)為:不同的等價關系個數(shù)等于不同的劃分個數(shù)，所以不同的等價關系個數(shù)為15。,定義1.2.14 加細,設C和C都是集合A的劃分，若C的每個劃分塊都含于C的某個劃分塊中，則稱C是C 的加細。 例：設A=1,2,3,4,5,6,7,8,9,10， C1=1,2,3,4,5,6,7,8,9,10

29、 C2=1,3,2,4,5,6,7,8,9,10 C3=1,4,7,10,2,5,8,3,6,9,C是C的加細當且僅當RCRC,例： 設A=x|x是吉大計算機學院的本科生， C=0901班的學生，0902班的學生，0903班的學生, C=大一的學生, 大二的學生,大三的學生, 大四的學生 C對應的等價關系RC是同班關系， C對應的等價關系RC是同年級關系。,例1.2.5,設A=a，b，c，找出A的全部劃分及對應的等價關系，以及劃分間的加細和關系中的包含關系。 解: 由第二類Stirling數(shù)易知，A上共有 個劃分。,這些劃分分別為：C1=a,b,c，C2=a,b,c，C3=b,a,c，C4=c

30、,a,b，C5=a,b,c。 它們對應的等價關系分別為:RC1=EA，RC2=IA(b, c), (c, b)，RC3= IA(a, c), (c, a)，RC4= IA(a, b), (b, a)，RC5=IA。 C2， C3， C4，C5都是C1的加細，RC2，RC3，RC4，RC5都是RC1的子集。,1.2.2部分序關系(partial ordering),定義1.2.15 設R是集合A上的一個關系。如果R具有自反性，反對稱性，傳遞性，則稱R為一個部分序關系(半序關系、偏序關系)。集合A在部分序關系R下做成一個部分序集(半序集、偏序集)。記作(A，R) 。 通常，將部分序關系R寫做“”，

31、讀做“小于或等于”。 顯然，一個部分序集的子集仍為部分序集。,例,設A是整數(shù)集合， R是小于等于關系(或大于等于關系)。 設A是自然數(shù)集合，R是整除關系。 設A是一個集合族，R是“”關系。則(A,R)是一個部分序集；,哈斯圖 (Hasse diagram),以平面上的點代表部分序集中的元素。 1）若xy，且xy，則將x畫在y的下面。 2）若xy，xy，并且沒有不同于x，y的z，使得xzy(稱y蓋住x)，則在x，y之間用直線連結。,例:,設Aa, b, a,b, a,b, c, a,b, c,d, a,b,c,e， 則(A, ) 是一個部分序集。,例:,設A1,2,3, 4,5,6,8,10,1

32、2,24，R是整除關系，則(A, R) 是一個部分序集。,定義 鏈(chain),設(A, )是一個部分序集，對任意x, yA，如果xy，或yx，稱x與y可比(comparable) ；否則，稱x與y不可比。 一個部分序集的子集，其中任意兩個元素都可比，稱該子集為一條鏈(chain)。,例:,設A1,2,3, 4,5,6,8,10,12,24，R是整除關系，則(A, R) 是一個部分序集。,定義1.2.16 全序集(totally ordered set),一個部分序集(A, )說是一個全序集，如果(A, )本身是一條鏈。 顯然，全序集的子集仍為全序集。,例:,設A1,2,4, 8,16,32

33、,64，R是整除關系，則(A, R) 是一個全序集。,1,2,4,8,32,16,64,例:,設A整數(shù)集合，R是“小于等于”關系，則(A, R) 是一個全序集。,定義1.2.17擬序關系,設R是集合A上的一個關系。如果R具有反自反性，傳遞性，則稱R為一個擬序關系。記為，讀做“小于”。 例：數(shù)間的小于（“”）關系；集合間的真包含（“”）關系。,定義1.2.18,設(A, )是一個部分序集(poset)，(1)如果A中有一個元素a，對于所有的xA，都有xa(ax)，則稱a為集合A的最大(最小)元。 （2）A中元素a說是一個極大(極小)元，如果除a之外，A中沒有元素x，使得ax(xa)。,定義1.2

34、.18,(3) 對于A中的子集M，A中元素a稱為子集M的一個上界(下界)，如果對M中任意元素m，都有ma(am)。 (4) 對于A中的子集M，A中元素a稱為M的一個最小上界(或稱上確界)，如果a是M的一個上界，并且對M的任意一個上界x，都有ax。,定義1.2.18,(5) 對于A中的子集M，A中元素a稱為M的一個最大下界(或稱下確界) ，如果a是M的一個下界，并且對M的任意一個下界x，都有xa 。,例:,例:,例題,設A=1,2,3,12,是A上的整除關系,(A,)和哈斯圖如下,求B=2,4,6,C=4,6,9,D=1,2,5,10的特殊元素.,8,10,4,2,12,6,9,5,7,3,11

35、,1,定理1.2.9,設(A,)是一個部分序集，BA。 （1）若b是B的最大元(最小元)，則b必為B的最小上界(最大下界)； （2）若b為B的上(下)界，且bB，則b必為B的最大(最小)元； （3）若B有最大下界(最小上界)，則最大下界(最小上界)唯一。,定義1.2.19,設(A, )是一個部分序集。（1）稱(A, )是良基的，如果A的任意非空子集都有關于的極小元；（2）稱(A, )是良序集(well-ordered set)，如果(A, )是全序的、良基的。 例如：Ax|x是整數(shù)，0x100,在“”關系下，組成的部分序集是良基的，也是良序集。,引理,每一個非空有窮部分序集(A, )都有極小元素。 證明：選擇A的一個元素a0，如