2.7 相容关系与偏序关系

◦ （1）B的最大（小）元和极大（小）元必须是子集B的元素， 而B的上界（下界）和最小上界（最大下界）可以是也可以 不是B的元素 ◦ （2）上界和下界可以存在也可以不存在，可以唯一也可以 不唯一 ◦ （3）极大元和极小元可以存在也可以不存在，可以唯一也 可以不唯一 ◦ （4）最大元、最小元可以存在也可以不存在，但若存在则 唯一

本结论对于无限的全序集合不一定成立。
例 在开区间集合(0, 1)中按≤是全序集，但集合本 身不存在最小元, 所以不是良序集。
授课教师：程文刚 wgcheng@

覆盖与划分 等价关系、等价类、商集 等价关系与划分的对应关系

相容关系 偏序关系

相容关系 最大相容类 最大相容类的求法 相容关系与覆盖
定义 设R是集合A上的二元关系, 若R是自反的和对称的, 则称R是相容关系。
我们可给出完全覆盖的另一等价定义。
定义 设R是集合A上的相容关系, 其最大相容类的集合 称为集合A的完全覆盖, 记作CR(A)。
定理 设 = {A1, A2, …, An}是A的覆盖, 由决定的关
系 R = (A1 A1)∪(A2 A2)∪…∪(A n A n)是A的的一 个相容关系。 证明 因为A = A1∪A2∪…∪A n, 对任一xA, 必有某i使xAi, 则‹x, x› Ai Ai R, 因此R是自反的。 又对任意 x, yA且‹x, y›R, 必存在某j, 使 ‹x, y›Aj Aj, 即x, y Aj, 则 ‹y, x›Aj Aj R,因此R是对称的。 所以得证R是A上的一个相容关系。▎
注意: 在(A, ≤)中, 不一定存在着最大元或最小元
例 若A = {2, 3, 4, 6, 8}, 偏序关系是整除关系。因为 对整除关系来说, A中所有元素的(最小)公分母和(最 大)公约数均不属于A, 所以A中既没有最大元, 也没 有最小元。
定理 设 (A, ≤) 是偏序集, B A, 若B有最大(最小) 元, 则必是唯一的。
n=1 n =5
n=2
n=3
n=4
上图给出了n = 1, 2, 3, 4, 5时的极大完全子 图。对于相容关系R, 如果我们能够找到关系 图GR的所有极大完全子图, 也就找到A的最大 相容类。
例 设给定的相容关系图表示成下图, 写出所有的最大相容
类。 解 最大相容类{h}, {a, b}, {d, e, f}, {b, c, d, f, g} 。
次序关系
事物之间的次序经常是事物群体之间的重要特征, 决定事物之间的次序也是通过事物间的关系来确定 的。 一. 偏序与哈斯图
定义 设R A A, 如果R是自反、反对称和可传递的, 则称R是A上的一个偏序关系(partial ordering), 通 常记作“≤”, 序偶(A, ≤)称作偏序集。偏序的逆也 是一个偏序, 记作“≥”。
的相容类, 我们称它为最大相容类。

也可以这样理解最大相容类CR: (等价定义) 对CR中的任意元素x, x必与CR中所有元素有相容 关系, 而在差集A – CR中没有任何元素与CR中所有 元素都是相容的。




可以利用相容关系的关系图来确定相容类和最大相 容类。 极大完全子图的顶点集合就是最大相容类。所谓极 大完全子图是指每对顶点都有边相连的多边形,而 最大相容类外的任何顶点不可能与类内的所有顶点 相连。 例如三角形是极大完全子图; 一个四边形加上两条 对角线也是极大完全子图。 图中极大完全子图的顶点集合就是最大相容类这里 “最大”的含义是: 如果一个极大完全子图在添加 任何新的顶点后就不再成为极大完全子图。另外孤 立顶点, 以及不在极大完全子图两个顶点及其连线, 也是最大相容类。
证明 因为 {1} {1,2} {1,2,3}, 即P上任意两 个元素都有包含关系。
定义 任一偏序集(A, ≤), 若任意S A且S中存在最
小元, 则称(A, ≤)为良序(well ordered)集 例 自然数集N对于≤来说是良序集合。 定理 每一个良序集合一定是全序集合。 证明 设(A, ≤)是良序集, 则对任意a, bA可构成子
集{a, b}, 必存在最小元, 这个最小元素不是a就是
b, 因此一定有a≤b或b≤a。
所以(A, ≤)是全序集。
▎
然而一个全序集却不一定是良序集。
定理 每一个有限的全序集一定是良序集。
证明 设(A, ≤)是任一有限全序集, B为A的任一非空 子集, 则B也是有限全序集。设B有n个元素, 则最 多经Cn2次每两个元素的考查, 必可找到B的最小元, 因而(A,≤)必是良序集。▎
定义 设 R 是集合 A 上的相容关系 , 若 CA, 若任意 a,bC, 有aRb, 则称C是由R产生的相容类 例 在上例的相容关系可产生相容类{a, b}, {a, c}, {b, c}, {f}, {b, d, e}等。 对于前三个相容类, 都能加进新的元素组成新的相
容类, 而后两个相容类就不能再增加新元素构成新
例如,<A,≤>是偏序集, 其中A＝{1,2,3,4,5}, ≤是整除关系. 那么,对任意x∈A都有1≤x,所以,1和1,2,3,4,5都是可 比的,但是2不能整除3,3也不能整除2,所以2和3是不 可比的.对于1和2来说,1＜2,并且不存在z∈A使得1整 除z并且z整除2,所以,2盖住 1.同样,4盖住2,但4不盖 住1,因为有1＜2＜4成立.显然,如果x与y不可比,则一 定不会有x盖住y或y盖住x.

