文章/答案/技术大牛

发布

【集合论】偏序关系 ( 偏序关系定义 | 偏序集定义 | 大于等于关系 | 小于等于关系 | 整除关系 | 包含关系 | 加细关系 )

韩曙亮

发布于 2023-03-27 08:16:37

5.8K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一. 偏序关系

1. 偏序关系定义

( 1 ) 偏序关系定义 ( 自反 | 反对称 | 传递 )

偏序关系定义 :

1.前置条件 1 :

$A \not= \varnothing$

, 并且

$R \subseteq A \times A$

;

2.前置条件 2 : 如果

$R$

是自反 , 反对称 , 传递的 ;

① 自反 : 每个元素自己和自己都有关系 ,

$xRx$

;

② 反对称 : 如果

$xRy$

并且

$yRx$

则

$x=y$

, 即

$x \not=y$

$xRy$

和

$yRx$

不能同时存在 ; 可以没有 , 但是一定不能同时出现 ;

③ 传递 : 如果有

$xRy$

y R z

$yRz$

, 那么必须有

x R z

$xRz$

, 如果前提不成立 , 那么也勉强称为传递 ;

3.结论 : 称

R

$R$

为

A

$A$

上的偏序关系 ;

4.表示 : 使用

⪯

$\preceq$

表示偏序关系 ;

5.读法 :

⪯

$\preceq$

读作 "小于等于" ;

6.使用公式表示 :

Misplaced &

$<x, y> \in R \Longleftrightarrow xRy \Longleftrightarrow x \preceq y$

7.公式解读 : 如果

x

$x$

y

$y$

两个元素构成有序对

Misplaced &

$<x,y>$

, 并且在偏序关系

R

$R$

中 ,

x

$x$

和

y

$y$

具有

R

$R$

关系 , 也可以写成

x

$x$

小于等于 ( 偏序符号 )

y

$y$

;

8.常见的偏序关系 : 树上的小于等于关系 , 集合上的包含关系 , 非

0

$0$

自然数之间的整除关系 , 都是常见的偏序关系 ;

( 2 ) 偏序关系与等价关系 ( 等价关系用于分类 | 偏序关系用于组织 )

偏序关系与等价关系 :

1.表示层次结构 : 偏序关系是非常常用的二元关系 , 通常用来 表示层次结构 ;
2.等价关系 : 等价关系是用来分类的 , 将一个集合分为几个等价类 ;
3.偏序关系 : 偏序关系通常是用来组织的 , 在每个类的内部 , 赋予其一个结构 , 特别是层次结构 , 有上下层级 ,

2. 偏序集定义

( 1 ) 偏序集定义

偏序集定义 :

1.前置条件 1 :

⪯

$\preceq$

是

A

$A$

上的偏序关系 ;

2.结论 :

Misplaced &

$<A , \preceq>$

是偏序集 ;

3.解读 : 集合

A

$A$

与偏序关系

⪯

$\preceq$

构成的有序对 , 称为偏序集 ;

二. 偏序关系示例

1. 小于等于关系

( 1 ) 小于等于关系说明

偏序集示例 1 ( 小于等于关系

\leq

$\leq$

是偏序关系 ) :

1.公式表示 :

Misplaced &

$\varnothing \not= A \subseteq R , <A , \leq >$

2.语言描述 : 如果

A

$A$

是实数集

R

$R$

的子集 , 并且

A

$A$

不能是空集

\emptyset

$\varnothing$

, 集合

$A$

中的小于等于关系 , 是偏序关系 ;

3.使用集合形式表示关系 :

$\leq = \{ <x,y> | x,y \in A \land x \leq y \}$

( 2 ) 小于等于关系分析

实数集

$A$

上的小于等于关系 (

$\leq$

) 分析 :

1.自反性质分析 :

$x$

小于等于

$x$

$x \leq x$

, 是成立的 , 小于等于关系是自反的 ;

2.反对称性质分析 :

$x$

小于等于

$y$

小于等于

$x$

, 推出

$x = y$

, 符合反对称性质的定义 , 因此 小于等于关系是反对称的 ,

3.传递性质分析 :

$x$

小于等于

$y$

小于等于

$z$

$x$

小于等于

$z$

, 是成立的 , 因此 小于等于关系是传递的 ;

