良擬序

数学分支序理论中，良擬序或良預序（英語：well-quasi-ordering，簡寫作wqo^[1]或WQO^[2]）是特殊的擬序^{[註 1]}，其元素的任意无穷序列 $x_{0},x_{1},x_{2},\ldots$ 中，必有先後兩項遞增，即存在 $i<j$ 使 $x_{i}\leq x_{j}$ 。

動機

良基歸納法可用於任何良基關係上，用以證明某集的全部元素皆具某性質。所以，或許會考慮某擬序是否良基^{[註 3]}。不過，良基擬序的類，對某些運算不封閉，即由某良基擬序出發，經若干運算，構造而成的新擬序，不一定良基。欲使新擬序仍為良基，原擬序需追加若干限制。

以冪集運算為例。給定集合 $X$ 上的擬序 $\leq$ ，可以定義冪集 ${\mathcal {P}}(X)$ 上的擬序 $\leq ^{+}$ ，使 $A\leq ^{+}B$ 當且僅當對 $A$ 的每個元素，皆可在 $B$ 中找到元素大於等於該元素。可以證明 $\leq ^{+}$ 不必良基，但若原擬序為良擬序，則冪集的擬序確實良基。^[3]^:116

定義

集合 $X$ 上的良擬序（well-quasi-ordering）是一種预序关系（即滿足自反性 $x\leq x$ 、传递性 $x\leq y\wedge y\leq z\implies x\leq z$ 的的二元關係 $\leq$ ），使得解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh1.bitforum.be.eu.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle X} 中任意无穷序列 $x_{0},x_{1},x_{2},\ldots$ ，皆有先後兩項 $x_{i}\leq x_{j}$ （ $i<j$ ）遞增。若有此種良擬序，則 $X$ 本身稱為良擬序集（well-quasi-ordered set），簡寫為wqo。^[1]^:210–211

良偏序（well-partial-ordering）既是良擬序又是偏序，即除前述條件外，尚具反對稱性 $x\leq y\wedge y\leq x\implies x=y$ 。

良擬序有其他等價定義，如將條件改為既不含無窮嚴格遞減序列 $x_{0}>x_{1}>x_{2}>\cdots$ ^{[註 2]}，又不含任意兩項不可比的無窮序列。換言之，擬序 $(X,\leq )$ 為良擬序當且僅當 $(X,<)$ 良基，且不含無窮反链。（與§ 無窮遞增子序列的拉姆齊論證相似。）^[1]^:211

性質

給定擬序 $(X,\leq )$ ，在冪集上有另一擬序 $({\mathcal {P}}(X),\leq ^{+})$ ，其中 $A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b$ 。此關係為良基當且僅當 $(X,\leq )$ 本身是wqo。^[3]^:116
給定良擬序 $(X,\leq )$ ，若有一列子集 $S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X$ ，其中每個子集皆向上封閉^{[註 4]}，則該序列終必恆定，即自某個 $n\in \mathbb {N}$ 起，以後各項 $S_{n}=S_{n+1}=\cdots$ 。假若不然，則對每個 $i\in \mathbb {N}$ ，存在 $\exists j>i$ 使 $S_{j}\setminus S_{i}$ 非空，從中選一個元素，如此可得某個無窮序列，其無遞增的兩項。
給定良擬序 $(X,\leq )$ ， $X$ 的任何子集 $S$ 關於 $\leq$ 僅得有限多個極小元，否則該些極小元組成無窮反鏈。

無窮遞增子序列

若 $(X,\leq )$ 為wqo，則任意無窮序列 $x_{0},x_{1},x_{2},\ldots$ ，皆有無窮上升子序列 $x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots$ （各下標 $n_{0}<n_{1}<n_{2}<\cdots$ ）。此種子序列或稱為「完美」（perfect）。^[4]^:245可用拉姆齊證法^{[註 5]}：給定序列 $(x_{i})_{i}$ ，考慮全部 $i$ 中，何者使 $x_{i}$ 右邊沒有任何 $j>i$ 滿足 $x_{j}\geq x_{i}$ 。記此種 $i$ 的集合為 $I$ 。若 $I$ 無窮，則以 $I$ 為下標集的子序列將不具遞增的兩項，與 $X$ 為wqo的假設抵觸。所以， $I$ 為有限集。衹要 $n$ 大於 $I$ 中所有元素，則 $n$ 不屬 $I$ ，故有某個 $m>n$ 使 $x_{m}\geq x_{n}$ ，如此可逐項延伸，得到無窮遞增子序列。

「任意序列皆有無窮上升子列」與wqo的條件等價，亦可作為另一種定義。^[4]^:245

例

圖一：整數的平常順序

