良拟序

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

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

动机

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

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

定义

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

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

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

性质

• 给定拟序${\displaystyle (X,\leq )}$，在幂集上有另一拟序${\displaystyle ({\mathcal {P}}(X),\leq ^{+})}$，其中${\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b}$。此关系为良基当且仅当${\displaystyle (X,\leq )}$本身是wqo。^[3]:116
• 给定良拟序${\displaystyle (X,\leq )}$，若有一列子集${\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X}$，其中每个子集皆向上封闭^{[注 4]}，则该序列终必恒定，即自某个${\displaystyle n\in \mathbb {N} }$起，以后各项${\displaystyle S_{n}=S_{n+1}=\cdots }$。假若不然，则对每个${\displaystyle i\in \mathbb {N} }$，存在${\displaystyle \exists j>i}$使${\displaystyle S_{j}\setminus S_{i}}$非空，从中选一个元素，如此可得某个无穷序列，其无递增的两项。
• 给定良拟序${\displaystyle (X,\leq )}$，${\displaystyle X}$的任何子集${\displaystyle S}$关于${\displaystyle \leq }$仅得有限多个极小元，否则该些极小元组成无穷反链。

无穷递增子序列

若${\displaystyle (X,\leq )}$为wqo，则任意无穷序列${\displaystyle x_{0},x_{1},x_{2},\ldots }$，皆有无穷上升子序列${\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots }$（各下标${\displaystyle n_{0}<n_{1}<n_{2}<\cdots }$）。此种子序列或称为“完美”（perfect）。^[4]:245可用拉姆齐证法^{[注 5]}：给定序列${\displaystyle (x_{i})_{i}}$，考虑全部${\displaystyle i}$中，何者使${\displaystyle x_{i}}$右边没有任何${\displaystyle j>i}$满足${\displaystyle x_{j}\geq x_{i}}$。记此种${\displaystyle i}$的集合为${\displaystyle I}$。若${\displaystyle I}$无穷，则以${\displaystyle I}$为下标集的子序列将不具递增的两项，与${\displaystyle X}$为wqo的假设抵触。所以，${\displaystyle I}$为有限集。只要${\displaystyle n}$大于${\displaystyle I}$中所有元素，则${\displaystyle n}$不属${\displaystyle I}$，故有某个${\displaystyle m>n}$使${\displaystyle x_{m}\geq x_{n}}$，如此可逐项延伸，得到无穷递增子序列。

“任意序列皆有无穷上升子列”与wqo的条件等价，亦可作为另一种定义。^[4]:245

例

图一：整数的平常顺序

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

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

• ${\displaystyle (\mathbb {N} ,\leq )}$，自然数集配备平常的大小序，是良偏序，乃至良序。不过，若允许负数，换成整数集的大小序${\displaystyle (\mathbb {Z} ,\leq )}$，则并非良拟序，因为此大小关系并非良基：负数组成无递增两项的序列。（图一）
• ${\displaystyle (\mathbb {N} ,|)}$，自然数集按整除序，不是良拟序：素数两两不可比较，组成无穷反链。（图二）
• ${\displaystyle (\mathbb {N} ^{k},\leq )}$，自然数${\displaystyle k}$元组的集合逐分量排序（英语：product order）^{[注 6]}，是良偏序。此为迪克逊引理（英语：Dickson's lemma）^[5]（图三）。更一般地，若${\displaystyle (X,\leq )}$为良拟序，则对任意正整数${\displaystyle k}$，积序（英语：product order）${\displaystyle (X^{k},\leq ^{k})}$亦是良拟序。
• 设${\displaystyle X}$为有限集，且至少有两个元素。克莱尼星号${\displaystyle X^{*}}$是字母取自${\displaystyle X}$的全体有限字串之集。按字典序，${\displaystyle X^{*}}$不是良拟序，因为有无穷递降序列${\displaystyle b,ab,aab,aaab,\ldots }$。同样，${\displaystyle X^{*}}$关于前缀关系亦非良拟序，因为前述序列在该偏序下是无穷反链。然而，${\displaystyle X^{*}}$倘按子序列关系排序，则是良偏序。^[6]（在${\displaystyle X}$只有一个元素的退化情况，此三种偏序完全一样。）
• 推而广之，以${\displaystyle (X,\leq )}$为字母集的有限串集${\displaystyle (X^{*},\leq )}$，按“嵌入”排序，如此组成良拟序当且仅当${\displaystyle (X,\leq )}$本身是良拟序，此结论称为希格曼引理（英语：Higman's lemma）^[7]。其中所谓字串${\displaystyle u}$可以嵌入到${\displaystyle v}$，意思是${\displaystyle v}$中有与${\displaystyle u}$等长的子序列，逐项大于等于${\displaystyle u}$。若取子母集为无序集${\displaystyle (X,=)}$，则字串${\displaystyle u\leq v}$当且仅当${\displaystyle u}$是${\displaystyle v}$的子序列，退化成前款情况。
• 相反，良拟序${\displaystyle (X,\leq )}$上的无穷序列集，记为${\displaystyle (X^{\omega },\leq )}$，按嵌入序，一般不为良拟序。换言之，希格曼引理不适用于无穷序列。数学家引入优拟序（英语：Better-quasi-ordering），以期望推广希格曼引理。
• 以wqo ${\displaystyle (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））
• 对每个正整数${\displaystyle t}$，树深（英语：tree-depth）至多为${\displaystyle t}$的图，按导出子图序，组成良拟序集。亦可同上考虑以良拟序${\displaystyle (X,\leq )}$标记其顶点，并要求该导出子图的嵌入映射，使每个顶点的像的标记皆大于等于原标记，仍得良拟序。^[12]此外，补可约图（英语：cograph）按导出子图序，构成良拟序。^[13]

与良偏序的关联

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

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