Examples
- , the set of natural numbers with standard ordering, is a well partial order. However, the set of positive and negative integers, is not a well-quasi-order, because 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 vectors of natural numbers with component-wise ordering, is a well partial order (Dickson's lemma). 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 (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 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 is a well-quasi-order if and only if is is a well-quasi-order (Higman's lemma). 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 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).
- Embedding between infinite trees with nodes labeled by elements of a wqo is a wqo (Nash-Williams' theorem).
- Embedding between countable scattered linear order types is a well-quasi-order (Laver's theorem).
- 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" is a well-quasi-order (Robertson–Seymour theorem).
- Graphs of finite tree-depth ordered by the induced subgraph relation form a well-quasi-order, as do the cographs ordered by induced subgraphs.
Read more about this topic: Well-quasi-ordering
Famous quotes containing the word examples:
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)