Well-quasi-ordering

In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set ${\displaystyle X}$ is a quasi-ordering of ${\displaystyle X}$ for which every infinite sequence of elements ${\displaystyle x_{0},x_{1},x_{2},\ldots }$ from ${\displaystyle X}$ contains an increasing pair ${\displaystyle x_{i}\leq x_{j}}$ with ${\displaystyle i<j.}$

Transitive binary relations v t e
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all ${\displaystyle a,b}$ and ${\displaystyle S\neq \varnothing$ :} ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation ${\displaystyle R}$ be transitive: for all ${\displaystyle a,b,c,}$ if ${\displaystyle aRb}$ and ${\displaystyle bRc}$ then ${\displaystyle aRc.}$ A term's definition may require additional properties that are not listed in this table.

Motivation

Well-founded induction can be used on any set with a well-founded relation, thus one is interested in when a quasi-order is well-founded. (Here, by abuse of terminology, a quasiorder ${\displaystyle \leq }$ is said to be well-founded if the corresponding strict order ${\displaystyle x\leq y\land y\nleq x}$ is a well-founded relation.) However the class of well-founded quasiorders is not closed under certain operations—that is, when a quasi-order is used to obtain a new quasi-order on a set of structures derived from our original set, this quasiorder is found to be not well-founded. By placing stronger restrictions on the original well-founded quasiordering one can hope to ensure that our derived quasiorderings are still well-founded.

An example of this is the power set operation. Given a quasiordering ${\displaystyle \leq }$ for a set ${\displaystyle X}$ one can define a quasiorder ${\displaystyle \leq ^{+}}$ on ${\displaystyle X}$'s power set ${\displaystyle P(X)}$ by setting ${\displaystyle A\leq ^{+}B}$ if and only if for each element of ${\displaystyle A}$ one can find some element of ${\displaystyle B}$ that is larger than it with respect to ${\displaystyle \leq }$. One can show that this quasiordering on ${\displaystyle P(X)}$ needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is.

Formal definition

A well-quasi-ordering on a set ${\displaystyle X}$ is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements ${\displaystyle x_{0},x_{1},x_{2},\ldots }$ from ${\displaystyle X}$ contains an increasing pair ${\displaystyle x_{i}\leq x_{j}}$ with ${\displaystyle i<j}$. The set ${\displaystyle X}$ is said to be well-quasi-ordered, or shortly wqo.

A well partial order, or a wpo, is a wqo that is a proper ordering relation, i.e., it is antisymmetric.

Among other ways of defining wqo's, one is to say that they are quasi-orderings which do not contain infinite strictly decreasing sequences (of the form ${\displaystyle x_{0}>x_{1}>x_{2}>\cdots }$) nor infinite sequences of pairwise incomparable elements. Hence a quasi-order (X, ≤) is wqo if and only if (X, <) is well-founded and has no infinite antichains.

Ordinal type

Let ${\displaystyle X}$ be well partially ordered. A (necessarily finite) sequence ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ of elements of ${\displaystyle X}$ that contains no pair ${\displaystyle x_{i}\leq x_{j}}$ with ${\displaystyle i<j}$ is usually called a bad sequence. The tree of bad sequences ${\displaystyle T_{X}}$ is the tree that contains a vertex for each bad sequence, and an edge joining each nonempty bad sequence ${\displaystyle (x_{1},\ldots ,x_{n-1},x_{n})}$ to its parent ${\displaystyle (x_{1},\ldots ,x_{n-1})}$. The root of ${\displaystyle T_{X}}$ corresponds to the empty sequence. Since ${\displaystyle X}$ contains no infinite bad sequence, the tree ${\displaystyle T_{X}}$ contains no infinite path starting at the root.^{[citation needed]} Therefore, each vertex ${\displaystyle v}$ of ${\displaystyle T_{X}}$ has an ordinal height ${\displaystyle o(v)}$, which is defined by transfinite induction as ${\displaystyle o(v)=\lim _{w\mathrm {\ child\ of\ } v}(o(w)+1)}$. The ordinal type of ${\displaystyle X}$, denoted ${\displaystyle o(X)}$, is the ordinal height of the root of ${\displaystyle T_{X}}$.

A linearization of ${\displaystyle X}$ is an extension of the partial order into a total order. It is easy to verify that ${\displaystyle o(X)}$ is an upper bound on the ordinal type of every linearization of ${\displaystyle X}$. De Jongh and Parikh^[1] proved that in fact there always exists a linearization of ${\displaystyle X}$ that achieves the maximal ordinal type ${\displaystyle o(X)}$.

