Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total, Semiconnex Anti-
reflexive
Equivalence relation Green tickY Green tickY
Preorder (Quasiorder) Green tickY
Partial order Green tickY Green tickY
Total preorder Green tickY Green tickY
Total order Green tickY Green tickY Green tickY
Prewellordering Green tickY Green tickY Green tickY
Well-quasi-ordering Green tickY Green tickY
Well-ordering Green tickY Green tickY Green tickY Green tickY
Lattice Green tickY Green tickY Green tickY Green tickY
Join-semilattice Green tickY Green tickY Green tickY
Meet-semilattice Green tickY Green tickY Green tickY
Strict partial order Green tickY Green tickY Green tickY
Strict weak order Green tickY Green tickY Green tickY
Strict total order Green tickY Green tickY Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions, for all and
Green tickY indicates that the column's property is always true the row's term (at the very left), while indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Green tickY in the "Symmetric" column and in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation be transitive: for all if and then
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 a quasi-ordering of for which every infinite sequence of elements from contains an increasing pair with

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. (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 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 (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.

Ordinal type

Let be well partially ordered. A (necessarily finite) sequence of elements of that contains no pair with is usually called a bad sequence. The tree of bad sequences is the tree that contains a vertex for each bad sequence, and an edge joining each nonempty bad sequence to its parent . The root of corresponds to the empty sequence. Since contains no infinite bad sequence, the tree contains no infinite path starting at the root.[citation needed] Therefore, each vertex of has an ordinal height , which is defined by transfinite induction as . The ordinal type of , denoted , is the ordinal height of the root of .

A linearization of is an extension of the partial order into a total order. It is easy to verify that 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 that achieves the maximal ordinal type .

Examples

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

Constructing new wpo's from given ones

Let and be two disjoint wpo sets. Let , and define a partial order on by letting if and only if for the same and . Then is wpo, and , where denotes natural sum of ordinals.[1]

Given wpo sets and , define a partial order on the Cartesian product , by letting if and only if and . Then is wpo (this is a generalization of Dickson's lemma), and , where denotes natural product of ordinals.[1]

Given a wpo set , let be the set of finite sequences of elements of , partially ordered by the subsequence relation. Meaning, let if and only if there exist indices such that for each . By Higman's lemma, is wpo. The ordinal type of is[1][5]

Given a wpo set , let be the set of all finite rooted trees whose vertices are labeled by elements of . Partially order by the tree embedding relation. By Kruskal's tree theorem, is wpo. This result is nontrivial even for the case (which corresponds to unlabeled trees), in which case equals the small Veblen ordinal. In general, for countable, we have the upper bound in terms of the ordinal collapsing function. (The small Veblen ordinal equals in this ordinal notation.)[6]

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[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 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 . 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

See also

Notes

^ Here x < y means: and

References

  1. ^ a b c d de Jongh, Dick H. G.; Parikh, Rohit (1977). "Well-partial orderings and hierarchies". Indagationes Mathematicae (Proceedings). 80 (3): 195–207. doi:10.1016/1385-7258(77)90067-1.
  2. ^ Gasarch, W. (1998), "A survey of recursive combinatorics", Handbook of Recursive Mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9, MR 1673598. See in particular page 1160.
  3. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Lemma 6.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 137, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
  4. ^ Damaschke, Peter (1990), "Induced subgraphs and well-quasi-ordering", Journal of Graph Theory, 14 (4): 427–435, doi:10.1002/jgt.3190140406, MR 1067237.
  5. ^ Schmidt, Diana (1979). Well-partial orderings and their maximal order types (Habilitationsschrift). Heidelberg. Republished in: Schmidt, Diana (2020). "Well-partial orderings and their maximal order types". In Schuster, Peter M.; Seisenberger, Monika; Weiermann, Andreas (eds.). Well-Quasi Orders in Computation, Logic, Language and Reasoning. Trends in Logic. Vol. 53. Springer. pp. 351–391. doi:10.1007/978-3-030-30229-0_13.
  6. ^ Rathjen, Michael; Weiermann, Andreas (1993). "Proof-theoretic investigations on Kruskal's theorem". Annals of Pure and Applied Logic. 60: 49–88. doi:10.1016/0168-0072(93)90192-G.
  7. ^ Forster, Thomas (2003). "Better-quasi-orderings and coinduction". Theoretical Computer Science. 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2.