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.

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

This article is issued from Wikipedia - version of the 3/15/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.