由定义知, 等价关系是具有传递性的相容关系; 相容 关系是一个比等价关系更为普遍的关系。

例子
◦ 在一群人的集合中, 年龄相等是相容关系

因为相容关系是自反和对称的, 其关系矩阵是对称 的且主对角线元素全为1, 因此我们可仅用下三角矩 阵T来表示和存储就够了, 即关系矩阵可以简化为 “阶梯形”。
定理 设R是有限集A上的相容关系, C是一个相容类, 那么必存在一个最大相容类CR, 使得C CR。 证明 设A = {a1, a2, …, an}, 构造相容类序列 C0 C1 C2 …, 其中C0 = C，源自i+1 = Ci∪{aj},
j是满足ajCi且aj与Ci中元素有相容关系的最小下标。
例 <I, ≤>设B={i|iN}则B的极大元不存在，最大元 不存在(极小元为0，最小元为0)
◦ （5）对于非空有限偏序集合，其极大元和极小元总是存在


链 设<A, ≤ >是一个偏序集合，在A的一个子集中， 如果每两个元素都是有关系的，则称这个子集为链。 反链 设〈A, ≤ 〉是一个偏序集合，在A的一个子集 中如果每两个元素都是无关的，则称这个子集为反链。 （若A的子集只有单个元素，则这个子集既是链又是反 链。）
显然盖住关系是唯一确定的, 盖住关系是“≤”的子 集。盖住关系的关系图称哈斯(Hasse)图, 它实际上 偏序关系是经过如下简化的关系图: 1. 省略关系图中的每个结点处的自环, 这是因为偏序 关系“≤”是自反的。

2. 若x<y 且y 盖住x, 将代表y 的结点放在代表 x 的结点之上, 并在 x与y之间连线, 省去有向边 的箭头, 使其成为无向边。 若x<y 但y不盖住x, 则省去x与y之间的连线。 例 A = {1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 24}, 偏序关系是A上的整除关系“|”, 偏序集(A, |) 的哈斯图如下:
证明 假定a和b都是B的最大元, 则a≤b和b≤a,
由偏序的反对称性, 得 a = b。 同理可证B的最小元必唯一。▎

设<A, ≤>是一偏序集合，B是A的子集
◦ a)若bB,b≤a 则aA称为B的上界 若bB,b≥a 则aA称为B的下界 ◦ b)若a是B的上界（下界），且对B的每一上界（下界）a’， 有a≤a’(a’ ≤a)， 那么aA叫做B的最小上界或上确界记为 lub(B)（最大下界或下确界记为glb(B）)
注意: 集合A的覆盖不唯一, 因此对给定的相容关系R, 可以作成不同的相容类的集合, 它们都是A的覆盖。 给定集合A上的一个覆盖, 必可在A上构造对应于此 覆盖的一个相容关系, 但是不同的覆盖却能构造相 同的相容关系。 例 设A = {a, b, c, d}, 集合{{a, b, c}, {c, d}}和{{a,b}, {a, c}, {b, c}, {c,d}}是A的不同覆盖, 但它们可以产生相同的相容关系 R = {{a, a},{a, b}, {b, a,}, {b, b}, {b, c}, {c, b}, {a, c}, {c, a}, {c, c}, {c, d}, {d, c}, {d, d}}。 但正如等价关系与划分间的联系一样, 集合A上的相 容关系R确定唯一的完全覆盖CR(A), A上的完全覆 盖CR(A)确定唯一的相容关系R。
因为 |A| = n，所以至多经过n – |C| 步, 就使这个
过程终止, 此序列的最后一个相容类, 就是所要找的 最大相容类。▎

从定理中可知, A中任一元素a可组成相容类{a}, 因
此必包含在一个最大相容类CR中。 如由所有最大相容类作出一个集合, 则A中每个元素 至少属于该集合的一个成员之中, 所以最大相容类 集合必覆盖集合A。

为了更清楚地描述偏序集合中元素间的层次关系, 也 为了更快、更有效地画出偏序关系的简化图, 下面介 绍“盖住”的概念。
定义 在偏序集中, 对x, yA, x≤y且x y, 且 A中无 任何其它元素z, 满足x≤z且z≤y, 称y盖住x, 或称x 是y的直接前趋, y是x的直接后继。盖住关系记作 cov(A) = {(x, y) | x, yA且y盖住x}。
例 设A = {cat, teacher, cold, desk, knife, by} R={‹x, y›|x, yA且x和y至少有一个相同的字母} 是A上的一个相容关系, 简记A中元素依次为a, b, c, d, e, f, 则R的关系矩阵MR和对应简化的下三角矩阵TR为: