Лемма Хигманса - Higmans lemma - Wikipedia

Не путать с Теорема Хигмана.

В математика, Лемма хигмана утверждает, что набор конечных последовательностей над конечным алфавитом, частично упорядоченный подпоследовательность отношение, является квазиупорядоченный. То есть, если ${\displaystyle w_{1},w_{2},\ldots }$ бесконечная последовательность слов над некоторым фиксированным конечным алфавитом, то существуют индексы ${\displaystyle i<j}$ такой, что ${\displaystyle w_{i}}$ можно получить из ${\displaystyle w_{j}}$ удалив некоторые (возможно, ни одного) символы. В более общем смысле это остается верным, когда алфавит не обязательно конечен, но сам хорошо квазиупорядочен, а отношение подпоследовательности позволяет заменять символы более ранними символами в хорошо квазиупорядоченном порядке меток. Это частный случай более позднего Теорема Крускала о дереве. Он назван в честь Грэм Хигман, опубликовавший его в 1952 году.

Рекомендации

• Хигман, Грэм (1952), «Упорядочение по делимости в абстрактных алгебрах», Труды Лондонского математического общества, (3), 2 (7): 326–336, Дои:10.1112 / плмс / с3-2.1.326