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:
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