|
Сводимость почти полиномиальными функциями
С. С. Марченков Московский государственный университет им. М.В Ломоносова, Ленинские горы, д. 1, г. Москва, 119991, Россия
Аннотация:
Целью работы является введение варианта $m$-сводимости с помощью почти полиномиальных функций и исследование образующегося частично упорядоченного множества $\mathcal M_{\mathbb P}$ соответствующих степеней неразрешимости. Доказывается, что множество $\mathcal M_{\mathbb P}$ имеет по крайней мере счетное число минимальных элементов, но не имеет максимальных элементов. Множество $\mathcal M_{\mathbb P}$ не является ни верхней, ни нижней полурешеткой. Каждый элемент множества $\mathcal M_{\mathbb P}$, отличный от наименьшего, можно включить в континуальную антицепь. Строится континуальное семейство попарно изоморфных начальных сегментов множества $\mathcal M_{\mathbb P}$, имеющих счетную ширину и высоту и пересекающихся только по наименьшему элементу множества.
Ключевые слова:
$m$-сводимость, почти полиномиальные функции.
Поступила: 01.02.2022 Исправленный вариант: 03.05.2022 Принята к публикации: 29.06.2022
Образец цитирования:
С. С. Марченков, “Сводимость почти полиномиальными функциями”, Изв. вузов. Матем., 2022, № 12, 68–78; Russian Math. (Iz. VUZ), 66:12 (2022), 62–70
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm9837 https://www.mathnet.ru/rus/ivm/y2022/i12/p68
|
Статистика просмотров: |
Страница аннотации: | 77 | PDF полного текста: | 25 | Список литературы: | 21 | Первая страница: | 4 |
|