4.总结 : 综上所述 , 小于等于关系是偏序关系 ;

2. 大于等于关系

( 1 ) 大于等于关系说明

偏序集示例 2 ( 大于等于关系

$\geq$

是偏序关系 ) :

1.公式表示 :

$\varnothing \not= A \subseteq R , <A , \geq >$

2.语言描述 : 如果

$A$

是实数集

$R$

的子集 , 并且

$A$

不能是空集

$\varnothing$

, 集合

$A$

中的大于等于关系 (

$\geq$

) , 是偏序关系 ;

3.使用集合形式表示关系 :

$\geq = \{ <x,y> | x,y \in A \land x \geq y \}$

( 2 ) 大于等于关系分析

实数集

$A$

上的大于等于关系 (

$\geq$

) 分析 :

1.自反性质分析 :

$x$

大于等于

$x$

$x \geq x$

, 是成立的 , 大于等于关系是自反的 ;

2.反对称性质分析 :

$x$

大于等于

$y$

大于等于

$x$

, 推出

$x = y$

, 符合反对称性质的定义 , 因此 大于等于关系是反对称的 ,

3.传递性质分析 :

$x$

大于等于

$y$

大于等于

$z$

$x$

大于等于

$z$

, 是成立的 , 因此 大于等于关系是传递的 ;

4.总结 : 综上所述 , 大于等于关系是偏序关系 ;

3. 整除关系

( 1 ) 整除关系说明

偏序集示例 3 ( 整除关系是偏序关系 ) :

1.公式表示 :

$\varnothing \not= A \subseteq Z_+ = \{ x | x \in Z \land x > 0 \}<A , | >$

2.语言描述 : 如果

$A$

是正整数集

$Z_+$

的子集 , 并且

$A$

不能是空集

$\varnothing$

, 集合

$A$

中的整除关系 (

$|$

) , 是偏序关系 ;

3.使用集合形式表示关系 :

$|= \{ <x,y> | x,y \in A \land x | y \}$

4.整除关系 :

$x|y$

$x$

是

$y$

的因子 , 或

$y$

是

$x$

的倍数 ;

( 2 ) 整除关系分析

正整数集

$A$

上的整除关系 (

$|$

) 分析 :

1.自反性质分析 :

$x$

整除

$x$

$x | x$

, 是成立的 , 整除关系 ( | ) 是自反的 ;

2.反对称性质分析 :

$x$

整除

$y$

整除

$x$

, 两个正整数互相都能整除 , 它们只能相等 , 推出

$x = y$

, 符合反对称性质的定义 , 因此 整除关系是反对称的 ,

3.传递性质分析 :

$x$

整除

$y$

整除

$z$

$x$

整除

$z$

, 是成立的 , 因此 整除关系是传递的 ;

4.总结 : 综上所述 , 整除关系是偏序关系 ;

4. 包含关系

( 1 ) 包含关系说明

偏序集示例 4 ( 包含关系

$\subseteq$

是偏序关系 ) :

1.公式表示 :

$\mathscr{A} \subseteq P(A) , \subseteq = \{<x , y> | x , y \in \mathscr{A} \land x \subseteq y \}$

2.语言描述 : 集合

$A$

上的幂集合

$P(A)$

的子集合构成集族

$\mathscr{A}$

, 该集族

$\mathscr{A}$

上的包含关系 , 是偏序关系 ;

( 2 ) 包含关系分析

分析集合的子集族之间的包含关系 :

① 假设一个比较简单的集合

$A=\{a, b\}$

② 分析下面

$A$

的 3 个子集族 ;

$\mathscr{A}_1 = \{ \varnothing , \{a\} , \{b\} \}$

集族

$\mathscr{A}_1$

包含空集

$\varnothing$

, 单元集

$\{a\}$

, 单元集

$\{b\}$

;

$\mathscr{A}_2 = \{ \{a\} , \{a, b\} \}$

集族

$\mathscr{A}_2$

包含单元集

$\{a\}$

, 2 元集

$\{a, b\}$

;

$\mathscr{A}_3 = P(A) = \{ \varnothing , \{a\} , \{b\} , \{a, b\} \}$

集族

$\mathscr{A}_3$

包含空集

$\varnothing$

, 单元集

$\{a\}$

, 单元集

$\{b\}$

, 2 元集

