Wqo

數學分支序理論中，**良擬序**或**良預序**（英語：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} ,\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  （英語）.