文章目录
- 一. 偏序关系
-
- 1. 偏序关系定义
-
- ( 1 ) 偏序关系定义 ( 自反 | 反对称 | 传递 )
- ( 2 ) 偏序关系 与 等价关系 ( 等价关系 用于分类 | 偏序关系 用于组织 )
- 2. 偏序集定义
-
- ( 1 ) 偏序集定义
- 二. 偏序关系 示例
-
- 1. 小于等于关系
-
- ( 1 ) 小于等于关系 说明
- ( 2 ) 小于等于关系 分析
- 2. 大于等于关系
-
- ( 1 ) 大于等于关系 说明
- ( 2 ) 大于等于关系 分析
- 3. 整除关系
-
- ( 1 ) 整除关系 说明
- ( 2 ) 整除关系 分析
- 4. 包含关系
-
- ( 1 ) 包含关系 说明
- ( 2 ) 包含关系 分析
- 5. 加细关系
-
- ( 1 ) 加细关系 说明
- ( 2 ) 加细关系 分析
一. 偏序关系
1. 偏序关系定义
( 1 ) 偏序关系定义 ( 自反 | 反对称 | 传递 )
偏序关系 定义 :
-
1.前置条件 1 :
A
̸
=
∅
A \not= \varnothing
A̸=∅ , 并且
R
⊆
A
×
A
R \subseteq A \times A
R⊆A×A ;
-
2.前置条件 2 : 如果
R
R
R 是 自反 , 反对称 , 传递的 ;
- ① 自反 : 每个元素 自己 和 自己 都有关系 ,
x
R
x
xRx
- ② 反对称 : 如果
x
R
y
xRy
y
R
x
yRx
x
=
y
x=y
x
̸
=
y
x \not=y
x
R
y
xRy
y
R
x
yRx
- ③ 传递 : 如果 有
x
R
y
xRy
y
R
z
yRz
x
R
z
xRz
- ① 自反 : 每个元素 自己 和 自己 都有关系 ,
-
3.结论 : 称
R
R
R 为
A
A
A 上的偏序关系 ;
-
4.表示 : 使用
⪯
\preceq
⪯ 表示偏序关系 ;
-
5.读法 :
⪯
\preceq
⪯ 读作 "小于等于" ;
-
6.使用公式表示 :
<
x
,
y
>
∈
R
⟺
x
R
y
⟺
x
⪯
y
<x, y> \in R \Longleftrightarrow xRy \Longleftrightarrow x \preceq y
<x,y>∈R⟺xRy⟺x⪯y
-
7.公式解读 : 如果
x
x
x ,
y
y
y 两个元素 构成 有序对
<
x
,
y
>
<x,y>
<x,y> , 并且在偏序关系
R
R
R 中 ,
x
x
x 和
y
y
y 具有
R
R
R 关系 , 也可以写成
x
x
x 小于等于 ( 偏序符号 )
y
y
y ;
-
8.常见的偏序关系 : 树 上 的 小于等于关系 , 集合上的包含关系 , 非
0
0
0 自然数之间的整除关系 , 都是常见的偏序关系 ;
( 2 ) 偏序关系 与 等价关系 ( 等价关系 用于分类 | 偏序关系 用于组织 )
偏序关系 与 等价关系 :
- 1.表示层次结构 : 偏序关系是非常常用的二元关系 , 通常用来 表示 层次结构 ;
- 2.等价关系 : 等价关系 是 用来分类的 , 将一个 集合 分为 几个等价类 ;
- 3.偏序关系 : 偏序关系 通常是 用来组织的 , 在每个类的内部 , 赋予其一个结构 , 特别是层次结构 , 有上下层级 ,
2. 偏序集定义
( 1 ) 偏序集定义
偏序集 定义 :
- 1.前置条件 1 :
⪯
\preceq
A
A
- 2.结论 :
<
A
,
⪯
>
<A , \preceq>
- 3.解读 : 集合
A
A
⪯
\preceq
二. 偏序关系 示例
1. 小于等于关系
( 1 ) 小于等于关系 说明
偏序集示例 1 ( 小于等于关系
≤
\leq
≤ 是 偏序关系 ) :
- 1.公式表示 :
∅
̸
=
A
⊆
R
,
<
A
,
≤
>
\varnothing \not= A \subseteq R , <A , \leq >
- 2.语言描述 : 如果
A
A
R
R
A
A
∅
\varnothing
A
A
- 3.使用集合形式表示关系 :
≤
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
≤
y
}
\leq = \{ <x,y> | x,y \in A \land x \leq y \}
( 2 ) 小于等于关系 分析
实数集
A
A
A 上的 小于等于关系 (
≤
\leq
≤ ) 分析 :
- 1.自反性质分析 :
x
x
x
x
x
≤
x
x \leq x
- 2.反对称性质分析 :
x
x
y
y
y
y
x
x
x
=
y
x = y
- 3.传递性质分析 :
x
x
y
y
y
y
z
z
x
x
z
z
- 4.总结 : 综上所述 , 小于等于 关系 是 偏序关系 ;
2. 大于等于关系
( 1 ) 大于等于关系 说明
偏序集示例 2 ( 大于等于关系
≥
\geq
≥ 是 偏序关系 ) :
- 1.公式表示 :
∅
̸
=
A
⊆
R
,
<
A
,
≥
>
\varnothing \not= A \subseteq R , <A , \geq >
- 2.语言描述 : 如果
A
A
R
R
A
A
∅
\varnothing
A
A
≥
\geq
- 3.使用集合形式表示关系 :
≥
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
≥
y
}
\geq = \{ <x,y> | x,y \in A \land x \geq y \}
( 2 ) 大于等于关系 分析
实数集
A
A
A 上的 大于等于关系 (
≥
\geq
≥ ) 分析 :
- 1.自反性质分析 :
x
x
x
x
x
≥
x
x \geq x
- 2.反对称性质分析 :
x
x
y
y
y
y
x
x
x
=
y
x = y
- 3.传递性质分析 :
x
x
y
y
y
y
z
z
x
x
z
z
- 4.总结 : 综上所述 , 大于等于 关系 是 偏序关系 ;
3. 整除关系
( 1 ) 整除关系 说明
偏序集示例 3 ( 整除关系 是 偏序关系 ) :
- 1.公式表示 :
∅
̸
=
A
⊆
Z
+
=
{
x
∣
x
∈
Z
∧
x
>
0
}
<
A
,
∣
>
\varnothing \not= A \subseteq Z_+ = \{ x | x \in Z \land x > 0 \}<A , | >
- 2.语言描述 : 如果
A
A
Z
+
Z_+
A
A
∅
\varnothing
A
A
∣
|
- 3.使用集合形式表示关系 :
∣
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
∣
y
}
|= \{ <x,y> | x,y \in A \land x | y \}
- 4.整除关系 :
x
∣
y
x|y
x
x
y
y
y
y
x
x
( 2 ) 整除关系 分析
正整数集
A
A
A 上的 整除关系 (
∣
|
∣ ) 分析 :
- 1.自反性质分析 :
x
x
x
x
x
∣
x
x | x
- 2.反对称性质分析 :
x
x
y
y
y
y
x
x
x
=
y
x = y
- 3.传递性质分析 :
x
x
y
y
y
y
z
z
x
x
z
z
- 4.总结 : 综上所述 , 整除 关系 是 偏序关系 ;
4. 包含关系
( 1 ) 包含关系 说明
偏序集示例 4 ( 包含关系
⊆
\subseteq
⊆ 是 偏序关系 ) :
- 1.公式表示 :
A
⊆
P
(
A
)
,
⊆
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
⊆
y
}
\mathscr{A} \subseteq P(A) , \subseteq = \{<x , y> | x , y \in \mathscr{A} \land x \subseteq y \}
- 2.语言描述 : 集合
A
A
P
(
A
)
P(A)
P
(
A
)
P(A)
A
\mathscr{A}
A
\mathscr{A}
( 2 ) 包含关系 分析
分析 集合的 子集族 之间的包含关系 :
① 假设一个比较简单的集合
A
=
{
a
,
b
}
A=\{a, b\}
A={a,b}
② 分析 下面
A
A
A 的 3 个子集族 ;
A
1
=
{
∅
,
{
a
}
,
{
b
}
}
\mathscr{A}_1 = \{ \varnothing , \{a\} , \{b\} \}
A1={∅,{a},{b}}
集族
A
1
\mathscr{A}_1
A1 包含 空集
∅
\varnothing
∅ , 单元集
{
a
}
\{a\}
{a} , 单元集
{
b
}
\{b\}
{b} ;
A
2
=
{
{
a
}
,
{
a
,
b
}
}
\mathscr{A}_2 = \{ \{a\} , \{a, b\} \}
A2={{a},{a,b}}
集族
A
2
\mathscr{A}_2
A2 包含 单元集
{
a
}
\{a\}
{a} , 2 元集
{
a
,
b
}
\{a, b\}
{a,b} ;
A
3
=
P
(
A
)
=
{
∅
,
{
a
}
,
{
b
}
,
{
a
,
b
}
}
\mathscr{A}_3 = P(A) = \{ \varnothing , \{a\} , \{b\} , \{a, b\} \}
A3=P(A)={∅,{a},{b},{a,b}}
集族
A
3
\mathscr{A}_3
A3 包含 空集
∅
\varnothing
∅ , 单元集
{
a
}
\{a\}
{a} , 单元集
{
b
}
\{b\}
{b} , 2 元集
{
a
,
b
}
\{a, b\}
{a,b} ; 这是 集合
A
A
A 的 幂集 ;
③ 列举出集族
A
1
\mathscr{A}_1
A1 上的包含关系 :
⊆
1
=
I
A
1
∪
{
<
∅
,
{
a
}
>
,
<
∅
,
{
b
}
>
}
\subseteq_1 = I_{\mathscr{A}1} \cup \{ <\varnothing , \{a\}> , <\varnothing , \{b\}> \}
⊆1=IA1∪{<∅,{a}>,<∅,{b}>}
⊆
1
\subseteq_1
⊆1 是集合
A
1
\mathscr{A}1
A1 上的偏序关系 ;
即 分析 空集
∅
\varnothing
∅ , 单元集
{
a
}
\{a\}
{a} , 单元集
{
b
}
\{b\}
{b} 三个 集合之间的包含关系 :
- 1.恒等关系
I
A
1
I_{\mathscr{A}1}
<
{
a
}
,
{
a
}
>
和
<
{
b
}
,
{
b
}
>
<\{a\} , \{a\}> 和 <\{b\} , \{b\}>
- 2.
<
∅
,
{
a
}
>
<\varnothing , \{a\}>
{
a
}
\{a\}
- 3.
<
∅
,
{
b
}
>
<\varnothing , \{b\}>
{
b
}
\{b\}
- 4.总结 : 这些包含关系 的性质分析 :
- ① 自反 : 每个元素自己 包含 自己 ,
A
⊆
A
A \subseteq A
- ② 反对称 : 如果 集合
A
⊆
B
A \subseteq B
B
⊆
A
B \subseteq A
A
=
B
A = B
- ③ 传递 : 如果
A
⊆
B
A \subseteq B
A
⊆
C
A \subseteq C
A
⊆
C
A \subseteq C
- ① 自反 : 每个元素自己 包含 自己 ,
④ 列举出集族
A
2
\mathscr{A}_2
A2 上的包含关系 :
⊆
2
=
I
A
2
∪
{
<
{
a
}
,
{
a
,
b
}
>
\subseteq_2 = I_{\mathscr{A}2} \cup \{ <\{a\} , \{a, b\}>
⊆2=IA2∪{<{a},{a,b}>
⊆
2
\subseteq_2
⊆2 是集合
A
2
\mathscr{A}2
A2 上的偏序关系 ;
⑤ 列举出集族
A
3
\mathscr{A}_3
A3 上的包含关系 :
⊆
3
=
I
A
3
∪
{
<
∅
,
{
a
}
>
,
<
∅
,
{
b
}
>
,
<
∅
,
{
a
,
b
}
>
,
<
{
a
}
,
{
a
,
b
}
>
,
<
{
b
}
,
{
a
,
b
}
>
}
\subseteq_3 = I_{\mathscr{A}3} \cup \{ <\varnothing , \{a\}> , <\varnothing , \{b\}>, <\varnothing , \{a, b\}> , <\{a\} , \{a, b\}> , <\{b\} , \{a, b\}> \}
⊆3=IA3∪{<∅,{a}>,<∅,{b}>,<∅,{a,b}>,<{a},{a,b}>,<{b},{a,b}>}
⊆
3
\subseteq_3
⊆3 是集合
A
3
\mathscr{A}_3
A3 上的偏序关系 ;
5. 加细关系
( 1 ) 加细关系 说明
偏序集示例 5 ( 加细关系
⪯
加
细
\preceq_{加细}
⪯加细 是 偏序关系 ) :
- 1.加细关系描述 :
A
̸
=
∅
A \not= \varnothing
π
\pi
A
A
⪯
加
细
=
{
<
x
,
y
>
∣
x
,
y
∈
π
∧
x
是
y
的
加
细
}
\preceq_{加细} = \{<x , y> | x , y \in \pi \land x 是 y 的 加细\}
⪯加细={<x,y>∣x,y∈π∧x是y的加细}
- 2.划分 : 划分 是 一个 集族 ( 集合的集合 ) , 其元素是集合 又叫 划分快 , 其中 每个元素(集族中的元素)集合 中的 元素 是 非空集合
A
A
- ① 该集族不包含空集 ;
- ② 该集族中任意两个集合都不想交 ;
- ③ 该集族中 所有 元素 取并集 , 得到 集合
A
A
( 2 ) 加细关系 分析
分析 集合的 划分之间 的 加细 关系 :
① 集合
A
=
{
a
,
b
,
c
}
A = \{a, b, c\}
A={a,b,c} , 下面的 划分 和 加细 都基于 该 集合 进行分析 ;
② 下面 列出集合
A
A
A 的 5 个划分 :
划分 1 : 对应 1 个等价关系 , 分成 1 类 ;
A
1
=
{
{
a
,
b
,
c
}
}
\mathscr{A}_1 =\{ \{ a, b, c \} \}
A1={{a,b,c}}
划分 2 : 对应 2 个等价关系 , 分成 2 类 ;
A
2
=
{
{
a
}
,
{
b
,
c
}
}
\mathscr{A}_2 = \{ \{ a \} , \{ b, c \} \}
A2={{a},{b,c}}
划分 3 : 对应 2 个等价关系 , 分成 2 类 ;
A
3
=
{
{
b
}
,
{
a
,
c
}
}
\mathscr{A}_3 = \{ \{ b \} , \{ a, c \} \}
A3={{b},{a,c}}
划分 4 : 对应 2 个等价关系 , 分成 2 类 ;
A
4
=
{
{
c
}
,
{
a
,
b
}
}
\mathscr{A}_4 = \{ \{ c \} , \{ a, b \}\}
A4={{c},{a,b}}
划分 5 : 对应 3 个等价关系 , 分成 3 类 ; 每个元素自己自成一类
A
5
=
{
{
a
}
,
{
b
}
,
{
c
}
}
\mathscr{A}_5 = \{ \{ a \} , \{ b \}, \{ c \} \}
A5={{a},{b},{c}}
③ 下面 列出要分析的几个由划分组成的集合 :
集合 1 :
π
1
=
{
A
1
,
A
2
}
\pi_1 = \{ \mathscr{A}_1, \mathscr{A}_2 \}
π1={A1,A2}
集合 2 :
π
2
=
{
A
2
,
A
3
}
\pi_2 = \{ \mathscr{A}_2, \mathscr{A}_3 \}
π2={A2,A3}
集合 3 :
π
3
=
{
A
1
,
A
2
,
A
3
,
A
4
,
A
5
}
\pi_3 = \{ \mathscr{A}_1, \mathscr{A}_2, \mathscr{A}_3, \mathscr{A}_4, \mathscr{A}_5 \}
π3={A1,A2,A3,A4,A5}
④ 集合
π
1
\pi_1
π1 上的加细关系分析 :
- 1.自己是自己的加细 : 每个划分 , 自己是自己的加细 , 因此 加细关系中 有
I
π
1
I_{\pi 1}
<
A
1
,
A
1
>
<\mathscr{A}_1 , \mathscr{A}_1>
<
A
2
,
A
2
>
<\mathscr{A}_2 , \mathscr{A}_2>
- 2.其它加细关系 :
A
2
\mathscr{A}_2
A
1
\mathscr{A}_1
A
2
\mathscr{A}_2
A
1
\mathscr{A}_1
<
A
2
,
A
1
>
<\mathscr{A}_2, \mathscr{A}_1>
- 3.加细的定义 :
A
1
\mathscr{A}_1
A
2
\mathscr{A}_2
A
A
A
2
\mathscr{A}_2
A
1
\mathscr{A}_1
A
2
\mathscr{A}_2
A
1
\mathscr{A}_1
- 4.加细关系列举 :
⪯
1
=
I
π
1
∪
{
<
A
2
,
A
1
>
}
\preceq_1 = I_{\pi 1} \cup \{ <\mathscr{A}_2, \mathscr{A}_1> \}
⪯1=Iπ1∪{<A2,A1>}
⑤ 集合
π
2
\pi_2
π2 上的加细关系分析 :
- 1.自己是自己的加细 : 每个划分 , 自己是自己的加细 , 因此 加细关系中 有
I
π
2
I_{\pi 2}
<
A
3
,
A
3
>
<\mathscr{A}_3 , \mathscr{A}_3>
<
A
2
,
A
2
>
<\mathscr{A}_2 , \mathscr{A}_2>
- 2.其它加细关系 :
A
2
\mathscr{A}_2
A
3
\mathscr{A}_3
- 4.加细关系列举 :
⪯
2
=
I
π
2
\preceq_2 = I_{\pi 2}
⪯2=Iπ2
⑥ 集合
π
3
\pi_3
π3 上的加细关系分析 :
- 1.自己是自己的加细 : 每个划分 , 自己是自己的加细 , 因此 加细关系中 有
I
π
3
I_{\pi 3}
<
A
1
,
A
1
>
<\mathscr{A}_1 , \mathscr{A}_1>
<
A
2
,
A
2
>
<\mathscr{A}_2 , \mathscr{A}_2>
<
A
3
,
A
3
>
<\mathscr{A}_3 , \mathscr{A}_3>
<
A
4
,
A
4
>
<\mathscr{A}_4 , \mathscr{A}_4>
<
A
5
,
A
5
>
<\mathscr{A}_5 , \mathscr{A}_5>
- 2.其它加细关系 :
- ① 与
A
5
\mathscr{A}_5
A
5
\mathscr{A}_5
A
5
\mathscr{A}_5
<
A
5
,
A
4
>
<\mathscr{A}_5 , \mathscr{A}_4>
<
A
5
,
A
3
>
<\mathscr{A}_5 , \mathscr{A}_3>
<
A
5
,
A
2
>
<\mathscr{A}_5 , \mathscr{A}_2>
<
A
5
,
A
1
>
<\mathscr{A}_5 , \mathscr{A}_1>
- ② 与
A
1
\mathscr{A}_1
A
1
\mathscr{A}_1
A
1
\mathscr{A}_1
<
A
5
,
A
1
>
<\mathscr{A}_5 , \mathscr{A}_1>
<
A
4
,
A
1
>
<\mathscr{A}_4 , \mathscr{A}_1>
<
A
3
,
A
1
>
<\mathscr{A}_3 , \mathscr{A}_1>
<
A
2
,
A
1
>
<\mathscr{A}_2 , \mathscr{A}_1>
- ① 与
- 4.加细关系列举 :
⪯
3
=
I
π
3
∪
{
<
A
5
,
A
4
>
,
<
A
5
,
A
3
>
,
<
A
5
,
A
2
>
,
<
A
5
,
A
1
>
,
<
A
4
,
A
1
>
,
<
A
3
,
A
1
>
,
<
A
2
,
A
1
>
}
\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> \}
⪯3=Iπ3∪{<A5,A4>,<A5,A3>,<A5,A2>,<A5,A1>,<A4,A1>,<A3,A1>,<A2,A1>}