Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
(Vx1 ... Xnk) (SK (X1, ..., хп%) ^ Ax (X1, ..., хП})). (1)
Полагаем ?3* = QU {Sx | Я, <С а} и обозначаем через объединение совокупности (© и совокупности всех формул (1). €>* и есть полное формульное обогащение <&. Докажем, что совокупность — модельно полная в сигнатуре й*.
Пусть И — алгебраическая система сигнатуры Q*, удовлетворяющая формулам из <3. Рассматриваем совокупность
©** = ?* U ?>(21)
в сигнатуре Qgi- Предположим, что нам дана какая-то формула А* сигнатуры Йад. Мы можем предполагать, что А* содержит предметные символы вида za (а ? 21), так как в противном случае вместо А* могли бы далее рассматривать равносильную ей формулу А* & Za = za. Итак, пусть формула А* в сигнатуре й* имеет свободные предметные переменные ZtJ1, . . ., zan. Заменяя их соответственно новыми предметными символами у}, . . ., уп, не входящими ни в запись формулы А*, ни в йя, получим формулу А* (уі, ..., уп). Эта формула имеет сигнатуру й* и потому может содержать подформулы вида Sx (dj, . . ., ап ), где каждое аг — либо один из сим-
Л
волов у1: ..., уп, либо сигнатурный символ, либо предметное переменное, связанное в формуле А*. Символу Sx отвечает определенная формула Ax (X1, . . ., жЛ ) сигнатуры й, причем совокупность €>* содержит формулу (1). Заменяя в формуле А* (уі, . . ., уп) каждую атомарную подформулу вида Sx (сч, . • аП}) соответствующей формулой Ax (Ct1 т . . ., ап ), получим какую-то формулу А (уі, . . ., уп) сигнатуры й. Так как совокупность ©* содержит все формулы вида (1), то из ©* следует формула
(Vyl...Уп) (А* (уи ...,уп)++А (уи ..., уп)). (2)
17* 260. ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Глі IV
Согласно построению для формулы Л (хи ..., хп) в Q* существует отвечающий ей предикатный символ Sft такой, что совокупность <&* содержит формулу
(Vxi ... хп) (хи .. ., хп) -<->-tЛ ..., хп)). (3)
Так как из €>* следуют формулы (2), (3), то из <&* следует и формула
Ofyi • • • • • уп)^л*(уи • •Уп)),
из которой в свою очередь вытекают формулы
Символ Sft входит в сигнатуру системы 21. Поэтому либо формула Sft (zav .. ., zan), либо формула S& (zav ..., zan) принадлежит D (?). В силу (4), (5) в первом случае из <§?** вытекает формула Jk* (zai, ..., zan), а во втором —из <&** вытекает формула i#(zei, ...,zan). Поэтому совокупность полна в сигнатуре Q^, и теорема 2 доказана.
Напомним, что для каждой совокупности формул сигнатуры Q (©-системами (€>-подсистемами) называются алгебраические системы, сигнатура которых содержит Q и в которых истинны все формулы из Следующее свойство модельно полных совокупностей иногда принимается в качестве определения модельной полноты.
Теорема 3. Для того чтобы совместная совокупность формул €> сигнатуры Q была модельно ,полной, необходимо и достаточно, чтобы все подсистемы произвольной системы были Q-элементарными.
Достаточность. Возьмем какую-нибудь <а-си-стему 2t и положим
Надо показать, что каждая формула Л (z01, . . ., zan) (at 6 21) сигнатуры Q, истинная в 21, является следствием совокупности €>*, т. е. что каждая такая формула истинна в любой модели 33 для Так как <В* содержит диаграмму системы 21, то 21 изоморфно вложена в 35. По условию отсюда вытекает, что 21 есть Q-элементарная подсистема в 35, и потому формула
Sft (Zan • • • 1 zan) > Jh* (zai, . ¦ ' , Zan),
И Sg (Za1, . . . , Zan) П Л* (Ze1, . . . , Zan).
(4)
(5)
(6) § 10] ПОЛНОТА И МОДЕЛЬНАЯ ПОЛНОТА 261
A (zai, . . ., zaa), истинная в 21, является истинной и в SS.
Необходимость. Пусть 95 — какая-то ©-система и 21 — ее произвольная ©-подсистема. Рассмотрим какую-нибудь формулу A (zai, . . ., zan) (at ? 2t) со свободными переменными zav . . ., Zaft, имеющую сигнатуру Q. По предположению, совокупность <©*, определенная соотношением (6), полная в сигнатуре Q^. Если из ©* вытекает A (zai, ¦ ¦ ., zan), то A (zai, . . ., zan) истинна в 2? и в 95. Если же из ©* вытекает ~1 A (zai, . . ., za„), то A (zai, . . ., zan) ложна и в 21 и в 95. Таким образом, каждая формула A (zai, . . ., zan) сигнатуры Q, истинная в 21, истинна в 95, и потому подсистема 21 й-злементар-на в 95.
Теорема 3 указывает достаточный признак модельной полноты. Однако этот признак очень сложный, так как для его проверки надо просматривать все формулы вида A (zajL, . . ., zan) для любой ©-системы 21 и любой ее ©-подсистемы 95. На самом деле вместо произвольных формул A (zai, . . ., zar,t) достаточно просматривать лишь формулы вида
(Bzi ... хт) SS (Ж|, . .., хт, zai, .. •, zan), (7)
где SS — конъюнкция некоторых атомарных формул и отрицаний атомарных формул. Формулы вида (7) называются примитивными.
В соответствии с п. 9.1 подсистему 21 системы 95 условимся называть примитивной (или примитивно элементарной) в 95, если из истинности в S произвольной примитивной формулы сигнатуры Q^ (т. е. формулы вида (7)) вытекает истинность этой формулы и в системе 21.
Теорема 4 (критерий модельной полноты А. Робинсона [55]). Для того чтобы совместная совокупность формул © сигнатуры Q была модельно полной, необходимо и достаточно, чтобы все ©-подсистемы произвольной ©-системы 95 были примитивными подсистемами системы 35.
