文章目录一、偏序关系二、偏序集三、可比四、严格小于五、覆盖六、哈斯图七、全序关系 ( 线序关系 )八、拟序关系九、拟序关系相关定理十、偏序关系八种特殊元素十一、链十二、反链十三、链与反链定理参考博客 :
【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )【集合论】序关系 ( 哈斯图示例 | 整除关系哈斯图 | 包含关系哈斯图 | 加细关系哈斯图 )【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )【集合论】序关系 ( 偏序关系中八种特殊元素 | ① 最大元 | ② 最小元 | ③ 极大元 | ④ 极小元 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 上确界 | ⑧ 最小下界 下确界 )【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 )一、偏序关系偏序关系 :
给定非空集合
A ,
A \not= \varnothing ,
R 关系是
A 集合上的二元关系 ,
R \subseteq A \times A ,
如果
R 关系满足以下性质 :
自反 : 关系图中所有顶点 都有环 ;反对称 : 两个顶点之间 有 0 个或
1 个有向边 ;
传递 : 前提 a \to b , b\to c 不成立 默认传递 ; 前提
a \to b , b\to c 成立 必须满足
a \to c 存在 ;
则称
R 关系是
A 集合上的 偏序关系 ;
偏序关系表示 : 使用
\preccurlyeq 符号表示偏序关系 , 读作 “小于等于” ;
符号化表示 :
R 中 , 则
x 与
y 之间有
R 关系 ,
x 小于等于
y ;
等价关系 是用于 分类 的 , 偏序关系 是用于 组织 的 , 在每个类的内部 , 赋予一个结构 ;
参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )
二、偏序集偏序集 :
\preccurlyeq 关系 是
A 集合上的偏序关系 , 则称 集合
A 与 偏序关系
\preccurlyeq 构成的 有序对
如果集合上有偏序关系 , 那么这个集合就称为偏序集 ;
参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )
三、可比可比 :
A 集合 , 该集合上存在 偏序关系
\preccurlyeq 小于等于 ,
偏序集 是 集合 和 偏序关系 组成的有序对
x, y 是
A 集合中的两个元素 ,
x , y \in A ,
要么是
x \preccurlyeq y , 要么就是
y \preccurlyeq x , 符号化表示是
x \preccurlyeq y \lor y \preccurlyeq x , 两种情况必选其一 ,
则称
x 与
y 是可比的 ;
只要
x, y 之间 存在偏序关系 , 不管谁在前 , 谁在后 , 都 统一称
x 与
y 是可比的 ;
参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )
四、严格小于严格小于 概念需要基于 可比概念
严格小于 :
A 集合 与
A 上偏序关系
\preccurlyeq , 组成 偏序集
x, y 是
A 集合中的两个元素 ,
x , y \in A ,
如果
x , y 是可比的 (
x,y 之间存在偏序关系 ) , 但是
x 与
y 不相等 , 则称
x 严格小于
y ;
符号化表示 :
x \preccurlyeq y \land x \not= y \Leftrightarrow x \prec y参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )
五、覆盖覆盖 概念需要基于 严格小于概念
覆盖 :
A 集合 与
A 上偏序关系
\preccurlyeq , 组成 偏序集
x, y , z 是
A 集合中的元素 ,
x , y , z \in A ,
x 严格小于
y ,
x \prec y ,
不存在
z , 使
x 严格小于
z , 并且
z 严格小于
y ,
则称
y 覆盖
x ; ( 注意是 大 覆盖 小 )
偏序关系中 大 覆盖 小
符号化表示 :
x \prec y \land \lnot \exist z( z \in A \land x \prec y \prec z )参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )
六、哈斯图A 集合 与
A 上偏序关系
\preccurlyeq , 组成 偏序集
x, y 是
A 集合中的两个元素 ,
x , y \in A ,
哈斯图 :
① 顶点 : 使用 顶点 表示
A 集合中的元素 ;
② 无向边 : 当且仅当
y 覆盖
x 时 ,
y 顶点在
x 顶点 上方 , 并且在
x 顶点 与
y 顶点之间 绘制一条 无向边 ;
上图是
6 元集 上的偏序关系
\preccurlyeqA 元素比
B,C,D 元素都小
偏序关系是传递的 ,
A 比
B 小 ,
B 比
F 小 , 因此
A 比
F 小
最下面的元素
A 是最小的 , 所有的元素都比
A 大 ( 包括
A , 偏序关系是自反的 )
最上面的元素
F 是最大的 , 所有的元素都比
F 小 ( 包括
F , 偏序关系是自反的 )
BCDE 四个元素互相都不可比
哈斯图 与 关系图对比 省略的内容 :
① 环 : 偏序关系是自反的 , 因此 每个顶点上都有环 , 可以省略掉环
② 箭头 : 偏序关系是反对称的 , 因此 两个顶点两两之间肯定没有双向边 , 都是单向边 , 因此可以省略箭头方向
③ 默认方向 : 使用上下位置表示箭头的方向 , 箭头默认向上 , 偏序是 小于等于 , 最小的在最小面, 最大的在最上面 ;
参考博客 :
【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )【集合论】序关系 ( 哈斯图示例 | 整除关系哈斯图 | 包含关系哈斯图 | 加细关系哈斯图 )七、全序关系 ( 线序关系 )A 集合与该集合之上的 偏序关系
\preccurlyeq 组成的有序对是 :
A 集合中 任意元素
x, y 都 可比 ;
则称
\preccurlyeq 关系是
A 集合上的 全序关系, 又称为 线序关系 ;
称
当且仅当
参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )
八、拟序关系非空集合
A , 二元关系
R 是
A 集合上的二元关系 ;
符号化表示 :
A \not= \varnothing ,
R \subseteq A \times A ;
如果 二元关系
R 是 反自反 , 传递 的 ,
则称
R 关系是
A 集合上的拟序关系 ,
使用
\prec 表示拟序关系 ,
称
偏序关系
\preccurlyeq 是 小于等于 关系 , 拟序关系
\prec 就是 严格小于 关系 ;
拟序关系示例 : 大于 , 小于 , 真包含 , 都是拟序关系 ;
拟序关系 完整的性质是 反自反 , 反对称 , 传递 ,
之所以概念中没有提 反对称 性质 , 是因为 根据 反自反 , 传递性质 , 可以推导出 反对称 性质 ;
数学中倾向于使用最小的条件进行定义 , 因此这里将反对称性去掉 ;
参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )
九、拟序关系相关定理定理 1 :
非空集合
A ,
A \not= \varnothing ,
\preccurlyeq 是非空集合
A 上的偏序关系 ,
\prec 是非空集合
A 上的拟序关系 ;
① 偏序关系性质 :
\preccurlyeq 是 自反 , 反对称 , 传递的
② 拟序关系性质 :
\prec 是 反自反 , 反对称 , 传递的
③ 偏序关系 -> 拟序关系 : 偏序关系 减去 恒等关系 就是 拟序关系 ,
\preccurlyeq - I_A = \prec④ 拟序关系 -> 偏序关系 : 拟序关系 与 恒等关系 的并集就是 偏序关系 ,
\prec \cup I_A = \preccurlyeq ;
定理 2 :
非空集合
A ,
A \not= \varnothing ,
\prec 是非空集合
A 上的拟序关系 ;
①
x \prec y ,
x=y ,
y \prec x 中最多有一个成立 ;
使用反证法 , 任意两个成立都会导致
x \prec x ;
②
(x\prec y \land x = y) \land (y \prec x \land x=y) \Rightarrow x = y定理 3 三歧性 , 拟线序 :
非空集合
A ,
A \not= \varnothing ,
\prec 是非空集合
A 上的拟序关系 ;
如果
x \prec y ,
x=y ,
y \prec x 中仅有一个城里 , 那么称
\prec 拟序关系 具有 三歧性 ;
有三歧性的 逆序关系
\prec 称为
A 集合上的 拟线序关系 , 又称为拟全序关系 ;
参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )
十、偏序关系八种特殊元素参考博客 : 【集合论】序关系 ( 偏序关系中八种特殊元素 | ① 最大元 | ② 最小元 | ③ 极大元 | ④ 极小元 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 上确界 | ⑧ 最小下界 下确界 )
十一、链
B \subseteq A ,
偏序集中一组元素组成集合
B , 如果
B 集合中的元素两两都可比 , 则称
B 集合是该偏序集
符号化表示 :
\forall x \forall y ( x \in B \land y \in B \to x 与 y 可比 )链的本质是一个集合
|B| 是链的长度
参考博客 :
【集合论】偏序关系 相关题目解析 ( 偏序关系 中的特殊元素 | 绘制哈斯图 | 链 | 反链 )【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 )十二、反链
B \subseteq A ,
偏序集中一组元素组成集合
B , 如果
B 集合中的元素两两都 不可比 , 则称
B 集合是该偏序集
符号化表示 :
\forall x \forall y ( x \in B \land y \in B \land x\not= y \to x 与 y 不可比 )反链的本质是一个集合
|B| 是反链的长度
参考博客 :
【集合论】偏序关系 相关题目解析 ( 偏序关系 中的特殊元素 | 绘制哈斯图 | 链 | 反链 )【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 )十三、链与反链定理参考博客 :
【集合论】偏序关系 相关题目解析 ( 偏序关系 中的特殊元素 | 绘制哈斯图 | 链 | 反链 )【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 )