(0,1)-category

(0,1)-topos

# Well-quasi-orders

## Definition

In classical mathematics, a well-quasi-order is a preorder $\left(P,\le \right)$ such that for any infinite sequence ${x}_{i}$ in $P$, there exist $i,j$ with $i 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 $\left(X,\le \right)$ be a quasi-order (i.e., a preorder). Define a partial order on the power set $P\left(X\right)$ by $A{\le }^{+}B$ if ${\forall }_{a:A}{\exists }_{b:B}\left(a\le b\right)$. 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

Revised on November 1, 2012 13:18:06 by Urs Schreiber (131.174.41.102)