Open main menu

In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements , , , … from contains an increasing pair with .

Contents

MotivationEdit

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. 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   for a set   one can define a quasiorder   on  's power set   by setting   if and only if for each element of   one can find some element of   that is larger than it under  . One can show that this quasiordering on   needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is.

Formal definitionEdit

A well-quasi-ordering on a set   is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements  ,  ,  , … from   contains an increasing pair    with  < . The set   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  > > >…)[1] 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.

ExamplesEdit

 
Pic.1: Integer numbers with the usual order
 
Pic.2: Hasse diagram of the natural numbers ordered by divisibility
 
Pic.3: Hasse diagram of   with componentwise order
  •  , the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However,  , the set of positive and negative integers, is not a well-quasi-order, because it is not well-founded (see Pic.1).
  •  , the set of natural numbers ordered by divisibility, is not a well-quasi-order: the prime numbers are an infinite antichain (see Pic.2).
  •  , the set of vectors of   natural numbers (where   is finite) with component-wise ordering, is a well partial order (Dickson's lemma; see Pic.3). More generally, if   is well-quasi-order, then   is also a well-quasi-order for all  .
  • Let   be an arbitrary finite set with at least two elements. The set   of words over   ordered lexicographically (as in a dictionary) is not a well-quasi-order because it contains the infinite decreasing sequence  . Similarly,   ordered by the prefix relation is not a well-quasi-order, because the previous sequence is an infinite antichain of this partial order. However,   ordered by the subsequence relation is a well partial order.[1] (If   has only one element, these three partial orders are identical.)
  • More generally,  , the set of finite  -sequences ordered by embedding is a well-quasi-order if and only if   is a well-quasi-order (Higman's lemma). Recall that one embeds a sequence   into a sequence   by finding a subsequence of   that has the same length as   and that dominates it term by term. When   is a finite unordered set,   if and only if   is a subsequence of  .
  •  , the set of infinite sequences over a well-quasi-order  , 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   is a wqo (Kruskal's tree theorem).
  • Embedding between infinite trees with nodes labeled by elements of a wqo   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,[2] as do the cographs ordered by induced subgraphs.[3]

Wqo's versus well partial ordersEdit

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   by divisibility, we end up with   if and only if  , so that  .

Infinite increasing subsequencesEdit

If ( , ≤) is wqo then every infinite sequence  ,  ,  , … contains an infinite increasing subsequence    ≤… (with  < < <…). Such a subsequence is sometimes called perfect. This can be proved by a Ramsey argument: given some sequence  , consider the set   of indexes   such that   has no larger or equal   to its right, i.e., with  . If   is infinite, then the  -extracted subsequence contradicts the assumption that   is wqo. So   is finite, and any   with   larger than any index in   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 wqosEdit

  • Given a quasiordering   the quasiordering   defined by   is well-founded if and only if   is a wqo.[4]
  • A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by  ) has no infinite descending sequences or antichains. (This can be proved using a Ramsey argument as above.)
  • Given a well-quasi-ordering  , any sequence of upward-closed subsets   eventually stabilises (meaning there is an index   such that  ; a subset   is called upward-closed if  ): assuming the contrary  , a contradiction is reached by extracting an infinite non-ascending subsequence.
  • Given a well-quasi-ordering  , any subset   which is upward-closed with respect to   has a finite number of minimal elements w.r.t.  , for otherwise the minimal elements of   would constitute an infinite antichain.

NotesEdit

^ Here x < y means: xy and y   x.

  1. ^ Gasarch, W. (1998), "A survey of recursive combinatorics", Handbook of Recursive Mathematics, Vol. 2, Stud. Logic Found. Math., 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9, MR 1673598. See in particular page 1160.
  2. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Lemma 6.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Heidelberg: Springer, p. 137, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
  3. ^ Damaschke, Peter (1990), "Induced subgraphs and well-quasi-ordering", Journal of Graph Theory, 14 (4): 427–435, doi:10.1002/jgt.3190140406, MR 1067237.
  4. ^ Forster, Thomas (2003). "Better-quasi-orderings and coinduction". Theoretical Computer Science. 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2.

ReferencesEdit

See alsoEdit