Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
ПОЛНОТА И МОДЕЛЬНАЯ ПОЛНОТА
251
Совокупность формул <з> фиксированной сигнатуры Q называется категоричной в сигнатуре Q1 s Q, если @ совместна и все ее модели сигнатуры Q являются QrH30-морфными. Совокупность © называется категоричной, если она категорична в сигнатуре Q. Ясно, что совокупность формул, категоричная в сигнатуре Q1, категорична и в каждой более узкой сигнатуре. Ясно также, что из категоричности @ в сигнатуре Q1 вытекает Qi-полнота Существуют ли категоричные совокупности формул?
Допустим, что какая-то совокупность формул © сигнатуры Q обладает бесконечной моделью 21 сигнатуры Q. Согласно теореме 5 п. 9.2 существует модель 3) сигнатуру Q, элементарно эквивалентная И и имеющая большую мощность, чем модель И. Из элементарной эквивалентности St и следует, что все формулы из (© истинны в 95, т. е. 95 '— модель для <&. В то же время St и 35 не изоморфны, так как имеют различные мощности. Поэтому совокупность <& не категорична. Никакую бесконечную алгебраическую систему нельзя описать с точностью до изоморфизма на языке 1-й ступени. Напротив, каждая конечная алгебраическая система легко описывается с точностью до изоморфизма.
Пусть St — какая-нибудь (конечная или бесконечная) алгебраическая система фиксированной сигнатуры Q. Каждому элементу а б St ставим в соответствие предметный символ za, не принадлежащий Q. Как и в п. 9.2, символом Qgi обозначим объединение Q и множества всех символов za (а ? St). Элемент а условимся называть каноническим значением символа Za в системе St. Диаграммой системы St (символически D (St)) называется совокупность тех атомарных и отрицаний атомарных формул сигнатуры Q^, которые истинны в St при канонических значениях предметных символов.
Сравнивая определение диаграммы системы St с определением описания О (St) п. 9.1, видим, что диаграмма составляет часть описания системы. Тогда как описание любой системы состоит из бесконечного числа формул, диаграмма конечной алгебраической системы конечной сигнатуры состоит из конечного числа формул. Например, диаграмма полугруппы ({0, 1}, •), где точкой обозначено обычное произведение, является совокупностью 252.
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Глі IV
следующих формул:
Zo = Z0, Z1 = Z1, Z0 ф Z1, Z1 Ф Zl1 Z0-Z0 = Z0, Z0-Zi = Z0, Zi-Z0 — Z0, Z1-Z1 = Zi, Z0-Z0 Ф Zil Z0-Zi Ф Zll Z1-Z0 ф Zil Zi-Zi Ф Z0.
Рассмотрим произвольную совместную совокупность формул <»> какой-то фиксированной сигнатуры ?2. Пусть а — модель для <&. Присоединяя к © диаграмму /)(?), получим совокупность формул <Si = @UD {Щ сигнатуры Qgj. Все формулы из ^1 истинны в а при канонических значениях сигнатурных переменных za.
Рассмотрим теперь какую-нибудь модель 95 совокупности Каждое переменное Za имеет в 95 определенное значение Ъа ? 95. Обозначим через а отображение а Ьа модели а в 95. Рассуждения, приведенные в п. 9.1 по поводу описаний моделей, показывают, что и в рассматриваемом случае отображение о есть изоморфизм а в 95. Отождествляя а с подмоделью а°, видим, что каждая модель для совокупности (S1 содержит подмодель а. Разница между описанием и диаграммой состоит в том, что каждая модель для (a (J О (а) содержит а в качестве своей элементарной подмодели, а каждая модель для <&[)D (а) содержит а лишь как «простую» подмодель. Из этих рассуждений, в частности, получаем
Следствие 3. Пусть а — конечная алгебраическая система с п элементами aif . . ., ап, имеющая сигнатуру Q. Тогда все модели сигнатуры Q^ совокупности формул
D (а), (Уж) (х = Za1 V X = Za2 V • • • V х = zan)
изоморфны модели а. Если сигнатура конечной алгебраической системы а конечна, то все модели сигнатуры Q для формулы
(3zai...zan)?*(a)&
& (Vz1 . . . Xnxn+ij (Xi = X2 V Xi = X3 \J ... \J xTI — Xn+l),
где D* (a) — конъюнкция формул из D (а), изоморфны а.
Таким образом, каждую конечную систему а бесконечной сигнатуры Q можно описать с точностью до изомор- § loj Полнота и модельная полнота 253
физма бесконечной системой формул сигнатуры ?2?, а каждую конечную систему И конечной сигнатуры Q можно описать с точностью до изоморфизма одной формулой сигнатуры Q.
Сопоставляя следствие 1 и следствие 7 п. 9.1, получаем
Следствие 4. Пусть совокупность формул 3 сигнатуры Q Г-полна и Г содержит 3-замыкания конъюнкций атомарных и отрицаний атомарных формул. Если существует конечная алгебраическая система St сигнатуры Q1 удовлетворяющая совокупности 3, то все модели для 3 изоморфны St.
Следствия 3 и 4 показывают, что, за исключением тривиальных случаев, полные системы формул обладают неизоморфными моделями различных мощностей и потому не категоричны. Если же рассматривать лишь модели какой-нибудь фиксированной бесконечной мощности, то такие модели могут оказаться и изоморфными. Поэтому целесообразно ввести следующее определение.
Совокупность формул 3 сигнатуры ?2 называется категоричной в мощности ш, если <3 имеет модели мощности ш и все модели для <3, имеющие мощность ш, изоморфны. Аналогично совокупность формул 3 называется TQi-полной в мощности m (Q1 s Q), если <3 имеет модели мощности nt и все модели для 3, имеющие мощность ш, являются TQj-эквивалентными. Ясно, что из категоричности <3 в мощности ш вытекает полнота З в этой мощности. Обратное не всегда верно.