$(\mathbb {N} ,\leq )$ ，自然數集配備平常的大小序，是良偏序，乃至良序。不過，若允許負數，換成整數集的大小序 $(\mathbb {Z} ,\leq )$ ，則並非良擬序，因為此大小關係並非良基：負數組成無遞增兩項的序列。（圖一）
$(\mathbb {N} ,|)$ ，自然數集按整除序，不是良擬序：質數兩兩不可比較，組成無窮反鏈。（圖二）
$(\mathbb {N} ^{k},\leq )$ ，自然數 $k$ 元組的集合逐分量排序（英语：product order）^{[註 6]}，是良偏序。此為迪克遜引理（英语：Dickson's lemma）^[5]（圖三）。更一般地，若 $(X,\leq )$ 為良擬序，則對任意正整數 $k$ ，積序（英语：product order） $(X^{k},\leq ^{k})$ 亦是良擬序。
設 $X$ 為有限集，且至少有兩個元素。克莱尼星号 $X^{*}$ 是字母取自 $X$ 的全體有限字串之集。按字典序， $X^{*}$ 不是良擬序，因為有無窮遞降序列 $b,ab,aab,aaab,\ldots$ 。同樣， $X^{*}$ 關於前綴關係亦非良擬序，因為前述序列在該偏序下是無窮反鏈。然而， $X^{*}$ 倘按子序列關係排序，則是良偏序。^[6]（在 $X$ 衹有一個元素的退化情況，此三種偏序完全一樣。）
推而廣之，以 $(X,\leq )$ 為字母集的有限串集 $(X^{*},\leq )$ ，按「嵌入」排序，如此組成良擬序當且僅當 $(X,\leq )$ 本身是良擬序，此結論稱為希格曼引理（英语：Higman's lemma）^[7]。其中所謂字串 $u$ 可以嵌入到 $v$ ，意思是 $v$ 中有與 $u$ 等長的子序列，逐項大於等於 $u$ 。若取子母集為無序集 $(X,=)$ ，則字串 $u\leq v$ 當且僅當 $u$ 是 $v$ 的子序列，退化成前款情況。
相反，良擬序 $(X,\leq )$ 上的無窮序列集，記為 $(X^{\omega },\leq )$ ，按嵌入序，一般不為良擬序。換言之，希格曼引理不適用於無窮序列。數學家引入優擬序（英语：Better-quasi-ordering），以期望推廣希格曼引理。
以wqo $(X,\leq )$ 之元素標記頂點的有限樹全體，按嵌入排序，也是wqo，即克魯斯克爾樹定理（英语：Kruskal's tree theorem）^[1]。此處的樹有選定根節點，而嵌入的要求有三：某節點的子節點要映到該節點之像的後嗣；同節點的不同子節點，要映到該節點之像的不同子分支上；每個節點處的標記，小於等於其像的標記。
無窮樹之間的嵌入關係^{[註 7]}是wqo，由克里斯平·納許-威廉斯（英语：Crispin St. J. A. Nash-Williams）所證。^[8]^[9]
可數全序類之間的嵌入關係是良擬序，同樣散佈（英语：scattered order）^{[註 8]}全序類之間亦然。（萊弗定理（英语：Laver's theorem）^[10]）
可數布尔代数的嵌入序是良擬序，由萊弗定理證得。^[11]^:98
有限圖按图子式序組成良擬序集。（羅伯遜-西摩定理（英语：Robertson–Seymour theorem））
對每個正整數 $t$ ，樹深（英语：tree-depth）至多為 $t$ 的圖，按导出子图序，組成良擬序集。亦可同上考慮以良擬序 $(X,\leq )$ 標記其頂點，並要求該導出子圖的嵌入映射，使每個頂點的像的標記皆大於等於原標記，仍得良擬序。^[12]此外，補可約圖（英语：cograph）按導出子圖序，構成良擬序。^[13]

與良偏序的關聯

字面上，良擬序較良偏序廣義，但基於以下觀察，兩者實際分別不大：^[4]^:250一方面，wpo必為wqo。另一方面，若有某wqo，則其各等價類^{[註 9]}組成wpo。舉例整數集 $\mathbb {Z}$ 的整除序是擬序 $(\mathbb {Z} ,|)$ （但不是良擬序），其等價類形如 $\{\pm m\}$ ，所以等價類組成的偏序同構於 $(\mathbb {N} ,|)$ 。

據米爾納^[2]，「考慮擬序，並不比偏序更為概括……僅是因為較方便。」又例如，在全序類的嵌入擬序中，開區間 $(0,1)$ 與閉區間 $[0,1]$ 不同構，但可互相嵌入，所以在對應偏序中屬同一等價類，托馬斯·福斯特（英语：Thomas Forster (mathematician)）稱該等價類「似乎不是很有啓發性」，而且，全體偏序集按包含關係組成的偏序類，雖然鏈完備（英语：Chain complete），但並不完備（英语：Completeness (order theory)），若改為考慮全體擬序集則不會有此問題。^[3]^:112

註

