Well-quasi-ordering

In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x_0, x_1, x_2, … from X contains an increasing pair x_i\le x_j with i<j.

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. 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 \le for a set X one 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 one can find some element of B which is larger than it under \le. One can show that this quasiordering on P(X) needn't 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 X is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements x_0, x_1, x_2, … from X contains an increasing pair x_ix_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 are quasi-orderings which do not contain infinite strictly decreasing sequences (of the form x_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 antichains.

Examples

Wqo's versus well partial orders

In practice, the wqo's one manipulates are quite often not orderings (see examples above), and 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 between equivalence classes induced by the kernel of the wqo. For example, if we order \mathbb{Z} by divisibility, we end up with n\equiv m if 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<j. 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

Notes

  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 (13): 111123. doi:10.1016/S0304-3975(03)00131-2.

References

See also

This article is issued from Wikipedia - version of the Monday, October 26, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.