Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
{A, I Ja = H) = WstD0, »x
то Jt истинна на 55 при любом s, т. е. модель 55 бесконечна. В силу леммы 4 I S5 I ^ 2Ко.
Теорема 3 дает точную информацию о мощности фильтрованного произведения для фильтров над счетным множеством I, но из нее не видно, как растет мощность ультрапроизведений с ростом мощности I. Этот пробел отчасти заполняет
Теорема 5 (см. Фрейн, Морел и Скотт [66]). Для каждого бесконечного I существует такой фильтр D, что для каждого фильтра D1 э D и каждой бесконечной системы Sf
\Ш1 ID1I^ 21Ц.
Доказательство основывается на следующей лемме Чанга и Кислера о вложении декартовых произведений.
Лемма 6. Пусть (/? [ к (? К) — последовательность подмножеств множества I, содержащая все конечные224 ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Гл. IV
непустые подмножества I и (Sfct | а 6 I) — последовательность каких-то алгебраических систем Sfa данной сигнатуры Q. Тогда существует такой фильтр (К, D), что для любого фильтра D1 D над К существует изоморфное вложение
П Я--> П ( П Иа)/А- (7)
Для каждого a 6 / полагаем
La = {k j a G Jh}. Для произвольных а, ..., у ? I
Laf\... C\Ly = {le 1 OE, ..., VеЛ} =H= 0,
поэтому совокупность всех надмножеств пересечений Z/a П • • • П L^ в К образует фильтр D над К. Этот фильтр и удовлетворяет требованиям леммы 6. Действительно, каждой функции / Є П Sta. ставим в соответствие функцию /рб П П Sfct, определенную УСЛОВИЯМИ
и (к) (ai) =f (а) («6 Jk).
Остается только показать, что из g=^f (g, /(їП^Іа) следует gp щкПі fp. По условию g (а) ф / (а) для какого-то и потому oL^Jk=^gp(к)Ф^p(к), т. е. {к I gP (к) Ф fp (к)} э La. Отсюда
{к\§р(к)Фір (к)} ев,
и, следовательно, gp
Теорема 5 непосредственно вытекает из леммы 6. В самом деле, так как множество I бесконечно, то существует однозначное отображение a -+Ja множества I на совокупность всех его конечных непустых частей Ja, и потому, применяя лемму 6 к фильтрованной степени їїVD1, можно положить K = I. Из соотношения (7) получаем
1*г|<1П(И'в)/А|
или
21 J1 ^ 1 S[J I с П |9IJa|/A- (8)
at=I§ 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 225
По предположению, система її бесконечна, поэтому (п. 2.6) I aJ« I = І її |. Заменяя в формуле (8) | Я7« 1 на І її I, закончим доказательство теоремы 5.
Как уже говорилось, теоремы 1—5 дают лишь общие оценки для мощностей фильтрованных произведений, однако достаточные для основных приложений. Ряд более тонких оценок указан в дополнениях к этому параграфу.
8.6. Регулярные произведения. Почти одновременно с фильтрованными произведениями были открыты регулярные произведения, которые тоже стали играть заметную роль при изучении проблем языка 1-й ступени.
Рассматривают две сигнатуры Q0 и Q1. Предполагается, что сигнатура Q1 содержит символы теоретико-множественных операций U, П, символ теоретико-множественного предиката включения s=, символ пустого множества 0 и, возможно, еще какие-то предикатные и функциональные символы.
Через S (I) обозначим множество всех подмножеств множества I. Алгебраическую систему @ сигнатуры Q1 назовем алгеброй подмножеств, если ее основное множество есть S (I) для некоторого множества /, а сигнатурным знакам U , П » 0 сопоставлены в качестве их зна-
чений в алгебраической системе <В соответственно теоретико-множественные операции объединения, пересечения, дополнения подмножеств множества I, теоретико-множественный предикат включения на S (I) и пустое подмножество.
Пусть каждому элементу а какого-то непустого множества I пооставлена в соответствие некоторая алгебраическая система аа = Q0) сигнатуры Q0. Рассмотрим декартово произведение M =\\ Aa (a QI). Пусть Jb (хх, ...,хп) — формула ПИП сигнатуры Q0. Через Ki^aqn (/„ ...,/„) для fi, . .., fnQM обозначим множество
{«Є I \ Jb (ft-----/?)==#).
В частности, если Jb — закрытая формула сигнатуры Q0, то
15
А. И. Мальцевт
ЙРОЙЗВЇЗ ДЕНЙЯ Й ПОЛНЫЕ КЛАССЫ [Гл. IV
Из этого определения непосредственно вытекают, например, такие свойства:
вЛИ«! "Ы,. , v гч , -
k^iA Ui. --т M = i \ Uu "-,Jn),
И91а1«61}
= a^Zj (/!' U) Il КАг Uly, In),
тугШа I ., ,
iyAiV^2 ^1' --'b/-
„{SlJaSO ,, , . ШаІ aei>
— Wi- •• Ui,---,Tn),
(/2т --T Tn)= U A^ (g, h, • • Jn).
Будем рассматривать всевозможные последовательности I = (i?; • ¦ •) Am), где SB — формула ПИП сигнатуры Q1, а . . ., ,^fm — формулы ПИП сигнатуры Q0. Последовательность | назовем допустимой, если все свободные предметные переменные формулы J? содержатся во множестве . . хт. Свободными
переменными последовательности I назовем те и только те предметные переменные, которые входят свободно хотя бы в одну из формул Aq, . . ., Am.
Последовательность ? называется стандартной допустимой, если свободные переменные і есть в точности х0, ..., Xh для некоторого натурального к. Последовательность I называется разбивающей, если формулы A0 \/ ... \J Am, H (At &Aj) (t < J < т) являются тождественно истинными.
Пусть {?> = (S (I), Q1) — алгебра подмножеств. С каждой стандартной допустимой последовательностью