良拟序

  “良预序”重定向至此。关于等价类组成良序的序结构，请见“预良序”。

数学分支序理论中，良拟序或良预序（英语：well-quasi-ordering，简写作wqo或WQO）是特殊的拟序，其元素的任意无穷序列$x_{0},x_{1},x_{2},\ldots$中，必有先后两项递增，即存在$i<j$使$x_{i}\leq x_{j}$。

动机

良基归纳法可用于任何良基关系上，用以证明某集的全部元素皆具某性质。所以，或许会考虑某拟序是否良基。不过，良基拟序的类，对某些运算不封闭，即由某良基拟序出发，经若干运算，构造而成的新拟序，不一定良基。欲使新拟序仍为良基，原拟序需追加若干限制。

以幂集运算为例。给定集合$X$上的拟序$\leq$，可以定义幂集${\mathcal {P}}(X)$上的拟序$\leq ^{+}$，使$A\leq ^{+}B$当且仅当对$A$的每个元素，皆可在$B$中找到元素大于等于该元素。可以证明$\leq ^{+}$不必良基，但若原拟序为良拟序，则幂集的拟序确实良基。

定义

集合$X$上的良拟序（well-quasi-ordering）是一种预序关系（即满足自反性$x\leq x$、传递性$x\leq y\wedge y\leq z\implies x\leq z$的的二元关系$\leq$），使得$X$中任意无穷序列$x_{0},x_{1},x_{2},\ldots$，皆有先后两项$x_{i}\leq x_{j}$（$i<j$）递增。若有此种良拟序，则$X$本身称为良拟序集（well-quasi-ordered set），简写为wqo。

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

良拟序有其他等价定义，如将条件改为既不含无穷严格递减序列$x_{0}>x_{1}>x_{2}>\cdots$，又不含任意两项不可比的无穷序列。换言之，拟序$(X,\leq )$为良拟序当且仅当$(X,<)$良基，且不含无穷反链。（与§ 无穷递增子序列的拉姆齐论证相似。）

性质

• 给定拟序$(X,\leq )$，在幂集上有另一拟序$({\mathcal {P}}(X),\leq ^{+})$，其中$A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b$。此关系为良基当且仅当$(X,\leq )$本身是wqo。
• 给定良拟序$(X,\leq )$，若有一列子集$S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X$，其中每个子集皆向上封闭，则该序列终必恒定，即自某个$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）。可用拉姆齐证法：给定序列$(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的条件等价，亦可作为另一种定义。

例

图一：整数的平常顺序

图二：自然数按整除序的哈斯图

图三：格网$\mathbb {N} ^{2}$逐分量排序的哈斯图

• $(\mathbb {N} ,\leq )$，自然数集配备平常的大小序，是良偏序，乃至良序。不过，若允许负数，换成整数集的大小序$(\mathbb {Z} ,\leq )$，则并非良拟序，因为此大小关系并非良基：负数组成无递增两项的序列。（图一）
• $(\mathbb {N} ,|)$，自然数集按整除序，不是良拟序：素数两两不可比较，组成无穷反链。（图二）
• $(\mathbb {N} ^{k},\leq )$，自然数$k$元组的集合逐分量排序，是良偏序。此为迪克逊引理（图三）。更一般地，若$(X,\leq )$为良拟序，则对任意正整数$k$，积序$(X^{k},\leq ^{k})$亦是良拟序。
• 设$X$为有限集，且至少有两个元素。克莱尼星号$X^{*}$是字母取自$X$的全体有限字串之集。按字典序，$X^{*}$不是良拟序，因为有无穷递降序列$b,ab,aab,aaab,\ldots$。同样，$X^{*}$关于前缀关系亦非良拟序，因为前述序列在该偏序下是无穷反链。然而，$X^{*}$倘按子序列关系排序，则是良偏序。（在$X$只有一个元素的退化情况，此三种偏序完全一样。）
• 推而广之，以$(X,\leq )$为字母集的有限串集$(X^{*},\leq )$，按“嵌入”排序，如此组成良拟序当且仅当$(X,\leq )$本身是良拟序，此结论称为希格曼引理。其中所谓字串$u$可以嵌入到$v$，意思是$v$中有与$u$等长的子序列，逐项大于等于$u$。若取子母集为无序集$(X,=)$，则字串$u\leq v$当且仅当$u$是$v$的子序列，退化成前款情况。
• 相反，良拟序$(X,\leq )$上的无穷序列集，记为$(X^{\omega },\leq )$，按嵌入序，一般不为良拟序。换言之，希格曼引理不适用于无穷序列。数学家引入优拟序，以期望推广希格曼引理。
• 以wqo $(X,\leq )$之元素标记顶点的有限树全体，按嵌入排序，也是wqo，即克鲁斯克尔树定理。此处的树有选定根节点，而嵌入的要求有三：某节点的子节点要映到该节点之像的后嗣；同节点的不同子节点，要映到该节点之像的不同子分支上；每个节点处的标记，小于等于其像的标记。
• 无穷树之间的嵌入关系是wqo，由克里斯平·纳许-威廉斯所证。
• 可数全序类之间的嵌入关系是良拟序，同样散布全序类之间亦然。（莱弗定理）
• 可数布尔代数的嵌入序是良拟序，由莱弗定理证得。
• 有限图按图子式序组成良拟序集。（罗伯逊-西摩定理）
• 对每个正整数$t$，树深至多为$t$的图，按导出子图序，组成良拟序集。亦可同上考虑以良拟序$(X,\leq )$标记其顶点，并要求该导出子图的嵌入映射，使每个顶点的像的标记皆大于等于原标记，仍得良拟序。此外，补可约图按导出子图序，构成良拟序。

与良偏序的关联

字面上，良拟序较良偏序广义，但基于以下观察，两者实际分别不大：一方面，wpo必为wqo。另一方面，若有某wqo，则其各等价类组成wpo。举例整数集$\mathbb {Z}$的整除序是拟序$(\mathbb {Z} ,|)$（但不是良拟序），其等价类形如$\{\pm m\}$，所以等价类组成的偏序同构于$(\mathbb {N} ,|)$。

据米尔纳，“考虑拟序，并不比偏序更为概括……仅是因为较方便。”又例如，在全序类的嵌入拟序中，开区间$(0,1)$与闭区间$[0,1]$不同构，但可互相嵌入，所以在对应偏序中属同一等价类，托马斯·福斯特称该等价类“似乎不是很有启发性”，而且，全体偏序集按包含关系组成的偏序类，虽然链完备，但并不完备，若改为考虑全体拟序集则不会有此问题。

参考文献

• Kruskal, J. B. The theory of well-quasi-ordering: A frequently discovered concept [良拟序论：常发现的概念]. 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  （英语）.