文章目錄
- 一、鍊
- 二、反鍊
- 三、鍊與反鍊示例
- 四、鍊與反鍊定理
- 五、鍊與反鍊推論
- 六、鍊與反鍊推論示例
- 七、良序關系
一、鍊
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> 是 偏序集 ,
B
⊆
A
B \subseteq A
B⊆A ,
偏序集中一組元素組成集合
B
B
B , 如果
B
B
B 集合中的元素兩兩都可比 , 則稱
B
B
B 集合是該偏序集
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> 的鍊 ;
符号化表示 :
∀
x
∀
y
(
x
∈
B
∧
y
∈
B
→
x
與
y
可
比
)
\forall x \forall y ( x \in B \land y \in B \to x 與 y 可比 )
∀x∀y(x∈B∧y∈B→x與y可比)
鍊的本質是一個集合
∣
B
∣
|B|
∣B∣ 是鍊的長度
二、反鍊
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> 是 偏序集 ,
B
⊆
A
B \subseteq A
B⊆A ,
偏序集中一組元素組成集合
B
B
B , 如果
B
B
B 集合中的元素兩兩都 不可比 , 則稱
B
B
B 集合是該偏序集
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> 的 反鍊 ;
符号化表示 :
∀
x
∀
y
(
x
∈
B
∧
y
∈
B
∧
x
≠
y
→
x
與
y
不
可
比
)
\forall x \forall y ( x \in B \land y \in B \land x\not= y \to x 與 y 不可比 )
∀x∀y(x∈B∧y∈B∧x=y→x與y不可比)
反鍊的本質是一個集合
∣
B
∣
|B|
∣B∣ 是反鍊的長度
三、鍊與反鍊示例
參考部落格 : 【集合論】偏序關系 相關題目解析 ( 偏序關系 中的特殊元素 | 繪制哈斯圖 | 鍊 | 反鍊 )
四、鍊與反鍊定理
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> 是 偏序集 ,
B
⊆
A
B \subseteq A
B⊆A ,
A
A
A 集合中最長鍊長度是
n
n
n , 則有以下結論 :
①
A
A
A 集合中存在極大元 ;
A
A
A 集合的極大元就是最長鍊中最大的元素 ;
②
A
A
A 集合中存在
n
n
n 個劃分塊 , 每個劃分塊都是反鍊 ;
将 鍊 中的極大元 , 與該極大元不可比的元素放在一個集合中 , 構成一個劃分塊 ; ( 注意劃分塊中的元素互相不可比 )
在鍊上剩餘的元素中 , 再次選擇一個極大元 , 然後将與該極大元不可比的元素放在一個集合中 , 構成另一個劃分塊 ;
⋮
\vdots
⋮
下面的示例講解了如何劃分 :
上述偏序集中 , 最長的鍊長度是
6
6
6 ;
① 将極大元
g
,
h
g,h
g,h , 與該極大元不可比的剩餘元素
k
k
k 放在一個集合中 ;
A
1
=
{
g
,
h
,
k
}
A_1 = \{ g , h , k \}
A1={g,h,k}
② 将剩餘元素的極大元
f
f
f , 與該極大元不可比的剩餘元素
j
j
j 放在一個集合中 ;
A
2
=
{
f
,
j
}
A_2 = \{ f,j \}
A2={f,j}
③ 将剩餘元素的極大元
e
e
e , 與該極大元不可比的剩餘元素
i
i
i 放在一個集合中 ;
A
3
=
{
e
,
i
}
A_3 = \{ e, i \}
A3={e,i}
④ 将剩餘元素的極大元
d
d
d , 剩餘的元素都與該極大元科比 ;
A
4
=
{
d
}
A_4 = \{ d \}
A4={d}
⑤ 将剩餘元素的極大元
c
c
c , 剩餘的元素都與該極大元科比 ;
A
5
=
{
c
}
A_5 = \{ c\}
A5={c}
⑥ 将剩餘元素的極大元
a
,
b
a,b
a,b , 沒有剩餘元素了 ;
A
6
=
{
a
,
b
}
A_6 = \{ a,b \}
A6={a,b}
整體的劃分為 :
A
=
{
{
g
,
h
,
k
}
,
{
f
,
j
}
,
{
e
,
i
}
,
{
d
}
,
{
c
}
,
{
a
,
b
}
}
\mathscr{A} = \{ \{ g , h , k \} ,\{ f,j \} , \{ e, i \} , \{ d \} , \{ c\} , \{ a,b \} \}
A={{g,h,k},{f,j},{e,i},{d},{c},{a,b}}
每次都将最長鍊去掉一層 , 最終将最長鍊去除幹淨 , 得到
n
n
n 個劃分塊 ;
五、鍊與反鍊推論
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> 是 偏序集 ,
B
⊆
A
B \subseteq A
B⊆A ,
A
A
A 集合大小為
m
n
+
1
mn + 1
mn+1 ,
∣
A
∣
=
m
n
+
1
|A| = mn + 1
∣A∣=mn+1 , 則有以下結論 :
A
A
A 集合中要麼存在
m
+
1
m+1
m+1 的反鍊 , 要麼存在
n
+
1
n + 1
n+1 的鍊 ;
使用反證法證明 :
如果既沒有
m
+
1
m+1
m+1 的反連 , 又沒有
n
+
1
n + 1
n+1 的鍊 ,
假設有長度為
n
n
n 的鍊 , 長度為
m
m
m 的反連 ,
A
A
A 集合最多劃分
n
n
n 個劃分塊 , 每個劃分塊最多有
m
m
m 個元素 , 該集合最多有
m
n
m n
mn 個元素 , 與
∣
A
∣
=
m
n
+
1
|A| = mn + 1
∣A∣=mn+1 沖突 ;
六、鍊與反鍊推論示例
上述偏序集中 , 最長的鍊長度是
6
6
6 ;
A
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
,
k
,
j
,
i
}
A = \{ a,b,c,d,e,f,g,h,k,j,i \}
A={a,b,c,d,e,f,g,h,k,j,i} 集合中 , 元素個數是
11
11
11 個 ,
A
A
A 集合中有
-
長度為
6
6
6 的鍊 ,
{
a
,
c
,
d
,
e
,
f
,
g
}
\{ a, c,d, e,f, g \}
{a,c,d,e,f,g} ,
{
b
,
c
,
d
,
e
,
f
,
h
}
\{ b, c,d, e,f, h \}
{b,c,d,e,f,h}
-
長度為
3
3
3 的反鍊 ,
{
g
,
h
,
k
}
\{ g,h,k \}
{g,h,k} ,
{
a
,
b
,
i
}
\{ a,b,i \}
{a,b,i} ,
{
g
,
h
,
i
}
\{ g,h,i \}
{g,h,i} ,
{
a
,
b
,
k
}
\{ a,b,k \}
{a,b,k}
∣
A
∣
=
11
=
2
×
5
+
1
|A| = 11 = 2 \times 5 + 1
∣A∣=11=2×5+1
A
A
A 集合中要麼有長度為
2
+
1
=
3
2 + 1 = 3
2+1=3 的反鍊 , 要麼有長度為
5
+
1
=
6
5 + 1 = 6
5+1=6 的鍊 ; ( 兩個都滿足 )
或
A
A
A 集合中要麼有長度為
5
+
1
=
6
5 + 1 = 6
5+1=6 的反鍊 , 要麼有長度為
2
+
1
=
3
2 + 1 = 3
2+1=3 的鍊 ; ( 滿足長度為
3
3
3 的鍊 )
A
A
A 集合上的劃分 :
-
A
=
{
{
g
,
h
,
k
}
,
{
f
,
j
}
,
{
e
,
i
}
,
{
d
}
,
{
c
}
,
{
a
,
b
}
}
\mathscr{A} = \{ \{ g , h , k \} ,\{ f,j \} , \{ e, i \} , \{ d \} , \{ c\} , \{ a,b \} \}
A={{g,h,k},{f,j},{e,i},{d},{c},{a,b}}
-
A
=
{
{
g
,
h
}
,
{
f
}
,
{
e
}
,
{
d
}
,
{
c
,
j
}
,
{
a
,
b
,
i
}
}
\mathscr{A} = \{ \{ g , h \} ,\{ f \} , \{ e \} , \{ d \} , \{ c, j\} , \{ a,b , i \} \}
A={{g,h},{f},{e},{d},{c,j},{a,b,i}}
七、良序關系
<
A
,
≺
>
<A, \prec>
<A,≺> 是 拟全序集 ,
如果
A
A
A 集合中的任何非空子集
B
B
B , 都有最小元 ,
則稱
≺
\prec
≺ 是集合
A
A
A 上的良序關系 ,
![區塊鍊學習4：區塊鍊的鍊式結構以及出塊、孤塊、孤鍊和追随最長鍊原則、分叉、主鍊、側鍊[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)