Higman's lemma explained

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 w _{1,} w _{2,} \ldots\in \Sigma ^{*} 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 w _{1,} w _{2,} w _{3,} \ldots\in \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,} \ldots) 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,\ldots,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\Sigma} and z ^{*} _{i\in\Sigma} . Since \Sigma is well-quasi-ordered, the sequence of leading symbols a _{1,} a _{2,} a _{3,} \ldots must contain an infinite increasing sequence a _{i _{1}} \le a _{i _{2}} \le a _{i _{3}} \le … with i _{1<i} _{2<i} _{3< …} .

Now consider the sequence of words $$w\_1,\; \backslash ldots,\; w\_,\; z\_,\; z\_,\; z\_,\; \backslash ldots.$$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

\Sigma ^{*} is related to the ordinal type of \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

ACA _{0} over the base theory RCA _{0} .^[3]

References

Citations

Notes and References

1. de Jongh . Dick H. G. . Parikh . Rohit . Well-partial orderings and hierarchies . Indagationes Mathematicae (Proceedings) . 1977 . 80 . 3 . 195-207 . 10.1016/1385-7258(77)90067-1. free .
2. Schmidt . Diana . Habilitationsschrift . 1979 . Well-partial orderings and their maximal order types . Heidelberg. Republished in: Book: Schmidt, Diana . 2020 . Well-partial orderings and their maximal order types . Well-Quasi Orders in Computation, Logic, Language and Reasoning . Springer . 351-391 . Schuster . Peter M. . Seisenberger . Monika . Weiermann . Andreas . Trends in Logic . 53 . 10.1007/978-3-030-30229-0_13.
3. J. van der Meeren, M. Rathjen, A. Weiermann, An order-theoretic characterization of the Howard-Bachmann-hierarchy (2015, p.41). Accessed 03 November 2022.