序关系重点课件

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

2、自然数集N+上: 整除关系、整倍数关系 (3) 实数集R上: 小于等于关系、大于等于关系 若是A上的偏序关系， 则-1 (记)也是A上的偏序关系, 和 都是偏序集。定义：设是非空集合A上的偏序关 系，对于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 上的整除关系 : (1) 2与3、24与36不可比 (2) 6与6、6与12、6与3可比 (3) 66、612、36

3、 66、612、36 有穷偏序集的关系图， 可以简化为哈斯图。二、哈斯图定义： 设 为偏序集，对于任意x, yA，若xy，且不存在 zA ，使得 xzy，则称 y 盖住 x 。 例：2,3,6,12,24,36 上的整除关系 : 6|36，636，但36没有盖住6， 36盖住12，12盖住6 哈斯图的画法： 对于任意x,yA，若xy，则 将x画在y的下方 若y盖住x，则用一条线段连接 x和y 对于有穷偏序集，哈斯图是关系图的简化。例：2,4,6,8上的整除关系44268682例： 2,3,6,12,24,36 上有整除关系 和整倍数关系 , 画出哈斯图。236361224243361262例：

4、集合A=a,b,c , P(A)上有子集关系 , 画出哈斯图。a,b,cbca,ba,cb,c a例：根据哈斯图，写出偏序关系。4268解：A = 2,4,6,8R = , , , , , A上的整倍数关系定义：设 为偏序集 , 若对任 意的 x,yA，x与y 都是可比 的，则称 为 A 上的全序关 系，称 为全序集。 三、全序关系全序关系一定是偏序关系，偏序关系不一定是全序关系。例：2,4,6,8 上的整除关系不是全序 关系，小于等于关系是全序关系。42688642例：(1) 实数集上的小于等于关系、大于 等于关系：是全序关系(2) 集合族上的子集关系、包含关系： 不是全序关系(3) 正自然

5、数集上的整除关系、整倍 数关系：不是全序关系 最小元 最大元极小元 极大元下界 上界下确界 上确界四、偏序集中一些特殊元素定义：设 为偏序集，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 上的整除关系， 求 2,3,6,12 的最元、极元。236361224最小元：无最大元：12极小元：2，3极大元：12最元与极元是有区别的： 最元与

6、 B 中其它元素都可比， 是 B 中最小(大)的元素 极元不一定与 B 中元素都可比， 只要没有比它小(大)的元素， 它就是极小(大)元定理：偏序集的非空子集，可能没有最元，若有必唯一，可能没有极元，若有未必唯一 。定义：设 为偏序集，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 上的整除关系， 求 2,3,6,12 的界、确界。23636122

7、4下界：无上界：12, 24, 36下确界：无上确界：12说明： B的界、确界在 A 的范围中， 可能在B中，也可能不在B中； 下确界是下界中的最大， 上确界是上界中的最小。定理：偏序集的非空子集，可能没有确界，若有必唯一，可能没有界，若有未必唯一 。定理：对偏序集的非空子集， 最小元一定是下界，且是下确界；下界、下确界不一定是最小元。 最大元一定是上界，且是上确界；上界、上确界不一定是最大元。没有最元、极元、确界、界例：整数集 Z 上的 小于等于关系 给定 Z 的奇数子集 考虑其最元、极元、确界、界定义：设 为偏序集 , 若A的任意非空子集都有最小元，则称为A上的良序关系，称为良序集。五、良序关系例： 是良序集， 、 不是良序集 定理： 良序集一定是全序集。 有限的全序集一定是良序集 (无限的全序集不一定是良序集)。证明：证明： 证明良序集一定是全序集：良序集的任意非空子集都有最小元，则对于A中任意两个元素x,y