11-序关系重点课件.ppt

1、3.12序关系序关系定义：定义：设设R是非空集合是非空集合A上的关系，上的关系， 若若R是自反、反对称和传递的，是自反、反对称和传递的， 则称则称R为为A上的偏序关系。称有上的偏序关系。称有 序偶序偶为偏序集。为偏序集。一、偏序关系一、偏序关系偏序关系一般记为偏序关系一般记为 偏序集一般记为偏序集一般记为 xy (读作小于等于读作小于等于)例：例：证明集合证明集合A=2,3,6,12,24,36上上 的整除关系是偏序关系。的整除关系是偏序关系。 证明：证明：R=|x,y A,x|yx|y表示：表示：x整除整除y（y被被x整除）整除） 对于任意的对于任意的x Ax|x R R是自反的是自反的 对

2、于任意的对于任意的x,y A， 若若 x|y 且且 y|x 则则 x=y 即：即： 若若 R且且 R则则x=y R是反对称的是反对称的 对于任意的对于任意的, R， 有有x|y 且且 y|z 有有x|z R R是传递的是传递的综合、，综合、，R是偏序关系是偏序关系例例: (1) 集合族上集合族上: 子集关系、包含关系子集关系、包含关系 (2) 正自然数集正自然数集N+上上: 整除关系、整倍数关系整除关系、整倍数关系 (3) 实数集实数集R上上: 小于等于关系、大于等于关系小于等于关系、大于等于关系 若若是是A上的偏序关系，上的偏序关系， 则则-1 (记记)也是也是A上的偏序关系上的偏序关系,

3、和和 都是偏序集。都是偏序集。定义：定义：设设是非空集合是非空集合A上的偏序关上的偏序关 系，对于系，对于x,y A :若有若有 或或 ， 则称则称 x 与与 y 可比可比若有若有 且且 ， 则称则称 x 与与 y 不可比不可比若有若有 且且 x y ， 则称则称 xy（读作（读作小于小于） 在偏序集在偏序集 中，中， x,y A，恰符合以下三种情况之一：，恰符合以下三种情况之一： (1) x与与y 不可比不可比 (2) xy (或或 yx) (3) x=y例：例：2,3,6,12,24,36 上的整除关系上的整除关系 : (1) 2与与3、24与与36不可比不可比 (2) 6与与6、6与与1

4、2、6与与3可比可比 (3) 66、612、36 66、612、36 有穷偏序集的关系图，有穷偏序集的关系图， 可以简化为哈斯图。可以简化为哈斯图。二、哈斯图二、哈斯图定义：定义： 设设 为偏序集，对于任意为偏序集，对于任意x, y A，若，若xy，且不存在，且不存在 z A ，使得使得 xzy，则称，则称 y 盖住盖住 x 。 例：例：2,3,6,12,24,36 上的整除关系上的整除关系 : 6|36，636，但，但36没有盖住没有盖住6， 36盖住盖住12，12盖住盖住6 哈斯图哈斯图的画法：的画法： 对于任意对于任意x,y A，若，若xy，则，则 将将x画在画在y的下方的下方 若若y盖

5、住盖住x，则用一条线段连接，则用一条线段连接 x和和y 对于有穷偏序集，哈斯图是关系图的简化。对于有穷偏序集，哈斯图是关系图的简化。例：例：2,4,6,8上的整除关系上的整除关系44268682例：例： 2,3,6,12,24,36 上有上有整除关系整除关系 和和整倍数关系整倍数关系 , 画出哈斯图。画出哈斯图。236361224243361262例：例：集合集合A=a,b,c , P(A)上有上有子集关系子集关系 , 画出哈斯图。画出哈斯图。a,b,cbca,ba,cb,c a例：例：根据哈斯图，根据哈斯图，写出偏序关系。写出偏序关系。4268解：解：A = 2,4,6,8R = , , ,

6、 , , A上的整倍数关系上的整倍数关系定义：定义：设设 为偏序集为偏序集 , 若对任若对任 意的意的 x,yA，x与与y 都是可比都是可比 的，则称的，则称 为为 A 上的上的全序关全序关 系系，称，称 为为全序集全序集。 三、全序关系三、全序关系全序关系一定是偏序关系，偏序关系全序关系一定是偏序关系，偏序关系不一定是全序关系。不一定是全序关系。例：例：2,4,6,8 上的上的整除关系整除关系不是全序不是全序 关系，关系，小于等于关系小于等于关系是全序关系。是全序关系。42688642例：例：(1) 实数集上的小于等于关系、大于实数集上的小于等于关系、大于 等于关系：等于关系：是是全序关系全

