Аннотация:
Исследуется p-сводимость нумераций, введенная и впервые изученная А. Н. Дегтевым и представляющая собой эффективно-ограниченный вариант e-сводимости нумераций. Доказано, что для любого множества A существует A-вычислимое семейство без универсальных нумераций, обладающее p-универсальными нумерациями. Получен критерий существования p-универсальных нумераций конечных семейств A-в.п. множеств. Наконец, доказано, что любое A-вычислимое семейство, где ∅″≤TA, обладает бесконечным множеством попарно не p-эквивалентных p-минимальных A-вычислимых нумераций.
Работа поддержана грантом Российского научного фонда (проект №18–11–00028) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение №075–02–2021–1393).
Статья поступила: 31.03.2021 Окончательный вариант: 31.03.2021 Принята к печати: 10.12.2021
M. Kh. Faizrahmanov, “A Family with a Single Minimal but Not Least Numbering”, Sib Math J, 65:2 (2024), 381
М. Х. Файзрахманов, “Семейство с единственной минимальной, но не наименьшей нумерацией”, Сиб. матем. журн., 65:2 (2024), 395–407
М. Х. Файзрахманов, “Позитивные сводимости, экстремальные нумерации и полнота”, Матем. тр., 26:1 (2023), 176–191; M. Kh. Faizrahmanov, “Positive reducibilities, extreme numberings, and completeness”, Siberian Adv. Math., 33:3 (2023), 204–213
М. Х. Файзрахманов, “Сводимость по перечислимости и позитивная сводимость нумераций семейств арифметических множеств”, Сиб. матем. журн., 64:1 (2023), 204–212; M. Kh. Faizrahmanov, “Enumeration reducibility and positive reducibility of the numberings of families of arithmetic sets”, Siberian Math. J., 64:1 (2023), 174–180