Higman's lemma

Remarks

The usual proof is the minimal bad sequence argument of Nash-Williams. Assume a bad sequence exists, and choose one in which each word is as short as possible given the earlier ones. Remove the first letter of each word; since $X$ is well-quasi-ordered, an infinite subsequence has non-decreasing first letters. The shortened words of this subsequence, put after the beginning of the minimal sequence, give a bad sequence that contradicts minimality.

Example: take $X = \set{a, b}$ with equality as the order. Then $u \le^* v$ means that $u$ is a subsequence of $v$, a scattered subword. So in every infinite list of words over two letters, some word is a scattered subword of a later one.

A consequence concerns any language $L \subseteq X^*$ over a finite alphabet. The set of words having a scattered subword in $L$ is regular, since it is generated by its finitely many minimal elements.

Going deeper

For a student

The lemma is the first step from simple well-quasi-orders, such as finite sets and $\N$, to orders on structured objects. Kruskal's tree theorem extends it from words to finite trees, and its proof uses Higman's lemma on the sequences of subtrees. In computer science it gives termination and decidability results for well-structured transition systems such as lossy channel systems.