7、序关系(2) 集合族上的子集关系、包含关系：集合族上的子集关系、包含关系： 不是不是全序关系全序关系(3) 正自然数集上的整除关系、整倍正自然数集上的整除关系、整倍 数关系：数关系：不是不是全序关系全序关系 最小元最小元 最大元最大元极小元极小元 极大元极大元下界下界 上界上界下确界下确界 上确界上确界四、偏序集中一些特殊元素四、偏序集中一些特殊元素定义：定义：设设 为偏序集，为偏序集，B A ： 若若 y B，使得，使得 x (x B yx)， 则称则称 y 是是 B 的的最小元最小元 若若 y B，使得，使得 x (x B xy)， 则称则称 y 是是 B 的的最大元最大元 若若 y B，

8、使得，使得 x (x B xy)， 则称则称 y 是是 B 的的极小元极小元 若若 y B，使得，使得 x (x B yx)， 则称则称 y 是是 B 的的极大元极大元例：例： 2,3,6,12,24,36 上的整除关系，上的整除关系， 求求 2,3,6,12 的最元、极元。的最元、极元。236361224最小元：无最小元：无最大元：最大元：12极小元：极小元：2，3极大元：极大元：12最元与极元是有区别的：最元与极元是有区别的： 最元与最元与 B 中其它元素都可比，中其它元素都可比， 是是 B 中最小中最小(大大)的元素的元素 极元不一定与极元不一定与 B 中元素都可比，中元素都可比， 只要

9、没有比它小只要没有比它小(大大)的元素，的元素， 它就是极小它就是极小(大大)元元定理：定理：偏序集的非空子集，偏序集的非空子集，可能没有最元，若有必唯一，可能没有最元，若有必唯一，可能没有极元，若有未必唯一可能没有极元，若有未必唯一 。定义：定义：设设 为偏序集，为偏序集，B A ： 若若 y A，使得，使得 x (x Byx)， 则称则称 y是是B的的下界下界 若若 y A，使得，使得 x (x Bxy)， 则称则称 y是是B的的上界上界 令令 C = y | y是是B的下界的下界 ， 则称则称 C的最大元的最大元 是是B的的下确界下确界 令令 C = y | y是是B的上界的上界 ， 则

10、称则称 C的最小元的最小元 是是B的的上确界上确界例：例： 2,3,6,12,24,36 上的整除关系，上的整除关系， 求求 2,3,6,12 的界、确界。的界、确界。236361224下界：无下界：无上界：上界：12, 24, 36下确界：无下确界：无上确界：上确界：12说明：说明： B的界、确界在的界、确界在 A 的范围中，的范围中， 可能在可能在B中，也可能不在中，也可能不在B中；中； 下确界是下界中的最大，下确界是下界中的最大， 上确界是上界中的最小。上确界是上界中的最小。定理：定理：偏序集的非空子集，偏序集的非空子集，可能没有确界，若有必唯一，可能没有确界，若有必唯一，可能没有界，若

11、有未必唯一可能没有界，若有未必唯一 。定理：定理：对偏序集的非空子集，对偏序集的非空子集， 最小元一定是下界，且是下确界；最小元一定是下界，且是下确界；下界、下确界不一定是最小元。下界、下确界不一定是最小元。 最大元一定是上界，且是上确界；最大元一定是上界，且是上确界；上界、上确界不一定是最大元。上界、上确界不一定是最大元。没有最元、极元、确界、界没有最元、极元、确界、界例：例：整数集整数集 Z 上的上的 小于等于关系小于等于关系 给定给定 Z 的奇数子集的奇数子集 考虑其最元、极元、确界、界考虑其最元、极元、确界、界定义：定义：设设 为偏序集为偏序集 , 若若A的的任意任意非空子集都有最小元

12、，则称非空子集都有最小元，则称为为A上的上的良序关系良序关系，称，称为为良序集良序集。五、良序关系五、良序关系例：例： 是良序集，是良序集， 、 不是良序集不是良序集 定理：定理： 良序集一定是全序集。良序集一定是全序集。 有限的全序集一定是良序集有限的全序集一定是良序集 (无限的全序集不一定是良序集无限的全序集不一定是良序集)。证明：证明：证明：证明： 证明良序集一定是全序集：证明良序集一定是全序集：良序集良序集的任意非空子集都有最小元，的任意非空子集都有最小元，则对于则对于A中中任意任意两个元素两个元素x,y，x,y有最小元有最小元x与与y可比可比是全序集是全序集 证明有限的全序集一定是良序集：证明有限的全序集一定是良序集： 全序集全序集中，中， 任意两个元素可比，任意两个元素可比， 又又A是有限集合是有限集合 任意非空子集都有最小元任意非空子集都有最小元 是良序集是良序集 序关系，反映了集合中元素的序关系，反映了集合中元素的顺序顺序性。性。小结：小结：P146 3-12 (5) (7)作业作业7：