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 $w_1, w_2, \ldots$ is an infinite sequence of words over some fixed finite alphabet, 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 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 $ACA_0$ over the base theory $RCA_0$.J. van der Meeren, M. Rathjen, A. Weiermann
An order-theoretic characterization of the Howard-Bachmann-hierarchy
(2015, p.41). Accessed 03 November 2022.

References

*

Wellfoundedness
Order theory
Lemmas

{{combin-stub