Лемма Хигманса - Википедия - Higmans lemma

В математика, Лемма хигмана утверждает, что набор конечных последовательностей над конечным алфавитом, частично упорядоченный подпоследовательность отношение, является квазиупорядоченный. То есть, если бесконечная последовательность слов над некоторым фиксированным конечным алфавитом, то существуют индексы такой, что можно получить из удалив некоторые (возможно, ни одного) символы. В более общем смысле это остается верным, когда алфавит не обязательно конечен, но сам хорошо квазиупорядочен, а отношение подпоследовательности позволяет заменять символы более ранними символами в хорошо квазиупорядоченном порядке меток. Это частный случай более позднего Теорема Крускала о дереве. Он назван в честь Грэм Хигман, опубликовавший его в 1952 году.

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

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