Well-quasi-ordering
All definitions tacitly require the homogeneous relation
A term's definition may require additional properties that are not listed in this table.
In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set
is said to be well-founded if the corresponding strict order
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.
needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is.
is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements
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.
contains no infinite bad sequence, the tree
contains no infinite path starting at the root.
is an upper bound on the ordinal type of every linearization of
De Jongh and Parikh[1] proved that in fact there always exists a linearization of
denotes natural sum of ordinals.
, define a partial order on the Cartesian product
is wpo (this is a generalization of Dickson's lemma), and
denotes natural product of ordinals.
be the set of finite sequences of elements of
, partially ordered by the subsequence relation.
be the set of all finite rooted trees whose vertices are labeled by elements of
(which corresponds to unlabeled trees), in which case
equals the small Veblen ordinal.
)[6] 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.
This can be proved by a Ramsey argument: given some sequence
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.
