Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
в) Существует ли алгоритм, позволяющий по записи произвольной замкнутой формулы сказать, является ли эта формула квадратоустойчивой?
Вопросы б), в) и некоторые их модификации были отрицательно решены Феферманом (для формул произвольной сигнатуры) и Маховером [45] (для;формул сигнатуры, содержащей или &-арный предикатный символ, k ^ 3, или два предикатных символа, один из которых бинарный, а другой не нульарный). Мы ограничимся здесь доказательством лишь следующей теоремы.
Теорема 3 (Алмагамбетов [4]). Не существует алгоритма Jk, позволяющего распознавать квад-ратоустойчивые формулы среди замкнутых формул ПИП, сигнатура которых состоит лишь из одного бинарного предикатного символа и которые не содержат знака равенства.
Обозначим через 5Ї класс моделей, сигнатура которых состоит лишь из одного бинарного предикатного символа P и на которых истинна формула
a=(Vxy) P (х, у).
Через ? обозначим класс тех моделей сигнатуры (P), на которых истинна формула
95 = (Vxy) (Р(х, y)\JP (у, X)).
Рассмотрим какую-нибудь замкнутую формулу
% ^L (Q1X1) ... (Qmxm) 9Ї (хи ...,хт) (9)
сигнатуры (P), не содержащую знака равенства. Чтобы КЛАССИФИКАЦИЯ ФОРМУЛ
191
узнать, истинно или ложна эта формула на какой-то модели SR класса Я, достаточно в ее бескванторной части Ж все выражения вида P (xt, х}) заменить их значением И и с помощью таблиц из п. 6.2 вычислить значение получившейся формулы. Если значение будет равно И, то формула |5г истинна не только на модели 9JI, но и на любой модели класса Я. Если значение 9Ї равно JI, то % ложна не только на SR, но и на любой модели класса Я. Следовательно, мы получили алгоритм, позволяющий для каждой формулы вида (9) сказать, истинна или нет эта формула на всех моделях класса Я.
В противоположность этому известно, что не существует алгоритма, посредством которого для каждой формулы вида (9) можно было бы сказать, выполнима или нет эта формула на всех моделях класса 2.
Поэтому для доказательства теоремы 3 достаточно показать, что если бы упоминаемый в этой теореме алгоритм Л существовал, то с помощью его для каждой формулы вида (9) можно было бы решить, выполнима или нет эта формула на моделях класса 2.
Итак, пусть задана какая-то формула $ вида (9). Прежде всего узнаем, истинна ли % на всех моделях класса Я. Если да, то g выполнима и на классе S (так как Я cz 2), и вопрос о выполнимости % на 2 решен.
Пусть Щ ложна на Я. С помощью алгоритма А решаем, является ли квадратоустойчивой формула % & 95.
Пусть нет. Тогда gf выполнима на 2. Действительно, неквадратоустойчивость формулы % & 95 означает, что существует такая модель SR, что на ней формула g & ® истинна, а на SR2- ложна. Из истинности на SR формулы % & 95 следует, что на SR истинны порознь формулы % и 95, т. е. что $ истинна на модели SR класса 2.
Пусть, наконец, формула квадратоустойчива.
Покажем, что в этом случае невыполнима на 2. Пусть, напротив, gf истинна на какой-то модели SR из 2. По условию на всех Я-моделях формула ^ ложна, и потому SR $ Я, т. е. в SR существуют элементы а, Ь, для которых P (а, Ъ) = JI. В модели SR2 рассмотрим элементы а = — (а, Ъ) и 5 = (Ъ, а). Так как P (a, b) = JI, то
P (а, Ъ)=Р(Ь, а)=Л 192
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ
[Гл. III
и, следовательно, на 5Ш2 формула ?5 ложна, хотя ввиду квадратоустойчивости формулы на ЗДІ2 должна
была бы быть истинной формула % & 35. Полученное противоречие доказывает, что утверждение о невыполнимости % на S истинно.
Совершенно аналогичными рассуждениями доказывается и
Теорема 4 (Алмагамбетов [4]). Не существует алгоритма, позволяющего для произвольной замкнутой формулы, сигнатура которой состоит из одного бинарного предикатного символа и которая не содержит знака равенства, решить, является или нет эта формула мультипликативно устойчивой. ГЛАВА IV
ПРОИЗВЕДЕНИЯ И ПОЛНЫЕ КЛАССЫ § 8. Фильтры и фильтрованные произведения
Видное место, занимаемое декартовыми произведениями в теории групп, теории колец и в теориях других классических объектов алгебры, в значительной степени зависит от того, что декартовы произведения групп являются группами, декартовы произведения колец — кольцами и т. д. Для теории языка 1-й ступени понятие декартова произведения менее удобно, так как декартово произведение систем, обладающих каким-либо свойством, выражаемым на указанном языке, само этим свойством, как правило, не обладает. В конце 50-х годов были открыты так называемые ультрапроизведения систем, в полной мере удовлетворяющие требованию сохранения свойств 1-й ступени. В настоящее время техника ультрапроизведения стала играть большую роль при решении более тонких проблем языка 1-й степени. Основные понятия и результаты теории ультрапроизведений и излагаются в данном параграфе.
8.1. Фильтры и ультрафильтры. Фильтром над непустым множеством I называется любая непустая совокупность D подмножеств множества I, удовлетворяющая требованиям:
i) пересечение любых двух подмножеств из D принадлежит D;
ii) все надмножества любого подмножества, принадлежащего D, принадлежат D;
