In classical mathematics, a well-quasi-order is a preorder such that for any infinite sequence in , there exist with and . Another way of expressing this condition is:
There are no infinite antichains in : if is a sequence in , then there exist some pair of elements , that are comparable, i.e., either or , and
There is no strictly decreasing sequence in : if in , then there exists such that for all .
One motivation for this notion is given by the following theorem:
Let be a quasi-order (i.e., a preorder). Define a partial order on the power set by if . Then is a well-founded relation if and only if is a well-quasi-ordering.
The collection of finite simple graphs is well-quasi-ordered by the graph minor relation. This is the celebrated Robertson-Seymour Graph Minor Theorem.
Revised on November 1, 2012 13:18:06
by Urs Schreiber