序關(guān)系重點(diǎn)課件

1、3.12序關(guān)系定義：設(shè)R是非空集合A上的關(guān)系， 若R是自反、反對(duì)稱和傳遞的， 則稱R為A上的偏序關(guān)系。稱有 序偶為偏序集。一、偏序關(guān)系偏序關(guān)系一般記為 偏序集一般記為 xy (讀作小于等于)例：證明集合A=2,3,6,12,24,36上 的整除關(guān)系是偏序關(guān)系。 證明：R=|x,yA,x|yx|y表示：x整除y（y被x整除） 對(duì)于任意的xAx|x R R是自反的 對(duì)于任意的x,yA， 若 x|y 且 y|x 則 x=y 即： 若R且R則x=y R是反對(duì)稱的 對(duì)于任意的,R， 有x|y 且 y|z 有x|z R R是傳遞的綜合、，R是偏序關(guān)系例: (1) 集合族上: 子集關(guān)系、包含關(guān)系 (2) 正

2、自然數(shù)集N+上: 整除關(guān)系、整倍數(shù)關(guān)系 (3) 實(shí)數(shù)集R上: 小于等于關(guān)系、大于等于關(guān)系 若是A上的偏序關(guān)系， 則-1 (記)也是A上的偏序關(guān)系, 和 都是偏序集。定義：設(shè)是非空集合A上的偏序關(guān) 系，對(duì)于x,yA :若有 或 ， 則稱 x 與 y 可比若有 且 ， 則稱 x 與 y 不可比若有 且 xy ， 則稱 xy（讀作小于） 在偏序集 中，x,yA，恰符合以下三種情況之一： (1) x與y 不可比 (2) xy (或 yx) (3) x=y例：2,3,6,12,24,36 上的整除關(guān)系 : (1) 2與3、24與36不可比 (2) 6與6、6與12、6與3可比 (3) 66、612、36

3、 66、612、36 有窮偏序集的關(guān)系圖， 可以簡(jiǎn)化為哈斯圖。二、哈斯圖定義： 設(shè) 為偏序集，對(duì)于任意x, yA，若xy，且不存在 zA ，使得 xzy，則稱 y 蓋住 x 。 例：2,3,6,12,24,36 上的整除關(guān)系 : 6|36，636，但36沒(méi)有蓋住6， 36蓋住12，12蓋住6 哈斯圖的畫(huà)法： 對(duì)于任意x,yA，若xy，則 將x畫(huà)在y的下方 若y蓋住x，則用一條線段連接 x和y 對(duì)于有窮偏序集，哈斯圖是關(guān)系圖的簡(jiǎn)化。例：2,4,6,8上的整除關(guān)系44268682例： 2,3,6,12,24,36 上有整除關(guān)系 和整倍數(shù)關(guān)系 , 畫(huà)出哈斯圖。236361224243361262例：

4、集合A=a,b,c , P(A)上有子集關(guān)系 , 畫(huà)出哈斯圖。a,b,cbca,ba,cb,c a例：根據(jù)哈斯圖，寫(xiě)出偏序關(guān)系。4268解：A = 2,4,6,8R = , , , , , A上的整倍數(shù)關(guān)系定義：設(shè) 為偏序集 , 若對(duì)任 意的 x,yA，x與y 都是可比 的，則稱 為 A 上的全序關(guān) 系，稱 為全序集。 三、全序關(guān)系全序關(guān)系一定是偏序關(guān)系，偏序關(guān)系不一定是全序關(guān)系。例：2,4,6,8 上的整除關(guān)系不是全序 關(guān)系，小于等于關(guān)系是全序關(guān)系。42688642例：(1) 實(shí)數(shù)集上的小于等于關(guān)系、大于 等于關(guān)系：是全序關(guān)系(2) 集合族上的子集關(guān)系、包含關(guān)系： 不是全序關(guān)系(3) 正自然

5、數(shù)集上的整除關(guān)系、整倍 數(shù)關(guān)系：不是全序關(guān)系 最小元 最大元極小元 極大元下界 上界下確界 上確界四、偏序集中一些特殊元素定義：設(shè) 為偏序集，B A ： 若 yB，使得 x (xB yx)， 則稱 y 是 B 的最小元 若 yB，使得 x (xB xy)， 則稱 y 是 B 的最大元 若 yB，使得 x (xB xy)， 則稱 y 是 B 的極小元 若 yB，使得 x (xB yx)， 則稱 y 是 B 的極大元例： 2,3,6,12,24,36 上的整除關(guān)系， 求 2,3,6,12 的最元、極元。236361224最小元：無(wú)最大元：12極小元：2，3極大元：12最元與極元是有區(qū)別的： 最元與

6、 B 中其它元素都可比， 是 B 中最小(大)的元素 極元不一定與 B 中元素都可比， 只要沒(méi)有比它小(大)的元素， 它就是極小(大)元定理：偏序集的非空子集，可能沒(méi)有最元，若有必唯一，可能沒(méi)有極元，若有未必唯一 。定義：設(shè) 為偏序集，B A ： 若 yA，使得 x (xByx)， 則稱 y是B的下界 若 yA，使得 x (xBxy)， 則稱 y是B的上界 令 C = y | y是B的下界 ， 則稱 C的最大元 是B的下確界 令 C = y | y是B的上界 ， 則稱 C的最小元 是B的上確界例： 2,3,6,12,24,36 上的整除關(guān)系， 求 2,3,6,12 的界、確界。23636122

7、4下界：無(wú)上界：12, 24, 36下確界：無(wú)上確界：12說(shuō)明： B的界、確界在 A 的范圍中， 可能在B中，也可能不在B中； 下確界是下界中的最大， 上確界是上界中的最小。定理：偏序集的非空子集，可能沒(méi)有確界，若有必唯一，可能沒(méi)有界，若有未必唯一 。定理：對(duì)偏序集的非空子集， 最小元一定是下界，且是下確界；下界、下確界不一定是最小元。 最大元一定是上界，且是上確界；上界、上確界不一定是最大元。沒(méi)有最元、極元、確界、界例：整數(shù)集 Z 上的 小于等于關(guān)系 給定 Z 的奇數(shù)子集 考慮其最元、極元、確界、界定義：設(shè) 為偏序集 , 若A的任意非空子集都有最小元，則稱為A上的良序關(guān)系，稱為良序集。五、良序關(guān)系例： 是良序集， 、 不是良序集 定理： 良序集一定是全序集。 有限的全序集一定是良序集 (無(wú)限的全序集不一定是良序集)。證明：證明： 證明良序集一定是全序集：良序集的任意非空子集都有最小元，則對(duì)于A中任意兩個(gè)元素x,y