УДК 510.678
А. М. Кунгожин
ДВА СВОЙСТВА ПОЗИТИВНО ЭКЗИСТЕНЦИОНАЛЬНО-ЗАМКНУТЫХ МОДЕЛЕЙ
(Казахский национальный университет имени аль-Фараби, Алматы)
Доказано, что элементарная подмодель позитивной экзистенционально-замкнутой модели h-универсально аксиоматизируемого класса моделей является позитивно экзистенционально-замкнутой. Приведен пример h-универсально аксиоматизируемого класса моделей, в котором элементарное расширение позитивной экзистенционально-замкнутой модели не является позитивно экзистенционально-замкнутой.
Ключевые слова: позитивная экзистенциональная замкнутость, аксиоматизация, элементарная подмодель, h-универсальное предложение.
1. Введение
Мы используем понятия, введенные в работе И. Бен Якова и Б. Пуаза [1]. Рассмотрим предикатную сигнатуру 
с отношением равенства, при этом образуем обычные формулы первого порядка, используя операции отрицания, конъюнкции, дизъюнкции и квантор существования. Позитивные формулы образуются без операции отрицания, они могут быть записаны следующим образом: 
, где 
бескванторная позитивная формула.
Гомоморфизм 
-структуры 
в -структуру 
есть отображение 
из основного множества A модели в основное множество B модели такое, что для любого кортежа 
из A, если 
удовлетворяет атомарной формуле 
, то ей также будет удовлетворять кортеж 
. При этом обратное не требуется, например, может удовлетворять большему количеству атомарных формул по сравнению с кортежем 
, а также может быть неинъективным отображением. Если существует гомоморфизм из модели в модель , то мы говорим, что 
является продолжением , и есть начало . (Термины расширение/сужение используются, когда является вложением, то есть когда и удовлетворяют одним и тем же атомарным формулам).
При гомоморфизме любая позитивная формула , удовлетворяющая кортежу , будет также удовлетворять и кортежу . Мы говорим, что является погружением, если выполняется обратное: и удовлетворяют одним и тем же позитивным формулам. При этом модель 
позитивно экзистенционально-замкнута в модели . Погружение является вложением, но позитивная экзистенциональная замкнутость слабее робинсоновского понятия, поскольку рассматриваются только позитивные экзистенциональные формулы.
h-универсальное предложение, по определению, является отрицанием позитивного предложения, его можно записать следующим образом: 
или, что эквивалентно, 
, где формула 
бескванторная и позитивная.
Пусть задан класс 
-структур, мы говорим, что модель класса позитивно экзистенционально-замкнута в , если любой гомоморфизм из в любую модель класса является погружением.
2. Позитивная экзистенциональная замкнутость элементарной подмодели
Изучая понятие позитивной экзистенциональной замкнутости (pec), автор ввел следующее понятие, которое обычно упрощает доказательство того, что данная модель является pec-моделью.
Определение. Модель класса назовем h-максимальной, если любой гомоморфизм из модели в произвольный элемент класса является изоморфным вложением.
Замечание. Нетрудно понять, что произвольная pec-модель является h-максимальной.
Утверждение. Модель является pec-моделью класса тогда и только тогда, когда 1) модель является h-максимальной моделью и 2) при любом гомоморфизме 
(где основное множество модели класса является конечным расширением основного множества модели , и позитивная диаграмма модели является конечным расширением позитивной диаграммы ) и для любой позитивной бескванторной формулы 
из истинности формулы 
в модели (
, 
) следует существование кортежа 
такого, что формула 
истинна в модели .
Доказательство. Свойства 1) и 2) являются частным случаем определения pec-модели. Докажем, что если модель удовлетворяет условиям 1) и 2), то она является pec-моделью. Рассмотрим произвольный гомоморфизм 
. Пусть какая-то позитивная формула 
истинна в модели 
на кортеже . Тогда существует конечное гомоморфное расширение модели , удовлетворяющее свойству 2). Но тогда эта формула будет истинна и в модели , что и требовалось доказать.
Теорема. Пусть модель 
является элементарной подмоделью pec-модели h-универсально аксиоматизируемого класса . Тогда модель также является pec-моделью этого класса.
Доказательство. Модель является pec-моделью тогда и только тогда, когда 1) модель является h-максимальной моделью и 2) при любом гомоморфизме 
и для любой позитивной бескванторной формулы 
из истинности формулы в модели (
, 
) следует существование кортежа 
такого, что формула истинна в модели .
Докажем 1). От противного. Пусть модель не h-максимальна. Тогда существует отношение 
и кортеж такие, что 
истинно в модели , но (*) теория 
– совместна. Но тогда (**) теория 
– совместна. Докажем (**) методом от противного. Пусть теория – не совместна. Тогда, по теореме компактности, найдется кортеж такой, что теория 
– не совместна. Так как модель является элементарной подмоделью модели , то найдется кортеж 
такой, что 
истинна в . Тогда теория 
– не совместна, но это противоречит со (*). Значит, (**) – доказано. Однако (**) – противоречит позитивно-экзистенционально замкнутости модели , то есть модель является h-максимальной моделью.
Докажем 2). Из истинности формулы в модели следует (***) совместность теории 
. Но тогда верно, что и (****) теория 
– совместна. Докажем (****) методом от противного. Если теория – не совместна, то 
– не совместна. Так как модель является элементарной подмоделью модели , то найдется кортеж 
такой, что 
– не совместна, что противоречит (***). Значит, (****) – доказано.
Нетрудно понять, что теория 
– совместна (так как совместность любой подтеории 
следует из совместности теории 
). Тогда существует модель , являющаяся продолжением модели , в которой истинна формула 
. Но модель является pec-моделью, и для некоторого 
формула 
истинна в модели . Снова, из того, что модель является элементарной подмоделью модели , следует существование кортежа такого, что формула истинна в модели . Что и требовалось доказать.
3. Пример класса моделей аксиоматизируемого h-универсальными предложениями, класс позитивно экзистенционально замкнутых моделей которого не элементарный.
Предлагаемый ниже пример показывает, что обращение предыдущей теоремы не выполняется. Автор здесь выражает Бруно Пуаза, значительно упростившему первоначальный вариант.
Пример. Пусть 
– унарные отношения, 
. Пусть этот класс описывается следующими предложениями: некоторые элементы имеют свойства 
, но при этом только одно из свойств. (
).
Доказательство. Нетрудно понять, что класс позитивно экзистенционально замкнутых моделей данного класса состоит из моделей , таких что 1) содержит бесконечное число элементов со свойством по каждому такому свойству, 2) других элементов нет.
Поймем, что класс всех таких моделей не аксиоматизируем. Действительно, все такие модели не содержат элементов, которые не обладают ни одним из свойств . Однако, модель , являющееся расширением pec-модели одним изолированным элементом 
, будет совместна с теорией 
модели . Докажем это. Для этого поймем, что модель совместна с любой конечной частью теории . Так как конечная часть теории содержит ограниченное число сигнатурных символов и для описания изолированности элемента необходимо бесконечное число формул, то модель совместна с этой конечной частью теории .
Легко заметить, что данный пример является контрпримером для обратного утверждения к теореме, доказанной в предыдущем параграфе.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Ben Yaacov I., Poizat B., Fondaments de la Logique Positive // The Journal of Symbolic Logic, vol. 82 (2007), pp. 1141-1162.
2. Ben Yaacov I., Positive model theory and compact abstract theories // The Journal of Mathematical Logic, vol. 3 (2003), pp. 85-118.
3. Fraisse R., Sur certaines relations qui généralisent l’orde des nombres rationnels // Les Comptes Rendus de l’Académie des sciences Paris, vol. 237 (1953), pp. 540-542.
Основные порталы (построено редакторами)