Well-quasi-ordering
Template:Short description Template:CS1 config Template:Stack 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 an increasing 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>)Template:Efn 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.<ref>Template:Cite journal Page 471: "Q is a well-quasi-order iff the tree of bad sequences from Q is well-founded."</ref> 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<ref name="dejongh_parikh">Template:Cite journal</ref> proved that in fact there always exists a linearization of <math>X</math> that achieves the maximal ordinal type <math>o(X)</math>.
Examples
- <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, is not a well-quasi-order, because it is not well-founded (see Pic.1).
- <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.<ref>Template:Cite book. See in particular page 1160.</ref> (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,<ref>Template:Cite book.</ref> as do the cographs ordered by induced subgraphs.<ref>Template:Cite journal.</ref>
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.<ref name="dejongh_parikh" />
Given wpo sets <math>X_1</math> and <math>X_2</math>, define a partial order on the Cartesian product <math>Y=X_1\times X_2</math>, by letting <math>(a_1,a_2)\le_Y (b_1,b_2)</math> if and only if <math>a_1\le_{X_1} b_1</math> and <math>a_2\le_{X_2} b_2</math>. Then <math>Y</math> is wpo (this is a generalization of Dickson's lemma), and <math>o(Y) = o(X_1)\otimes o(X_2)</math>, where <math>\otimes</math> denotes natural product of ordinals.<ref name="dejongh_parikh" />
Given a wpo set <math>X</math>, let <math>X^*</math> be the set of finite sequences of elements of <math>X</math>, partially ordered by the subsequence relation. Meaning, let <math>(x_1,\ldots,x_n)\le_{X^*} (y_1,\ldots,y_m)</math> if and only if there exist indices <math>1\le i_1<\cdots<i_n\le m</math> such that <math>x_j \le_X y_{i_j}</math> for each <math>1\le j\le n</math>. By Higman's lemma, <math>X^*</math> is wpo. The ordinal type of <math>X^*</math> is<ref name="dejongh_parikh" /><ref name="schmidt">Template:Cite thesis Republished in: Template:Cite book</ref> <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.)<ref>Template:Cite journal</ref>
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.<ref>Template:Cite book</ref>
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.<ref name="forster"/>
- A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by <math>x \sim y \iff x\le y \land y \le x</math>) has no infinite descending sequences or antichains. (This can be proved using a Ramsey argument as above.)
- Given a well-quasi-ordering <math>(X,\le)</math>, any sequence of upward-closed subsets <math>S_0 \subseteq S_1 \subseteq \cdots \subseteq X</math> eventually stabilises (meaning there exists <math>n \in \N</math> such that <math>S_n = S_{n+1} = \cdots</math>; a subset <math>S \subseteq X</math> is called upward-closed if <math>\forall x,y \in X, x \le y \wedge x \in S \Rightarrow y \in S</math>): assuming the contrary <math>\forall i \in \N, \exists j \in \N, j > i, \exists x \in S_j \setminus S_i</math>, a contradiction is reached by extracting an infinite non-ascending subsequence.
- Given a well-quasi-ordering <math>(X,\le)</math>, any subset <math>S</math> of <math>X</math> has a finite number of minimal elements with respect to <math>\le</math>, for otherwise the minimal elements of <math>S</math> would constitute an infinite antichain.