In
mathematics, specifically
order theory
Order theory is a branch of mathematics that investigates the 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 int ...
, a well-quasi-ordering or wqo is a
quasi-ordering
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special ...
such that any
infinite
Infinite may refer to:
Mathematics
* Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...
sequence of elements
from
contains an increasing pair
with
Motivation
Well-founded induction
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s&nbs ...
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
is said to be well-founded if the corresponding strict order
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
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
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 with respect to
. 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 definition
A well-quasi-ordering on a set
is a
quasi-ordering
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special ...
(i.e., a
reflexive,
transitive binary relation) such that any
infinite
Infinite may refer to:
Mathematics
* Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...
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
) 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
antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
The size of the largest antichain in a partially ordered set is known as its wid ...
s.
Examples
*
, the set of natural numbers with standard ordering, is a well partial order (in fact, a
well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
). 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 In mathematics, Dickson's lemma states that every set of n-tuples of natural numbers has finitely many minimal elements. This simple fact from combinatorics has become attributed to the American algebraist L. E. Dickson, who used it to prove a re ...
; 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
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
(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
In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...
relation is a well partial order. (If
has only one element, these three partial orders are identical.)
* More generally,
, the set of finite
-sequences ordered by
embedding
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.
When some object X is said to be embedded in another object Y, the embedding is g ...
is a well-quasi-order if and only if
is a well-quasi-order (
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. That is, if w_1, w_2, \ldots is an infinite sequence of words over some fixed ...
). 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 an 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
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 under homeomorphic embedding.
History
The theorem was conjectured by Andrew Vázsonyi and proved b ...
).
* Embedding between infinite trees with nodes labeled by elements of a wqo
is a wqo (
Nash-Williams' theorem).
* Embedding between countable
scattered linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
types is a well-quasi-order (
Laver's theorem Laver's theorem, in order theory, states that order embeddability of countable total orders is a well-quasi-ordering. That is, for every infinite sequence of totally-ordered countable sets, there exists an order embedding from an earlier member of ...
).
* 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
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
" is a well-quasi-order (
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is c ...
).
* Graphs of finite
tree-depth ordered by the
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
relation form a well-quasi-order, as do the
cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s ordered by induced subgraphs.
[.]
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. 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 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: given some sequence
, consider the set
of indexes
such that
has no larger or equal
to its right, i.e., with