Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Позитивные формулы строятся из простейших формул вида P (Xil, . . ., xig) или / = g, где P — предикатный символ, /, g — термы, с помощью операций конъюнкции, дизъюнкции и квантования. Поэтому теорема 1 будет доказана, если мы убедимся, что простейшие формулы устойчивы относительно гомоморфизмов и что конъюнкции, дизъюнкции и квантования гомоморфно устойчивых формул являются гомоморфно устойчивыми формулами.
Гомоморфная устойчивость упомянутых простейших формул была доказана в п. 6.1. Пусть R1, R2- гомоморфно устойчивые предикаты. Если их дизъюнкция
Ri (xiv ..., Xig) V R2 (Xjv Xjt) (2)
истинна для некоторых значений X0i, . . ., х% из системы ЗЛ, то истинен хотя бы один член этой дизъюнкции. Пусть, например, Ri (X0il, . . ., xjj = И. Тогда по условию Ri • • ., ж?чр) = И и, следовательно, дизъюнкция (2) истинна И в системе ДЛЯ Xi = .Гіф, ...,Xk = = хьЦ). Аналогично доказывается, что конъюнкция гомоморфно устойчивых предикатов есть гомоморфно устойчивый предикат.
Рассмотрим теперь предикат (Vxi) Ri (Xi, х2, ¦ • •, xs). Пусть OH истинен ДЛЯ некоторых значений х\, . . ., xt 182
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
в системе ДЯ. Это значит, что для любого х ? Sft истинно выражение Ri (х, х\, . . ., я"), и потому в системе 9? истинно выражение Ri (дар, жзф» • ¦ жвф) для любого X Q ЯК. Так как ф есть гомоморфизм Sft на Ш, то жф пробегает всю систему 3?, когда х пробегает Sft. Иначе говоря, выражение Ri (х, х^Ц), . . ., ж°ф) истинно для любого X Q 9І и, следовательно, в Si истинно выражение (Vx) Ri (х, х°2<р, . . ., ж"<р), т. е. формульный предикат (Vx) Ri (х, ж2, . . ., Xs) гомоморфно устойчив.
Аналогично доказывается гомоморфная устойчивость предиката (За;) Ri (х, х%, . . ., xs).
Следствие 1. Если на некоторой алгебраической системе ЮЇ истинна какая-то замкнутая позитивная формула, то эта формула истинна и на любом гомоморфном образе системы SJl.
Формула называется негативной, если она образована с помощью конъюнкций, дизъюнкций и кванторов из выражений вида
f?*g, HiVSi, .... Sm),
где ?г — предметные переменные, f,g — термы, Pj- предикатные символы.
Если S — позитивная формула, то H S обычными операциями углубления отрицаний и вынесения кванторов приводится к негативной форме, и, обратно, если S — негативная формула, то указанными преобразова-
ниями приводится к позитивному виду.
Следствие 2. Пусть % (у i, . . ., уп) — негативная формула со свободными переменными уi, . . ., уп, имеющая сигнатуру а, и пусть ф — гомоморфизм некоторой алгебраической системы 3)1 сигнатуры 0 на алгебраическую систему 9Ї. Тогда из истинности % (УіЦ>, ¦ ¦ ., упф) для каких-либо элементов у,, . . ., уп системы Sft вытекает истинность формулы % (у . . ., уп) на ЭЛ.
В частности, если замкнутая негативная формула истинна на какой-либо системе 91, то она истинна и на любом гомоморфном прообразе системы 9І.
Действительно, если бы S (г/t, . . ., уп) была ложна, то позитивная формула H S (у\, • • •, уп) была бы истинна, а тогда была бы истинна и формула ~1 % (г/іф, • • упф)> что противоречит предположению. КЛАССИФИКАЦИЯ ФОРМУЛ
183
Обращение теоремы 1 (и следствия 2) верно, но требует для доказательства более тонких соображений (см. Линд о н [28]).
Вопрос о существовании алгоритма, распознающего по записи формулы эквивалентна ли она какой-нибудь позитивной формуле, легко решается отрицательно.
Теорема 2. Не существует алгоритма, позволяющего по записи произвольной замкнутой формулы % узнать, эквивалентна или нет % какой-нибудь позитивной формуле.
Согласно теореме Чёрча не существует алгоритма, распознающего тождественно истинные формулы ПИП. Покажем, что если бы существовал алгоритм Л, позволяющий распознавать, эквивалентна или нет произвольно заданная формула какой-нибудь позитивной формуле, то при помощи Jh можно было бы распознавать и тождественно истинные формулы.
Действительно, если бы заданная формула % была тождественно истинной, то она была бы эквивалентна позитивной формуле, например формуле (V х) х = х. С другой стороны, пусть ff эквивалентна некоторой позитивной формуле. Процесс Гильберта дает возможность эффективно найти одну из таких формул. Пусть — позитивная формула, эквивалентная Остается узнать, является ли тождественно истинной формулой. Этот вопрос равносилен вопросу: является ли выполнимой негативная формула ^1? Но если негативная формула истинна на некоторой системе, то она истинна и на любом ее гомоморфном прообразе и, в частности, на абсолютно свободной алгебраической системе с бесконечным числом порождающих (см. п. 12.2). Итак, вопрос свелся к следующему: узнать, истинна или ложна формула И ^ч на абсолютно свободной системе бесконечного ранга. Алгоритм для решения этого вопроса указан в работе [38].
7.5. Мультипликативно устойчивые формулы. Хорнов-ской формулой (см. А. Хорн [71]) называется предваренная формула, у которой бескванторная часть есть конъюнкция членов, каждый] из которых есть или простейшая] формула, т. е. атомарная формула вида P (Si, • • S«) или / = g (где P — сигнатурный предикатный символ, f,g — термы), или дизъюнкция одной простейшей формулы указанного вида и нескольких І84
