Higman's lemma
From Wikipedia, the free encyclopedia
Not to be confused with Higman's theorem.
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.