|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Позитивные сводимости, экстремальные нумерации и полнота
М. Х. Файзрахмановab a Казанский (Приволжский) федеральный университет, Казань, 420008, РОССИЯ
b Научно-образовательный математический центр ПФО ул. Кремлевская, д. 35, Казань, 420008, РОССИЯ
Аннотация:
В статье исследуются нумерации семейств арифметических множеств и свойства их универсальности, минимальности и полноты. Доказано, что для произвольного $m\in\mathbb{N}$ каждое нетривиальное $\Sigma^0_{m+2}$-вычислимое семейство $\mathcal{S}$ обладает $\Sigma^0_{m+2}$-вычислимой неуниверсальной относительно позитивных сводимостей нумерацией, полной относительно любого наперед заданного элемента $B\in\mathcal{S}$. Для конечных семейств в.п. множеств получен критерий существования их полных вычислимых неуниверсальных относительно позитивных сводимостей нумераций. Для любого бесконечного $\Sigma^0_{m+2}$-вычислимого семейства $\mathcal{S}$ и любого элемента $B\in\mathcal{S}$ построена его $\Sigma^0_{m+2}$-вычислимая полная относительно $B$ нумерация, минимальная относительно классической и позитивных сводимостей.
Ключевые слова и фразы:
нумерация, $\Sigma^0_n$-вычислимая нумерация, сводимость нумераций, $e$-сводимость, $p$-сводимость, универсальная нумерация, минимальная нумерация, полная нумерация.
Статья поступила: 15.08.2022 Переработанный вариант: 17.04.2023 Принята к публикации: 17.05.2023
Образец цитирования:
М. Х. Файзрахманов, “Позитивные сводимости, экстремальные нумерации и полнота”, Матем. тр., 26:1 (2023), 176–191; Siberian Adv. Math., 33:3 (2023), 204–213
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mt694 https://www.mathnet.ru/rus/mt/v26/i1/p176
|
Статистика просмотров: |
Страница аннотации: | 5 | PDF полного текста: | 2 |
|