RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2022, номер 12, страницы 68–78 (Mi ivm9837)

Сводимость почти полиномиальными функциями

С. С. Марченков

Московский государственный университет им. М.В Ломоносова, Ленинские горы, д. 1, г. Москва, 119991, Россия

Аннотация: Целью работы является введение варианта $m$-сводимости с помощью почти полиномиальных функций и исследование образующегося частично упорядоченного множества $\mathcal M_{\mathbb P}$ соответствующих степеней неразрешимости. Доказывается, что множество $\mathcal M_{\mathbb P}$ имеет по крайней мере счетное число минимальных элементов, но не имеет максимальных элементов. Множество $\mathcal M_{\mathbb P}$ не является ни верхней, ни нижней полурешеткой. Каждый элемент множества $\mathcal M_{\mathbb P}$, отличный от наименьшего, можно включить в континуальную антицепь. Строится континуальное семейство попарно изоморфных начальных сегментов множества $\mathcal M_{\mathbb P}$, имеющих счетную ширину и высоту и пересекающихся только по наименьшему элементу множества.

Ключевые слова: $m$-сводимость, почти полиномиальные функции.

УДК: 510.531

Поступила: 01.02.2022
Исправленный вариант: 03.05.2022
Принята к публикации: 29.06.2022

DOI: 10.26907/0021-3446-2022-12-68-78


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2022, 66:12, 62–70


© МИАН, 2024