nLab
well-quasi-order

Well-quasi-orders

Definition

In classical mathematics, a well-quasi-order is a preorder (P,)(P, \leq) such that for any infinite sequence x ix_i in PP, there exist i,ji, j with i<ji \lt j and x ix jx_i \leq x_j. Another way of expressing this condition is:

  • There are no infinite antichains in PP: if x ix_i is a sequence in PP, then there exist some pair of elements x ix_i, x jx_j that are comparable, i.e., either x ix jx_i \leq x_j or x jx ix_j \leq x_i, and

  • There is no strictly decreasing sequence in PP: if x 0x 1x_0 \geq x_1 \geq \ldots in PP, then there exists nn such that x ix i+1x_i \leq x_{i+1} for all ini \geq n.

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

Theorem

Let (X,)(X, \leq) be a quasi-order (i.e., a preorder). Define a partial order on the power set P(X)P(X) by A +BA \leq^+ B if a:A b:B(ab)\forall_{a\colon A} \exists_{b\colon B} (a \leq b). Then +\leq^+ is a well-founded relation if and only if \leq 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)