Editing Well-quasi-ordering (section)

==Examples==

[[File:Integers-line.svg|thumb|200px|'''Pic.1:''' Integer numbers with the usual order]]
[[File:Infinite lattice of divisors.svg|thumb|200px|'''Pic.2:''' [[Hasse diagram]] of the natural numbers ordered by divisibility]]
[[File:N-Quadrat, gedreht.svg|thumb|200px|'''Pic.3:''' Hasse diagram of <math>\N^2</math> with componentwise order]]

* <math>(\N, \le)</math>, the set of natural numbers with standard ordering, is a well partial order (in fact, a [[well-order]]). However, <math>(\Z, \le)</math>, the set of positive and negative integers, is '''not''' a well-quasi-order, because it is not well-founded (see Pic.1).
* <math>(\N, |)</math>, the set of natural numbers ordered by divisibility, is '''not''' a well-quasi-order: the prime numbers are an infinite antichain (see Pic.2).
* <math>(\N^k, \le)</math>, the set of vectors of <math>k</math> natural numbers (where <math>k</math> is finite) with [[product order|component-wise ordering]], is a well partial order ([[Dickson's lemma]]; see Pic.3). More generally, if <math>(X, \le)</math> is well-quasi-order, then <math>(X^k,\le^k)</math> is also a well-quasi-order for all <math>k</math>.
* Let <math>X</math> be an arbitrary finite set with at least two elements. The set [[Kleene star|<math>X^*</math>]] of [[Formal language#Words_over_an_alphabet|words over]] <math>X</math> ordered [[lexicographical order|lexicographically]] (as in a dictionary) is '''not''' a well-quasi-order because it contains the infinite decreasing sequence <math>b, ab, aab, aaab, \ldots</math>. Similarly, <math>X^*</math> ordered by the [[prefix (computer science)#Prefix|prefix]] relation is '''not''' a well-quasi-order, because the previous sequence is an infinite antichain of this partial order. However, <math>X^*</math> ordered by the [[subsequence]] relation is a well partial order.<ref>{{citation | last = Gasarch | first = W. | author1-link=William Gasarch  | contribution = A survey of recursive combinatorics | doi = 10.1016/S0049-237X(98)80049-9 | location = Amsterdam | mr = 1673598 | pages = 1041–1176 | publisher = North-Holland | series = Stud. Logic Found. Math. | title = Handbook of Recursive Mathematics, Vol. 2 | volume = 139 | year = 1998}}. See in particular page 1160.</ref>  (If <math>X</math> has only one element, these three partial orders are identical.)
* More generally, <math>(X^*,\le)</math>, the set of finite <math>X</math>-sequences ordered by [[embedding]] is a well-quasi-order if and only if <math>(X, \le)</math> is a well-quasi-order ([[Higman's lemma]]). Recall that one embeds a sequence <math>u</math> into a sequence <math>v</math> by finding a subsequence of <math>v</math> that has the same length as <math>u</math> and that dominates it term by term. When <math>(X,=)</math> is an unordered set, <math>u\le v</math> if and only if <math>u</math> is a subsequence of <math>v</math>.
* <math>(X^\omega,\le)</math>, the set of infinite sequences over a well-quasi-order <math>(X, \le)</math>, 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-ordering]]s 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 <math>(X, \le)</math> is a wqo ([[Kruskal's tree theorem]]).
* Embedding between infinite trees with nodes labeled by elements of a wqo <math>(X, \le)</math> is a wqo ([[Crispin St. J. A. Nash-Williams|Nash-Williams]]' theorem).
* Embedding between countable [[scattered order|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,<ref>{{citation | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | contribution = Lemma 6.13 | doi = 10.1007/978-3-642-27875-4 | isbn = 978-3-642-27874-7 | location = Heidelberg | mr = 2920058 | pages = 137 | publisher = Springer
 | series = Algorithms and Combinatorics | title = Sparsity: Graphs, Structures, and Algorithms | volume = 28 | year = 2012 }}.</ref> as do the [[cograph]]s ordered by induced subgraphs.<ref>{{citation | last = Damaschke | first = Peter | doi = 10.1002/jgt.3190140406 | issue = 4 | journal = [[Journal of Graph Theory]] | mr = 1067237 | pages = 427–435 | title = Induced subgraphs and well-quasi-ordering | volume = 14 | year = 1990}}.</ref>