Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
имеющей хорновский вид.
Заметим еще, что каждая хорновская формула, содержащая термы, легко преобразуется к хорновской формуле (1), в которой все подформулы Qpij являются атомарными формулами вида R (xiv . . ., xip) (iu . . ., ip = 1, ... . . ., n), где R или принадлежит Q, или отвечает функциональному символу из Q. Для этого достаточно каждый терм заменить его выражением, указанным в п. 7.1.
А. Хорном [71] было показано (см. также п. 7.5), что все закрытые хорновские формулы мультипликативно устойчивы. Здесь мы докажем следующее более сильное утверждение, восходящее к статье Чанга и Морел [75].
Теорема 1. Все формулы хорновского вида — условно фильтрующиеся в любом фильтре. В частности, если замкнутая хорновская формула А истинна в каждой алгебраической системе Stcc (а ? I) фиксированной сигнатуры, то А истинна и в произведении [] SaAD этих систем, фильтрованном по любому фильтру D над I. Предварительно докажем следующую лемму. Лемма 2. Если формулы <9^, ...,35? со свободными предметными переменными хи ..., хп сигнатуры Q филь- § 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 215
труются в фильтрованном произведении її = П ^iJD алгебраических систем Slct сигнатуры Q, а формула • • хп) условно фильтруется в указанном произведении, то формулы
условно фильтруются в указанном произведении.
Согласно лемме 5 из п. 8.2 формула оР = & ... & ^ft фильтруется в упомянутом произведении, т. е.
сР = И<=>{а І оР — И) Q D, Sl 1 1 Я«
и, следовательно,
11 Sfa аа а
Поэтому формула & = 1 ?f*i\/ .. aPk. определяет условно фильтрующийся предикат.
Покажем, что формула сТ>—> также условно фильтруется. Пусть {a I —> — И} ? D. Надо убедиться, что
а<х
^==IF влечет сГ'0==:if. Так как предикат 8і фильтруется,
то из следует {a I if3 —И) f D. Но
а Sla
Ша, ^a «я
И потому
Перейдем к доказательству теоремы 1. Мы можем предполагать, что формула Л (xu . . ., zm) имеет вид (1) и при этом формулы &І) атомарные. Атомарные формулы фильтруются на любом фильтре. В силу леммы 2 заключаем, что подформулы . . ., Л$ в формуле Ji условно фильтрующиеся. Применяя теперь лемму 6 из п. 8.2, видим, что формула Jkfa . . . &Jks, а вместе с нею и сама формула Jt, условно фильтрующаяся.
Из определения понятия условной фильтруемости непосредственно видно, что если какая-нибудь формула Л условно фильтруется на некотором произведении, то каждая формула, эквивалентная Л, также условно фильтруется на этом произведении. Поэтому из теоремы 1 следует, что каждая формула, эквивалентная формуле 216
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ [Гл. IV
хорновского вида, условно фильтруется на любом фильтрованном произведении.
В предположении истинности обобщенной гипотезы континуума *) К и с л е р [20] доказал, что обратное утверждение также верно: если формула условно фильтруется на любом фильтрованном произведении, то она эквивалентна формуле хорновского вида.
Возникает вопрос, не будет ли условная фильтруемость формулы на фильтрах какого-нибудь частного вида достаточной, чтобы формула была эквивалентна формуле хорновского вида? В частности, в течение некоторого времени в литературе обсуждалась гипотеза, что условная фильтруемость формулы на декартовых произведениях достаточна для приводимости формулы к хорновскому виду. Однако Чанг и Морел [75] нашли примеры, опровергающие эту гипотезу. Одним из таких примеров может служить формула
(ЗаЬ) (Vx) (а Ф Ъ &ах = а &Ьх = а\/ Ъх = Ъ). (2)
Эта формула условно фильтруется на всех декартовых произведениях. Действительно, пусть формула (2) истинна на каждой алгебре Sfct = {Аа,- ) (а ? I). Обозначим через 21 декартово произведение этих алгебр. По условию в каждой алгебре 2ta существуют элементы аа Ф Ьа такие, что для каждого Xct Є Aa
ааха = аа & baxa = aa\f baxa = ba. (3)
Обозначим через a, b элементы алгебры 21, проекции которых аа, Ьа определяются формулами
а*=аа (а Єї), (4)
ч: ГЛ'
где Я — какой-нибудь фиксированный индекс из /. Так как а^фЬх, то афЬ. Из (4) следует, что для каждого XЄ 21 и каждого a ?/ ааха=аа, т. е. ах= а. Из (5) и (3)
*) Предположение, что для всякой бесконечной мощности
¦ мощностей, лежащих между с і гипотезой континуума.— Прим. редт
с нет мощностей, лежащих между с и 2е, называется обобщенно^ § 8] ФИЛЬТРЫ И ФИЛЬТРОВАННЫЕ ПРОИЗВЕДЕНИЯ' 217
следует:
baxa=ba = aa (афк), J3Kx^ = 6?^ = №.
Если b%xx = Ok, то Ъх = а, если же Ъххх = то bx = Ь, и потому формула (2) истинна в ST.
Остается показать, что формула (2) не эквивалентна никакой хорновской формуле. Если бы она была эквивалентна хорновской формуле, то по теореме 1 она бы условно фильтровалась на любом фильтрованном произведении. Покажем, что это не так. Обозначим через D фильтр Фреше над множеством TV (N = {0, 1, 2, . . .}), т. е. совокупность множеств натуральных чисел, дополнения которых конечны. Каждому п ? N поставим в соответствие одну и ту же алгебру Stn = {{0, 1}, • ), где • означает обычное умножение натуральных чисел. Ясно, что формула (2) в Sln истинна. Покажем, что на фильтрованном произведении [J9tn/D истинна не формула (2), а ее отрицание, которое мы запишем в виде
