Эта публикация цитируется в
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$-минимальная нумерация.
УДК:
510.57
MSC: 35R30 Статья поступила: 04.02.2022
Окончательный вариант: 03.10.2022
Принята к печати: 10.10.2022
DOI:
10.33048/smzh.2023.64.117