Higman's lemma

Not to be confused with Higman's theorem.

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

Proof

Let $\Sigma$ be a well-quasi-ordered alphabet of symbols (in particular, $\Sigma$ could be finite and ordered by the identity relation). Suppose for a contradiction that there exist infinite bad sequences, i.e. infinite sequences of words $w_{1},w_{2},w_{3},\ldots \in \Sigma ^{*}$ such that no $w_{i}$ embeds into a later $w_{j}$. Then there exists an infinite bad sequence of words $W=(w_{1},w_{2},w_{3},\ldots )$ that is minimal in the following sense: $w_{1}$ is a word of minimum length from among all words that start infinite bad sequences; $w_{2}$ is a word of minimum length from among all infinite bad sequences that start with $w_{1}$; $w_{3}$ is a word of minimum length from among all infinite bad sequences that start with $w_{1},w_{2}$; and so on. In general, $w_{i}$ is a word of minimum length from among all infinite bad sequences that start with $w_{1},\ldots ,w_{i-1}$.

Since no $w_{i}$ can be the empty word, we can write $w_{i}=a_{i}z_{i}$ for $a_{i}\in \Sigma$ and $z_{i}\in \Sigma ^{*}$. Since $\Sigma$ is well-quasi-ordered, the sequence of leading symbols $a_{1},a_{2},a_{3},\ldots$ must contain an infinite increasing sequence $a_{i_{1}}\leq a_{i_{2}}\leq a_{i_{3}}\leq \cdots$ with $i_{1}<i_{2}<i_{3}<\cdots$.

Now consider the sequence of words $$w_{1},\ldots ,w_{{i_{1}}-1},z_{i_{1}},z_{i_{2}},z_{i_{3}},\ldots .$$ Because $z_{i_{1}}$ is shorter than $w_{i_{1}}=a_{i_{1}}z_{i_{1}}$, this sequence is "more minimal" than $W$, and so it must contain a word $u$ that embeds into a later word $v$. But $u$ and $v$ cannot both be $w_{j}$'s, because then the original sequence $W$ would not be bad. Similarly, it cannot be that $u$ is a $w_{j}$ and $v$ is a $z_{i_{k}}$, because then $w_{j}$ would also embed into $w_{i_{k}}=a_{i_{k}}z_{i_{k}}$. And similarly, it cannot be that $u=z_{i_{j}}$ and $v=z_{i_{k}}$, $j<k$, because then $w_{i_{j}}=a_{i_{j}}z_{i_{j}}$ would embed into $w_{i_{k}}=a_{i_{k}}z_{i_{k}}$. In every case we arrive at a contradiction.

Ordinal type

The ordinal type of $\Sigma ^{*}$ is related to the ordinal type of $\Sigma$ as follows: $$o(\Sigma ^{*})={\begin{cases}\omega ^{\omega ^{o(\Sigma )-1}},&o(\Sigma ){\text{ finite}};\\\omega ^{\omega ^{o(\Sigma )+1}},&o(\Sigma )=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(\Sigma )}},&{\text{otherwise}}.\end{cases}}$$

Reverse-mathematical calibration

Higman's lemma has been reverse mathematically calibrated (in terms of subsystems of second-order arithmetic) as equivalent to $ACA_{0}$ over the base theory $RCA_{0}$.

References

• Higman, Graham (1952), "Ordering by divisibility in abstract algebras", Proceedings of the London Mathematical Society, (3), 2 (7): 326–336, doi:10.1112/plms/s3-2.1.326