В математике , лемма Хигмэы гласит , что множество конечных последовательностей над конечным алфавитом, а частично упорядоченный по подпоследовательности отношения, является хорошо квазиупорядоченным . То есть, если бесконечная последовательность слов над некоторым фиксированным конечным алфавитом, то существуют индексы такой, что можно получить из удалив некоторые (возможно, ни одного) символы. В более общем смысле это остается верным, когда алфавит не обязательно конечен, но сам хорошо квазиупорядочен, а отношение подпоследовательности позволяет заменять символы более ранними символами в правильном квазиупорядочении меток. Это частный случай более поздней теоремы Крускала о дереве . Он назван в честь Грэма Хигмана , опубликовавшего его в 1952 году.
Рекомендации
- Хигман, Грэхэй (1952), "Заказ по делимости в абстрактных алгебрах", Труды Лондонского математического общества , (3), 2 (7): 326-336, DOI : 10.1112 / PLMS / s3-2.1.326