$\{a, b\}$

; 这是集合

$A$

的幂集 ;

③ 列举出集族

$\mathscr{A}_1$

上的包含关系 :

$\subseteq_1 = I_{\mathscr{A}1} \cup \{ <\varnothing , \{a\}> , <\varnothing , \{b\}> \}$

$\subseteq_1$

是集合

$\mathscr{A}1$

上的偏序关系 ;

即分析空集

$\varnothing$

, 单元集

$\{a\}$

, 单元集

$\{b\}$

三个集合之间的包含关系 :

1.恒等关系

$I_{\mathscr{A}1}$

$<\{a\} , \{a\}> 和 <\{b\} , \{b\}>$

, 集合上的恒等关系 , 每个集合肯定自己包含自己 ;

$<\varnothing , \{a\}>$

: 空集肯定包含于集合

$\{a\}$

;

$<\varnothing , \{b\}>$

: 空集肯定包含于集合

$\{b\}$

;

4.总结 : 这些包含关系的性质分析 :
- ① 自反 : 每个元素自己包含自己 ,
$A \subseteq A$
, 包含关系具有自反性质 ;
- ② 反对称 : 如果集合
$A \subseteq B$
,
$B \subseteq A$
, 那么
$A = B$
, 显然 包含关系具有反对称性质 ;
- ③ 传递 : 如果
$A \subseteq B$
, 并且
$A \subseteq C$
, 那么有
$A \subseteq C$
, 包含关系具有传递性质 ;

④ 列举出集族

$\mathscr{A}_2$

上的包含关系 :

