Аннотация:
В статье исследуются нумерации семейств арифметических множеств и свойства их универсальности, минимальности и полноты. Доказано, что для произвольного $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