In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set X {\displaystyle X} is a quasi-ordering of X {\displaystyle X} for which every infinite sequence of elements x 0 , x 1 , x 2 , … {\displaystyle x_{0},x_{1},x_{2},\ldots } from X {\displaystyle X} contains a non-decreasing pair x i ≤ x j {\displaystyle x_{i}\leq x_{j}} with i < j . {\displaystyle i<j.}
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 ≤ {\displaystyle \leq } is said to be well-founded if the corresponding strict order x ≤ y ∧ y ≰ x {\displaystyle x\leq y\land y\nleq x} 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 ≤ {\displaystyle \leq } for a set X {\displaystyle X} one can define a quasiorder ≤ + {\displaystyle \leq ^{+}} on X {\displaystyle X} 's power set P ( X ) {\displaystyle P(X)} by setting A ≤ + B {\displaystyle A\leq ^{+}B} if and only if for each element of A {\displaystyle A} one can find some element of B {\displaystyle B} that is larger than it with respect to ≤ {\displaystyle \leq } . One can show that this quasiordering on P ( X ) {\displaystyle P(X)} need not 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 X {\displaystyle X} is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements x 0 , x 1 , x 2 , … {\displaystyle x_{0},x_{1},x_{2},\ldots } from X {\displaystyle X} contains an increasing pair x i ≤ x j {\displaystyle x_{i}\leq x_{j}} with i < j {\displaystyle i<j} . The set X {\displaystyle X} 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 x 0 > x 1 > x 2 > ⋯ {\displaystyle x_{0}>x_{1}>x_{2}>\cdots } ) 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 X {\displaystyle X} be well partially ordered. A (necessarily finite) sequence ( x 1 , x 2 , … , x n ) {\displaystyle (x_{1},x_{2},\ldots ,x_{n})} of elements of X {\displaystyle X} that contains no pair x i ≤ x j {\displaystyle x_{i}\leq x_{j}} with i < j {\displaystyle i<j} is usually called a bad sequence. The tree of bad sequences T X {\displaystyle T_{X}} is the tree that contains a vertex for each bad sequence, and an edge joining each nonempty bad sequence ( x 1 , … , x n − 1 , x n ) {\displaystyle (x_{1},\ldots ,x_{n-1},x_{n})} to its parent ( x 1 , … , x n − 1 ) {\displaystyle (x_{1},\ldots ,x_{n-1})} . The root of T X {\displaystyle T_{X}} corresponds to the empty sequence. Since X {\displaystyle X} contains no infinite bad sequence, the tree T X {\displaystyle T_{X}} contains no infinite path starting at the root. Therefore, each vertex v {\displaystyle v} of T X {\displaystyle T_{X}} has an ordinal height o ( v ) {\displaystyle o(v)} , which is defined by transfinite induction as o ( v ) = lim w c h i l d o f v ( o ( w ) + 1 ) {\displaystyle o(v)=\lim _{w\mathrm {\ child\ of\ } v}(o(w)+1)} . The ordinal type of X {\displaystyle X} , denoted o ( X ) {\displaystyle o(X)} , is the ordinal height of the root of T X {\displaystyle T_{X}} . A linearization of X {\displaystyle X} is an extension of the partial order into a total order. It is easy to verify that o ( X ) {\displaystyle o(X)} is an upper bound on the ordinal type of every linearization of X {\displaystyle X} . De Jongh and Parikh proved that in fact there always exists a linearization of X {\displaystyle X} that achieves the maximal ordinal type o ( X ) {\displaystyle o(X)} .
Examples
( N , ≤ ) {\displaystyle (\mathbb {N} ,\leq )} , the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However, ( Z , ≤ ) {\displaystyle (\mathbb {Z} ,\leq )} , the set of positive and negative integers (see Pic.1), is not a well-quasi-order, because it is not well-founded. The infinite sequence -1, -2,... contains no increasing pair.
( N , | ) {\displaystyle (\mathbb {N} ,|)} , the set of natural numbers ordered by divisibility, is not a well-quasi-order: the prime numbers are an infinite antichain (see Pic.2).
( N k , ≤ ) {\displaystyle (\mathbb {N} ^{k},\leq )} , the set of vectors of k {\displaystyle k} natural numbers (where k {\displaystyle k} is finite) with component-wise ordering, is a well partial order (Dickson's lemma; see Pic.3). More generally, if ( X , ≤ ) {\displaystyle (X,\leq )} is well-quasi-order, then ( X k , ≤ k ) {\displaystyle (X^{k},\leq ^{k})} is also a well-quasi-order for all k {\displaystyle k} . Let X {\displaystyle X} be an arbitrary finite set with at least two elements. The set X ∗ {\displaystyle X^{*}} of words over X {\displaystyle X} ordered lexicographically (as in a dictionary) is not a well-quasi-order because it contains the infinite decreasing sequence b , a b , a a b , a a a b , … {\displaystyle b,ab,aab,aaab,\ldots } . Similarly, X ∗ {\displaystyle X^{*}} ordered by the prefix relation is not a well-quasi-order, because the previous sequence is an infinite antichain of this partial order. However, X ∗ {\displaystyle X^{*}} ordered by the subsequence relation is a well partial order. (If X {\displaystyle X} has only one element, these three partial orders are identical.) More generally, ( X ∗ , ≤ ) {\displaystyle (X^{*},\leq )} , the set of finite X {\displaystyle X} -sequences ordered by embedding is a well-quasi-order if and only if ( X , ≤ ) {\displaystyle (X,\leq )} is a well-quasi-order (Higman's lemma). Recall that one embeds a sequence u {\displaystyle u} into a sequence v {\displaystyle v} by finding a subsequence of v {\displaystyle v} that has the same length as u {\displaystyle u} and that dominates it term by term. When ( X , = ) {\displaystyle (X,=)} is an unordered set, u ≤ v {\displaystyle u\leq v} if and only if u {\displaystyle u} is a subsequence of v {\displaystyle v} .
( X ω , ≤ ) {\displaystyle (X^{\omega },\leq )} , the set of infinite sequences over a well-quasi-order ( X , ≤ ) {\displaystyle (X,\leq )} , 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 ( X , ≤ ) {\displaystyle (X,\leq )} is a wqo (Kruskal's tree theorem). Embedding between infinite trees with nodes labeled by elements of a wqo ( X , ≤ ) {\displaystyle (X,\leq )} 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.
Constructing new wpo's from given ones Let X 1 {\displaystyle X_{1}} and X 2 {\displaystyle X_{2}} be two disjoint wpo sets. Let Y = X 1 ∪ X 2 {\displaystyle Y=X_{1}\cup X_{2}} , and define a partial order on Y {\displaystyle Y} by letting y 1 ≤ Y y 2 {\displaystyle y_{1}\leq _{Y}y_{2}} if and only if y 1 , y 2 ∈ X i {\displaystyle y_{1},y_{2}\in X_{i}} for the same i ∈ { 1 , 2 } {\displaystyle i\in \{1,2\}} and y 1 ≤ X i y 2 {\displaystyle y_{1}\leq _{X_{i}}y_{2}} . Then Y {\displaystyle Y} is wpo, and o ( Y ) = o ( X 1 ) ⊕ o ( X 2 ) {\displaystyle o(Y)=o(X_{1})\oplus o(X_{2})} , where ⊕ {\displaystyle \oplus } denotes natural sum of ordinals. Given wpo sets X 1 {\displaystyle X_{1}} and X 2 {\displaystyle X_{2}} , define a partial order on the Cartesian product Y = X 1 × X 2 {\displaystyle Y=X_{1}\times X_{2}} , by letting ( a 1 , a 2 ) ≤ Y ( b 1 , b 2 ) {\displaystyle (a_{1},a_{2})\leq _{Y}(b_{1},b_{2})} if and only if a 1 ≤ X 1 b 1 {\displaystyle a_{1}\leq _{X_{1}}b_{1}} and a 2 ≤ X 2 b 2 {\displaystyle a_{2}\leq _{X_{2}}b_{2}} . Then Y {\displaystyle Y} is wpo (this is a generalization of Dickson's lemma), and o ( Y ) = o ( X 1 ) ⊗ o ( X 2 ) {\displaystyle o(Y)=o(X_{1})\otimes o(X_{2})} , where ⊗ {\displaystyle \otimes } denotes natural product of ordinals. Given a wpo set X {\displaystyle X} , let X ∗ {\displaystyle X^{*}} be the set of finite sequences of elements of X {\displaystyle X} , partially ordered by the subsequence relation. Meaning, let ( x 1 , … , x n ) ≤ X ∗ ( y 1 , … , y m ) {\displaystyle (x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})} if and only if there exist indices 1 ≤ i 1 < ⋯ < i n ≤ m {\displaystyle 1\leq i_{1}<\cdots <i_{n}\leq m} such that x j ≤ X y i j {\displaystyle x_{j}\leq _{X}y_{i_{j}}} for each 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} . By Higman's lemma, X ∗ {\displaystyle X^{*}} is wpo. The ordinal type of X ∗ {\displaystyle X^{*}} is o ( X ∗ ) = { ω ω o ( X ) − 1 , o ( X ) finite ; ω ω o ( X ) + 1 , o ( X ) = ε α + n for some α and some finite n ; ω ω o ( X ) , otherwise . {\displaystyle o(X^{*})={\begin{cases}\omega ^{\omega ^{o(X)-1}},&o(X){\text{ finite}};\\\omega ^{\omega ^{o(X)+1}},&o(X)=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(X)}},&{\text{otherwise}}.\end{cases}}}
Given a wpo set X {\displaystyle X} , let T ( X ) {\displaystyle T(X)} be the set of all finite rooted trees whose vertices are labeled by elements of X {\displaystyle X} . Partially order T ( X ) {\displaystyle T(X)} by the tree embedding relation. By Kruskal's tree theorem, T ( X ) {\displaystyle T(X)} is wpo. This result is nontrivial even for the case | X | = 1 {\displaystyle |X|=1} (which corresponds to unlabeled trees), in which case o ( T ( X ) ) {\displaystyle o(T(X))} equals the small Veblen ordinal. In general, for o ( X ) {\displaystyle o(X)} countable, we have the upper bound o ( T ( X ) ) ≤ ϑ ( Ω ω o ( X ) ) {\displaystyle o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))} in terms of the ϑ {\displaystyle \vartheta } ordinal collapsing function. (The small Veblen ordinal equals ϑ ( Ω ω ) {\displaystyle \vartheta (\Omega ^{\omega })} in this ordinal notation.)
Wqo's versus well partial orders 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 Z {\displaystyle \mathbb {Z} } by divisibility, we end up with n ≡ m {\displaystyle n\equiv m} if and only if n = ± m {\displaystyle n=\pm m} , so that ( Z , | ) ≈ ( N , | ) {\displaystyle (\mathbb {Z} ,|)\approx (\mathbb {N} ,|)} .
Infinite increasing subsequences If ( X , ≤ ) {\displaystyle (X,\leq )} is wqo then every infinite sequence x 0 , x 1 , x 2 , … , {\displaystyle x_{0},x_{1},x_{2},\ldots ,} contains an infinite increasing subsequence x n 0 ≤ x n 1 ≤ x n 2 ≤ ⋯ {\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots } (with n 0 < n 1 < n 2 < ⋯ {\displaystyle n_{0}<n_{1}<n_{2}<\cdots } ). Such a subsequence is sometimes called perfect. This can be proved by a Ramsey argument: given some sequence ( x i ) i {\displaystyle (x_{i})_{i}} , consider the set I {\displaystyle I} of indexes i {\displaystyle i} such that x i {\displaystyle x_{i}} has no larger or equal x j {\displaystyle x_{j}} to its right, i.e., with i < j {\displaystyle i<j} . If I {\displaystyle I} is infinite, then the I {\displaystyle I} -extracted subsequence contradicts the assumption that X {\displaystyle X} is wqo. So I {\displaystyle I} is finite, and any x n {\displaystyle x_{n}} with n {\displaystyle n} larger than any index in I {\displaystyle I} 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 Given a quasiordering ( X , ≤ ) {\displaystyle (X,\leq )} the quasiordering ( P ( X ) , ≤ + ) {\displaystyle (P(X),\leq ^{+})} defined by A ≤ + B ⟺ ∀ a ∈ A , ∃ b ∈ B , a ≤ b {\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b} is well-founded if and only if ( X , ≤ ) {\displaystyle (X,\leq )} is a wqo. A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by x ∼ y ⟺ x ≤ y ∧ y ≤ x {\displaystyle x\sim y\iff x\leq y\land y\leq x} ) has no infinite descending sequences or antichains. (This can be proved using a Ramsey argument as above.) Given a well-quasi-ordering ( X , ≤ ) {\displaystyle (X,\leq )} , any sequence of upward-closed subsets S 0 ⊆ S 1 ⊆ ⋯ ⊆ X {\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X} eventually stabilises (meaning there exists n ∈ N {\displaystyle n\in \mathbb {N} } such that S n = S n + 1 = ⋯ {\displaystyle S_{n}=S_{n+1}=\cdots } ; a subset S ⊆ X {\displaystyle S\subseteq X} is called upward-closed if ∀ x , y ∈ X , x ≤ y ∧ x ∈ S ⇒ y ∈ S {\displaystyle \forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S} ): assuming the contrary ∀ i ∈ N , ∃ j ∈ N , j > i , ∃ x ∈ S j ∖ S i {\displaystyle \forall i\in \mathbb {N} ,\exists j\in \mathbb {N} ,j>i,\exists x\in S_{j}\setminus S_{i}} , a contradiction is reached by extracting an infinite non-ascending subsequence. Given a well-quasi-ordering ( X , ≤ ) {\displaystyle (X,\leq )} , any subset S {\displaystyle S} of X {\displaystyle X} has a finite number of minimal elements with respect to ≤ {\displaystyle \leq } , for otherwise the minimal elements of S {\displaystyle S} would constitute an infinite antichain.
See also Better-quasi-ordering Prewellordering – Set theory concept Well-order – Class of mathematical orderings
Notes
References
Further reading Dickson, L. E. (1913). "Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors". American Journal of Mathematics. 35 (4): 413–422. doi:10.2307/2370405. JSTOR 2370405. Higman, G. (1952). "Ordering by divisibility in abstract algebras". Proceedings of the London Mathematical Society. 2: 326–336. doi:10.1112/plms/s3-2.1.326. Kruskal, J. B. (1972). "The theory of well-quasi-ordering: A frequently discovered concept". Journal of Combinatorial Theory. Series A. 13 (3): 297–305. doi:10.1016/0097-3165(72)90063-5. Ketonen, Jussi (1978). "The structure of countable Boolean algebras". Annals of Mathematics. 108 (1): 41–89. doi:10.2307/1970929. JSTOR 1970929. Gallier, Jean H. (1991). "What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory". Annals of Pure and Applied Logic. 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E.