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

Сиб. матем. журн., 2022, том 63, номер 2, страницы 427–436 (Mi smj7667)

Эта публикация цитируется в 4 статьях

О $p$-универсальных и $p$-минимальных нумерациях

М. Х. Файзрахманов

Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр Приволжского федерального округа, ул. Кремлевская, 35, Казань 420008

Аннотация: Исследуется $p$-сводимость нумераций, введенная и впервые изученная А. Н. Дегтевым и представляющая собой эффективно-ограниченный вариант $e$-сводимости нумераций. Доказано, что для любого множества $A$ существует $A$-вычислимое семейство без универсальных нумераций, обладающее $p$-универсальными нумерациями. Получен критерий существования $p$-универсальных нумераций конечных семейств $A$-в.п. множеств. Наконец, доказано, что любое $A$-вычислимое семейство, где $\emptyset''\leq _TA$, обладает бесконечным множеством попарно не $p$-эквивалентных $p$-минимальных $A$-вычислимых нумераций.

Ключевые слова: вычислимая нумерация, $A$-вычислимая нумерация, $p$-сводимость, универсальная нумерация, $p$-универсальная нумерация, $p$-минимальная нумерация.

УДК: 510.57

Статья поступила: 31.03.2021
Окончательный вариант: 31.03.2021
Принята к печати: 10.12.2021

DOI: 10.33048/smzh.2022.63.213


 Англоязычная версия: Siberian Mathematical Journal, 2022, 63:2, 365–373

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


© МИАН, 2024