良擬序

數學分支序理論中，良擬序或良預序（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的條件等價，亦可作為另一種定義。

## 例

- $(\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]$不同構，但可互相嵌入，所以在對應偏序中屬同一等價類，托馬斯·福斯特 (數學家)稱該等價類「似乎不是很有啓發性」，而且，全體偏序集按包含關係組成的偏序類，雖然鏈完備，但並不完備序，若改為考慮全體擬序集則不會有此問題。