提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

【集合论】序关系 : 总结 ( 偏序关系 | 偏序集 | 可比 | 严格小于 | 覆盖 | 哈斯图 | 全序关系 | 拟序关系 | 偏序关系八种特殊元素 | 链 | 反链 ) ★★

总结 元素 关系 覆盖 特殊 小于 严格 集合论
2023-06-13 09:17:48 时间

文章目录

参考博客 :

一、偏序关系

偏序关系 :

给定非空集合

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

符号表示偏序关系 , 读作 “小于等于” ;

符号化表示 :

<x,y> \in R \Leftrightarrow xRy \Leftrightarrow x \preccurlyeq y

, 解读 :

<x,y>

有序对在偏序关系

R

中 , 则

x

与

y

之间有

R

关系 ,

x

小于等于

y

;

等价关系 是用于 分类 的 , 偏序关系 是用于 组织 的 , 在每个类的内部 , 赋予一个结构 ;

参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )

二、偏序集

偏序集 :

\preccurlyeq

关系 是

A

集合上的偏序关系 , 则称 集合

A

与 偏序关系

\preccurlyeq

构成的 有序对

<A, \preccurlyeq>

称为偏序集 ;

如果集合上有偏序关系 , 那么这个集合就称为偏序集 ;

参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )

三、可比

可比 :

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

, 组成 偏序集

<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

, 组成 偏序集

<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

, 组成 偏序集

<A, \preccurlyeq>

,

x, y

是

A

集合中的两个元素 ,

x , y \in A

,

哈斯图 :

① 顶点 : 使用 顶点 表示

A

集合中的元素 ;

② 无向边 : 当且仅当

y

覆盖

x

时 ,

y

顶点在

x

顶点 上方 , 并且在

x

顶点 与

y

顶点之间 绘制一条 无向边 ;

上图是

6

元集 上的偏序关系

\preccurlyeq
A

元素比

B,C,D

元素都小

偏序关系是传递的 ,

A

比

B

小 ,

B

比

F

小 , 因此

A

比

F

小

最下面的元素

A

是最小的 , 所有的元素都比

A

大 ( 包括

A

, 偏序关系是自反的 )

最上面的元素

F

是最大的 , 所有的元素都比

F

小 ( 包括

F

, 偏序关系是自反的 )

BCDE

四个元素互相都不可比

哈斯图 与 关系图对比 省略的内容 :

① 环 : 偏序关系是自反的 , 因此 每个顶点上都有环 , 可以省略掉环

② 箭头 : 偏序关系是反对称的 , 因此 两个顶点两两之间肯定没有双向边 , 都是单向边 , 因此可以省略箭头方向

③ 默认方向 : 使用上下位置表示箭头的方向 , 箭头默认向上 , 偏序是 小于等于 , 最小的在最小面, 最大的在最上面 ;

参考博客 :

七、全序关系 ( 线序关系 )

A

集合与该集合之上的 偏序关系

\preccurlyeq

组成的有序对是 :

<A, \preccurlyeq>

偏序集 ;

A

集合中 任意元素

x, y

都 可比 ;

则称

\preccurlyeq

关系是

A

集合上的 全序关系, 又称为 线序关系 ;

称

<A, \preccurlyeq>

为全序集 ( 线序集 ) ;

<A, \preccurlyeq>

偏序集 是全序集

当且仅当

<A, \preccurlyeq>

偏序集的哈斯图是一条直线

参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )

八、拟序关系

非空集合

A

, 二元关系

R

是

A

集合上的二元关系 ;

符号化表示 :

A \not= \varnothing

,

R \subseteq A \times A

;

如果 二元关系

R

是 反自反 , 传递 的 ,

则称

R

关系是

A

集合上的拟序关系 ,

使用

\prec

表示拟序关系 ,

称

<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

集合上的 拟线序关系 , 又称为拟全序关系 ;

<A \prec>

被称为 拟线序集 ;

参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )

十、偏序关系八种特殊元素

参考博客 : 【集合论】序关系 ( 偏序关系中八种特殊元素 | ① 最大元 | ② 最小元 | ③ 极大元 | ④ 极小元 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 上确界 | ⑧ 最小下界 下确界 )

十一、链

<A, \preccurlyeq>

是 偏序集 ,

B \subseteq A

,

偏序集中一组元素组成集合

B

, 如果

B

集合中的元素两两都可比 , 则称

B

集合是该偏序集

<A, \preccurlyeq>

的链 ;

符号化表示 :

\forall x \forall y ( x \in B \land y \in B \to x 与 y 可比 )

链的本质是一个集合

|B|

是链的长度

参考博客 :

十二、反链

<A, \preccurlyeq>

是 偏序集 ,

B \subseteq A

,

偏序集中一组元素组成集合

B

, 如果

B

集合中的元素两两都 不可比 , 则称

B

集合是该偏序集

<A, \preccurlyeq>

的 反链 ;

符号化表示 :

\forall x \forall y ( x \in B \land y \in B \land x\not= y \to x 与 y 不可比 )

反链的本质是一个集合

|B|

是反链的长度

参考博客 :

十三、链与反链定理

参考博客 :

相关文章