第6讲 等价关系、相容关系 与偏序关系 主要内容: 1.等价关系. 2.相容关系. 3.偏序关系.

2.5 等价关系 在实际应用时，具有某几种性质的关系是有用的. 接下来的三节，我们分别介绍集合A上的等价关系、相容关系和序关系. 等价关系是一种非常重要的特殊关系，它是相等关系“=”、全等关系“”等的一种推广.等价关系基于某种观点将不同的事物看成是同一类，例如研究整数时，基于能否被2整除观点将整数分为奇数和偶数两类，进而有“奇数加偶数是奇数”的结论. 等价关系以及根据它对集合进行划分是粗糙集(rough set)理论的基础, 粗糙集理论是智能信息处理的重要方法之一.

1.等价关系 Def 设R  A  A, 若R具有自反性、对称性以及传递性, 则称R为A上的等价关系. 例2-47 设A = {a, b, c}, R = {(a, a), (b, b), (c, c), (b, c), (c, b)}, 则R具有自反性、对称性以及传递性, 因此R为A上的等价关系.

例2-48 Z上的模3同余关系R: 则R具有自反性、对称性以及传递性, 因此R为Z上的等价关系.

Theorem 2-21(P60) 设R和S为A上的等价关系,则R-1及R  S为A上的等价关系. F

2.等价类 Def 2-18(P60) 设R为A上的等价关系, 对于任意a  A: 例(见前) Theorem 设R为A上的等价关系, 对于任意x , y  A, 则 Proof ()

() 同理可证,

Theorem 设R为A上的等价关系, 对于任意x , y  A, 则 . Hint (反证) Theorem 设R是集合A上的等价关系，则A关于R的商集A/R是集合A的划分. (1)每个等价类非空; (2)不同的等价类不相交; (3)所有等价类的并就是A. 例子? Def 2-29 A/R = {[x]R|x  A}: A关于R的商集.

给定集合A的一个划分, 按下面的方式可以得出A上的一个关系R: (x, y)  R  x和y在划分 的同一个块. 思考 R是等价关系? 例2-51 设A = {a, b, c},  = {{a}, {b, c}}, 则R = {(a, a), (b, b), (c, c), (b, c), (c, b)}, 它是A上的一个等价关系.

Theorem 对于任意集合A, 集合A上的所有划分组成的集合X与其上的所有等价关系组成的集合Y是对等的. Proof (1)f是单射. (2)f是满射. 课堂 P63, 12.

若R1和R2是A上的等价关系, 则R1R2是A上的等价关系, 问

2.6 相容关系 在实际问题中, 两个事物具有某种共同的性质, 但与等价关系不同的是这种共性可能不具有传递性. 例2-52 设A = {set, logic, algebra, graph}, R = {(x, y)|x, y  A, x 和 y有相同的字母}, 试验证R具有自反性和对称性,但不具有传递性. (set, algebra)  R, (algebra, graph)  R, 但(set, graph)  R.

相容关系就是对具有这种性质的事物进行的数学描述,根据它可以得出集合的覆盖. 1.相容关系 Def 2-20 设R  A  A, 若R具有自反性、对称性则称R为A上的相容关系. 等价关系相容关系,但相容关系不一定是等价关系, 前例就是这方面的例子.

例2-54(P64) 设R和S为A上的相容关系, R ◦ S为A上的相容关系? F

在上节知道, 由集合A的划分可得出集合A的等价关系,同样,根据集合A的覆盖可产生集合A的相容关系. 先看一个例子. 例 设A = {a, b, c , d}, {A1, A2}是A的覆盖, 其中A1 = {a, b, c}, A2 = {c, d}, 令R = (A1 A1)  (A2  A2), 容易验证R是A上的一个相容关系. Theorem 若{Ai|i  I}是集合A的覆盖, 则 是A上的相容关系.

Remark 集合A的不同覆盖可得出相同的A上的相容关系. 例2-56(P64) 设A = {a, b, c , d}, {{a, b, c}, {c, d}}和{{a, b}, {b, c}, {a, c}, {c, d}}是A的两个不同覆盖, 按上面的方式可得出相同的A上的相容关系.

A上相容关系R的简化关系图:

2.相容类 Def 2-21 设R是集合A上的相容关系,   C  A,若对于任意x, y  C, 均有(x, y)  R, 则称C是由相容关系R产生的相容类. 在前例中, {set}, {set, algebra}, {logic}, {logic, algebra}, {logic, graph}, {logic, algebra, graph}等是由相容关系R产生的相容类, 而{set, logic}, {set, graph}等不是. 由相容关系R产生的相容类是很多的, 我们主要关心的是极大相容类.

Def 2-22 设R是集合A上的相容关系, C是由相容关系R产生的相容类, 若对于任意C  D, D不是相容类, 则称C是由相容关系R产生的极大相容类. 可以证明, 集合A中的任意元素至少在由相容关系R产生的一个极大相容类中. 在前例中, {set, algebra}和{logic, algebra, graph}由相容关系R产生的两个极大相容类.

在相容关系R的简化关系图中, 一个极大的完全多边形对应的A中元素构成一个极大相容类. 所谓完全多边形是指该多边形的任意两个顶点都有边 由于集合A中的任意元素至少在由相容关系R产生的一个极大相容类中, 所以所有的极大相容类构成集合A的一种覆盖.

2.7 偏序关系 在解决实际问题时, 我们常依据某个标准对事物进行比较, 同时按这个标准对两个事物之间的先后进行排序. 在计算机科学中, 对数据进行排序是十分有意义的工作. 偏序关系是最基本、最常用的一种序关系, 它本质上是两实数之间的小于等于关系“”的一种推广. 本节在偏序的基础上, 介绍偏序集中的特殊元素.

