In mathematics, Higman's lemma states that the set
, as partially ordered by the subsequence relation, is a well partial order.
is an infinite sequence of words over a finite alphabet
, then there exist indices
by deleting some (possibly none) symbols.
More generally the set of sequences is well-quasi-ordered even when
is not necessarily finite, but is itself well-quasi-ordered, and the subsequence ordering is generalized into an "embedding" quasi-order 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.
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
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
is a word of minimum length from among all infinite bad sequences that start with
can be the empty word, we can write
is well-quasi-ordered, the sequence of leading symbols
must contain an infinite increasing sequence
, this sequence is "more minimal" than
In every case we arrive at a contradiction.
The ordinal type of
is related to the ordinal type of
{\displaystyle o(\Sigma ^{*})={\begin{cases}\omega ^{\omega ^{o(\Sigma )-1}},&o(\Sigma ){\text{ finite}};\\\omega ^{\omega ^{o(\Sigma )+1}},&o(\Sigma )=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(\Sigma )}},&{\text{otherwise}}.\end{cases}}}
Higman's lemma has been reverse mathematically calibrated (in terms of subsystems of second-order arithmetic) as equivalent to
over the base theory
This combinatorics-related article is a stub.
You can help Wikipedia by expanding it.