良拟序

数学分支序理论中,良拟序良预序(英语: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 (英语). 
  • 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  (英语).