「
良預序 」重定向至此。关于等價類組成良序的序結構,请见「
預良序 」。
数学 分支序理论 中,良擬序 或良預序 (英語:well-quasi-ordering ,簡寫作wqo [ 1] 或WQO [ 2] )是特殊的擬序 [ 註 1] ,其元素的任意无穷 序列
x
0
,
x
1
,
x
2
,
…
{\displaystyle x_{0},x_{1},x_{2},\ldots }
中,必有先後兩項遞增,即存在
i
<
j
{\displaystyle i<j}
使
x
i
≤
x
j
{\displaystyle x_{i}\leq x_{j}}
。
動機
良基歸納法 可用於任何良基關係 上,用以證明某集的全部元素皆具某性質。所以,或許會考慮某擬序是否良基[ 註 3] 。不過,良基擬序的類,對某些運算不封閉,即由某良基擬序出發,經若干運算,構造而成的新擬序,不一定良基。欲使新擬序仍為良基,原擬序需追加若干限制。
以冪集 運算為例。給定集合
X
{\displaystyle X}
上的擬序
≤
{\displaystyle \leq }
,可以定義冪集
P
(
X
)
{\displaystyle {\mathcal {P}}(X)}
上的擬序
≤
+
{\displaystyle \leq ^{+}}
,使
A
≤
+
B
{\displaystyle A\leq ^{+}B}
當且僅當對
A
{\displaystyle A}
的每個元素,皆可在
B
{\displaystyle B}
中找到元素大於等於該元素。可以證明
≤
+
{\displaystyle \leq ^{+}}
不必良基,但若原擬序為良擬序,則冪集的擬序確實良基。[ 3] :116
定義
集合
X
{\displaystyle X}
上的良擬序 (well-quasi-ordering )是一種预序关系 (即滿足自反性
x
≤
x
{\displaystyle x\leq x}
、传递性
x
≤
y
∧
y
≤
z
⟹
x
≤
z
{\displaystyle x\leq y\wedge y\leq z\implies x\leq z}
的的二元關係
≤
{\displaystyle \leq }
),使得
X
{\displaystyle X}
中任意无穷 序列
x
0
,
x
1
,
x
2
,
…
{\displaystyle x_{0},x_{1},x_{2},\ldots }
,皆有先後兩項
x
i
≤
x
j
{\displaystyle x_{i}\leq x_{j}}
(
i
<
j
{\displaystyle i<j}
)遞增。若有此種良擬序,則
X
{\displaystyle X}
本身稱為良擬序集 (well-quasi-ordered set ),簡寫為wqo 。[ 1] :210–211
良偏序 (well-partial-ordering )既是良擬序又是偏序 ,即除前述條件外,尚具反對稱性
x
≤
y
∧
y
≤
x
⟹
x
=
y
{\displaystyle x\leq y\wedge y\leq x\implies x=y}
。
良擬序有其他等價定義,如將條件改為既不含無窮嚴格遞減序列
x
0
>
x
1
>
x
2
>
⋯
{\displaystyle x_{0}>x_{1}>x_{2}>\cdots }
[ 註 2] ,又不含任意兩項不可比的無窮序列。換言之,擬序
(
X
,
≤
)
{\displaystyle (X,\leq )}
為良擬序當且僅當
(
X
,
<
)
{\displaystyle (X,<)}
良基 ,且不含無窮反链 。(與§ 無窮遞增子序列 的拉姆齊論證 相似。)[ 1] :211
性質
給定擬序
(
X
,
≤
)
{\displaystyle (X,\leq )}
,在冪集上有另一擬序
(
P
(
X
)
,
≤
+
)
{\displaystyle ({\mathcal {P}}(X),\leq ^{+})}
,其中
A
≤
+
B
⟺
∀
a
∈
A
,
∃
b
∈
B
,
a
≤
b
{\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b}
。此關係為良基當且僅當
(
X
,
≤
)
{\displaystyle (X,\leq )}
本身是wqo 。[ 3] :116
給定良擬序
(
X
,
≤
)
{\displaystyle (X,\leq )}
,若有一列子集
S
0
⊆
S
1
⊆
⋯
⊆
X
{\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X}
,其中每個子集皆向上封閉[ 註 4] ,則該序列終必恆定,即自某個
n
∈
N
{\displaystyle n\in \mathbb {N} }
起,以後各項
S
n
=
S
n
+
1
=
⋯
{\displaystyle S_{n}=S_{n+1}=\cdots }
。假若不然,則對每個
i
∈
N
{\displaystyle i\in \mathbb {N} }
,存在
∃
j
>
i
{\displaystyle \exists j>i}
使
S
j
∖
S
i
{\displaystyle S_{j}\setminus S_{i}}
非空,從中選一個元素,如此可得某個無窮序列,其無遞增的兩項。
給定良擬序
(
X
,
≤
)
{\displaystyle (X,\leq )}
,
X
{\displaystyle X}
的任何子集
S
{\displaystyle S}
關於
≤
{\displaystyle \leq }
僅得有限多個極小元,否則該些極小元組成無窮反鏈。
無窮遞增子序列
若
(
X
,
≤
)
{\displaystyle (X,\leq )}
為wqo ,則任意無窮序列
x
0
,
x
1
,
x
2
,
…
{\displaystyle x_{0},x_{1},x_{2},\ldots }
,皆有無窮上升子序列
x
n
0
≤
x
n
1
≤
x
n
2
≤
⋯
{\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots }
(各下標
n
0
<
n
1
<
n
2
<
⋯
{\displaystyle n_{0}<n_{1}<n_{2}<\cdots }
)。此種子序列或稱為「完美」(perfect )。[ 4] :245 可用拉姆齊證法 [ 註 5] :給定序列
(
x
i
)
i
{\displaystyle (x_{i})_{i}}
,考慮全部
i
{\displaystyle i}
中,何者使
x
i
{\displaystyle x_{i}}
右邊沒有任何
j
>
i
{\displaystyle j>i}
滿足
x
j
≥
x
i
{\displaystyle x_{j}\geq x_{i}}
。記此種
i
{\displaystyle i}
的集合為
I
{\displaystyle I}
。若
I
{\displaystyle I}
無窮,則以
I
{\displaystyle I}
為下標集的子序列將不具遞增的兩項,與
X
{\displaystyle X}
為wqo 的假設抵觸。所以,
I
{\displaystyle I}
為有限集。衹要
n
{\displaystyle n}
大於
I
{\displaystyle I}
中所有元素,則
n
{\displaystyle n}
不屬
I
{\displaystyle I}
,故有某個
m
>
n
{\displaystyle m>n}
使
x
m
≥
x
n
{\displaystyle x_{m}\geq x_{n}}
,如此可逐項延伸,得到無窮遞增子序列。
「任意序列皆有無窮上升子列」與wqo 的條件等價,亦可作為另一種定義。[ 4] :245
例
圖一:整數的平常順序
圖二:自然數按整除序的哈斯圖
圖三:格網
N
2
{\displaystyle \mathbb {N} ^{2}}
逐分量排序的哈斯圖
(
N
,
≤
)
{\displaystyle (\mathbb {N} ,\leq )}
,自然數集配備平常的大小序,是良偏序,乃至良序 。不過,若允許負數,換成整數集的大小序
(
Z
,
≤
)
{\displaystyle (\mathbb {Z} ,\leq )}
,則並非良擬序,因為此大小關係並非良基:負數組成無遞增兩項的序列。(圖一)
(
N
,
|
)
{\displaystyle (\mathbb {N} ,|)}
,自然數集按整除序,不是良擬序:質數兩兩不可比較,組成無窮反鏈。(圖二)
(
N
k
,
≤
)
{\displaystyle (\mathbb {N} ^{k},\leq )}
,自然數
k
{\displaystyle k}
元組的集合逐分量排序 [ 註 6] ,是良偏序。此為迪克遜引理 [ 5] (圖三)。更一般地,若
(
X
,
≤
)
{\displaystyle (X,\leq )}
為良擬序,則對任意正整數
k
{\displaystyle k}
,積序
(
X
k
,
≤
k
)
{\displaystyle (X^{k},\leq ^{k})}
亦是良擬序。
設
X
{\displaystyle X}
為有限集,且至少有兩個元素。克莱尼星号
X
∗
{\displaystyle X^{*}}
是字母取自
X
{\displaystyle X}
的全體有限字串 之集。按字典序 ,
X
∗
{\displaystyle X^{*}}
不是良擬序,因為有無窮遞降序列
b
,
a
b
,
a
a
b
,
a
a
a
b
,
…
{\displaystyle b,ab,aab,aaab,\ldots }
。同樣,
X
∗
{\displaystyle X^{*}}
關於前綴 關係亦非良擬序,因為前述序列在該偏序下是無窮反鏈。然而,
X
∗
{\displaystyle X^{*}}
倘按子序列 關係排序,則是良偏序。[ 6] (在
X
{\displaystyle X}
衹有一個元素的退化情況,此三種偏序完全一樣。)
推而廣之,以
(
X
,
≤
)
{\displaystyle (X,\leq )}
為字母集的有限串集
(
X
∗
,
≤
)
{\displaystyle (X^{*},\leq )}
,按「嵌入」排序,如此組成良擬序當且僅當
(
X
,
≤
)
{\displaystyle (X,\leq )}
本身是良擬序,此結論稱為希格曼引理 [ 7] 。其中所謂字串
u
{\displaystyle u}
可以嵌入到
v
{\displaystyle v}
,意思是
v
{\displaystyle v}
中有與
u
{\displaystyle u}
等長的子序列,逐項大於等於
u
{\displaystyle u}
。若取子母集為無序集
(
X
,
=
)
{\displaystyle (X,=)}
,則字串
u
≤
v
{\displaystyle u\leq v}
當且僅當
u
{\displaystyle u}
是
v
{\displaystyle v}
的子序列,退化成前款情況。
相反,良擬序
(
X
,
≤
)
{\displaystyle (X,\leq )}
上的無窮序列集,記為
(
X
ω
,
≤
)
{\displaystyle (X^{\omega },\leq )}
,按嵌入序,一般不為良擬序。換言之,希格曼引理不適用於無窮序列。數學家引入優擬序 ,以期望推廣希格曼引理。
以wqo
(
X
,
≤
)
{\displaystyle (X,\leq )}
之元素標記頂點的有限樹全體,按嵌入排序,也是wqo ,即克魯斯克爾樹定理 [ 1] 。此處的樹有選定根節點 ,而嵌入的要求有三:某節點的子節點要映到該節點之像的後嗣;同節點的不同子節點,要映到該節點之像的不同子分支上;每個節點處的標記,小於等於其像的標記。
無窮樹之間的嵌入關係[ 註 7] 是wqo ,由克里斯平·納許-威廉斯 所證。[ 8] [ 9]
可數全序 類之間的嵌入關係是良擬序,同樣散佈 [ 註 8] 全序類之間亦然。(萊弗定理 [ 10] )
可數布尔代数 的嵌入序是良擬序,由萊弗定理證得。[ 11] :98
有限圖按图子式 序組成良擬序集。(羅伯遜-西摩定理 )
對每個正整數
t
{\displaystyle t}
,樹深 至多為
t
{\displaystyle t}
的圖,按导出子图 序,組成良擬序集。亦可同上考慮以良擬序
(
X
,
≤
)
{\displaystyle (X,\leq )}
標記其頂點,並要求該導出子圖的嵌入映射,使每個頂點的像的標記皆大於等於原標記,仍得良擬序。[ 12] 此外,補可約圖 按導出子圖序,構成良擬序。[ 13]
與良偏序的關聯
字面上,良擬序較良偏序廣義,但基於以下觀察,兩者實際分別不大:[ 4] :250 一方面,wpo 必為wqo 。另一方面,若有某wqo ,則其各等價類 [ 註 9] 組成wpo 。舉例整數集
Z
{\displaystyle \mathbb {Z} }
的整除序是擬序
(
Z
,
|
)
{\displaystyle (\mathbb {Z} ,|)}
(但不是良擬序),其等價類形如
{
±
m
}
{\displaystyle \{\pm m\}}
,所以等價類組成的偏序同構於
(
N
,
|
)
{\displaystyle (\mathbb {N} ,|)}
。
據米爾納[ 2] ,「考慮擬序,並不比偏序更為概括……僅是因為較方便。」又例如,在全序類的嵌入擬序中,開區間
(
0
,
1
)
{\displaystyle (0,1)}
與閉區間
[
0
,
1
]
{\displaystyle [0,1]}
不同構,但可互相嵌入,所以在對應偏序中屬同一等價類,托馬斯·福斯特 稱該等價類「似乎不是很有啓發性」,而且,全體偏序集按包含關係組成的偏序類,雖然鏈完備 ,但並不完備 ,若改為考慮全體擬序集則不會有此問題。[ 3] :112
註
參考文獻
^ 1.0 1.1 1.2 1.3 Kruskal, J. B. Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture [良擬序、樹定理、瓦容尼猜想] (PDF) . Transactions of the American Mathematical Society (American Mathematical Society). 1960-05, 95 (2): 210–225 [2021-12-24 ] . JSTOR 1993287 . MR 0111704 . doi:10.2307/1993287 . (原始内容存档 (PDF) 于2021-10-21) (英语) .
^ 2.0 2.1 Milner, E. C. Basic WQO- and BQO-theory [基礎WQO與BQO論]. Rival, I. (编). Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and Its Applications [圖與序:有序集理論中,圖的角色,及應用] . D. Reidel Publishing Co. 1985: 487–502 [2021-12-24 ] . ISBN 90-277-1943-8 . (原始内容存档 于2021-12-24) (英语) . no real gain in generality is obtained by considering quasi-orders rather than partial orders… it is simply more convenient to do so.
^ 3.0 3.1 3.2 Forster, Thomas. Better-quasi-orderings and coinduction [優擬序與餘歸納]. Theoretical Computer Science. 2003, 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2 (英语) .
^ 4.0 4.1 4.2 Harzheim, Egbert. 8.2 The notions well-quasi-ordered and partially well-ordered set [第8.2節:良擬序與偏良序集之概念]. Ordered sets [有序集] . [2021-12-20 ] . doi:10.1007/0-387-24222-8_9 . (原始内容存档 于2021-12-24) (英语) .
^ Dickson, L. E. Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors [r 個互異質因數的奇完全數與本原過剩數僅得有限]. American Journal of Mathematics . 1913, 35 (4): 413–422. JSTOR 2370405 . doi:10.2307/2370405 (英语) .
^ W. Gasarch . A survey of recursive combinatorics [遞歸組合學綜述]. Yu. L. Ershov, S.S. Goncharov, A. Nerode, J.B. Remmel, V.W. Marek (编). Handbook of Recursive Mathematics, Vol. 2 [遞歸數學手冊·卷二]. Stud. Logic Found. Math. 139 . Amsterdam: North-Holland. 1998: 1041–1176. MR 1673598 . doi:10.1016/S0049-237X(98)80049-9 (英语) . 尤其見第1160頁。
^ Higman, G. Ordering by divisibility in abstract algebras [抽象代數中,按整除排序]. Proceedings of the London Mathematical Society. 1952, 2 : 326–336. doi:10.1112/plms/s3-2.1.326 (英语) .
^ Nash-Williams, C. On well-quasi-ordering infinite trees [將無窮樹良擬序]. Mathematical Proceedings of the Cambridge Philosophical Society. 1965, 61 (3): 697–720. doi:10.1017/S0305004100039062 (英语) .
^ Kühn, D. On well-quasi-ordering infinite trees – Nash–Williams's theorem revisited [將無窮樹良擬序——再論納許-威廉斯定理]. Mathematical Proceedings of the Cambridge Philosophical Society. 2001, 130 (3): 401–408. doi:10.1017/S0305004101005011 (英语) .
^ Laver, Richard. On Fraïssé's Order Type Conjecture [論弗拉伊塞序類猜想]. Annals of Mathematics, Second Series. 1971-01, 93 (1): 89–111 (英语) .
^ Ruškuc, Nik. Well quasi-order in combinatorics and algebra [組合與代數之良擬序] (PDF) . 2015 [2021-12-24 ] . (原始内容存档 (PDF) 于2021-12-24) (英语) .
^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice. Lemma 6.13. Sparsity: Graphs, Structures, and Algorithms [稀疏性:圖、結構、算法]. Algorithms and Combinatorics 28 . Heidelberg: Springer. 2012: 137. ISBN 978-3-642-27874-7 . MR 2920058 . doi:10.1007/978-3-642-27875-4 (英语) .
^ Damaschke, Peter. Induced subgraphs and well-quasi-ordering [導出子圖與良擬序] . Journal of Graph Theory. 1990, 14 (4): 427–435. MR 1067237 . doi:10.1002/jgt.3190140406 (英语) .