Well-quasi-ordering

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,\dots }$ from ${\displaystyle X}$ contains an increasing pair ${\displaystyle x_i\le 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,\dots ,x_n)}$ of elements of ${\displaystyle X}$ that contains no pair ${\displaystyle x_i\le 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,\dots ,x_{n-1},x_n)}$ to its parent ${\displaystyle (x_1,\dots ,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. 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)=\underset{w\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{d}\mathrm{o}\mathrm{f}v}{lim}(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 proved that in fact there always exists a linearization of ${\displaystyle X}$ that achieves the maximal ordinal type ${\displaystyle o(X)}$.

Examples

• ${\displaystyle (\mathbb{N},\le )}$, the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However, ${\displaystyle (\mathbb{Z},\le )}$, the set of positive and negative integers (see Pic.1), is not a well-quasi-order, because it is not well-founded. The infinite sequence -1, -2,... contains no increasing pair.
• ${\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,\le )}$, 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,\le )}$ is well-quasi-order, then ${\displaystyle (X^k,{\le }^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^{\ast }}$ 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,\dots }$. Similarly, ${\displaystyle X^{\ast }}$ 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^{\ast }}$ ordered by the subsequence relation is a well partial order. (If ${\displaystyle X}$ has only one element, these three partial orders are identical.)
• More generally, ${\displaystyle (X^{\ast },\le )}$, the set of finite ${\displaystyle X}$-sequences ordered by embedding is a well-quasi-order if and only if ${\displaystyle (X,\le )}$ 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\le v}$ if and only if ${\displaystyle u}$ is a subsequence of ${\displaystyle v}$.
• ${\displaystyle (X^{\omega },\le )}$, the set of infinite sequences over a well-quasi-order ${\displaystyle (X,\le )}$, 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,\le )}$ is a wqo (Kruskal's tree theorem).
• Embedding between infinite trees with nodes labeled by elements of a wqo ${\displaystyle (X,\le )}$ 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, as do the cographs ordered by induced subgraphs.

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{\le }_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{\le }_{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.

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){\le }_Y(b_1,b_2)}$ if and only if ${\displaystyle a_1{\le }_{X_1}{b}_1}$ and ${\displaystyle a_2{\le }_{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.

Given a wpo set ${\displaystyle X}$, let ${\displaystyle X^{\ast }}$ be the set of finite sequences of elements of ${\displaystyle X}$, partially ordered by the subsequence relation. Meaning, let ${\displaystyle (x_1,\dots ,x_n){\le }_{X^{\ast }}(y_1,\dots ,y_m)}$ if and only if there exist indices ${\displaystyle 1\le i_1<\cdots <i_n\le m}$ such that ${\displaystyle x_j{\le }_X{y}_{i_j}}$ for each ${\displaystyle 1\le j\le n}$. By Higman's lemma, ${\displaystyle X^{\ast }}$ is wpo. The ordinal type of ${\displaystyle X^{\ast }}$ is $${\displaystyle o(X^{\ast })=\{\begin{array}{ll}{\omega }^{{\omega }^{o(X)-1}},& o(X)\text{ finite};\\ {\omega }^{{\omega }^{o(X)+1}},& o(X)={\epsilon }_{\alpha }+n\text{ for some }\alpha \text{ and some finite }n;\\ {\omega }^{{\omega }^{o(X)}},& \text{otherwise}.\end{array}}$$

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))\le \vartheta ({\mathrm{\Omega }}^{\omega }o(X))}$ in terms of the ${\displaystyle \vartheta }$ ordinal collapsing function. (The small Veblen ordinal equals ${\displaystyle \vartheta ({\mathrm{\Omega }}^{\omega })}$ in this ordinal notation.)

Wqo's versus well partial orders

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,\le )}$ is wqo then every infinite sequence ${\displaystyle x_0,x_1,x_2,\dots ,}$ contains an infinite increasing subsequence ${\displaystyle x_{n_0}\le x_{n_1}\le x_{n_2}\le \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,\le )}$ the quasiordering ${\displaystyle (P(X),{\le }^{+})}$ defined by ${\displaystyle A{\le }^{+}B⟺\mathrm{\forall }a\in A,\mathrm{\exists }b\in B,a\le b}$ is well-founded if and only if ${\displaystyle (X,\le )}$ is a wqo.
• A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by ${\displaystyle x\sim y⟺x\le y\wedge y\le 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,\le )}$, 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 \mathrm{\forall }x,y\in X,x\le y\wedge x\in S\Rightarrow y\in S}$): assuming the contrary ${\displaystyle \mathrm{\forall }i\in \mathbb{N},\mathrm{\exists }j\in \mathbb{N},j>i,\mathrm{\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,\le )}$, any subset ${\displaystyle S}$ of ${\displaystyle X}$ has a finite number of minimal elements with respect to ${\displaystyle \le }$, for otherwise the minimal elements of ${\displaystyle S}$ would constitute an infinite antichain.