RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2023, том 64, номер 1, страницы 204–212 (Mi smj7756)

Эта публикация цитируется в 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


 Англоязычная версия: Siberian Mathematical Journal, 2023, 64:1, 174–180

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


© МИАН, 2024