well-quasi-ordering

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 $\backslash le$ is said to be well-founded if the corresponding strict order $x\backslash le\; y\backslash land\; y\backslash 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 $\backslash le$ for a set $X$ one can define a quasiorder $\backslash le^\{+\}$ on $X$'s power set $P(X)$ by setting $A\; \backslash le^\{+\}\; B$ if and only if for each element of $A$ one can find some element of $B$ that is larger than it with respect to $\backslash le$. One can show that this quasiordering on $P(X)$ needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is.

A well-quasi-ordering on a set $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,\; \backslash ldots$ from $X$ contains an increasing pair $x\_i\; \backslash le\; x\_j$ with . The set $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>\; \backslash cdots$){{ref|a}} 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.

Let $X$ be well partially ordered. A (necessarily finite) sequence $(x\_1,\; x\_2,\; \backslash ldots,\; x\_n)$ of elements of $X$ that contains no pair $x\_i\; \backslash le\; x\_j$ with is usually called a bad sequence. The tree of bad sequences $T\_X$ is the tree that contains a vertex for each bad sequence, and an edge joining each nonempty bad sequence $(x\_1,\; \backslash ldots,\; x\_\{n-1\},\; x\_n)$ to its parent $(x\_1,\; \backslash ldots,\; x\_\{n-1\})$. The root of $T\_X$ corresponds to the empty sequence. Since $X$ contains no infinite bad sequence, the tree $T\_X$ contains no infinite path starting at the root.{{cn|reason=This is far from being obvious, and requires a (reference to a) proof.|date=February 2024}} Therefore, each vertex $v$ of $T\_X$ has an ordinal height $o(v)$, which is defined by transfinite induction as $o(v)\; =\; \backslash lim\_\{w\; \backslash mathrm\{\backslash \; child\backslash \; of\backslash \; \}\; v\}\; (o(w)+1)$. The ordinal type of $X$, denoted $o(X)$, is the ordinal height of the root of $T\_X$.

A linearization of $X$ is an extension of the partial order into a total order. It is easy to verify that $o(X)$ is an upper bound on the ordinal type of every linearization of $X$. De Jongh and Parikh{{cite journal |last1=de Jongh |first1=Dick H. G. |last2=Parikh |first2=Rohit |title=Well-partial orderings and hierarchies |journal=Indagationes Mathematicae (Proceedings) |date=1977 |volume=80 |issue=3 |pages=195-207 |doi=10.1016/1385-7258(77)90067-1|doi-access=free }} proved that in fact there always exists a linearization of $X$ that achieves the maximal ordinal type $o(X)$.

File:Integers-line.svg

File:Infinite lattice of divisors.svg of the natural numbers ordered by divisibility]]

File:N-Quadrat, gedreht.svg

