Математическая энциклопедия - нумерованная модель

пара , где модель нек-рой фиксированной сигнатуры и нумерация основного множества модели Наиболее развитым направлением в изучении Н. м. является конструктивных моделей теория. Другим направлением в теории Н. м. является исследование проблемы сложности Н.. м., под к-рой понимается сложность множеств натуральных чисел либо множества . В качестве здесь берется нек-рая гёделева нумерация всех формул сигнатуры где константы не принадлежат сигнатуре это множество всех замкнутых формул сигнатуры истинных на системе , к-рая получается из системы обогащением сигнатуры до , причем значение константы полагает равным элементу означает соответственно, множество всех бескванторных предложений, истинных на системе

Различные специальные модели элементарных теорий играют важную роль в математич. логике и алгебре. Один из важных вопросов проблема их сложности. Получены следующие результаты. Пусть и обозначают соответственно арифметическую и аналитическую иерархии относительно множества А.

Если теория Трекурсивна относительно Аи имеет простую модель , то существует нумерация модели такая, что то есть рекурсивно относительно множества всех гёделевых номеров хтаких вычислимых относительно Афункций , для к-рых определено.

Если теория Трекурсивна относительно Аи имеет счетную насыщенную модель , то существует нумерация модели такая, что то есть есть гиперарифметич. множество относительно А; эти оценки сложности являются в нек-ром смысле точными.

С нахождением точной оценки связан также следующий результат. Известно, что любая непротиворечивая формула .имеет Н. м. сложности , т. е.

Иерархия ЕрпгоЕа дает более тонкую классификацию множеств из . Доказана теорема: для любого существует непротиворечивая формула , не имеющая Н. м.с предикатами из , то есть и . В конструктивной безатомной булевой алгебре построен рекурсивно перечислимый идеал I (т. е. множество рекурсивно перечислимо) такой, что булева алгебра не конструктивизируема. Это позволило доказать нерекурсивную представимость решетки рекурсивно перечислимых множеств.

Исследование нумерованных линейных порядков позволило опровергнуть гипотезу сильной однородности для тьюринговых степеней.

Лит.:[1] Гончаров С. С, Дроботун Б. Н., "Сиб. матем. ж.", 1980, т. 21, [4] 2, с. 25-41; [2] Денисов С. Д., "Алгебра и логика", 1972, т. И, № 6, с. 648 55; [3] Дроботун Б. Н., "Сиб. матем. ж.", 1977, т. 18, №5, с. 1002-14; [4] Ершов Ю. Л., Теория нумераций, М., 1977; [5] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [6] Feiner L., "J. Symbol. Logic", 1970, v. 35, p. 365-74; [7] eго же, там же, р. 375-77.

С. С. Гончаров

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985