In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set <math>X</math> is a quasi-ordering of <math>X</math> for which every infinite sequence of elements <math>x_0, x_1, x_2, \ldots</math> from <math>X</math> contains a non-decreasing pair <math>x_i \leq x_j</math> with <math>i < j.</math>

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 <math>\le</math> is said to be well-founded if the corresponding strict order <math>x\le y\land y\nleq x</math> 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 <math>\le</math> for a set <math>X</math> one can define a quasiorder <math>\le^{+}</math> on <math>X</math>'s power set <math>P(X)</math> by setting <math>A \le^{+} B</math> if and only if for each element of <math>A</math> one can find some element of <math>B</math> that is larger than it with respect to <math>\le</math>. One can show that this quasiordering on <math>P(X)</math> need not 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 <math>X</math> is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements <math>x_0, x_1, x_2, \ldots</math> from <math>X</math> contains an increasing pair <math>x_i \le x_j</math> with <math>i< j</math>. The set <math>X</math> 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 <math>x_0> x_1> x_2> \cdots</math>) 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 <math>X</math> be well partially ordered. A (necessarily finite) sequence <math>(x_1, x_2, \ldots, x_n)</math> of elements of <math>X</math> that contains no pair <math>x_i \le x_j</math> with <math>i< j</math> is usually called a bad sequence. The tree of bad sequences <math>T_X</math> is the tree that contains a vertex for each bad sequence, and an edge joining each nonempty bad sequence <math>(x_1, \ldots, x_{n-1}, x_n)</math> to its parent <math>(x_1, \ldots, x_{n-1})</math>. The root of <math>T_X</math> corresponds to the empty sequence. Since <math>X</math> contains no infinite bad sequence, the tree <math>T_X</math> contains no infinite path starting at the root. Therefore, each vertex <math>v</math> of <math>T_X</math> has an ordinal height <math>o(v)</math>, which is defined by transfinite induction as <math>o(v) = \lim_{w \mathrm{\ child\ of\ } v} (o(w)+1)</math>. The ordinal type of <math>X</math>, denoted <math>o(X)</math>, is the ordinal height of the root of <math>T_X</math>.

A linearization of <math>X</math> is an extension of the partial order into a total order. It is easy to verify that <math>o(X)</math> is an upper bound on the ordinal type of every linearization of <math>X</math>. De Jongh and Parikh proved that in fact there always exists a linearization of <math>X</math> that achieves the maximal ordinal type <math>o(X)</math>.

Examples

thumb|200px|Pic.1: A non-example: integers with the usual order

thumb|200px|Pic.2: Another non-example: [[Hasse diagram of the natural numbers ordered by divisibility]]

thumb|200px|Pic.3: Hasse diagram of <math>\N^2</math> with componentwise order

  • <math>(\N, \le)</math>, the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However, <math>(\Z, \le)</math>, 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.
  • <math>(\N, |)</math>, the set of natural numbers ordered by divisibility, is not a well-quasi-order: the prime numbers are an infinite antichain (see Pic.2).
  • <math>(\N^k, \le)</math>, the set of vectors of <math>k</math> natural numbers (where <math>k</math> is finite) with component-wise ordering, is a well partial order (Dickson's lemma; see Pic.3). More generally, if <math>(X, \le)</math> is well-quasi-order, then <math>(X^k,\le^k)</math> is also a well-quasi-order for all <math>k</math>.
  • Let <math>X</math> be an arbitrary finite set with at least two elements. The set <math>X^*</math> of words over <math>X</math> ordered lexicographically (as in a dictionary) is not a well-quasi-order because it contains the infinite decreasing sequence <math>b, ab, aab, aaab, \ldots</math>. Similarly, <math>X^*</math> ordered by the prefix relation is not a well-quasi-order, because the previous sequence is an infinite antichain of this partial order. However, <math>X^*</math> ordered by the subsequence relation is a well partial order. (If <math>X</math> has only one element, these three partial orders are identical.)
  • More generally, <math>(X^*,\le)</math>, the set of finite <math>X</math>-sequences ordered by embedding is a well-quasi-order if and only if <math>(X, \le)</math> is a well-quasi-order (Higman's lemma). Recall that one embeds a sequence <math>u</math> into a sequence <math>v</math> by finding a subsequence of <math>v</math> that has the same length as <math>u</math> and that dominates it term by term. When <math>(X,=)</math> is an unordered set, <math>u\le v</math> if and only if <math>u</math> is a subsequence of <math>v</math>.
  • <math>(X^\omega,\le)</math>, the set of infinite sequences over a well-quasi-order <math>(X, \le)</math>, 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 <math>(X, \le)</math> is a wqo (Kruskal's tree theorem).
  • Embedding between infinite trees with nodes labeled by elements of a wqo <math>(X, \le)</math> 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 <math>X_1</math> and <math>X_2</math> be two disjoint wpo sets. Let <math>Y=X_1\cup X_2</math>, and define a partial order on <math>Y</math> by letting <math>y_1\le_Y y_2</math> if and only if <math>y_1,y_2\in X_i</math> for the same <math>i\in\{1,2\}</math> and <math>y_1 \le_{X_i} y_2</math>. Then <math>Y</math> is wpo, and <math>o(Y) = o(X_1) \oplus o(X_2)</math>, where <math>\oplus</math> denotes natural sum of ordinals. <math display="block">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}</math>

Given a wpo set <math>X</math>, let <math>T(X)</math> be the set of all finite rooted trees whose vertices are labeled by elements of <math>X</math>. Partially order <math>T(X)</math> by the tree embedding relation. By Kruskal's tree theorem, <math>T(X)</math> is wpo. This result is nontrivial even for the case <math>|X|=1</math> (which corresponds to unlabeled trees), in which case <math>o(T(X))</math> equals the small Veblen ordinal. In general, for <math>o(X)</math> countable, we have the upper bound <math>o(T(X))\le\vartheta(\Omega^\omega o(X))</math> in terms of the <math>\vartheta</math> ordinal collapsing function. (The small Veblen ordinal equals <math>\vartheta(\Omega^\omega)</math> 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 <math>\Z</math> by divisibility, we end up with <math>n\equiv m</math> if and only if <math>n=\pm m</math>, so that <math>(\Z,|)\approx(\N,|)</math>.

Infinite increasing subsequences

If <math>(X, \le)</math> is wqo then every infinite sequence <math>x_0, x_1, x_2, \ldots,</math> contains an infinite increasing subsequence <math>x_{n_0} \le x_{n_1}\le x_{n_2} \le \cdots</math> (with <math>n_0< n_1< n_2< \cdots</math>). Such a subsequence is sometimes called perfect.

This can be proved by a Ramsey argument: given some sequence <math>(x_i)_i</math>, consider the set <math>I</math> of indexes <math>i</math> such that <math>x_i</math> has no larger or equal <math>x_j</math> to its right, i.e., with <math>i<j</math>. If <math>I</math> is infinite, then the <math>I</math>-extracted subsequence contradicts the assumption that <math>X</math> is wqo. So <math>I</math> is finite, and any <math>x_n</math> with <math>n</math> larger than any index in <math>I</math> 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 <math>(X,\le)</math> the quasiordering <math>(P(X), \le^+)</math> defined by <math> A \le^+ B \iff \forall a \in A, \exists b \in B, a \le b</math> is well-founded if and only if <math>(X,\le)</math> is a wqo.

Further reading