Нумерованная модель

- пара [img: http://localhost:8080/file/031513-45.jpg], где [img: http://localhost:8080/file/031513-46.jpg] - модель нек-рой фиксированной сигнатуры [img: http://localhost:8080/file/031513-47.jpg] и [img: http://localhost:8080/file/031513-48.jpg] - нумерация основного множества [img: http://localhost:8080/file/031513-49.jpg] модели [img: http://localhost:8080/file/031513-50.jpg] Наиболее развитым направлением в изучении Н. м. является конструктивных моделей теория. Другим направлением в теории Н. м. является исследование проблемы сложности Н.. м., под к-рой понимается сложность множеств натуральных чисел [img: http://localhost:8080/file/031513-51.jpg] либо множества [img: http://localhost:8080/file/031513-52.jpg]. В качестве [img: http://localhost:8080/file/031513-53.jpg] здесь берется нек-рая гёделева нумерация всех формул сигнатуры [img: http://localhost:8080/file/031513-54.jpg] где константы [img: http://localhost:8080/file/031513-55.jpg] не принадлежат сигнатуре [img: http://localhost:8080/file/031513-56.jpg] - это множество всех замкнутых формул сигнатуры [img: http://localhost:8080/file/031513-57.jpg] истинных на системе [img: http://localhost:8080/file/031513-58.jpg], к-рая получается из системы [img: http://localhost:8080/file/031513-59.jpg] обогащением сигнатуры [img: http://localhost:8080/file/031513-60.jpg] до [img: http://localhost:8080/file/031513-61.jpg], причем значение константы [img: http://localhost:8080/file/031513-62.jpg] полагает равным элементу [img: http://localhost:8080/file/031513-63.jpg] означает соответственно, множество всех бескванторных предложений, истинных на системе [img: http://localhost:8080/file/031513-64.jpg] Различные специальные модели элементарных теорий играют важную роль в математич. логике и алгебре. Один из важных вопросов - проблема их сложности. Получены следующие результаты. Пусть [img: http://localhost:8080/file/031513-65.jpg] и [img: http://localhost:8080/file/031513-66.jpg] обозначают соответственно арифметическую и аналитическую иерархии относительно множества А. Если теория Трекурсивна относительно Аи имеет простую модель [img: http://localhost:8080/file/031513-67.jpg], то существует нумерация [img: http://localhost:8080/file/031513-68.jpg] модели [img: http://localhost:8080/file/031513-69.jpg] такая, что [img: http://localhost:8080/file/031513-70.jpg] то есть [img: http://localhost:8080/file/031513-71.jpg] рекурсивно относительно множества [img: http://localhost:8080/file/031513-72.jpg] всех гёделевых номеров хтаких вычислимых относительно Афункций [img: http://localhost:8080/file/031513-73.jpg], для к-рых [img: http://localhost:8080/file/031513-74.jpg] определено. Если теория Трекурсивна относительно Аи имеет счетную насыщенную модель [img: http://localhost:8080/file/031513-75.jpg], то существует нумерация [img: http://localhost:8080/file/031513-76.jpg] модели [img: http://localhost:8080/file/031513-77.jpg] такая, что [img: http://localhost:8080/file/031513-78.jpg] то есть [img: http://localhost:8080/file/031513-79.jpg] есть гиперарифметич. множество относительно А; эти оценки сложности являются в нек-ром смысле точными. С нахождением точной оценки связан также следующий результат. Известно, что любая непротиворечивая формула.имеет Н. м. [img: http://localhost:8080/file/031513-80.jpg] сложности [img: http://localhost:8080/file/031513-81.jpg], т. е. [img: http://localhost:8080/file/031513-82.jpg] Иерархия ЕрпгоЕа дает более тонкую классификацию множеств из [img: http://localhost:8080/file/031513-83.jpg]. Доказана теорема: для любого [img: http://localhost:8080/file/031513-84.jpg] существует непротиворечивая формула [img: http://localhost:8080/file/031513-85.jpg], не имеющая Н. м. [img: http://localhost:8080/file/031513-86.jpg] с предикатами из [img: http://localhost:8080/file/031513-87.jpg], то есть [img: http://localhost:8080/file/031513-88.jpg] и [img: http://localhost:8080/file/031513-89.jpg]. В конструктивной безатомной булевой алгебре [img: http://localhost:8080/file/031513-90.jpg] построен рекурсивно перечислимый идеал I (т. е. множество [img: http://localhost:8080/file/031513-91.jpg] рекурсивно перечислимо) такой, что булева алгебра [img: http://localhost:8080/file/031513-92.jpg] не конструктивизируема. Это позволило доказать нерекурсивную представимость решетки рекурсивно перечислимых множеств. Исследование нумерованных линейных порядков позволило опровергнуть гипотезу сильной однородности для тьюринговых степеней.