以wqo之元素標記頂點的有限樹全體,按嵌入排序,也是wqo,即克魯斯克爾樹定理(英语:Kruskal's tree theorem)[1]。此處的樹有選定根節點,而嵌入的要求有三:某節點的子節點要映到該節點之像的後嗣;同節點的不同子節點,要映到該節點之像的不同子分支上;每個節點處的標記,小於等於其像的標記。
無窮樹之間的嵌入關係[註 7]是wqo,由克里斯平·納許-威廉斯(英语:Crispin St. J. A. Nash-Williams)所證。[8][9]
^ 1.01.11.21.3Kruskal, 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.02.1Milner, 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.
^ 4.04.14.2Harzheim, 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(英语).
十月 04, 2023
良擬序, 良预序, 重定向至此, 关于等價類組成良序的序結構, 请见, 預良序, 英语, prewellordering, 数学分支序理论中, 或良預序, 英語, well, quasi, ordering, 簡寫作wqo, 或wqo, 是特殊的擬序, 其元素的任意无穷序列x, displaystyle, ldots, 必有先後兩項遞增, 即存在i, displaystyle, 使x, displaystyle, 目录, 動機, 定義, 性質, 無窮遞增子序列, 與良偏序的關聯, 參考文獻動機, 编辑良基歸納法可用. 良预序 重定向至此 关于等價類組成良序的序結構 请见 預良序 英语 prewellordering 数学分支序理论中 良擬序或良預序 英語 well quasi ordering 簡寫作wqo 1 或WQO 2 是特殊的擬序 註 1 其元素的任意无穷序列x 0 x 1 x 2 displaystyle x 0 x 1 x 2 ldots 中 必有先後兩項遞增 即存在i lt j displaystyle i lt j 使x i x j displaystyle x i leq x j 目录 1 動機 2 定義 3 性質 3 1 無窮遞增子序列 4 例 5 與良偏序的關聯 6 註 7 參考文獻動機 编辑良基歸納法可用於任何良基關係上 用以證明某集的全部元素皆具某性質 所以 或許會考慮某擬序是否良基 註 3 不過 良基擬序的類 對某些運算不封閉 即由某良基擬序出發 經若干運算 構造而成的新擬序 不一定良基 欲使新擬序仍為良基 原擬序需追加若干限制 以冪集運算為例 給定集合X displaystyle X nbsp 上的擬序 displaystyle leq nbsp 可以定義冪集P X displaystyle mathcal P X nbsp 上的擬序 displaystyle leq nbsp 使A B displaystyle A leq B nbsp 當且僅當對A displaystyle A nbsp 的每個元素 皆可在B displaystyle B nbsp 中找到元素大於等於該元素 可以證明 displaystyle leq nbsp 不必良基 但若原擬序為良擬序 則冪集的擬序確實良基 3 116定義 编辑集合X displaystyle X nbsp 上的良擬序 well quasi ordering 是一種预序关系 即滿足自反性x x displaystyle x leq x nbsp 传递性x y y z x z displaystyle x leq y wedge y leq z implies x leq z nbsp 的的二元關係 displaystyle leq nbsp 使得X displaystyle X nbsp 中任意无穷序列x 0 x 1 x 2 displaystyle x 0 x 1 x 2 ldots nbsp 皆有先後兩項x i x j displaystyle x i leq x j nbsp i lt j displaystyle i lt j nbsp 遞增 若有此種良擬序 則X displaystyle X nbsp 本身稱為良擬序集 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 nbsp 良擬序有其他等價定義 如將條件改為既不含無窮嚴格遞減序列x 0 gt x 1 gt x 2 gt displaystyle x 0 gt x 1 gt x 2 gt cdots nbsp 註 2 又不含任意兩項不可比的無窮序列 換言之 擬序 X displaystyle X leq nbsp 為良擬序當且僅當 X lt displaystyle X lt nbsp 良基 且不含無窮反链 與 無窮遞增子序列的拉姆齊論證相似 1 211性質 编辑給定擬序 X displaystyle X leq nbsp 在冪集上有另一擬序 P X displaystyle mathcal P X leq nbsp 其中A B a A b B a b displaystyle A leq B iff forall a in A exists b in B a leq b nbsp 此關係為良基當且僅當 X displaystyle X leq nbsp 本身是wqo 3 116 給定良擬序 X displaystyle X leq nbsp 若有一列子集S 0 S 1 X displaystyle S 0 subseteq S 1 subseteq cdots subseteq X nbsp 其中每個子集皆向上封閉 註 4 則該序列終必恆定 即自某個n N displaystyle n in mathbb N nbsp 起 以後各項S n S n 1 displaystyle S n S n 1 cdots nbsp 假若不然 則對每個i N displaystyle i in mathbb N nbsp 存在 j gt i displaystyle exists j gt i nbsp 使S j S i displaystyle S j setminus S i nbsp 非空 從中選一個元素 如此可得某個無窮序列 其無遞增的兩項 給定良擬序 X displaystyle X leq nbsp X displaystyle X nbsp 的任何子集S displaystyle S nbsp 關於 displaystyle leq nbsp 僅得有限多個極小元 否則該些極小元組成無窮反鏈 無窮遞增子序列 编辑 若 X displaystyle X leq nbsp 為wqo 則任意無窮序列x 0 x 1 x 2 displaystyle x 0 x 1 x 2 ldots nbsp 皆有無窮上升子序列x n 0 x n 1 x n 2 displaystyle x n 0 leq x n 1 leq x n 2 leq cdots nbsp 各下標n 0 lt n 1 lt n 2 lt displaystyle n 0 lt n 1 lt n 2 lt cdots nbsp 此種子序列或稱為 完美 perfect 4 245可用拉姆齊證法 註 5 給定序列 x i i displaystyle x i i nbsp 考慮全部i displaystyle i nbsp 中 何者使x i displaystyle x i nbsp 右邊沒有任何j gt i displaystyle j gt i nbsp 滿足x j x i displaystyle x j geq x i nbsp 記此種i displaystyle i nbsp 的集合為I displaystyle I nbsp 若I displaystyle I nbsp 無窮 則以I displaystyle I nbsp 為下標集的子序列將不具遞增的兩項 與X displaystyle X nbsp 為wqo 的假設抵觸 所以 I displaystyle I nbsp 為有限集 衹要n displaystyle n nbsp 大於I displaystyle I nbsp 中所有元素 則n displaystyle n nbsp 不屬I displaystyle I nbsp 故有某個m gt n displaystyle m gt n nbsp 使x m x n displaystyle x m geq x n nbsp 如此可逐項延伸 得到無窮遞增子序列 任意序列皆有無窮上升子列 與wqo 的條件等價 亦可作為另一種定義 4 245例 编辑 nbsp 圖一 整數的平常順序 nbsp 圖二 自然數按整除序的哈斯圖 nbsp 圖三 格網N 2 displaystyle mathbb N 2 nbsp 逐分量排序的哈斯圖 N displaystyle mathbb N leq nbsp 自然數集配備平常的大小序 是良偏序 乃至良序 不過 若允許負數 換成整數集的大小序 Z displaystyle mathbb Z leq nbsp 則並非良擬序 因為此大小關係並非良基 負數組成無遞增兩項的序列 圖一 N displaystyle mathbb N nbsp 自然數集按整除序 不是良擬序 質數兩兩不可比較 組成無窮反鏈 圖二 N k displaystyle mathbb N k leq nbsp 自然數k displaystyle k nbsp 元組的集合逐分量排序 英语 product order 註 6 是良偏序 此為迪克遜引理 英语 Dickson s lemma 5 圖三 更一般地 若 X displaystyle X leq nbsp 為良擬序 則對任意正整數k displaystyle k nbsp 積序 英语 product order X k k displaystyle X k leq k nbsp 亦是良擬序 設X displaystyle X nbsp 為有限集 且至少有兩個元素 克莱尼星号X displaystyle X nbsp 是字母取自X displaystyle X nbsp 的全體有限字串之集 按字典序 X displaystyle X nbsp 不是良擬序 因為有無窮遞降序列b a b a a b a a a b displaystyle b ab aab aaab ldots nbsp 同樣 X displaystyle X nbsp 關於前綴關係亦非良擬序 因為前述序列在該偏序下是無窮反鏈 然而 X displaystyle X nbsp 倘按子序列關係排序 則是良偏序 6 在X displaystyle X nbsp 衹有一個元素的退化情況 此三種偏序完全一樣 推而廣之 以 X displaystyle X leq nbsp 為字母集的有限串集 X displaystyle X leq nbsp 按 嵌入 排序 如此組成良擬序當且僅當 X displaystyle X leq nbsp 本身是良擬序 此結論稱為希格曼引理 英语 Higman s lemma 7 其中所謂字串u displaystyle u nbsp 可以嵌入到v displaystyle v nbsp 意思是v displaystyle v nbsp 中有與u displaystyle u nbsp 等長的子序列 逐項大於等於u displaystyle u nbsp 若取子母集為無序集 X displaystyle X nbsp 則字串u v displaystyle u leq v nbsp 當且僅當u displaystyle u nbsp 是v displaystyle v nbsp 的子序列 退化成前款情況 相反 良擬序 X displaystyle X leq nbsp 上的無窮序列集 記為 X w displaystyle X omega leq nbsp 按嵌入序 一般不為良擬序 換言之 希格曼引理不適用於無窮序列 數學家引入優擬序 英语 Better quasi ordering 以期望推廣希格曼引理 以wqo X displaystyle X leq nbsp 之元素標記頂點的有限樹全體 按嵌入排序 也是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 displaystyle t nbsp 樹深 英语 tree depth 至多為t displaystyle t nbsp 的圖 按导出子图序 組成良擬序集 亦可同上考慮以良擬序 X displaystyle X leq nbsp 標記其頂點 並要求該導出子圖的嵌入映射 使每個頂點的像的標記皆大於等於原標記 仍得良擬序 12 此外 補可約圖 英语 cograph 按導出子圖序 構成良擬序 13 與良偏序的關聯 编辑字面上 良擬序較良偏序廣義 但基於以下觀察 兩者實際分別不大 4 250一方面 wpo 必為wqo 另一方面 若有某wqo 則其各等價類 註 9 組成wpo 舉例整數集Z displaystyle mathbb Z nbsp 的整除序是擬序 Z displaystyle mathbb Z nbsp 但不是良擬序 其等價類形如 m displaystyle pm m nbsp 所以等價類組成的偏序同構於 N displaystyle mathbb N nbsp 據米爾納 2 考慮擬序 並不比偏序更為概括 僅是因為較方便 又例如 在全序類的嵌入擬序中 開區間 0 1 displaystyle 0 1 nbsp 與閉區間 0 1 displaystyle 0 1 nbsp 不同構 但可互相嵌入 所以在對應偏序中屬同一等價類 托馬斯 福斯特 英语 Thomas Forster mathematician 稱該等價類 似乎不是很有啓發性 而且 全體偏序集按包含關係組成的偏序類 雖然鏈完備 英语 Chain complete 但並不完備 英语 Completeness order theory 若改為考慮全體擬序集則不會有此問題 3 112註 编辑 擬序 quasi ordering 為預序 preorder 的別名 2 0 2 1 x lt y displaystyle x lt y nbsp 謂x y displaystyle x leq y nbsp 且y x displaystyle y nleq x nbsp 此處有濫用術語 稱擬序 X displaystyle X leq nbsp 良基實際是說嚴格序 X lt displaystyle X lt nbsp 註 2 為良基 子集S X displaystyle S subseteq X nbsp 向上封閉 意思是 x y X x y x S y S displaystyle forall x y in X x leq y wedge x in S Rightarrow y in S nbsp 拉姆齊定理斷言 無窮個頂點的圖中 每邊染紅藍兩色之一 則必有同色無窮階完全圖 此處若i lt j displaystyle i lt j nbsp 且x j x i displaystyle x j geq x i nbsp 則邊i j displaystyle ij nbsp 染紅 否則染藍 Wqo 條件即無紅色無窮階完全圖 故必有藍色無窮階完全圖 即遞增子序列 x y displaystyle boldsymbol x leq boldsymbol y nbsp 是逐個分量有x i y i displaystyle x i leq y i nbsp 即拓撲圖子式 英语 topological minor 關係 沒有多於一個元素的稠密子序 兩元素x y displaystyle x y nbsp 等價定義為x y y x displaystyle x leq y land y leq x nbsp 參考文獻 编辑 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 nbsp 英语 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 英语 Kuhn 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 Fraisse s Order Type Conjecture 論弗拉伊塞序類猜想 Annals of Mathematics Second Series 1971 01 93 1 89 111 英语 Ruskuc Nik Well quasi order in combinatorics and algebra 組合與代數之良擬序 PDF 2015 2021 12 24 原始内容存档 PDF 于2021 12 24 英语 Nesetril 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 nbsp 英语 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 Go A survey of some results in proof theory 克魯斯克爾定與與序數Go有何特別 證明論若干結果的綜述 Annals of Pure and Applied Logic 1991 53 3 199 260 doi 10 1016 0168 0072 91 90022 E nbsp 英语 取自 https zh wikipedia org w index php title 良擬序 amp oldid 70679087, 维基百科,wiki,书籍,书籍,图书馆,