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

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