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 well-quasi-ordered. 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 this remains true when ${\displaystyle \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 ${\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.

Proof

Let ${\displaystyle \Sigma }$ be a well-quasi-ordered alphabet of symbols (in particular, ${\displaystyle \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 ${\displaystyle w_{1},w_{2},w_{3},\ldots \in \Sigma ^{*}}$ such that no ${\displaystyle w_{i}}$ embeds into a later ${\displaystyle w_{j}}$. Then there exists an infinite bad sequence of words ${\displaystyle W=(w_{1},w_{2},w_{3},\ldots )}$ that is minimal in the following sense: ${\displaystyle w_{1}}$ is a word of minimum length from among all words that start infinite bad sequences; ${\displaystyle w_{2}}$ is a word of minimum length from among all infinite bad sequences that start with ${\displaystyle w_{1}}$; ${\displaystyle w_{3}}$ is a word of minimum length from among all infinite bad sequences that start with ${\displaystyle w_{1},w_{2}}$; and so on. In general, ${\displaystyle w_{i}}$ is a word of minimum length from among all infinite bad sequences that start with ${\displaystyle w_{1},\ldots ,w_{i-1}}$.

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

Now consider the sequence of words

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

Ordinal type

The ordinal type of ${\displaystyle \Sigma ^{*}}$ is related to the ordinal type of ${\displaystyle \Sigma }$ as follows:^[1][2]

Reverse-mathematical calibration

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

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

Citations