$\subseteq_2 = I_{\mathscr{A}2} \cup \{ <\{a\} , \{a, b\}>$

$\subseteq_2$

是集合

$\mathscr{A}2$

上的偏序关系 ;

⑤ 列举出集族

$\mathscr{A}_3$

上的包含关系 :

$\subseteq_3 = I_{\mathscr{A}3} \cup \{ <\varnothing , \{a\}> , <\varnothing , \{b\}>, <\varnothing , \{a, b\}> , <\{a\} , \{a, b\}> , <\{b\} , \{a, b\}> \}$

$\subseteq_3$

是集合

$\mathscr{A}_3$

上的偏序关系 ;

5. 加细关系

( 1 ) 加细关系说明

偏序集示例 5 ( 加细关系

$\preceq_{加细}$

是偏序关系 ) :

1.加细关系描述 :

$A \not= \varnothing$

$\pi$

是由

$A$

的一些划分组成的集合 ;

$\preceq_{加细} = \{<x , y> | x , y \in \pi \land x 是 y 的加细\}$

2.划分 : 划分是一个集族 ( 集合的集合 ) , 其元素是集合又叫划分快 , 其中每个元素(集族中的元素)集合中的元素是非空集合

$A$

的元素 ;

① 该集族不包含空集 ;
② 该集族中任意两个集合都不想交 ;
③ 该集族中所有元素取并集 , 得到集合

$A$

;

( 2 ) 加细关系分析

分析集合的划分之间的加细关系 :

① 集合

$A = \{a, b, c\}$

, 下面的划分和加细都基于该集合进行分析 ;

② 下面列出集合

$A$

的 5 个划分 :

划分 1 : 对应 1 个等价关系 , 分成 1 类 ;

$\mathscr{A}_1 =\{ \{ a, b, c \} \}$

划分 2 : 对应 2 个等价关系 , 分成 2 类 ;

$\mathscr{A}_2 = \{ \{ a \} , \{ b, c \} \}$

划分 3 : 对应 2 个等价关系 , 分成 2 类 ;

$\mathscr{A}_3 = \{ \{ b \} , \{ a, c \} \}$

划分 4 : 对应 2 个等价关系 , 分成 2 类 ;

$\mathscr{A}_4 = \{ \{ c \} , \{ a, b \}\}$

划分 5 : 对应 3 个等价关系 , 分成 3 类 ; 每个元素自己自成一类

$\mathscr{A}_5 = \{ \{ a \} , \{ b \}, \{ c \} \}$

③ 下面列出要分析的几个由划分组成的集合 :

集合 1 :

$\pi_1 = \{ \mathscr{A}_1, \mathscr{A}_2 \}$

集合 2 :

$\pi_2 = \{ \mathscr{A}_2, \mathscr{A}_3 \}$

集合 3 :

$\pi_3 = \{ \mathscr{A}_1, \mathscr{A}_2, \mathscr{A}_3, \mathscr{A}_4, \mathscr{A}_5 \}$

④ 集合

$\pi_1$

上的加细关系分析 :

1.自己是自己的加细 : 每个划分 , 自己是自己的加细 , 因此 加细关系中有

$I_{\pi 1}$

$<\mathscr{A}_1 , \mathscr{A}_1>$

$<\mathscr{A}_2 , \mathscr{A}_2>$

;

2.其它加细关系 :

$\mathscr{A}_2$

划分中的每个划分块 , 都是

$\mathscr{A}_1$

划分中块的某个划分块的子集合 , 因此有

$\mathscr{A}_2$

是

$\mathscr{A}_1$

的加细 , 记做

$<\mathscr{A}_2, \mathscr{A}_1>$

;

3.加细的定义 :

$\mathscr{A}_1$

和

$\mathscr{A}_2$

都是集合

$A$

的划分,

$\mathscr{A}_2$

中的每个划分块 , 都含于

$\mathscr{A}_1$

中的某个划分块中 , 则称

$\mathscr{A}_2$

是

$\mathscr{A}_1$

的加细 ;

- 4.加细关系列举 :

$\preceq_1 = I_{\pi 1} \cup \{ <\mathscr{A}_2, \mathscr{A}_1> \}$

⑤ 集合

$\pi_2$

上的加细关系分析 :

1.自己是自己的加细 : 每个划分 , 自己是自己的加细 , 因此 加细关系中有

$I_{\pi 2}$

$<\mathscr{A}_3 , \mathscr{A}_3>$

$<\mathscr{A}_2 , \mathscr{A}_2>$

;

2.其它加细关系 :

$\mathscr{A}_2$

和

$\mathscr{A}_3$

这两个划分互相不是加细 , 因此 该集合中没有其它加细关系 ;

- 4.加细关系列举 :

$\preceq_2 = I_{\pi 2}$

⑥ 集合

$\pi_3$

上的加细关系分析 :

1.自己是自己的加细 : 每个划分 , 自己是自己的加细 , 因此 加细关系中有

$I_{\pi 3}$

$<\mathscr{A}_1 , \mathscr{A}_1>$

$<\mathscr{A}_2 , \mathscr{A}_2>$

$<\mathscr{A}_3 , \mathscr{A}_3>$

$<\mathscr{A}_4 , \mathscr{A}_4>$

$<\mathscr{A}_5 , \mathscr{A}_5>$

;

2.其它加细关系 :
- ① 与
$\mathscr{A}_5$
划分相关的加细 :
$\mathscr{A}_5$
是划分最细的等价关系 ,
$\mathscr{A}_5$
是其它所有划分的加细 , 因此有
$<\mathscr{A}_5 , \mathscr{A}_4>$
,
$<\mathscr{A}_5 , \mathscr{A}_3>$
,
$<\mathscr{A}_5 , \mathscr{A}_2>$
,
$<\mathscr{A}_5 , \mathscr{A}_1>$
;
- ② 与
$\mathscr{A}_1$
划分相关的加细 :
$\mathscr{A}_1$
是划分最粗的等价关系 , 所有的划分都是
$\mathscr{A}_1$
的加细 , 因此有
$<\mathscr{A}_5 , \mathscr{A}_1>$
,
$<\mathscr{A}_4 , \mathscr{A}_1>$
,
$<\mathscr{A}_3 , \mathscr{A}_1>$
,
$<\mathscr{A}_2 , \mathscr{A}_1>$
;
4.加细关系列举 :

$\preceq_3 = I_{\pi 3} \cup \{ <\mathscr{A}_5 , \mathscr{A}_4> , <\mathscr{A}_5 , \mathscr{A}_3> , <\mathscr{A}_5 , \mathscr{A}_2> , <\mathscr{A}_5 , \mathscr{A}_1> , <\mathscr{A}_4 , \mathscr{A}_1>, <\mathscr{A}_3 , \mathscr{A}_1>, <\mathscr{A}_2 , \mathscr{A}_1> \}$

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-07-03，如有侵权请联系 cloudcommunity@tencent.com 删除

集合