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 is an infinite sequence of words over a finite alphabet , then there exist indices such that can be obtained from by deleting some (possibly none) symbols. More generally this remains true when 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 . This is a special case of the later Kruskal's tree theorem. It is named after Graham Higman, who published it in 1952.
Proof[edit]
Let be a well-quasi-ordered alphabet of symbols (in particular, 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 embeds into a later . Then there exists an infinite bad sequence of words that is minimal in the following sense: is a word of minimum length from among all words that start infinite bad sequences; is a word of minimum length from among all infinite bad sequences that start with ; is a word of minimum length from among all infinite bad sequences that start with ; and so on. In general, is a word of minimum length from among all infinite bad sequences that start with .
Since no can be the empty word, we can write for and . Since is well-quasi-ordered, the sequence of leading symbols must contain an infinite increasing sequence with .
Now consider the sequence of words
Ordinal type[edit]
The ordinal type of is related to the ordinal type of as follows:[1][2]
Reverse-mathematical calibration[edit]
Higman's lemma has been reverse mathematically calibrated (in terms of subsystems of second-order arithmetic) as equivalent to over the base theory .[3]
References[edit]
- 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
Citations[edit]
- ^ de Jongh, Dick H. G.; Parikh, Rohit (1977). "Well-partial orderings and hierarchies". Indagationes Mathematicae (Proceedings). 80 (3): 195–207. doi:10.1016/1385-7258(77)90067-1.
- ^ Schmidt, Diana (1979). Well-partial orderings and their maximal order types (Habilitationsschrift). Heidelberg. Republished in: Schmidt, Diana (2020). "Well-partial orderings and their maximal order types". In Schuster, Peter M.; Seisenberger, Monika; Weiermann, Andreas (eds.). Well-Quasi Orders in Computation, Logic, Language and Reasoning. Trends in Logic. Vol. 53. Springer. pp. 351–391. doi:10.1007/978-3-030-30229-0_13.
- ^ J. van der Meeren, M. Rathjen, A. Weiermann, An order-theoretic characterization of the Howard-Bachmann-hierarchy (2015, p.41). Accessed 03 November 2022.