Семинары: В. Л. Селиванов, И. В. Смирнов, О высоте гомоморфных порядков конечных размеченных деревьев

СЕМИНАРЫ


Рабочий семинар по математической логике 11 декабря 2025 г. 16:00, г. Москва, МИАН, комн. 303 (ул. Губкина, 8)

О высоте гомоморфных порядков конечных размеченных деревьев В. Л. Селиванов, И. В. Смирнов Санкт-Петербургский государственный университет
Аннотация: Работа относится к теории стройных порядков, т.е. фундированных частичных порядков, не имеющих бесконечных антицепей. Эта теория является популярным разделом бесконечной комбинаторики с интересными применениями к ряду областей математики и теоретической информатики. Как принято в теории стройных порядков, наши обозначения для простоты не различают предпорядок и его фактор-порядок по индуцированному отношению эквивалентности. Мы сосредоточимся на вычислении высоты $h (Q)$ некоторых стройных порядков $Q$, т.е. супремума ординалов, изоморфно вложимых в $Q$. Точнее, изучим высоту так называемого гомоморфного порядка, определяемого следующим образом. Сопоставим любому предпорядку $Q$ гомоморфный предпорядок $T (Q)$ конечных $Q$-размеченных деревьев $(T, t)$, где $T$ — конечное дерево, $t$ — его разметка, и $(T, t) \leq_h (U, u)$, если существует монотонная функция $f$ из $T$ в $U$ такая, что $t (x) \leq_Q u (f (x))$ для любого $x$ из $T$. Из теоремы Краскала о дереве следует, что если порядок $Q$ стройный, то порядок $T (Q)$ тоже стройный. Основной результат состоит в установлении оптимальной верхней оценки ординала $h (T (Q))$ в зависимости от $h (Q)$. Оценка получена в виде подходящих ординалов Веблена. В качестве следствий вычислим высоту некоторых конкретных гомоморфных порядков, изучавшихся в литературе.