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

Матем. тр., 2023, том 26, номер 1, страницы 176–191 (Mi mt694)

Эта публикация цитируется в 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$-сводимость, универсальная нумерация, минимальная нумерация, полная нумерация.

УДК: 510.57

Статья поступила: 15.08.2022
Переработанный вариант: 17.04.2023
Принята к публикации: 17.05.2023

DOI: 10.33048/mattrudy.2023.26.109


 Англоязычная версия: Siberian Advances in Mathematics, 2023, 33:3, 204–213

Реферативные базы данных:


© МИАН, 2024