^ 擬序（quasi-ordering）為預序（preorder）的別名。
^ ^2.0 ^2.1 $x<y$ 謂 $x\leq y$ 且 $y\nleq x$ 。
^ 此處有濫用術語，稱擬序 $(X,\leq )$ 良基實際是說嚴格序 $(X,<)$ ^{[註 2]}為良基。
^ 子集 $S\subseteq X$ 向上封閉，意思是 $\forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S$ 。
^ 拉姆齊定理斷言，無窮個頂點的圖中，每邊染紅藍兩色之一，則必有同色無窮階完全圖。此處若 $i<j$ 且 $x_{j}\geq x_{i}$ 則邊 $ij$ 染紅，否則染藍。Wqo條件即無紅色無窮階完全圖，故必有藍色無窮階完全圖，即遞增子序列。
^ ${\boldsymbol {x}}\leq {\boldsymbol {y}}$ 是逐個分量有 $x_{i}\leq y_{i}$ 。
^ 即拓撲圖子式（英语：topological minor）關係。
^ 沒有多於一個元素的稠密子序。
^ 兩元素 $x,y$ 等價定義為 $x\leq y\land y\leq x$ 。

參考文獻

^ ^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（英语：American Journal of Mathematics）. 1913, 35 (4): 413–422. JSTOR 2370405. doi:10.2307/2370405 （英语）.
^ W. Gasarch（英语：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 （英语）.

Kruskal, J. B. The theory of well-quasi-ordering: A frequently discovered concept [良擬序論：常發現的概念]. Journal of Combinatorial Theory（英语：Journal of Combinatorial Theory）. Series A. 1972, 13 (3): 297–305. doi:10.1016/0097-3165(72)90063-5  （英语）.
Ketonen, Jussi. The structure of countable Boolean algebras [可數布爾代數的結構]. Annals of Mathematics. 1978, 108 (1): 41–89. JSTOR 1970929. doi:10.2307/1970929 （英语）.
Gallier, Jean H. What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory [克魯斯克爾定與與序數Γo有何特別？證明論若干結果的綜述]. Annals of Pure and Applied Logic. 1991, 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E  （英语）.

[3] 擬序（quasi-ordering）為預序（preorder）的別名。

[strict-4] 2.0 ^2.1 $x<y$ 謂 $x\leq y$ 且 $y\nleq x$ 。

[5] 此處有濫用術語，稱擬序 $(X,\leq )$ 良基實際是說嚴格序 $(X,<)$ ^{[註 2]}為良基。

[7] 子集 $S\subseteq X$ 向上封閉，意思是 $\forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S$ 。

[9] 拉姆齊定理斷言，無窮個頂點的圖中，每邊染紅藍兩色之一，則必有同色無窮階完全圖。此處若 $i<j$ 且 $x_{j}\geq x_{i}$ 則邊 $ij$ 染紅，否則染藍。Wqo條件即無紅色無窮階完全圖，故必有藍色無窮階完全圖，即遞增子序列。

[10] ${\boldsymbol {x}}\leq {\boldsymbol {y}}$ 是逐個分量有 $x_{i}\leq y_{i}$ 。

[14] 即拓撲圖子式（英语：topological minor）關係。

[17] 沒有多於一個元素的稠密子序。

[equiv-22] 兩元素 $x,y$ 等價定義為 $x\leq y\land y\leq x$ 。

[krus60-1] 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）（英语）.

[miln-2] 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.

[forster-6] 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  （英语）.

[Harz-8] 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）（英语）.

[11] Dickson, L. E. Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors [r個互異質因數的奇完全數與本原過剩數僅得有限]. American Journal of Mathematics（英语：American Journal of Mathematics）. 1913, 35 (4): 413–422. JSTOR 2370405. doi:10.2307/2370405 （英语）.

[12] W. Gasarch（英语：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頁。

[13] 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 （英语）.

[15] 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 （英语）.

[16] 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 （英语）.

[18] Laver, Richard. On Fraïssé's Order Type Conjecture [論弗拉伊塞序類猜想]. Annals of Mathematics, Second Series. 1971-01, 93 (1): 89–111 （英语）.

[19] Ruškuc, Nik. Well quasi-order in combinatorics and algebra [組合與代數之良擬序] (PDF). 2015 [2021-12-24]. （原始内容存档 (PDF)于2021-12-24）（英语）.

[20] 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 （英语）.

[21] Damaschke, Peter. Induced subgraphs and well-quasi-ordering [導出子圖與良擬序]. Journal of Graph Theory. 1990, 14 (4): 427–435. MR 1067237. doi:10.1002/jgt.3190140406 （英语）.

[1]

[2]

[註 1]

[註 3]

[3]

[註 2]

[註 4]

[4]

[註 5]

[註 6]

[5]

[6]

[7]

[註 7]

[8]

[9]

[註 8]

[10]

[11]

[12]

[13]

[註 9]