Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Теорема 7. Объединение St локальной в себе (см. п. 2.3) совокупности Y-подсистем SIa (а ? I) алгебраической системы сигнатуры Q является Y-подсистемой 55.
В частности, объединение возрастающей цепочки Y-подсистем системы 95 есть Y-подсистема 95.
Воспользуемся теоремой 1. Пусть (Bx) Л (х) есть Г-формула сигнатуры Q^, истинная в 95. В записи этой формулы содержится лишь конечное число символов za, ..., Za (а, . . ., с б Si). Ищем такое а, чтобы элементы а, . . ., с содержались в Sta. Так как формула (Эх) Л (х) имеет сигнатуру ?2? , истинна в 95 и SIa <г <г95, то указанная формула истинна и в Sta, т. е. S (d) истинна в Sta для подходящего d Є Sta. Из SIaCr следует, что Л (d) истинна в 95. Поскольку d ? Si, то в силу теоремы 1 Sl < г95.
§ 10. Полнота и модельная полнота
Допустим, что рассматривается класс каких-то структур в самом общем понимании этого слова, для которых определено понятие изоморфизма. Пусть система утверждений сформулированных на каком-то языке 3, выделяет из всех упомянутых структур некоторый подкласс. Система утверждений (или аксиом) <& называется категоричной, если все структуры, обладающие свойствами <а, изоморфны. Система © называется полной (в языке Е), если все структуры, обладающие свойствами <г, B-эквивалентны, т. е. если любые две (^-структуры обладают совершенно одинаковыми свойствами, допускающими § 10]
полнота и модельная полнота
249
формулировку на языке В (Е-равносвойственны). Если язык В совпадает с языком 1-й ступени, а рассматриваемые структуры — алгебраические системы данной сигнатуры, то общее понятие B-полноты системы аксиом переходит в точное понятие элементарной полноты, которое и будет изучено в этом параграфе.
10.1. Полные совокупности формул. Как и в § 9, через Г обозначим какой-нибудь класс формул 1-й ступени, инвариантный относительно изменения наименований предметных переменных, встречающихся в формулах этого класса.
Пусть 3 — совокупность каких-то закрытых Г-фор-мул данной сигнатуры ?2. Говорят, что алгебраическая система St удовлетворяет системе 3 или что совокупность <& выполняется на системе St, если сигнатура St равна Q и каждая формула из <& истинна на St. Формулы @ часто называют аксиомами, а алгебраические системы, на которых выполняется совокупность называются моделями (?. Совокупность (3> называется совместной (или выполнимой, см. п. 6.4), если существует хотя бы одна алгебраическая система, удовлетворяющая €>. Формула Л называется следствием совокупности 3, если Л истинна в каждой алгебраической системе, удовлетворяющей
Совокупность формул © называется Г-полной в сигнатуре Q, если совокупность © совместная и для каждой Г-формулы Л сигнатуры Q либо Jt, либо ~~1 Jh является следствием совокупности (?>.
Символом TQ условимся обозначать класс Г-формул, имеющих сигнатуру ?2. Ясно, что свойства совокупности <3 быть Г-полной в сигнатуре Q и быть Гй-полной равносильны. Ясно также, что Г?2-полнота совокупности <В влечет TjQj-полноту <& для любых T1 S Г, Q1 ^ Q.
Если Г есть совокупность произвольных формул 1-й ступени, то Г-полнота в сигнатуре Q называется просто полнотой в сигнатуре Q (Q-полнотой). Наконец, совокупность формул @ фиксированной сигнатуры Q называется. полной, если полна в сигнатуре Q.
Пусть предикатный символ P не содержится в сигнатуре Q совокупности формул (э. Тогда ни формула (Vx) P (х, . . ., х), ни ее отрицание (Эх) 1 P (х, . . ., х) не следуют из и потому совокупность @ не может 250.
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Глі IV
быть полной ни в какой сигнатуре, содержащей Р. Аналогично, если предметные символы а, b не содержатся в ?3, то ни формула а = Ъ, ни формула а Ф b не следуют из (S, и потому <з> не может быть полной в сигнатуре, содержащей символы а, Ъ. За исключением тривиальных случаев, совокупность @ не может быть полной и в сигнатуре, содержащей предметный символ а, не встречающийся в формулах совокупности (?>. Таким образом, когда идет речь о полноте совокупности формул (3, имеющей сигнатуру ?2 и полной в сигнатуре Q1, то можно без существенного ограничения общности предполагать, что Q1 s Q.
Указанному выше определению полноты можно придать иной вид.
Следствие 1. Для того чтобы совокупность формул €> была T-полной в сигнатуре Q, необходимо и достаточно, чтобы все алгебраические системы, удовлетворяющие <2, были YQ-эквивалентны.
Необходимость. Пусть модели Si, 35 для совокупности <& не TQ-эквивалентны. Это означает, что существует TQ-формула Л, истинная на одной из указанных моделей и ложная на другой. Поэтому ни Л, ни П Л не следуют из
Достаточность. Пусть St, 25 — модели для TQ-полной совокупности формул <2>. Рассмотрим произвольную TQ-формулу Л, истинную в 21. Так как либо Л, либо H Л должна следовать из и 1Л заведомо из <& не следует, то Л следует из <&, т. е. Л истинна на всех ©-моделях, в том числе и на 95.
Следствие 2 (теорема Линденбау-м а). Каждая совместная совокупность формул <? сигнатуры Q может быть пополнена до полной совокупности формул сигнатуры Q.
По условию совокупность @ обладает некоторой моделью St сигнатуры Q. Обозначим через Tq (21) совокупность всех формул сигнатуры Q, истинных в 21. Ясно, что @ = Ta(St). С другой^ стороны,*для каждой формулы Л сигнатуры Q либо Л, либо П Л истинна на Й, и потому либо Л, либо H Л содержится в Tq (SE), а потому и следует из Tq (St). Поэтому Tu (21) — искомое пополнение § 10]
