|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Сводимость по перечислимости и позитивная сводимость нумераций семейств арифметических множеств
М. Х. Файзрахманов Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФО, ул. Кремлевская, 35, Казань 420008
Аннотация:
Исследуются структуры нумераций семейств арифметических множеств, заданные $e$- и $p$-сводимостями нумераций. Доказано, что любое конечное семейство $\Sigma^0_{d+1}$-множеств обладает $\Sigma^0_{d+1}$-вычислимой $e$-универсальной нумерацией. Приводятся примеры $\Sigma^0_{d+2}$-вычислимых семейств, обладающих $\Sigma^0_{d+2}$-вычислимыми $e$-универсальными, но не $p$-универсальными нумерациями. Строятся $\Sigma^0_{d+1}$-вычислимые семейства всюду определенных функций без $\Sigma^0_{d+1}$-вычислимых $e$-универсальных нумераций. Устанавливается, что любое бесконечное $\Sigma^0_{d+2}$-вычислимое семейство имеет бесконечно много как $e$-минимальных, так и $p$-минимальных $\Sigma^0_{d+2}$-вычислимых нумераций. В заключение доказывается, что любое неодноэлементное $\Sigma^0_{d+2}$-вычислимое семейство имеет бесконечно много попарно не $e$-эквивалентных $\Sigma^0_{d+2}$-вычислимых нумераций.
Ключевые слова:
нумерация, $\Sigma^0_{d+1}$-вычислимая нумерация, $e$-сводимость, $p$-сводимость, $e$-универсальная нумерация, $p$-универсальная нумерация, $e$-минимальная нумерация, $p$-минимальная нумерация.
Статья поступила: 04.02.2022 Окончательный вариант: 03.10.2022 Принята к печати: 10.10.2022
Образец цитирования:
М. Х. Файзрахманов, “Сводимость по перечислимости и позитивная сводимость нумераций семейств арифметических множеств”, Сиб. матем. журн., 64:1 (2023), 204–212; Siberian Math. J., 64:1 (2023), 174–180
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj7756 https://www.mathnet.ru/rus/smj/v64/i1/p204
|
Статистика просмотров: |
Страница аннотации: | 112 | PDF полного текста: | 17 | Список литературы: | 34 | Первая страница: | 6 |
|