良拟序

良基归纳法可用于任何良基关系上，用以证明某集的全部元素皆具某性质。所以，或许会考虑某拟序是否良基^{[注 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} ,\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

• 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   （英语）.