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

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

Эта публикация цитируется в 1 статье

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

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

Московский государственный университет им. М.В Ломоносова, Ленинские горы, д. 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


© МИАН, 2025