Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Отметим одно следствие, непосредственно вытекающее из теоремы 8.
Следствие 9. Пусть класс формул T содержит конъюнкции атомарных и отрицаний атомарных формул, а также 3-закрытия указанных конъюнкций. Тогда из T-эквивалентности алгебраической системы St какой-нибудь конечной алгебраической системе вытекает изоморфизм систем St и Sb.
Класс Г удовлетворяет условиям теоремы 8 и следствия 4. Так как St =у 55, то по теореме 8 существует Г-вложение о системы St в подходящую ультрастепень Sb1ID. Согласно следствию 4 о есть изоморфизм St в Sb1ID. § 9] НЕОТЛИЧИМОСТЬ И ЭЛЕМЕНТАРНАЯ ЁЛОЖИМОСТЬ 243
По условию система 95 конечна, и потому SB1ID изоморфна 95. Итак, существует изоморфизм SI в откуда | St | ^
< I® I.
Меняя теперь ролями SI и 95, получим | 35 | ^ | SI |. Следовательно, 1 SI | = | 25 и упомянутый выше изоморфизм SI в 95 на самом деле есть изоморфизм SI на 95.
9.2. Элементарные подсистемы. В предыдущем пункте было введено понятие Г-элементарной подсистемы алгебраической системы. Теперь мы хотим более подробно рассмотреть свойства совокупности всех Г-подсистем заданной системы. При этом всюду (в данном пункте) будем предполагать, что класс Г формул 1-й ступени удовлетворяет следующим требованиям:
i) Все формулы из Г имеют предваренный вид. Если в произвольной Г-формуле переименовать связанные и свободные переменные, то получится снова Г-формула.
ii) Для каждой Г-формулы Jk существует Г-формула, равносильная Jk.
iii) Если (Qx) Л Є Г (Q = З, V), то Л 6 Г.
Пусть задана подсистема Si. Как и в предшествующем пункте, каждому а ? St ставим в соответствие предметный символ za и предполагаем, что символы Za не входят в сигнатуру Q системы Si. Через обозначаем объединение Q и совокупности всех символов JSa (а ? Si). Элемент а будем называть значением символа Za. Пусть SI — подсистема системы 95. Тогда Q81 ^ Q?g. В каждой закрытой формуле Л сигнатуры Qgl свободными предметными переменными могут быть лишь предметные символы из Q и предметные символы вида za. Так как и те и другие символы имеют фиксированные значения в SI и в 95, то истинное значение формулы Jk определено как в Si, так и в 95.
Подсистема алгебраической системы SI сигнатуры 95 называется Q-элементарной подсистемой (Г-подсистемой, символически St<Cr95), если каждая формула Л сигнатуры ?2?, истинная в Si, истинна и в 95.
Как уже указывалось в п. 9.1, из свойства ii) вытекает, что подсистема SI алгебраической системы 35 сигнатуры Q тогда и только тогда Г-элементарна в 95, когда каждая Г-формула сигнатуры ?2?, истинная в 95, истинна в Si.
16* 244 Произведения и полные классьї trn. iv
Простой и удобный признак элементарности подсистемы указывает
Теорема 1. Для того чтобы подсистема И алгебраической системы 55 сигнатуры Q была Г -элементарной, необходимо и достаточно, чтобы из истинности в 95 произвольной T-формулы вида (Эх) JF(х), имеющей сигнатуру Йц, вытекала истинность в 95 формулы JF(za) для подходящего а из И.
Необходимость очевидна. Докажем достаточность. Пусть SI и 95 удовлетворяют условиям теоремы 1. Надо доказать, что из истинности в 95 предваренной Г-фор-мулы Л сигнатуры Qgj вытекает истинность Jb в Si. Доказательство ведем индукцией по числу п кванторов в Jb. Если п = 0, то утверждение тривиально. Пусть для Г-формул, имеющих п ^ 0 кванторов, утверждение справедливо, и пусть Jb имеет вид (Эх) 38 (х), где 38 (х) содержит п кванторов. По условию (Эх) Jg3 (х) истинна в 95 и, следовательно, для некоторого а ? SI формула S (za) истинна в 95. Но 38 (za) имеет п кванторов и сигнатуру Йщ. В силу индукции 38 (Za) истинна в Si, и потому (Зх) 3$ (х) истинна в Si.
Если Л имеет вид (Vx) 38 (х) и формула (Vx) J? (х) истинна в 95, то (za) истинна в 95 для, любого а 6 Si. По индукции из истинности JF (za) в 95 вытекает истинность 38 (Za) в Si, и потому (Vx) 38 (х) истинна в И.
Из теоремы 1 непосредственно вытекает «алгебраическое»
Следствие 2. Если для каждой конечной совокупности U1, . . ап элементов подсистемы SI алгебраической системы 35 и каждого Ъ ? 95 существует автоморфизм о системы 95, оставляющий неподвижными элементы at, . . ., ап и переводящий Ъ в некоторый элемент St, то подсистема SI элементарна в 95.
Согласно теореме 1 достаточно показать, что из истинности в 95 формулы
Jb {Ь, aI, ••• і aJi) (olt • • • , О-п 6?, &€»),
имеющей в сигнатуре Q в качестве свободных символов лишь alt ..., ап, b, вытекает истинность в 93 формулы Л (a; аи ...,On) для подходящего а ? St. Так как § 9 ] НЕОТЛИЧИМОСТЬ И ЭЛЕМЕНТАРНАЯ ВЛОЯШМобТЬ 23?
а—автоморфизм 35, то (п. 6.3)
H==Jtib1O1, ...,an)<=>Jk (bo, Ct1O, ..., апа) =H so да
<=> J (bo, CL1, ..., ап) = И,
то
где bo Q Я, что и требовалось.
Теорема 3 (A. T а р с к и й [64]). Произвольное множество M элементов произвольной алгебраической системы. 95 сигнатуры Q содержится в ее подходящей элементарной подсистеме 21, мощность которой не превосходит max ( I M I, I Q I, н0). Положим
ttt = max(|.M|, |Q|, н0)
и рассмотрим совокупность S всех закрытых формул сигнатуры Qm, имеющих вид (Зж) Jk (х) (Jk (х) может содержать кванторы) и истинных в 95. Согласно п. 2.6 | S [ = = ш. Для каждой формулы (3z) Jk (х) ^ S выберем в 95 какой-нибудь элемент а, для которого Л (а) истинно в 95, Совокупность всех выбранных элементов обозначим через M1. Мощность M1 не превосходит мощности множества всех закрытых формул сигнатуры Qjtf, т. е. не превосходит ш. Так как для каждой формулы вида (Зж) (х = а) (a Q М) придется выбрать именно элемент а, то M = M1.
