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 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 such that no w_i embeds into a later w_j. Then there exists an infinite bad sequence of words 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. Since no w_i can be the empty word, we can write for and. Since \Sigma is well-quasi-ordered, the sequence of leading symbols must contain an infinite increasing sequence with. Now consider the sequence of words Because z_{i_1} is shorter than , 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. And similarly, it cannot be that u=z_{i_j} and v=z_{i_k}, j<k, because then would embed into. 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:

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.

Citations