Well-quasi-ordering

A well partial order, or a '''wpo''', is a wqo that is a proper ordering relation, i.e., it is Antisymmetric .

Another way of defining wqo sets is to say that they do not contain infinite ''strictly decreasing'' sequences (of the form

x_0

x_1

x_2

>…)
nor infinite sequences of ''pairwise incomparable'' elements. Hence a quasi-order (

X

,≤) is wqo iff it is Well-founded and has no infinite Antichains .

EXAMPLES

$(\mathbb{N}, \le)$ , the set of natural numbers with standard ordering, is a well partial order. $(\mathbb{Z}, \le)$ , the set of positive and negative integers, is not: it is not well-founded.

$(\mathbb{N}, \mid)$ , the set of natural numbers ordered by divisibility, is not a well partial order: the prime numbers are an infinite antichain.

The set of words ordered lexicographically, i.e., as in a dictionary, is not a wqo: it is not well-founded as witnessed by the decreasing sequence $b$ , $ab$ , $aab$ , $aaab$ , ... If we consider the prefix ordering for comparing words, then the previous sequence becomes an infinite antichain.

$(\mathbb{N}^k, \le)$ , the set of vectors of $k$ natural numbers with component-wise ordering, is a well partial order ( Dickson's Lemma ). More generally, if $(X, \le)$ is wqo, then for any $k$ , $(X^k,\le^k)$ is wqo.

$(X^---,\le)$ , the set of finite $X$ -sequences ordered by Embedding is a wqo iff $(X, \le)$ is ( 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 a finite unordered set, $u\le v$ iff $u$ is a subsequence of $v$ .

$(X^\omega,\le)$ , the set of infinite sequences over a wqo $(X, \le)$ , ordered by embedding is not a wqo 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 $(X, \le)$ is a wqo ( Kruskal's Tree Theorem ).

Finite graphs ordered by a notion of embedding called " Graph Minor " is a wqo ( Robertson-Seymour Theorem ).

WQO'S VERSUS WELL PARTIAL ORDERS

In practice, the wqo's one manipulates are almost always orderings (see examples above), but the theory is technically smoother if we do not require antisymmetry, so it is built with wqo's as the basic notion.

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

\mathbb{Z}

by divisibility, we end up with

n\equiv m

iff

n=\pm m

, so that

(\mathbb{Z},\mid)\;\;\approx\;\;(\mathbb{N},\mid)

.

INFINITE INCREASING SUBSEQUENCES

If (

X

, ≤) is wqo then every infinite sequence

x_0

x_1

x_2

, … contains an infinite increasing subsequence

x_{n0}

≤

x_{n1}

≤

x_{n2}

≤…
(with

{n0}

{n1}

{n2}

<…).
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

i . If I is infinite, then the I -extracted subsequence contradicts the assumption that X is wqo. So I is finite, and any x_n with n larger than any index in 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.

REFERENCES

# ¹
# ²
# ³
# ⁴

SEE ALSO

Prewellordering

Well-order

Information About

Well-quasi-ordering