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

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

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

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

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

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

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

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

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

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

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

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

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