nLab
well-quasi-order

Definition

In classical mathematics, a well-quasi-order is a preorder $(P,\le )$ such that for any infinite sequence $x_i$ in $P$, there exist $i,j$ with $i<j$ and $x_i\le x_j$. Another way of expressing this condition is:

• There are no infinite antichains in $P$: if $x_i$ is a sequence in $P$, then there exist some pair of elements $x_i$, $x_j$ that are comparable, i.e., either $x_i\le x_j$ or $x_j\le x_i$, and

• There is no strictly decreasing sequence in $P$: if $x_0\ge x_1\ge \dots$ in $P$, then there exists $n$ such that $x_i\le x_{i+1}$ for all $i\ge n$.

One motivation for this notion is given by the following theorem:

Theorem

Let $(X,\le )$ be a quasi-order (i.e., a preorder). Define a partial order on the power set $P(X)$ by $A{\le }^{+}B$ if ${\forall }_{a:A}{\exists }_{b:B}(a\le b)$. Then ${\le }^{+}$ is a well-founded relation if and only if $\le$ is a well-quasi-ordering.

Example

The collection of finite simple graphs is well-quasi-ordered by the graph minor relation. This is the celebrated Robertson-Seymour Graph Minor Theorem.

References

• Wikipedia article