偏序关系

一、偏序关系
（2） 偏序集 ＜A, R 意指在一个集合 A 中给定于一 个序列关系。若 x, y A且xy ，我们就说 y 在 x 的 后面或 x 在 y 的前面或 x 包含在 y 中。 例 1：说明实数集 R 上的小于等于关系是偏序 关系，即 R, ；任意集合 S 的幂集上的包含 关系是偏序关系,即 P(S ),
定义 4-25 设 A, 是一个偏序集合， B A ，若 存在一个元素 b B ， 对所有 x B 都有 xb ， 则称 b 是 B 的最大元； 若对所有 x B 都有 bx ， 则称 b 是 B 的最小元.特别 B A 时，称 b 为 A 的最大元（最小 元）
1.最大元和最小元
2.极大元和极小元
指出下列偏序集的极大元和极小元： （1）设 A={1, 2} ， 偏序集 P( A), ；
24} ，偏序集 A,| ； （2）设 A={2,3,6,12, 24，
（3）设 A {1, 4,6,8,7,10,0} ，偏序集 A,
极大（小）元与最大（小）元的区别 ： 最小（大）元存在，则必是唯一的，出现在 偏序关系哈斯图中最低 （高） 部的所有元素； 极小（大）元（不唯一） ，不同的极小（大） 元是不可比的；最小元必是极小元， 最大元 必是极大元； 对任何非空有限子集， 极大元， 极小元一定存在； 若子集 B 有最大元 （最小 元） ，则 B 的极大元（极小元）惟一。
二、哈斯图
画出下列偏序集的哈斯图 （1）设 A={1, 2} ，画出 A 的幂集 P ( A) 上的包含关系 的哈斯图； （2）设 A={2,3,6,12, 24,36} ，画出偏序集 A,| 的 哈斯图； （3）设 A {1, 4,6,8,7,10} ，画出 A, 的哈斯图
三、偏序集合A中的几个特殊的元素 1．最大元和最小元
小元） ，则必唯一。
三、偏序集合A中的几个特殊的元素
2．极大元和极小元 定义 4-26 设 A, 是一个偏序集合， B A ，若 存在一个元素 b B ，且在 B 中不存在元素 x ，使
b x ， bx ，则称 b 是 B 的极大元；若 B 中不存在
元素 x ，使 b x ， xb ，则称 b 是 B 的极小元。特 别 B A 时，称 b 为 A 的极大元（或极小元）
4.上确界和下确界 定义 4-28 设 ( A, ) 是一个偏序集， B A ，若
a A 是 B 的上界且对 B 中每个上界 x 都有
； ax ，则称 a 为 B 的上确界（或称最小上界） 若 a A 是 B 的下界且对 B 中每个下界 x 都有
xa ，则称 a 为 B 的下确界（或称最大下界）
（1）写出 R 的关系距阵，画出 R 的关系图。
4.上确界和下确界
（2） 证明 R 是 A 上的偏序关系，画出其哈斯图。
（3） 若 B {2， 3, 4,5} ，求 B 的最大元、最小元、极大元、
极小元、上确界和下确界。 例 4-18 对下列集合中的整除关系， 画出哈斯图， 并指出哪是 全序集，写出下列集合中的最大元、最小元、极大元、极小 元 （1） {1, 2,3, 4,6,8,12,14} ; （3） {1,3,5,9,15, 45} （2） {2, 4,8,16}
指出下列偏序集的最大元或最小元： （1）设 A={1, 2} ， 偏序集 P( A), ； （2）设 A={2,3,6,12, 24} ，偏序集 A,| ； （3）设 A {1, 4,6,8,7,10} ，偏序集 A,
B A， 定理 4-17 在 A, ， 若 B 存在最大元 （最
一、偏序关系
例 4-2 设 A {2,3,4,5,6,12,24,30} ， R 是 A 上 的整除关系， R { x, y x y} ，证明 R 是偏序 关系。 定义 Leabharlann Baidu-23 对于集合 A 上的偏序关系 R ，如果 A 中两个 a ， b ，有 aRb ,则称 a 与 b 是可比较 的。
二、哈斯图
偏序集 A, 可以通过哈斯图表示，它是对关系图的

简化。 （1）由于偏序关系是自反的，即对每个元素 a ，都有 aRa ，因此在图上省去自环。 （2）由于偏序关系是传递的，即若有 aRb 和 bRc ，则 必有 aRc ，因此在图中省去 a 与 c 之间的连线。 （3）对于 aRb ，规定 b 在 a 的上方，则可省去箭头。 这样的图称为哈斯图。
4.上确界和下确界
注：一个子集 B 的上界和下界未必存在，也未必唯一，上 确界和下确界也未必存在。若上（下）确界存在，则必是 唯一的，上（下）确界的符号分别是 sup 与inf 。 例 设 集 合 A {1,2,3,4,5} ， A 上 的 二 元 关 系 R 为
R { 1,1 , 2, 2 , 3,3 , 3, 4 , 4, 4 , 5,3 , 5, 4 , 5,5 }
3.上界和下界 定义 4-27 设 ( A, ) 是一个偏序集合， B A ，
若存在一个元素 a A ， 对所有 x B ， 都有 xa ， 则称 a 是 B 的上界；若对所有 x B ，都有 ax ， 则称 a 是 B 的下界。 注：最大（小）元素要求最大（小）元 B ，而 上（下）界无此要求。
一、偏序关系 定义 4-22 设 R 是集合 A 上的二元关系，若 R 是 自反的，反对称的和传递的，则称 R 是 A 上的偏
序关系， 又记为 .带偏序关系 R 的集合 A 称为偏 序集，记为 ＜A,

注： （1）这里“ ”单意味着实数的“小于或等 于” ，而是借用它来表示更为普通的偏序关系
一、偏序关系 定义 4-24 设偏序集<A, >，如果对于 A 中任意
两个元素 a, b A ,必有 a b 或 b a ，则称 是 A

上的全序关系。称 A, 为全序集。 例如，实数集 R 上的小于等于关系就是全序关 系。但是，整数集 Z 上的整除关系就不是全序 关系。