#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/).

11 декабря 2025 г. доклад В.Л. Селиванова и И.В. Смирнова (СПбГУ) «О высоте гомоморфных порядков конечных размеченных деревьев».

Время: 16:00
Место: МИАН, ауд. 104 + Контур.Толк
Для получения ссылки зарегистрируйтесь на странице семинара: www.mathnet.ru/conf2533
(ссылка единая для всех заседаний в этом семестре).

Аннотация:
Работа относится к теории стройных порядков, т.е. фундированных частичных порядков, не имеющих бесконечных антицепей. Эта теория является популярным разделом бесконечной комбинаторики с интересными применениями к ряду областей математики и теоретической информатики. Как принято в теории стройных порядков, наши обозначения для простоты не различают предпорядок и его фактор-порядок по индуцированному отношению эквивалентности. Мы сосредоточимся на вычислении высоты 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). Оценка получена в виде подходящих ординалов Веблена. В качестве следствий вычислим высоту некоторых конкретных гомоморфных порядков, изучавшихся в литературе.

➰ ВК