RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические труды // Архив

Матем. тр., 2022, том 25, номер 1, страницы 177–197 (Mi mt665)

О нумерациях классов семейств тотальных функций

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

Казанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, ул. Кремлевская, 18, Казань, 420008 РОССИЯ

Аннотация: В статье изучаются вычислимые нумерации и полурешетки Роджерса классов семейств всюду определенных (тотальных) вычислимых функций. Доказано, что тип изоморфизма полурешетки Роджерса любого конечного класса вычислимых семейств тотальных функций $\mathfrak{F}$ зависит только от упорядочений по включению самого класса $\mathfrak{F}$ и класса $C(\mathfrak{F})$ замыканий его элементов, рассматриваемых как подмножества бэровского пространства. Получен критерий существования универсальных нумераций конечных классов вычислимых семейств тотальных функций, а также исследовано свойство замкнутости произвольных классов семейств тотальных функций, обладающих универсальными нумерациями, относительно объединений вычислимых возрастающих последовательностей их элементов. Установлено, что нетривиальные полурешетки Роджерса вычислимых классов $\mathfrak{F}$, у которых $C(\mathfrak{F})$ конечно, бесконечны и не являются решетками.

Ключевые слова и фразы: нумерация, вычислимая нумерация, $\Sigma^0_n$-вычислимая нумерация, вычислимое семейство, $\Sigma^0_n$-вычислимое семейство, вычислимый класс семейств, полурешетка Роджерса, универсальная нумерация.

УДК: 510.57

Статья поступила: 11.05.2021
Переработанный вариант: 15.07.2021
Принята к публикации: 30.08.2021

DOI: 10.33048/mattrudy.2022.25.108



© МИАН, 2024