Higman's lemma

In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered. That is, if [math]\displaystyle{ w_1, w_2, \ldots }[/math] is an infinite sequence of words over some fixed finite alphabet, then there exist indices [math]\displaystyle{ i \lt j }[/math] such that [math]\displaystyle{ w_i }[/math] can be obtained from [math]\displaystyle{ w_j }[/math] by deleting some (possibly none) symbols. More generally this remains true when the alphabet is not necessarily finite, but is itself well-quasi-ordered, and the subsequence relation allows the replacement of symbols by earlier symbols in the well-quasi-ordering of labels. This is a special case of the later Kruskal's tree theorem. It is named after Graham Higman, who published it in 1952.

Reverse-mathematical calibration

Higman's lemma has been reverse mathematically calibrated (in terms of subsystems of second-order arithmetic) as equivalent to [math]\displaystyle{ ACA_0 }[/math] over the base theory [math]\displaystyle{ RCA_0 }[/math].

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