【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 )

韩曙亮

发布于 2023-03-28 18:09:47

1.5K0

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

文章目录

一、链

<A, \preccurlyeq>

是偏序集 ,

B \subseteq A

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

, 如果

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

集合是该偏序集

<A, \preccurlyeq>

的链 ;

符号化表示 :

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

链的本质是一个集合

|B|

是链的长度

二、反链

<A, \preccurlyeq>

是偏序集 ,

B \subseteq A

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

, 如果

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

集合是该偏序集

<A, \preccurlyeq>

的反链 ;

符号化表示 :

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

反链的本质是一个集合

|B|

是反链的长度

三、链与反链示例

四、链与反链定理

<A, \preccurlyeq>

是偏序集 ,

B \subseteq A

集合中最长链长度是

, 则有以下结论 :

①

集合中存在极大元 ;

集合的极大元就是最长链中最大的元素 ;

②

集合中存在

个划分块 , 每个划分块都是反链 ;

将链中的极大元 , 与该极大元不可比的元素放在一个集合中 , 构成一个划分块 ; ( 注意划分块中的元素互相不可比 )

在链上剩余的元素中 , 再次选择一个极大元 , 然后将与该极大元不可比的元素放在一个集合中 , 构成另一个划分块 ;

\vdots

下面的示例讲解了如何划分 :

上述偏序集中 , 最长的链长度是

;

① 将极大元

g,h

, 与该极大元不可比的剩余元素

放在一个集合中 ;

A_1 = \{ g , h , k \}

② 将剩余元素的极大元

, 与该极大元不可比的剩余元素

放在一个集合中 ;

A_2 = \{ f,j \}

③ 将剩余元素的极大元

, 与该极大元不可比的剩余元素

放在一个集合中 ;

A_3 = \{ e, i \}

④ 将剩余元素的极大元

, 剩余的元素都与该极大元科比 ;

A_4 = \{ d \}

⑤ 将剩余元素的极大元

, 剩余的元素都与该极大元科比 ;

A_5 = \{ c\}

⑥ 将剩余元素的极大元

a,b

, 没有剩余元素了 ;

A_6 = \{ a,b \}

整体的划分为 :

\mathscr{A} = \{ \{ g , h , k \} ,\{ f,j \} , \{ e, i \} , \{ d \} , \{ c\} , \{ a,b \} \}

每次都将最长链去掉一层 , 最终将最长链去除干净 , 得到

个划分块 ;

五、链与反链推论

<A, \preccurlyeq>

是偏序集 ,

B \subseteq A

集合大小为

mn + 1

|A| = mn + 1

, 则有以下结论 :

集合中要么存在

m+1

的反链 , 要么存在

n + 1

的链 ;

使用反证法证明 :

如果既没有

m+1

的反连 , 又没有

n + 1

的链 ,

假设有长度为

的链 , 长度为

的反连 ,

集合最多划分

个划分块 , 每个划分块最多有

个元素 , 该集合最多有

m n

个元素 , 与

|A| = mn + 1

矛盾 ;

六、链与反链推论示例

上述偏序集中 , 最长的链长度是

;

A = \{ a,b,c,d,e,f,g,h,k,j,i \}

集合中 , 元素个数是

个 ,

集合中有

长度为

的链 ,

\{ a, c,d, e,f, g \}

\{ b, c,d, e,f, h \}

长度为

的反链 ,

\{ g,h,k \}

\{ a,b,i \}

\{ g,h,i \}

\{ a,b,k \}

|A| = 11 = 2 \times 5 + 1

集合中要么有长度为

2 + 1 = 3

的反链 , 要么有长度为

5 + 1 = 6

的链 ; ( 两个都满足 ) 或

集合中要么有长度为

5 + 1 = 6

的反链 , 要么有长度为

2 + 1 = 3

的链 ; ( 满足长度为

的链 )

集合上的划分 :

\mathscr{A} = \{ \{ g , h , k \} ,\{ f,j \} , \{ e, i \} , \{ d \} , \{ c\} , \{ a,b \} \}

\mathscr{A} = \{ \{ g , h \} ,\{ f \} , \{ e \} , \{ d \} , \{ c, j\} , \{ a,b , i \} \}

七、良序关系

<A, \prec>

是拟全序集 ,

如果

集合中的任何非空子集

, 都有最小元 ,

则称

\prec

是集合

上的良序关系 ,

称

<A, \prec>

为良序集

<N, <>

是良序集 ,

集合中的非空子集有最小元 , 最小就是

;

<Z, <>

不是良序集 ,

集合中的非空子集可能没有最小元 , 可能是

-\infty

;

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

原始发表：2020-10-14，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

集合