Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Пусть т = 2"1'+1, и пусть г0, . . -, rm — последовательность всех подмножеств множества {0, 1, . . ., т'}. Для каждого натурального к т пусть
j?rh ІЄ{0, 1.....m'}\rk
(при этом конъюнкцию пустого множества формул считаем тождественно истинной формулой). Пусть для каждого натурального ?<т'
si={k\k*Cm&.l? ги),
и пусть
SS=SS'({) Xh, U Xh),
где для конечного множества s натуральных чисел U^i= 0, если S пусто, И U^i есть ( U Xi) U Xh, если к —
i?s i?s i?s'
наибольшее число в s и s' = s \ {/ь}. Непосредственно проверяется, что g = J0, ..., Jm) — стандартная допустимая разбивающая последовательность и что предикаты Qi
<3
и Qi> совпадают на М.
Возвратимся к доказательству теоремы- Сначала рассмотрим случай, когда Г — атомарная формула.
Если Г есть qi (хі0, . . ., xik), достаточно просто сослаться на замечание, с которого мы начали доказывать эту теорему.
Если же Г есть Qy (хіо, ..., xh), где j0, ..., ^ — некоторые из чисел г'о, . . ., ifc, то положим = (SS \ J'u, . •. - J'm).• § 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 231
Пусть А% получается из Ai заменой хт на Xm- для каждой такой пары (т, т'), что Xjm есть xim, (т = 1, ...,s; т'= 1, ...,к). Непосредственно проверяется, что последовательность І = (38; Ай, ..., Jbm) удовлетворяет условию а); эту последовательность | можно превратить в разбивающую.
Если Г есть Xia=Xil, в качестве последовательности ? возьмем (X0 = 0; X0=X1, X0=^X1), и если Г есть Xio= хіо, в качестве I возьмем (х0 = 0; ха = х0, х0Ф х0).
Если T1 есть Qll (x.i,..., х.г), где I1=^1; А\, ..., A1mi),
F2 есть Qb (х.%, . ..,X г), где I2 = A20, ..., Ah2), сна-
j о ^f2
чала заметим, что Q^1 (х0, .. ., хп) V Q\a(xsl+i, ¦ ¦ ., zSl+S2+i) есть Qi (х0, ..., zSl-fS2+i) для подходящей последовательности В качестве такой % можно взять последовательность
j (х0, . . . , Xmi) \j 382 • • • і ^mi+m2+l)> Jk0>
• • •, Am^, AQ (®8х+ІІ • ¦ • І Xg^g^i), . . .
Zei-N2+і)>-
Теперь I11 V г2 есть Q1 (X.i, ..., X i , х.%, .. ., х.2), — и дело
9 J О J-S^JO JS^
свелось к уже разобранному случаю.
Если формула Г есть Qf (xj0, ...,Xjs), то H Г есть Ql (xj0, ..., Xjs), где 1 = (^ 38; A0, ..., Am), если I' = = (Ж; A0, А ті'
Остается рассмотреть случай, когда формула Г есть (3z{ft+1) Qv (хій, xh.....xih, xikJ. Пусть V — разбивающая последовательность и = (38'; .. ., А'т). Пусть Ai есть (3Xih+i)Al, а 38 есть
(By0) • • • (Зут) ( U Vj = 0 & Д (Vif)Vj= 0)&
i^m Ki^m
& Д (yj<=Xj)&&'(y0t ...,Vm))-
Пусть 1 = (38; A0, ..., Am). Покажем, что і удовлетворяет условию а). 232
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Гл. IV
. Пусть /о, ..., UeM и Q1 (/о, ..., fh) = И. Тогда найдутся такие подмножества у0, . . ., ут в I, что
(Уо, ...,Ут)=И, ©
Vi S K?^V (/о, ••.,/*), Уо U ••• U Ут = I
и множества г/0> • • ч Ут попарно не пересекаются. Если а ЄI, то найдется одно и только одно такое натуральное /<яг., что а Є Уі- Значит, существует такой ft+ \Є
aqi,, что
А'і (/о, fk+i) =и• Покажем, что
VXa
Qv (/о, • ¦., U, Ых) = И. Надо показать, что 3?'(K{J?]a?I}(f0, ...,fk, !ш),...
• • • ч k^Il! Є }(/о, • • U, fh+i))==H.
т <?э
тт ту IcJa^ /j , j- V
Но Kj=K^r (/о, ..., fk, fk+O^yj, множества
К о, ..., ^Tm попарно не пересекаются и их объединение
есть I. Значит, Kj^yj. Теперь 38' (K0, ..., Km) = И.
<3
Наоборот, пусть /0, ..., UeM и Г(/0, ..., fh) = И. Тогда найдется такой fu+іЄМ, что Qv (f0, ..., fh, fh+l) =И.
Пусть у j = К^Ъ?1 } (/а, • -, fh+i)- Тогда по определе-
з
нию Qi', у о, ..., ут попарно не пересекаются, их объединение есть I, 38' (уо, ..ут) = И. Кроме ТОГО, Уі є
©
= •••' /*)• Это показывает, что
Qi(U^U) = H.
Построенная последовательность ^ может не оказаться разбивающей, но ее можно будет превратить в разбивающую. Теорема 1 доказана.
Напомним, что элементарной теорией Th (й) класса й алгебраических систем сигнатуры а называется совокупность всех закрытых форм ПИП сигнатуры о, истинных на всех системах из класса SL Элементарная теория класса й называется разрешимой, если существует алго- § 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 233
ритм, который по произвольной замкнутой формуле ПИП сигнатуры о определяет, принадлежит эта формула Th (Я) или нет.
Простым следствием теоремы 1 является Теорема 2. Пусть Я — класс алгебраических систем сигнатуры Q0, S — класс алгебр подмножеств сигнатуры Q1, cPg O—класс всех таких моделей ар1®?!« (а?/), что для всех и основное множество алгебры под-
множеств @ есть S(I). Если теории Th(S) и Th(S) разрешимы, то теория Th (ZPfti g) тоже разрешима.
Пусть Г-—замкнутая формула сигнатуры Q = Q (Q0, Q1). Найдем такую допустимую разбивающую стандартную последовательность \ = .. ., с4т), которая удовле-
творяет условию б).
Для каждого Лі определим, верно ли, что H Jbi ? Th (R). Пусть t—множество всех тех натуральных для
которых H Aj 6 Th (Я). Пусть
Y = (Vx0 ...ят)(( U х,= 0&
j^m
& Д (Xj П Xi--= 0)& Д Xj = 0)->&(хо, ..., Xm)).
i<i<:m j?t
Мы можем определить, верно ли, что 1P^Th(S). Покажем, что
