Higman's lemma

In mathematics, Higman's lemma states that the set ${\displaystyle \Sigma ^{*}}$ of finite sequences over a finite alphabet ${\displaystyle \Sigma }$, as partially ordered by the subsequence relation, is a well partial order. That is, if ${\displaystyle w_{1},w_{2},\ldots \in \Sigma ^{*}}$ is an infinite sequence of words over a finite alphabet ${\displaystyle \Sigma }$, then there exist indices ${\displaystyle i<j}$ such that ${\displaystyle w_{i}}$ can be obtained from ${\displaystyle w_{j}}$ by deleting some (possibly none) symbols. More generally the set of sequences is well-quasi-ordered even when ${\displaystyle \Sigma }$ is not necessarily finite, but is itself well-quasi-ordered, and the subsequence ordering is generalized into an "embedding" quasi-order that allows the replacement of symbols by earlier symbols in the well-quasi-ordering of ${\displaystyle \Sigma }$. This is a special case of the later Kruskal's tree theorem. It is named after Graham Higman, who published it in 1952.