- Well-quasi-ordering
In
mathematics , specificallyorder theory , a well-quasi-ordering or wqo is awell-founded quasi-ordering with an additional restriction on sequences - that there is no infinite sequence x_i with x_i ot le x_j for all i < j .Motivation
We can use
well-founded induction on any set with a well-founded relation, thus one is interested in when a quasi-order is well-founded. However the class of well-founded quasiorders is not closed under certain operations - that is, when we use a quasi-order to obtain a new quasi-order on a set of structures derived from our original set, we find this quasiorder is 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 le for a set X we can define a quasiorder le^{+} on X's power set P(X) by setting A le^{+} B if and only if for each element of A we can find some element of B which is larger than it under le. We find that this quasiordering on P(X) needn't be well-founded but that if we took our original quasi-ordering to be a well-quasi-ordering then it is.
Formal definition
A well-quasi-ordering ≤ on a set X is a
quasi-ordering (i.e., a reflexive, transitivebinary relation ) such that anyinfinite sequence of elements x_0, x_1, x_2, … from X contains an increasing pair x_i≤x_j with i<j. The set 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 do not contain infinite "strictly decreasing" sequences (of the formx_0>x_1>x_2>…)nor infinite sequences of "pairwise incomparable" elements. Hence a quasi-order (X,≤) is wqo if and only if it is well-founded and has no infinite
antichain s.Examples
* mathbb{N}, le), the set of natural numbers with standard ordering, is a well partial order. mathbb{Z}, le), the set of positive and negative integers, is not: it is not well-founded.
* mathbb{N}, mid), the set of natural numbers ordered by divisibility, is not a well partial order: the prime numbers are an infinite antichain.
* The set of words ordered lexicographically, i.e., as in a dictionary, is not a wqo: it is not well-founded as witnessed by the decreasing sequence b, ab, aab, aaab, ... If we consider the prefix ordering for comparing words, then the previous sequence becomes an infinite antichain.
* mathbb{N}^k, le), the set of vectors of k natural numbers with component-wise ordering, is a well partial order (
Dickson's lemma ). More generally, if X, le) is wqo, then for any k, X^k,le^k) is wqo.* X^*,le), the set of finite X-sequences ordered by
embedding is a wqo if and only if X, le) is (Higman's lemma ). Recall that one embeds a sequence u into a sequence v by finding a subsequence of v that has the same length as u and that dominates it term by term. When X,=) is a finite unordered set, ule v if and only if u is a subsequence of v.* X^omega,le), the set of infinite sequences over a wqo X, le), ordered by embedding is not a wqo in general. That is, Higman's lemma does not carry over to infinite sequences.
Better-quasi-ordering s 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 X, le) is a wqo (
Kruskal's tree theorem ).* Embedding between infinite trees with nodes labeled by elements of a wqo X, le) is a wqo (Nash-Williams' theorem).
* Embedding between countable scattered
linear order types is a wqo (Laver's theorem). Scattered linear orders are those that do not contain adense order .* Embedding between countable
boolean algebras is a wqo. This follows from Laver's theorem and a theorem of Ketonen.* Finite graphs ordered by a notion of embedding called "
graph minor " is a wqo (Robertson-Seymour theorem ).Wqo's versus well partial orders
In practice, the wqo's one manipulates are almost always orderings (see examples above), but the theory is technically smoother if we do not require antisymmetry, so it is built with wqo's as the basic notion.
Observe that a wpo is a wqo, and that a wqo gives rise to a wpo betweenequivalence classes induced by the kernel of the wqo. For example, if we order mathbb{Z} by divisibility, we end up with nequiv mif and only if n=pm m, so that mathbb{Z},mid);;approx;;(mathbb{N},mid).
Infinite increasing subsequences
If (X, ≤) is wqo then every infinite sequence x_0, x_1, x_2, … contains an infinite increasing subsequence x_{n0}≤x_{n1}≤x_{n2}≤…(with n0}<n1}<n2}<…). Such a subsequence is sometimes called perfect.This can be proved by a Ramsey argument: given some sequence x_i)_i, consider the set I of indexes i such that x_i has no larger or equal x_j to its right, i.e., with i
. If I is infinite, then the I-extracted subsequence contradicts the assumption that X is wqo. So I is finite, and any x_n with n larger than any index in 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 X,le) the quasiordering P(X), le^+) defined by A le^+ B iff forall a in Aexists b in B(a le b) is well-founded if an only if X,le) is a wqo.
* A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by x sim y iff xle y land y le x) has no infinite descending sequences oranti-chains . (This can be proved using a Ramsey argument as above)References
#
#
#
#
#
#ee also
*
Prewellordering
*Well-order
Wikimedia Foundation. 2010.