" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

КОНСТРУКТИВНЫХ МОДЕЛЕЙ ТЕОРИЯ

Значение КОНСТРУКТИВНЫХ МОДЕЛЕЙ ТЕОРИЯ в математической энциклопедии:

- один из разделов математики, возникший на границе моделей теории, алгебры и теории рекурсивных функций и связанный с изучением вопросов эффективности в моделях и алгебрах.

Статья А. И. Мальцева "Конструктивные алгебры" [1] явилась первой обзорной работой по конструктивным моделям, в к-рой были выработаны и систематизированы основные понятия и намечены дальнейшие пути развития этой теории. Большую роль в становлении и развитии этого раздела математики сыграли работы Ю. Л. Ершова и его учеников, в к-рых был решен ряд основных проблем, выработаны новые понятия и определены новые направления в исследовании конструктивных моделей (см. [2]).

Ниже сформулированы основные понятия и результаты К. м. т. Все рассмотрения обычно ведутся в нек-рой фиксированной сигнатуре

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

к-рая получается присоединением к s₀ счетного числа символов для констант. Всегда предполагается, что п ₀=2 и предикат на любой модели определен как равенство. Пусть L_i,i=0,1,- совокупность всех формул узкого исчисления предикатов с равенством сигнатуры s_i, i=0,1, и g- некоторая фиксированная гёделевская нумерация (см. [3]) множества Подмножество наз. разрешимым, если множество g^-1(S)рекурсивно. Нумерованной моделью (сигнатуры s₀) наз. пара где =- модель сигнатуры s₀, a v - нумерация основного множества Ммодели Нумерованная модель наз. конструктивной моделью, если множество рекурсивно.

По каждой нумерованной модели можно канонич. образом построить нек-рое s₁-oбогащение модели т. е. модель сигнатуры s₁, основное множество к-рой есть основное множество модели лредикаты из s₀ в совпадают с соответствующими предикатами а константы определены следующим образом: в качестве значения а _k, k<w, полагают элемент Пусть - элементарная теория модели т. е. множество всех замкнутых формул сигнатуры s₀, истинных на модели а v)- элементарная теория нумерованной модели Нумерованная модель наз. сильно конструктивной, если теория разрешима.

Непосредственно из определения видно, что сильно конструктивная модель конструктивна.

Одной из основных проблем К. м. т. является проблема существования конструктивных моделей с различными элементарными свойствами, т. е. свойствами, записываемыми на языке узкого исчисления предикатов. В этом направлении получен (к 1978) ряд интересных и важных теорем. Существование широкого класса сильно конструктивных моделей дает следующая теорема: если - разрешимая теория, то существует такая последовательность сильно конструктивных моделей

что: множество {{х, y)|g{y)Th(v_x)}является рекурсивным. Было замечено, что существуют формулы, не имеющие конструктивных моделей. Следующие две теоремы дают нек-рые достаточные условия существования конструктивных моделей у теорий с рекурсивно перечислимым множеством аксиом.

Если Т- рекурсивно перечислимая -теория, имеющая модель с рекурсивно перечислимой -теорией, то теория Тимеет конструктивную модель.

Теория Тконечной сигнатуры s=. . ., с ₀, . .. , c_l )наз. -конечной, если универсальная теория любого расширения (той же сигнатуры) конечно аксиоматизируема (универсальными предложениями). Теория Тназ. сильно -конечной, если для любого конечного множества константных символов теория Т*, определенная теорией Тв языке сигнатуры является -конечной.

Если теория Тсильно -конечна, а Т'- рекурсивно перечислимое расширение Т, то Т' имеет конструктивную модель.

Другой круг исследуемых вопросов связан с проблемой существования для заданной модели нумерации v такой, чтобы пара стала (сильно) конструктивной моделью. Модель, для к-рой существует такая нумерация, наз. (сильно) конструктивизируемой, а соответствующая нумерация (сильной) конструкт и визацией. Для решения ряда вопросов, связанных с конструктивизируемостью моделей, оказывается полезной теорема Ершова о ядре, применение к-рой к конкретным алгебралч. системам позволяет решить ряд естественных вопросов. В частности, установлено: 1) для любой конструктивной локально нильпотентной группы без кручения существует конструктивное пополнение; 2) если (F, v) - конструктивное поле, F₀- алгебраич. расширение поля F, то v продолжается до конструктивизации поля F₀ тогда и только тогда, когда семейство конечных множеств многочленов над Fот счетного числа переменных, имеющих корень в F, рекурсивно перечислимо.

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

Изучался вопрос о числе неэквивалентных конструктивизаций для данной модели. Две конструктивизации v и m. модели наз. (рекурсивно) эквивалентными, если существуют изоморфизм j(j=и рекурсивная функция f такие, что jv=mf. Модель наз. (рекурсивно устойчивой) автоустойчивой, если любые две ее конструктивизации (рекурсивно) эквивалентны.

Для широкого класса алгебраич. систем показано, что существует либо только одна (с точностью до эквивалентности), либо счетное число неэквивалентных конструктивизаций [4], [5]. Полностью решен вопрос о числе неэквивалентных конструктивизаций и описаны автоустойчивые модели для полей, булевых алгебр и абелевых групп без кручения. А также показано, что вопросы автоустойчивости связаны с изучением вычислимости классов конструктивных моделей.

Лит.:[1] Мальцев А. И., "Успехи матем. наук", 1961, т. 16, № 3, с. 3-60; [2] Ершов Ю. Л., Теория нумераций ч. 3 - Конструктивные модели, Новосиб., 1974; [3] Ершов Ю. Л. и др., "Успехи матем. наук", 1965, т. 20, № 4, с. 37-108; [4] Гончаров С. С, "Алгебра и логика", 1975, т. 14 № 6,с. 647-80; [5] Нуртазин А. Т., там же, 1974, т. 13, № 3, с. 311-23; [6] Соbham А., в кн.: Summaries of talks presented at the Summer Institute for Symbolic Logic Cornell University 1957, Wash., 1960, p. 391-95; [7] Frohliсh A., Shepherdson J. C, "Phil. Trans. Royal Soc. London" 1956 ser. A, v. 248, p. 407-32; [8] Mostowski A., "Fundam. math.", 1955, v. 42, Mi 1, p. 125-40; [9] Rabin M. O. "Trans. Amer. Math. Soc", 1960, v. 95, № 2, p. 341-60; [10] Vaught R. L., "J. Symb. Logic", 1960, v. 25, Mi i,p. 39-53.