Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Так как из элементарности подсистемы какой-либо системы заведомо следует ее примитивность в этой системе, то необходимость условий теоремы 4 вытекает из теоремы 3- Поэтому будем доказывать достаточность, 262. ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Глі IV
Временно будем говорить, что формула A (zl5 . . хп) сигнатуры Q со свободными предметными переменными X1, . . ., хп ©-сильная, если для каждой ©-системы 21 и каждых а1у . . ., ап из 21 либо формула A (zai, . . ., zan), либо формула A (zai, . . ., zan) вытекает из совокупности ©LIZ) (21). Нам надо доказать, что несильных формул сигнатуры Q нет. Допустим, напротив, что несильные формулы указанного вида есть. Так как все формулы, равносильные несильным, несильные, то есть и несильные формулы предваренного вида. Пусть А (Xi, . . ., хп)— несильная формула предваренного вида, имеющая наименьшее число к кванторов. Так как все формулы сигнатуры й, не содержащие кванторов, очевидно, сильные, то 1. Из определения следует, что вместе с А несильной будет и формула H А. Пусть (3у) 98 (у, xit . .., хп) — та из формул А, н А, которая в предваренной форме начинается квантором существования. Таким образом, формула (Зг/) 98 (у, X1, . . ., хп) несильная, а формула 98 (х0, Xi, . . ., хп) уже сильная. Первое означает, что для подходящей ©-системы 2[ и подходящих ее элементов ал, . . ., а„ каждая из совокупностей
<Sl)?>(2[)U{(3V) Я {у, Zai, ---,Zan)) (8)
U D (21) и П т SS (у, Za1, . . . , Zan)) (9)
совместна.
Рассмотрим произвольную систему 35, удовлетворяющую аксиомам (8). Так как совокупность (8) содержит формулу (3у) 98 {у, Za1, ¦ - ., Zan), то для некоторого b ?93 в 95 истинна формула JF (zb, zai, . . ., zan). Но формула 98 (х0, Xi, . . ., хп) ©-сильная, 95 есть ©-система и для элементов Ь, CLi, . . ., Cin из 95 формула 98 (zb, zai, . . ., zan) истинна в 95. Поэтому формула 98 (zb, zai, . . ., zan) является следствием совокупности
(10)
Из 98 (z6, zai, . . ., Zan) формально вытекает формула (3у) 98 (у, Zai, . . ., zan), и потому из совокупности (10) вытекает формула (Iy) 98 (у, zai, . . ., zaJ.
Совокупность (10), вообще говоря, бесконечна, но в силу теоремы компактности найдется некоторая конеч- § 10] ПОЛНОТА И МОДЕЛЬНАЯ ПОЛНОТА 263
ная часть M совокупности (10), из которой также будет вытекать формула (Ву) S (у, zav . . ¦ , zan). Обозначая через (Si конъюнкцию формул из (а, входящих в M, и через D1 — конъюнкцию формул из D (33), входящих в М, видим, что формула
& D1 -> (Зу) M (у, Za1, Zan) (11)
тождественно истинная.
В' сигнатуре Q формула S1 закрытая, а формула Di может содержать и свободные предметные переменные. Это будут символы вида Z0 (с ?35). Они частью будут совпадать с некоторыми из символов zai, ¦ Zan, а частью будут новыми—символы вида zcv .. ., zcv, где аь . . ., ап, c1, cv—попарно различные элементы системы 35.
Поэтому формулу (11) можно более подробно переписать в виде
SiD1 (Zav ..., Za-a, ^cji) • • •» zCp) ' (3 у)?(у, Zai, • • • , Zan)-
(12)
Так как D1 есть часть диаграммы системы 35, то в 33 заведомо истинна примитивная формула
(3zCl ... zCp) D1 (zai, •. ., zan, zci, . .., zCp).
По условию теоремы отсюда следует, что в системе Sf найдутся элементы ап+1, .. ., ап+р, для которых будет истинна'формула
Dі (.Za1, • • • , Zan, ZajlJrl, . . . , Z0n+p). (13)
Подставляя в тождественно истинную формулу (12) вместо свободных предметных переменных Zc1, ... , zcp соответственно переменные zan+l, . . . , zan+p, получим формулу
©і ^D1 (zai, . . •, zan, zan+v ..., zan+p) >
->(Эу)® (у, Zai, ¦ • • , Zan)) (14) і
которая будет также тождественно истинной. Формула (13) есть конъюнкция части формул из D (?). Это совместно с формулой (14) означает, что формула
(Зу) % (у, zav . .., zan) 264.
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Глі IV
является следствием совокупности
@и л (И),
что противоречит выполнимости совокупности (9).
Пусть Г — какой-то вид формул. Условимся говорить, что класс Sl систем сигнатуры Q Y-приводим, если для каждой формулы A (Xi, . .., хп) сигнатуры ?2 со свободными предметными переменными x1, ..., хп существует формула JF (хи ..., хп) вида Г сигнатуры Q такая, что на каждой Я-системе истинна формула
(Vx1 ... хп) (A (xi, . . ., хп) SB (.X1, . .., хп)), (15)
т. е. если на ^ каждый формульный предикат эквивалентен предикату, определяемому подходящей формулой вида Г.
В частности,. класс й систем называется 3-приводимым, если каждая формула А (хх, . . ., хп) на этом классе эквивалентна подходящей 3-формуле. Ясно, что если класс S? 3-приводим, то он и V-приводим, так как из эквивалентности формулы А какой-то 3-формуле 98 вытекает эквивалентность формулы А V-формуле H SB.
Совокупность 3 закрытых формул сигнатуры ?2 называется Y-приводимой, если Г-приводим класс всех систем сигнатуры ?2, на которых истинны все формулы из 3, т. е. если формулы (15) являются следствиями совокупности з.
Теорема 5 (А. Робинсон [55]). Для того чтобы совокупность формул 3 была модельно полной, необходимо и достаточно, чтобы она была 3-приводимой.
