Well-quasi-ordering

Summary

A well-quasi-ordering is a preorder in which every infinite sequence $x_1, x_2, \ldots$ has indices $i < j$ with $x_i \le x_j$. Equivalently, it is well-founded and has no infinite antichain. Well-quasi-orders give finiteness results: every upward closed set is the upward closure of finitely many of its elements. Basic examples are $\N^k$ with the product order (Dickson's lemma), finite words under subword embedding (Higman's lemma) and finite trees under embedding (Kruskal's tree theorem).