• $(\backslash N,\; \backslash le)$, the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However, $(\backslash Z,\; \backslash le)$, the set of positive and negative integers, is not a well-quasi-order, because it is not well-founded (see Pic.1).
• $(\backslash 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).
• $(\backslash N^k,\; \backslash le)$, the set of vectors of $k$ natural numbers (where $k$ is finite) with component-wise ordering, is a well partial order (Dickson's lemma; see Pic.3). More generally, if $(X,\; \backslash le)$ is well-quasi-order, then $(X^k,\backslash le^k)$ is also a well-quasi-order for all $k$.
• Let $X$ be an arbitrary finite set with at least two elements. The set $X^*$ of words over $X$ ordered lexicographically (as in a dictionary) is not a well-quasi-order because it contains the infinite decreasing sequence $b,\; ab,\; aab,\; aaab,\; \backslash ldots$. Similarly, $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^*$ ordered by the subsequence relation is a well partial order.{{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. (If $X$ has only one element, these three partial orders are identical.)
• More generally, $(X^*,\backslash le)$, the set of finite $X$-sequences ordered by embedding is a well-quasi-order if and only if $(X,\; \backslash le)$ is a well-quasi-order (Higman's lemma). Recall that one embeds a sequence $u$ into a sequence $v$ by finding a subsequence of $v$ that has the same length as $u$ and that dominates it term by term. When $(X,=)$ is an unordered set, $u\backslash le\; v$ if and only if $u$ is a subsequence of $v$.
• $(X^\backslash omega,\backslash le)$, the set of infinite sequences over a well-quasi-order $(X,\; \backslash le)$, 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,\; \backslash le)$ is a wqo (Kruskal's tree theorem).
• Embedding between infinite trees with nodes labeled by elements of a wqo $(X,\; \backslash le)$ 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,{{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 }}. as do the cographs ordered by induced subgraphs.{{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}}.

Let $X\_1$ and $X\_2$ be two disjoint wpo sets. Let $Y=X\_1\backslash cup\; X\_2$, and define a partial order on $Y$ by letting $y\_1\backslash le\_Y\; y\_2$ if and only if $y\_1,y\_2\backslash in\; X\_i$ for the same $i\backslash in\backslash \{1,2\backslash \}$ and $y\_1\; \backslash le\_\{X\_i\}\; y\_2$. Then $Y$ is wpo, and $o(Y)\; =\; o(X\_1)\; \backslash oplus\; o(X\_2)$, where $\backslash oplus$ denotes natural sum of ordinals.

Given wpo sets $X\_1$ and $X\_2$, define a partial order on the Cartesian product $Y=X\_1\backslash times\; X\_2$, by letting $(a\_1,a\_2)\backslash le\_Y\; (b\_1,b\_2)$ if and only if $a\_1\backslash le\_\{X\_1\}\; b\_1$ and $a\_2\backslash le\_\{X\_2\}\; b\_2$. Then $Y$ is wpo (this is a generalization of Dickson's lemma), and $o(Y)\; =\; o(X\_1)\backslash otimes\; o(X\_2)$, where $\backslash otimes$ denotes natural product of ordinals.

Given a wpo set $X$, let $X^*$ be the set of finite sequences of elements of $X$, partially ordered by the subsequence relation. Meaning, let $(x\_1,\backslash ldots,x\_n)\backslash le\_\{X^*\}\; (y\_1,\backslash ldots,y\_m)$ if and only if there exist indices

Given a wpo set $X$, let $T(X)$ be the set of all finite rooted trees whose vertices are labeled by elements of $X$. Partially order $T(X)$ by the tree embedding relation. By Kruskal's tree theorem, $T(X)$ is wpo. This result is nontrivial even for the case $|X|=1$ (which corresponds to unlabeled trees), in which case $o(T(X))$ equals the small Veblen ordinal. In general, for $o(X)$ countable, we have the upper bound $o(T(X))\backslash le\backslash vartheta(\backslash Omega^\backslash omega\; o(X))$ in terms of the $\backslash vartheta$ ordinal collapsing function. (The small Veblen ordinal equals $\backslash vartheta(\backslash Omega^\backslash omega)$ in this ordinal notation.){{cite journal |last1=Rathjen |first1=Michael |last2=Weiermann |first2=Andreas |title=Proof-theoretic investigations on Kruskal's theorem |journal=Annals of Pure and Applied Logic |date=1993 |volume=60 |pages=49-88 |doi=10.1016/0168-0072(93)90192-G|doi-access=free }}

In practice, the wqo's one manipulates are quite often not orderings (see examples above), and the theory is technically smoother{{fact|date=March 2017}} 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 $\backslash Z$ by divisibility, we end up with $n\backslash equiv\; m$ if and only if $n=\backslash pm\; m$, so that $(\backslash Z,|)\backslash approx(\backslash N,|)$.

If $(X,\; \backslash le)$ is wqo then every infinite sequence $x\_0,\; x\_1,\; x\_2,\; \backslash ldots,$ contains an infinite increasing subsequence $x\_\{n\_0\}\; \backslash le\; x\_\{n\_1\}\backslash le\; x\_\{n\_2\}\; \backslash le\; \backslash cdots$ (with ). Such a subsequence is sometimes called perfect.

This can be proved by a Ramsey argument: given some sequence $(x\_i)\_i$, consider the set $I$ of indexes $i$ such that $x\_i$ has no larger or equal $x\_j$ to its right, i.e., with

The existence of such infinite increasing subsequences is sometimes taken as a definition for well-quasi-ordering, leading to an equivalent notion.

• Given a quasiordering $(X,\backslash le)$ the quasiordering $(P(X),\; \backslash le^+)$ defined by $A\; \backslash le^+\; B\; \backslash iff\; \backslash forall\; a\; \backslash in\; A,\; \backslash exists\; b\; \backslash in\; B,\; a\; \backslash le\; b$ is well-founded if and only if $(X,\backslash le)$ is a wqo.
• A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by $x\; \backslash sim\; y\; \backslash iff\; x\backslash le\; y\; \backslash land\; y\; \backslash le\; x$) has no infinite descending sequences or antichains. (This can be proved using a Ramsey argument as above.)
• Given a well-quasi-ordering $(X,\backslash le)$, any sequence of upward-closed subsets $S\_0\; \backslash subseteq\; S\_1\; \backslash subseteq\; \backslash cdots\; \backslash subseteq\; X$ eventually stabilises (meaning there exists $n\; \backslash in\; \backslash N$ such that $S\_n\; =\; S\_\{n+1\}\; =\; \backslash cdots$; a subset $S\; \backslash subseteq\; X$ is called upward-closed if $\backslash forall\; x,y\; \backslash in\; X,\; x\; \backslash le\; y\; \backslash wedge\; x\; \backslash in\; S\; \backslash Rightarrow\; y\; \backslash in\; S$): assuming the contrary $\backslash forall\; i\; \backslash in\; \backslash N,\; \backslash exists\; j\; \backslash in\; \backslash N,\; j\; >\; i,\; \backslash exists\; x\; \backslash in\; S\_j\; \backslash setminus\; S\_i$, a contradiction is reached by extracting an infinite non-ascending subsequence.
• Given a well-quasi-ordering $(X,\backslash le)$, any subset $S$ of $X$ has a finite number of minimal elements with respect to $\backslash le$, for otherwise the minimal elements of $S$ would constitute an infinite antichain.

• {{annotated link|Better-quasi-ordering}}
• {{annotated link|Prewellordering}}
• {{annotated link|Well-order}}

{{note|a}}Here x < y means: $x\backslash le\; y$ and $x\; \backslash neq\; y.$

{{Reflist|

refs=

{{cite journal | last = Forster | first = Thomas | authorlink = Thomas Forster (mathematician)| title= Better-quasi-orderings and coinduction | journal = Theoretical Computer Science | year = 2003 | volume = 309 | pages= 111–123 | doi= 10.1016/S0304-3975(03)00131-2 | issue = 1–3| doi-access = }}

}}

• {{cite journal | last = Dickson | first = L. E. | authorlink = Leonard Dickson | title=Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors | journal=American Journal of Mathematics | year = 1913 | volume = 35 | pages=413–422 | doi=10.2307/2370405 | jstor = 2370405 | issue = 4 }}
• {{cite journal | last = Higman | first = G. |authorlink = Graham Higman | title=Ordering by divisibility in abstract algebras | journal=Proceedings of the London Mathematical Society | year=1952 | volume=2 | pages=326–336 | doi=10.1112/plms/s3-2.1.326}}
• {{cite journal | authorlink = Joseph Kruskal | last=Kruskal |first= J. B. | title=The theory of well-quasi-ordering: A frequently discovered concept | journal=Journal of Combinatorial Theory | series = Series A | year=1972 | volume=13 | pages=297–305 | doi=10.1016/0097-3165(72)90063-5 | issue = 3| doi-access=free }}
• {{cite journal | last = Ketonen | first = Jussi | title = The structure of countable Boolean algebras | journal = Annals of Mathematics | volume = 108 | pages = 41–89 | year = 1978 | doi = 10.2307/1970929 | jstor = 1970929 | issue = 1}}
• {{cite book | last=Milner | first = E. C. | authorlink = Eric Charles Milner | year=1985 | chapter = Basic WQO- and BQO-theory | editor-first=I.|editor-last=Rival|editor-link=Ivan Rival | title = Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and Its Applications | pages=487–502 | publisher=D. Reidel Publishing Co. | isbn=90-277-1943-8}}
• {{cite journal | last = Gallier | first = Jean H. |authorlink= Jean Gallier | title= What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory | journal = Annals of Pure and Applied Logic | year = 1991 | volume = 53 | pages= 199–260 | doi= 10.1016/0168-0072(91)90022-E | issue = 3| doi-access = }}

{{Order theory}}

Category:Order theory

Category:Wellfoundedness