Higman's lemma

In mathematics, Higman's lemma states that the set ${\mathrm{\Sigma }}^{*}$ of finite sequences over a finite alphabet $\mathrm{\Sigma }$, as partially ordered by the subsequence relation, is a well partial order. That is, if $w_1,w_2,\dots \in {\mathrm{\Sigma }}^{*}$ is an infinite sequence of words over a finite alphabet $\mathrm{\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 the set of sequences is well-quasi-ordered even when $\mathrm{\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 $\mathrm{\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 $\mathrm{\Sigma }$ be a well-quasi-ordered alphabet of symbols (in particular, $\mathrm{\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,\dots \in {\mathrm{\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,\dots )$ 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,\dots ,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 \mathrm{\Sigma }$ and $z_i\in {\mathrm{\Sigma }}^{*}$. Since $\mathrm{\Sigma }$ is well-quasi-ordered, the sequence of leading symbols $a_1,a_2,a_3,\dots$ must contain an infinite increasing sequence $a_{i_1}\le a_{i_2}\le a_{i_3}\le \cdots$ with $i_1<i_2<i_3<\cdots$.

Now consider the sequence of words $$w_1,\dots ,w_{i_1-1},z_{i_1},z_{i_2},z_{i_3},\dots .$$ 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 ${\mathrm{\Sigma }}^{*}$ is related to the ordinal type of $\mathrm{\Sigma }$ as follows: $$o({\mathrm{\Sigma }}^{*})=\{\begin{array}{cc}{\omega }^{{\omega }^{o(\mathrm{\Sigma })-1}},& o(\mathrm{\Sigma })\text{ finite};\\ {\omega }^{{\omega }^{o(\mathrm{\Sigma })+1}},& o(\mathrm{\Sigma })={\epsilon }_{\alpha }+n\text{ for some }\alpha \text{ and some finite }n;\\ {\omega }^{{\omega }^{o(\mathrm{\Sigma })}},& \text{otherwise}.\end{array}$$

Reverse-mathematical calibration

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

References

• Template:Citation

Citations

Template:Combin-stub