In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, specifically order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, a well-quasi-ordering or wqo is a well-founded quasi-ordering with an additional restriction on sequences - that there is no infinite sequence with for all .

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 for a set we can define a quasiorder on 's power set by setting if and only if for each element of we can find some element of which is larger than it under . We find that this quasiordering on 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 is a quasi-ordering (i.e., a reflexive

Reflexive relation

In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

, transitive

Transitive relation

In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

 binary relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

) 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

Antisymmetric relation

In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...

.

Among other ways of defining wqo's, one is to say that they do not contain infinite strictly decreasing sequences (of the form
>>>…)
nor infinite sequences of pairwise incomparable elements. Hence a quasi-order (,≤) is wqo if and only if it is well-founded

Well-founded relation

In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...

 and has no infinite antichain

Antichain

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...

s.

Examples

• , the set of natural numbers with standard ordering, is a well partial order. , the set of positive and negative integers, is not: it is not well-founded.
• , 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 , , , , ... If we consider the prefix ordering for comparing words, then the previous sequence becomes an infinite antichain.
• , the set of vectors of natural numbers with component-wise ordering, is a well partial order (Dickson's lemma
  Dickson's lemma
  In mathematics, Dickson's lemma is a finiteness statement applying to n-tuples of natural numbers. It is a simple fact from combinatorics, which has become attributed to the American algebraist L. E. Dickson...
  
  ). More generally, if is wqo, then for any , is wqo.
• , the set of finite -sequences ordered by embedding
  Embedding
  In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
  
   is a wqo if and only if is (Higman's lemma
  Higman's lemma
  In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered...
  
  ). 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 wqo , ordered by embedding is not a wqo 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
  Kruskal's tree theorem
  In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered...
  
  ).
• Embedding between infinite trees with nodes labeled by elements of a wqo is a wqo (Nash-Williams
  Crispin St. J. A. Nash-Williams
  Crispin St. John Alvah Nash-Williams was a British and Canadian mathematician. His research interest was in the field of discrete mathematics, especially graph theory....
  
  ' theorem).
• Embedding between countable scattered
  Scattered order
  In mathematics, specifically order theory, a scattered order is a linear order that contains no densely ordered subset with more than 1 element....
  
   linear order types is a wqo (Laver
  Richard Laver
  Richard Laver is an American mathematician, working in set theory. He is a professor emeritus at the Department of Mathematics of the University of Colorado at Boulder.-His main results:Among Laver's notable achievements some are the following....
  
  's theorem).
• 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
  Robertson–Seymour theorem
  In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
  
  ).

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 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 subsequences

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

Ramsey theory

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...

: 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 wqos

• Given a quasiordering the quasiordering defined by is well-founded if and only if is a wqo.
• A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by ) has no infinite descending sequences or antichain
  Antichain
  In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
  
  s. (This can be proved using a Ramsey argument
  Ramsey theory
  Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
  
  as above)