1.偏序关系 Def 设R  A  A, 若R具有自反性、反对称性和传递性, 则称R为A上的偏序. 例2-57 R, ? 例2-58 P(X), ? Remark 借用数的 表示偏序(理由?), 可读作“小于等于”, (A,  ) 称为偏序集. 例 N+, |?

线性序关系是最常见、最简单的一种偏序关系. Def 2-24(P67) 设是A上的偏序,若对任意x, y  A, 有x  y或y  x, 则称是线性序关系, 简称线性序(linear order), 又称为全序(total order). 显然, 实数集R上的数的小于等于关系是线性序. 例2-60 拟序?

几种满足特殊性质的关系见下表: 自反 反自反 对称 反对称 传递 等价关系 T 相容关系 偏序关系 拟序关系 (T)

2.偏序集的Hasse图 Hasse图用于表示元素间的相对位置(或次序)关系. 在偏序的关系图中, 每个点处都有环,可以不必画出来. 又因为它的反对称性和传递性,其边的方向是一致的, 通常都是从下到上方向,更主要的是可去掉由于传递出现的边,同时去掉边的方向. 按这种方式得到的图就是哈斯图(Hasse diagram), 是以德国数学家Helmut Hasse的名字命名的. 例2-61(P67).

显然,哈斯图表明了偏序集中的元素按相对大小进行的排序. 从另一个角度定义Hasse图. 先介绍: 元素y盖住元素x? 为了方便, 记x < y: x  y且x  y. Def 2-25(P68) 设(A, )是偏序集, x, y  A, (1)x < y; (2)满足x < z且z < y的元素z不存在. 则称y盖住x. COV(A) = {(x, y)| x, y  A且y盖住x}.

例2-62(P68) 设X = {a, b}, 则P(X) = {, {a}, {b}, {a, b}}, 集P(X)上的包含关系“”是其上的偏序关系,求COV(A). Solution 根据定义知, {a}盖住, {b}盖住, {a, b}盖住{a}, {a, b}盖住{b}. 因此COV(A) = {(, {a}), (, {b}), ({a}, {a, b}), ({b}, {a, b})}. Hasse图的画法(P68): (1)用黑点代表A中元素; (2) y盖住x, y画在x的上方, 且用线段连接x和y. 

课堂练习 X = {a, b, c}, (P(X), ) 的Hasse图? Cf. P175(格与布尔代数常用到!) Remark {a}与{b}没有关系“”, 不能比较“大小”? 从Hasse图看,两元素x, y, 有“x  y ”? x在下方,可以连到上方的y. 课堂练习 X = {a, b, c}, (P(X), ) 的Hasse图? Cf. P175(格与布尔代数常用到!)

P70, 2: Solution 很容易得出R是偏序? (a, b)  R, b盖住a. (a, c)  R, c不盖住a. 同理, (a, d)  R, d盖住a; (a, e)  R, e不盖住a; (b, c)  R, c盖住b; (b, e)  R, e不盖住b; (c, e)  R, e盖住c; (d, e)  R, e盖住d.

3.偏序集中的特殊元素 设(A, )是偏序集,   S  A, S中处于特殊位置的元素对于有些问题的讨论是很重要的. 建议在理解这些特殊元素时,将偏序“”当作“小于等于”, 虽然它一般不是数的小于等于. (1)最大元和最小元 S的最大元b: S的最小元b:

Theorem 2-27 若S存在最大(小)元, 则唯一. Proof(P68) 存在性? (R, ), S = Z? (P(X), ), S = P(X)?   A  X. (Z+, |), S = Z+? S = {2, 4, 6, 12}? 1|x. 唯一性? Theorem 2-27 若S存在最大(小)元, 则唯一. Proof(P68)

A的最大元通常记为1, A的最小元通常记为0. 借助于非空集合S的最小元素的概念,可以给出良序关系的定义. Def 2-27(P69) (A, )偏序集, A的任意非空子集均存在最小元,则称是良序. (N, )是良序集? Theorem2-28 良序  线性序, 但反过来不成立. (Z, )?

(2)极大元和极小元 S的极大元b: S的极小元b: b是S的极大元素是指S中没有比b更大的元素; b是S的极小元素是指S中没有比b更小的元素. 存在性? (R, ), S = R?

唯一性? S = {a, b, c, d, e, f}. Remark 区别 (1)最大与极大. (2)最小与极小. 显然,在偏序集中, 任意有限的非空子集都存在极小元. 若A是有限集, 利用这个结论可以在集合A上定义一个与“”一致的线性序, 进而将A进行拓扑排序.

(3)上界和下界 S的上界a: S的下界a: 存在性与唯一性? 在上例中: S = {c, d}? A中元素a是S上(下)界是指a在S中每一个元素的上(下)方. 在上面的Hasse图中, a在b的上方? NO. 于是S = {a, b, c, d, e, f}的上界和下界均不存在. 存在性与唯一性? 在上例中: S = {c, d}?

(4)上确界和下确界 S的上确界sup S: 最小上界. S的下确界inf S: 最大下界. S = {d, e}? S = {a, b}? 因为子集S的上(下)界不一定存在, 所以子集S的上(下)确界不一定存在. 下例说明, 即使子集S的上(下)界存在,子集S的上(下)确界也不一定存在. S = {d, e}? S = {a, b}? 若存在, 则唯一.

例2-67(P70) (P(X), ), Proof (1) (2) Remark Chapter 6中常提到.

例2-68 (N+, |),