Examples

Pic.1: Integer numbers with the usual order

Pic.2: Hasse diagram of the natural numbers ordered by divisibility

Pic.3: Hasse diagram of ${\displaystyle \mathbb {N} ^{2}}$ with componentwise order

• ${\displaystyle (\mathbb {N} ,\leq )}$, the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However, ${\displaystyle (\mathbb {Z} ,\leq )}$, the set of positive and negative integers, is not a well-quasi-order, because it is not well-founded (see Pic.1).
• ${\displaystyle (\mathbb {N} ,|)}$, the set of natural numbers ordered by divisibility, is not a well-quasi-order: the prime numbers are an infinite antichain (see Pic.2).
• ${\displaystyle (\mathbb {N} ^{k},\leq )}$, the set of vectors of ${\displaystyle k}$ natural numbers (where ${\displaystyle k}$ is finite) with component-wise ordering, is a well partial order (Dickson's lemma; see Pic.3). More generally, if ${\displaystyle (X,\leq )}$ is well-quasi-order, then ${\displaystyle (X^{k},\leq ^{k})}$ is also a well-quasi-order for all ${\displaystyle k}$.
• Let ${\displaystyle X}$ be an arbitrary finite set with at least two elements. The set ${\displaystyle X^{*}}$ of words over ${\displaystyle X}$ ordered lexicographically (as in a dictionary) is not a well-quasi-order because it contains the infinite decreasing sequence ${\displaystyle b,ab,aab,aaab,\ldots }$. Similarly, ${\displaystyle X^{*}}$ ordered by the prefix relation is not a well-quasi-order, because the previous sequence is an infinite antichain of this partial order. However, ${\displaystyle X^{*}}$ ordered by the subsequence relation is a well partial order.^[2] (If ${\displaystyle X}$ has only one element, these three partial orders are identical.)
• More generally, ${\displaystyle (X^{*},\leq )}$, the set of finite ${\displaystyle X}$-sequences ordered by embedding is a well-quasi-order if and only if ${\displaystyle (X,\leq )}$ is a well-quasi-order (Higman's lemma). Recall that one embeds a sequence ${\displaystyle u}$ into a sequence ${\displaystyle v}$ by finding a subsequence of ${\displaystyle v}$ that has the same length as ${\displaystyle u}$ and that dominates it term by term. When ${\displaystyle (X,=)}$ is an unordered set, ${\displaystyle u\leq v}$ if and only if ${\displaystyle u}$ is a subsequence of ${\displaystyle v}$.
• ${\displaystyle (X^{\omega },\leq )}$, the set of infinite sequences over a well-quasi-order ${\displaystyle (X,\leq )}$, ordered by embedding, is not a well-quasi-order in general. That is, Higman's lemma does not carry over to infinite sequences. Better-quasi-orderings have been introduced to generalize Higman's lemma to sequences of arbitrary lengths.
• Embedding between finite trees with nodes labeled by elements of a wqo ${\displaystyle (X,\leq )}$ is a wqo (Kruskal's tree theorem).
• Embedding between infinite trees with nodes labeled by elements of a wqo ${\displaystyle (X,\leq )}$ is a wqo (Nash-Williams' theorem).
• Embedding between countable scattered linear order types is a well-quasi-order (Laver's theorem).
• Embedding between countable boolean algebras is a well-quasi-order. This follows from Laver's theorem and a theorem of Ketonen.
• Finite graphs ordered by a notion of embedding called "graph minor" is a well-quasi-order (Robertson–Seymour theorem).
• Graphs of finite tree-depth ordered by the induced subgraph relation form a well-quasi-order,^[3] as do the cographs ordered by induced subgraphs.^[4]

Constructing new wpo's from given ones

Let ${\displaystyle X_{1}}$ and ${\displaystyle X_{2}}$ be two disjoint wpo sets. Let ${\displaystyle Y=X_{1}\cup X_{2}}$, and define a partial order on ${\displaystyle Y}$ by letting ${\displaystyle y_{1}\leq _{Y}y_{2}}$ if and only if ${\displaystyle y_{1},y_{2}\in X_{i}}$ for the same ${\displaystyle i\in \{1,2\}}$ and ${\displaystyle y_{1}\leq _{X_{i}}y_{2}}$. Then ${\displaystyle Y}$ is wpo, and ${\displaystyle o(Y)=o(X_{1})\oplus o(X_{2})}$, where ${\displaystyle \oplus }$ denotes natural sum of ordinals.^[1]

Given wpo sets ${\displaystyle X_{1}}$ and ${\displaystyle X_{2}}$, define a partial order on the Cartesian product ${\displaystyle Y=X_{1}\times X_{2}}$, by letting ${\displaystyle (a_{1},a_{2})\leq _{Y}(b_{1},b_{2})}$ if and only if ${\displaystyle a_{1}\leq _{X_{1}}b_{1}}$ and ${\displaystyle a_{2}\leq _{X_{2}}b_{2}}$. Then ${\displaystyle Y}$ is wpo (this is a generalization of Dickson's lemma), and ${\displaystyle o(Y)=o(X_{1})\otimes o(X_{2})}$, where ${\displaystyle \otimes }$ denotes natural product of ordinals.^[1]

Given a wpo set ${\displaystyle X}$, let ${\displaystyle X^{*}}$ be the set of finite sequences of elements of ${\displaystyle X}$, partially ordered by the subsequence relation. Meaning, let ${\displaystyle (x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})}$ if and only if there exist indices ${\displaystyle 1\leq i_{1}<\cdots <i_{n}\leq m}$ such that ${\displaystyle x_{j}\leq _{X}y_{i_{j}}}$ for each ${\displaystyle 1\leq j\leq n}$. By Higman's lemma, ${\displaystyle X^{*}}$ is wpo. The ordinal type of ${\displaystyle X^{*}}$ is^[1][5] $${\displaystyle o(X^{*})={\begin{cases}\omega ^{\omega ^{o(X)-1}},&o(X){\text{ finite}};\\\omega ^{\omega ^{o(X)+1}},&o(X)=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(X)}},&{\text{otherwise}}.\end{cases}}}$$

Given a wpo set ${\displaystyle X}$, let ${\displaystyle T(X)}$ be the set of all finite rooted trees whose vertices are labeled by elements of ${\displaystyle X}$. Partially order ${\displaystyle T(X)}$ by the tree embedding relation. By Kruskal's tree theorem, ${\displaystyle T(X)}$ is wpo. This result is nontrivial even for the case ${\displaystyle |X|=1}$ (which corresponds to unlabeled trees), in which case ${\displaystyle o(T(X))}$ equals the small Veblen ordinal. In general, for ${\displaystyle o(X)}$ countable, we have the upper bound ${\displaystyle o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))}$ in terms of the ${\displaystyle \vartheta }$ ordinal collapsing function. (The small Veblen ordinal equals ${\displaystyle \vartheta (\Omega ^{\omega })}$ in this ordinal notation.)^[6]

Wqo's versus well partial orders

In practice, the wqo's one manipulates are quite often not orderings (see examples above), and the theory is technically smoother^{[citation needed]} if we do not require antisymmetry, so it is built with wqo's as the basic notion. On the other hand, according to Milner 1985, no real gain in generality is obtained by considering quasi-orders rather than partial orders... it is simply more convenient to do so.

Observe that a wpo is a wqo, and that a wqo gives rise to a wpo between equivalence classes induced by the kernel of the wqo. For example, if we order ${\displaystyle \mathbb {Z} }$ by divisibility, we end up with ${\displaystyle n\equiv m}$ if and only if ${\displaystyle n=\pm m}$, so that ${\displaystyle (\mathbb {Z} ,|)\approx (\mathbb {N} ,|)}$.

Infinite increasing subsequences

If ${\displaystyle (X,\leq )}$ is wqo then every infinite sequence ${\displaystyle x_{0},x_{1},x_{2},\ldots ,}$ contains an infinite increasing subsequence ${\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots }$ (with ${\displaystyle n_{0}<n_{1}<n_{2}<\cdots }$). Such a subsequence is sometimes called perfect. This can be proved by a Ramsey argument: given some sequence ${\displaystyle (x_{i})_{i}}$, consider the set ${\displaystyle I}$ of indexes ${\displaystyle i}$ such that ${\displaystyle x_{i}}$ has no larger or equal ${\displaystyle x_{j}}$ to its right, i.e., with ${\displaystyle i<j}$. If ${\displaystyle I}$ is infinite, then the ${\displaystyle I}$-extracted subsequence contradicts the assumption that ${\displaystyle X}$ is wqo. So ${\displaystyle I}$ is finite, and any ${\displaystyle x_{n}}$ with ${\displaystyle n}$ larger than any index in ${\displaystyle I}$ can be used as the starting point of an infinite increasing subsequence.

The existence of such infinite increasing subsequences is sometimes taken as a definition for well-quasi-ordering, leading to an equivalent notion.

Properties of wqos

• Given a quasiordering ${\displaystyle (X,\leq )}$ the quasiordering ${\displaystyle (P(X),\leq ^{+})}$ defined by ${\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b}$ is well-founded if and only if ${\displaystyle (X,\leq )}$ is a wqo.^[7]
• A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by ${\displaystyle x\sim y\iff x\leq y\land y\leq x}$) has no infinite descending sequences or antichains. (This can be proved using a Ramsey argument as above.)
• Given a well-quasi-ordering ${\displaystyle (X,\leq )}$, any sequence of upward-closed subsets ${\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X}$ eventually stabilises (meaning there exists ${\displaystyle n\in \mathbb {N} }$ such that ${\displaystyle S_{n}=S_{n+1}=\cdots }$; a subset ${\displaystyle S\subseteq X}$ is called upward-closed if ${\displaystyle \forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S}$): assuming the contrary ${\displaystyle \forall i\in \mathbb {N} ,\exists j\in \mathbb {N} ,j>i,\exists x\in S_{j}\setminus S_{i}}$, a contradiction is reached by extracting an infinite non-ascending subsequence.
• Given a well-quasi-ordering ${\displaystyle (X,\leq )}$, any subset ${\displaystyle S}$ of ${\displaystyle X}$ has a finite number of minimal elements with respect to ${\displaystyle \leq }$, for otherwise the minimal elements of ${\displaystyle S}$ would constitute an infinite antichain.

See also

• Better-quasi-ordering – mathematical relationPages displaying wikidata descriptions as a fallback
• Prewellordering – Set theory concept
• Well-order – Class of mathematical orderings

Notes

^ Here x < y means: ${\displaystyle x\leq y}$ and ${\displaystyle x\neq y.}$

References

1. de Jongh, Dick H. G.; Parikh, Rohit (1977). "Well-partial orderings and hierarchies". Indagationes Mathematicae (Proceedings). 80 (3): 195–207. doi:10.1016/1385-7258(77)90067-1.
2. Gasarch, W. (1998), "A survey of recursive combinatorics", Handbook of Recursive Mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9, MR 1673598. See in particular page 1160.
3. Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Lemma 6.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 137, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
4. Damaschke, Peter (1990), "Induced subgraphs and well-quasi-ordering", Journal of Graph Theory, 14 (4): 427–435, doi:10.1002/jgt.3190140406, MR 1067237.
5. Schmidt, Diana (1979). Well-partial orderings and their maximal order types (Habilitationsschrift). Heidelberg. Republished in: Schmidt, Diana (2020). "Well-partial orderings and their maximal order types". In Schuster, Peter M.; Seisenberger, Monika; Weiermann, Andreas (eds.). Well-Quasi Orders in Computation, Logic, Language and Reasoning. Trends in Logic. Vol. 53. Springer. pp. 351–391. doi:10.1007/978-3-030-30229-0_13.
6. Rathjen, Michael; Weiermann, Andreas (1993). "Proof-theoretic investigations on Kruskal's theorem". Annals of Pure and Applied Logic. 60: 49–88. doi:10.1016/0168-0072(93)90192-G.
7. Forster, Thomas (2003). "Better-quasi-orderings and coinduction". Theoretical Computer Science. 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2.

• Dickson, L. E. (1913). "Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors". American Journal of Mathematics. 35 (4): 413–422. doi:10.2307/2370405. JSTOR 2370405.
• Higman, G. (1952). "Ordering by divisibility in abstract algebras". Proceedings of the London Mathematical Society. 2: 326–336. doi:10.1112/plms/s3-2.1.326.
• Kruskal, J. B. (1972). "The theory of well-quasi-ordering: A frequently discovered concept". Journal of Combinatorial Theory. Series A. 13 (3): 297–305. doi:10.1016/0097-3165(72)90063-5.
• Ketonen, Jussi (1978). "The structure of countable Boolean algebras". Annals of Mathematics. 108 (1): 41–89. doi:10.2307/1970929. JSTOR 1970929.
• Milner, E. C. (1985). "Basic WQO- and BQO-theory". In Rival, I. (ed.). Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and Its Applications. D. Reidel Publishing Co. pp. 487–502. ISBN 90-277-1943-8.
• Gallier, Jean H. (1991). "What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory". Annals of Pure and Applied Logic. 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E.