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

20 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.

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

В.Е. Карпов (МФТИ)

О $\Pi^1_1$-полноте $\Sigma_2$-теории натуральных чисел со стандартным порядком и свободной эквивалентностью

Аннотация:

Обозначим через LEq класс всех пар, состоящих из линейного порядка и эквивалентности на общем носителе. Этот класс и его подклассы играют важную роль в изучении алгоритмических свойств элементарных теорий. Нас будет интересовать естественный подкласс LEq*, состоящий из структур на натуральных числах, в которых порядок интерпретируется стандартным образом, а эквивалентность остаётся «свободной». Нетрудно видеть, что \Pi_2-теория LEq* является разрешимой. Вместе с тем будет доказано, что \Sigma_2-теория LEq* является \Pi^1_1-полной (для сравнения \Sigma_2-теория LEq является лишь \Sigma^0_1-полной).

Для доказательства желаемого результата о \Pi^1_1-полноте будет использоваться тот факт (встречающийся в работе Д. Хареля, А. Пнуэли и Дж. Стави), что множество всех кодов рекурректных недетерминированных машин Тьюринга является \Sigma^1_1-полным. Здесь прилагательное «рекуррентный» означает, что при запуске на пустой ленте у данной машины существует бесконечное вычисление, в ходе которого начальное состояние посещается бесконечно часто.