良拟序

数学分支序理论中，良拟序或良预序（well-quasi-ordering，简写作wqo或WQO）是特殊的拟序拟序（quasi-ordering）为预序（preorder）的别名。其元素的任意无穷序列$x_0, x_1, x_2, \ldots$中，必有先后两项递增，即存在$i < j$使$x_i\le x_j$。

## 动机

良基归纳法可用于任何良基关系上，用以证明某集的全部元素皆具某性质。所以，或许会考虑某拟序是否良基此处有滥用术语，称拟序$(X, \le)$良基实际是说严格序$(X, <)$"strict"为良基。不过，良基拟序的类，对某些运算不封闭，即由某良基拟序出发，经若干运算，构造而成的新拟序，不一定良基。欲使新拟序仍为良基，原拟序需追加若干限制。

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

## 定义

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

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

良拟序有其他等价定义，如将条件改为既不含无穷严格递减序列$x_0> x_1> x_2> \cdots$ $x < y$谓$x\le y$且$y \nleq x$。又不含任意两项不可比的无穷序列。换言之，拟序$(X, \le )$为良拟序当且仅当$(X, <)$良基，且不含无穷反链。（与#无穷递增子序列的拉姆齐论证相似。）

## 性质

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

### 无穷递增子序列

若$(X, \le)$为wqo，则任意无穷序列$x_0, x_1, x_2, \ldots$，皆有无穷上升子序列$x_{n_0} \le x_{n_1}\le x_{n_2} \le \cdots$（各下标$n_0< n_1< n_2< \cdots$）。此种子序列或称为“完美”（perfect）。可用拉姆齐证法拉姆齐定理断言，无穷个顶点的图中，每边染红蓝两色之一，则必有同色无穷阶完全图。此处若$i < j$且$x_j \ge x_i$则边$ij$染红，否则染蓝。Wqo条件即无红色无穷阶完全图，故必有蓝色无穷阶完全图，即递增子序列。给定序列$(x_i)_i$，考虑全部$i$中，何者使$x_i$右边没有任何$j > i$满足$x_j \ge x_i$。记此种$i$的集合为$I$。若$I$无穷，则以$I$为下标集的子序列将不具递增的两项，与$X$为wqo的假设抵触。所以，$I$为有限集。只要$n$大于$I$中所有元素，则$n$不属$I$，故有某个$m > n$使$x_m \ge x_n$，如此可逐项延伸，得到无穷递增子序列。

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

## 例

<image>

<image>

<image>

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

## 与良偏序的关联

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

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