良擬序

一種預序,其中無窮序列必有先後兩項遞增

數學分支序理論中,良擬序良預序(英語:well-quasi-ordering,簡寫作wqo[1]WQO[2])是特殊的擬序[註 1],其元素的任意無窮序列中,必有先後兩項遞增,即存在使

動機

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

冪集運算為例。給定集合 上的擬序 ,可以定義冪集 上的擬序 ,使 當且僅當對 的每個元素,皆可在 中找到元素大於等於該元素。可以證明 不必良基,但若原擬序為良擬序,則冪集的擬序確實良基。[3]:116

定義

集合 上的良擬序well-quasi-ordering)是一種預序關係(即滿足自反性 遞移性 的的二元關係 ),使得 中任意無窮序列 ,皆有先後兩項  )遞增。若有此種良擬序,則 本身稱為良擬序集well-quasi-ordered set),簡寫為wqo[1]:210–211

良偏序well-partial-ordering)既是良擬序又是偏序,即除前述條件外,尚具反對稱性 

良擬序有其他等價定義,如將條件改為既不含無窮嚴格遞減序列 [註 2],又不含任意兩項不可比的無窮序列。換言之,擬序 為良擬序當且僅當 良基,且不含無窮反鏈。(與§ 無窮遞增子序列拉姆齊論證相似。)[1]:211

性質

  • 給定擬序 ,在冪集上有另一擬序 ,其中 。此關係為良基當且僅當 本身是wqo[3]:116
  • 給定良擬序 ,若有一列子集 ,其中每個子集皆向上封閉[註 4],則該序列終必恆定,即自某個 起,以後各項 。假若不然,則對每個 ,存在 使 非空,從中選一個元素,如此可得某個無窮序列,其無遞增的兩項。
  • 給定良擬序  的任何子集 關於 僅得有限多個極小元,否則該些極小元組成無窮反鏈。

無窮遞增子序列

 wqo,則任意無窮序列 ,皆有無窮上升子序列 (各下標 )。此種子序列或稱為「完美」(perfect)。[4]:245可用拉姆齊證法[註 5]:給定序列 ,考慮全部 中,何者使 右邊沒有任何 滿足 。記此種 的集合為 。若 無窮,則以 為下標集的子序列將不具遞增的兩項,與 wqo的假設抵觸。所以, 為有限集。衹要 大於 中所有元素,則 不屬 ,故有某個 使 ,如此可逐項延伸,得到無窮遞增子序列。

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

 
圖一:整數的平常順序
 
圖二:自然數按整除序的哈斯圖
 
圖三:格網 逐分量排序的哈斯圖
  •  ,自然數集配備平常的大小序,是良偏序,乃至良序。不過,若允許負數,換成整數集的大小序 ,則並非良擬序,因為此大小關係並非良基:負數組成無遞增兩項的序列。(圖一)
  •  ,自然數集按整除序,不是良擬序:質數兩兩不可比較,組成無窮反鏈。(圖二)
  •  ,自然數 元組的集合逐分量排序英語product order[註 6],是良偏序。此為迪克遜引理英語Dickson's lemma[5](圖三)。更一般地,若 為良擬序,則對任意正整數 積序英語product order 亦是良擬序。
  •  為有限集,且至少有兩個元素。克萊尼星號 是字母取自 的全體有限字串之集。按字典序 不是良擬序,因為有無窮遞降序列 。同樣, 關於前綴關係亦非良擬序,因為前述序列在該偏序下是無窮反鏈。然而, 倘按子序列關係排序,則是良偏序。[6](在 衹有一個元素的退化情況,此三種偏序完全一樣。)
  • 推而廣之,以 為字母集的有限串集 ,按「嵌入」排序,如此組成良擬序當且僅當 本身是良擬序,此結論稱為希格曼引理英語Higman's lemma[7]。其中所謂字串 可以嵌入到 ,意思是 中有與 等長的子序列,逐項大於等於 。若取子母集為無序集 ,則字串 當且僅當  的子序列,退化成前款情況。
  • 相反,良擬序 上的無窮序列集,記為 ,按嵌入序,一般不為良擬序。換言之,希格曼引理不適用於無窮序列。數學家引入優擬序英語Better-quasi-ordering,以期望值推廣希格曼引理。
  • wqo  之元素標記頂點的有限樹全體,按嵌入排序,也是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
  • 對每個正整數 樹深英語tree-depth至多為 的圖,按導出子圖序,組成良擬序集。亦可同上考慮以良擬序 標記其頂點,並要求該導出子圖的嵌入映射,使每個頂點的像的標記皆大於等於原標記,仍得良擬序。[12]此外,補可約圖英語cograph按導出子圖序,構成良擬序。[13]

與良偏序的關聯

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

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

  1. ^ 擬序(quasi-ordering)為預序(preorder)的別名。
  2. ^ 2.0 2.1    
  3. ^ 此處有濫用術語,稱擬序 良基實際是說嚴格序 [註 2]為良基。
  4. ^ 子集 向上封閉,意思是 
  5. ^ 拉姆齊定理斷言,無窮個頂點的圖中,每邊染紅藍兩色之一,則必有同色無窮階完全圖。此處若  則邊 染紅,否則染藍。Wqo條件即無紅色無窮階完全圖,故必有藍色無窮階完全圖,即遞增子序列。
  6. ^  是逐個分量有 
  7. ^ 拓撲圖子式英語topological minor關係。
  8. ^ 沒有多於一個元素的稠密子序。
  9. ^ 兩元素 等價定義為 

參考文獻

  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) (英語). 
  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. 
  3. ^ 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. ^ 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) (英語). 
  5. ^ 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 (英語). 
  6. ^ 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頁。
  7. ^ 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 (英語). 
  8. ^ 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 (英語). 
  9. ^ 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 (英語). 
  10. ^ Laver, Richard. On Fraïssé's Order Type Conjecture [論弗拉伊塞序類猜想]. Annals of Mathematics, Second Series. 1971-01, 93 (1): 89–111 (英語). 
  11. ^ Ruškuc, Nik. Well quasi-order in combinatorics and algebra [組合與代數之良擬序] (PDF). 2015 [2021-12-24]. (原始內容存檔 (PDF)於2021-12-24) (英語). 
  12. ^ 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 (英語). 
  13. ^ Damaschke, Peter. Induced subgraphs and well-quasi-ordering [導出子圖與良擬序]. Journal of Graph Theory. 1990, 14 (4): 427–435. MR 1067237. doi:10.1002/jgt.3190140406 (英語).