Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Xm)', А о (х0, • . . , Xjl), . . . , Am (Xq, . . . , Xk))
свяжем (к + 1)-арный предикат Qi на М, полагая для /о, heM
.. • . .. Л). ¦ K1JklaenV* .... h))=H. § 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 227
Занумеруем все стандартные допустимые последовательности трансфинитными числами, меньшими ?, и пусть ga — стандартная допустимая последовательность, занумерованная числом а.
Полным регулярным произведением (i ? J) алгеб-
раических систем Stj (i QI) по алгебре подмножеств © =
@
= (S(I)fQl) назовем модель (M,{Q%a}) (a<?).
Регулярными произведениями алгебраических систем Sti (г?/) по алгебре подмножеств @ называются обеднения модели ^ai (ієі).
Если все модели Sti совпадают с одной и той же моделью St, то вместо (i 6 і) ішшут st®. Модель St®
называют полной регулярной степенью алгебраической системы St по алгебре подмножеств а обеднения модели St® называют регулярными степенями модели St по алгебре подмножеств (©.
Пусть Q = Q (Q0, Q1) = {<?ga} (а < ?). Каждому Qia сопоставим предикат Qfa, после чего на аГ>®2Гі (і в I) можно смотреть как на модель сигнатуры Q.
Приведем примеры регулярных произведений.
Пример 1. Пусть Q1 = ((J , П , 0). G каждым
«-арным предикатным символом P из Qo свяжем стандартную допустимую последовательность
= ..., з„-і)>.
С каждым л-арным функциональным символом F из Q0 свяжем стандартную допустимую последовательность
^ ^ = (X0 = 0; F (х0, .. ., Xn-j) = хп).
Теперь для /о, ..., fn-i?M Q^P) (/о, . •fn-i) = n<=>
<=> I \ Kp^.....«„-!) (jfo, • • • , in-l) = 0 <=>
AP(K0.....(10, ¦ • • , Jn-l) = і -
Аналогично
Ql(F) (to, fn-i, и)=И-<е>
<=> .,Xn~i)=xn \Jo> • • • , Jn-Ii Jn) — 1 •
15* 228
Произведения и полные классы Еґл. rt
Поэтому, если <& = (S (I), Q1) — алгебра подмножеств, Q' = <<??(f), Q^(P) I F, P Q Qo), то Q'-обеднение
модели (і Q I) является моделью, представляющей
декартово произведение алгебраических систем Я? (г Q I) (разумеется, с точностью до наименования главных операций и предикатов).
Пример 2. Пусть Q1 = < U , П , 0, Fin),
где Fin — символ унарного предиката, Q0 = (•, е), где • — символ бинарной операции, _1 — символ унарной операции, е — символ выделенного элемента. Пусть 2t; (i Ql) — группы (в которых • — операция умножения, — операция взятия обратного элемента, е — единица), а @ = (S (/), Q1) — такая алгебра подмножеств, что Fin (х) = И тогда и только тогда, когда х — ©
конечное подмножество множества I. Если
I0 = (Fin (х0); х0 фе); I1 = (х0 = 0; х0 ¦ X1 = лг2); І2 = (х0 = 01 X'1 = X1); I3 = (х0= 0; X0 = е),
то, как уже было замечено, (Q^1, Q%2, (?g3 )-обеднение модели аР1®^ (i Q I) есть модель, представляющая декартово произведение групп (i Q I). Легко понять также, что Q^0 (f) = И тогда и только тогда, когда fa Ф е только для конечного множества а из I.
Пример 3. Пусть Q1 = <U, П, ", 5=, 0, D), где D — символ унарного предиката. Для простоты будем предполагать, что Q0 содержит только предикатные символы. Пусть Sta (a Q I) — модели сигнатуры Q0.
Рассмотрим алгебру подмножеств <3 = (S (I), Q1), в которой множество всех тех X Q S(I), для которых D(x) = И, образует фильтр D на I.
Для каждого гс-арного PQ Q0 рассмотрим стандартную допустимую последовательность i(p) = (Z>(ar0); Р(х0, . . ., Xn^1)). Тогда для /о, ..., fn-i Q M
Q%p) (/о, - ..,fn-i) = И о
<=>D (isTpfi",'.. f, ед-і) (/о, • • •, fn-i) — И. § 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 229
Другими словами, Qf(P) (/о- • • •, U-1) = MoP (UD, ..., Іп-їЩ
Рассмотрим еще последовательность | = (D (х0)\ X0 = X1).
©
Понятно, что для /о, fi?M Qi (f0, /і) тогда и только тогда истинно, когда f0D = J1D.
<5
Легко Проверить, что Qi есть отношение конгруенции на модели {M, [Qf(P))) (Р E ^o) и что фактор-модель по этому отношению Qf модели <M, (Qf(P))) (Р 6 Йо) и есть
П SIaAD (а?/). Эта проверка фактически проделана в п. 8.2.
Приведенные примеры показывают, что понятие регулярного произведения охватывает многие алгебраические конструкции. Важные применения нашла поэтому следующая
Теорема 1. Существует эффективная процедура, которая каждой формуле Г(xi(t, . . ., xift) ПИП сигнатуры Q = Q (Q0, Q1), где Xi0, . . ., Хі — попарно различные переменные, сопоставляет такую стандартную допустимую разбивающую последовательность
Ь — 1 О (xOi • • ч xk) 1---1 <Дт (xOi ¦ • • 1 xk))i
что
а) для любого непустого семейства SIa = (Аа, йо> («ЄЛ алгебраических систем сигнатуры Q0 и для любой алгебры подмножеств @ ={S (I), Q1)
(Vxio .. . xih) (Г (хій, ..., xih) ++ Qf (xio, ..., xih)) =z if *);
б) в частности, если Г — закрытая формула сигнатуры Q, то JIq, ..., Jim—закрытые формулы сигнатуры Q0 и
T = И <=> Qf == И.
*) $ используется как сокращение формулы (Л 3$) &
& (JB Jt). 230
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Гл. IV
Доказательство проведем индукцией по числу знаков V, 3, встречающихся в записи формулы Г, предполагая, что в записи формулы Г не встречаются знаки V, &.
Предварительно докажем, что каждой стандартной допустимой последовательности I' = (J?', J'0, . . ., Jm-) можно эффективно сопоставить стандартную допустимую разбивающую последовательность | с теми же самыми свободными переменными так, что для каждой алгебры подмножеств <3 = (S (I), Q1) и для каждого семейства SIa = (Аа, Q0) (а ? I) алгебраических систем сигнатуры Q0 предикаты Qf и Qf совпадают на M', = [J Aa (a ? I).
