Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Ясно, что тождественно истинные формулы сигнатуры с истинны на любом классе алгебраических систем сигнатуры ст. Обратно, если формула % сигнатуры с истинна на классе St всех алгебраических систем сигнатуры а, то % тождественно истинна.
Отметим еще ряд непосредственных следствий указанных выше определений.
Формула % тогда и только тогда невыполнима на классе St, когда на St истинна формула H
Формула ^1 &. . . &%т тогда и только тогда истинна на классе St, когда на классе St истинна каждая из формул
Si. • ¦ •) •
И А. И. Мальцев 162
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
Формула griV-.-V З™ тогда и только тогда выполнима на классе Й, когда на Й выполнима хотя бы одна из формул glf ..., ftm.
Замкнутые формулы сигнатуры о называются
эквивалентными на классе й алгебраических систем сигнатуры о, если на каждой системе класса Sl' значение % совпадает со значением ^1.
Ясно, что замкнутые формулы %, gfi сигнатуры а тогда и только тогда эквивалентны на классе й систем сигнатуры о, когда на Й истинна формула
(1)
Для незамкнутых формул и сигнатуры а будем говорить, что ^0? эквивалентны на классе Й систем сигнатуры 0, если формула (1) истинна на классе Й.
Пусть @—некоторая совокупность замкнутых формул ПИП сигнатуры о. Класс всех алгебраических систем сигнатуры о, на каждой из которых истинны все формулы из 6, будет обозначаться Kg. Ясно, что если gt^g2, то Kgl ^Kg2-
Пусть Й— произвольный класс алгебраических систем сигнатуры о. Совокупность всех замкнутых формул ПИП сигнатуры 0, истинных на классе Й, называется элементарной теорией класса $ и обозначается Th й. Заметим, что если то Th ThK2- Ясно также, что
Ш^К ThE.
Класс й систем сигнатуры 0 называется аксиоматизируемым, если
Я = JTTh Jt
Теорема 1. Класс Й алгебраических систем сигнатуры о аксиоматизируем тогда и только тогда, когда существует такая совокупность g замкнутых формул ГІИП сигнатуры а, что Й =Kg.
Если Й = І? ТЬЙ, то в качестве g можно взять ТІїй. Пусть © — такая совокупность замкнутых формул ПИП сигнатуры о, что Й = Kg. Так как g S Th й, то Kg ^ Э .AT ThJL С другой стороны, ЯсЛГТЬЙ. Следовательно, Й = #ТЬЙ. СйнтакСйс й сбМайтйка
163
Примеры и дополнения
1. Множество A s2 всех аксиоматизируемых классов алгебраических систем любой фиксированной сигнатуры Q имеет мощность 2|а|+Ко.
, 2. Мощность подсистемы, порожденной в алгебраической
системе Щ сигнатуры Q множеством С, не превосходит max {і Q|, I С I, N0}. j 3. Существует эффективная процедура (алгоритм Гиль-
берт а), позволяющая последовательно выписывать все тождественно истинные формулы ПИП (см. Новиков [51], Клини [22], Гильберт и Аккерман [14]).
4. Пусть о — некоторая конечная сигнатура, а © — некоторая совокупность бескванторных формул сигнатуры ст, каждая из которых не содержит свободных предметных переменных, отличных от yt, . . . , ут. Совокупность © называется совместной, если существует такая система Wl сигнатуры а, на которой возможно так задать значения уи . . ., уг, что при этих значениях все формулы из © будут истинны на 50/. Принцип локализации для бескванторных формул ПИП: если каждая конечная подсистема системы формул © совместна, то и вся система фор-f мул © совместна.
Доказательство. Все формулы ПИП сигнатуры а вида
Q1 = CI2, PlnHai, а„),
где at, а2, . . ., а„ — термы, все функциональные символы которых принадлежат ст, а все предметные переменные содержатся в множестве {г/і, . . . , г/Г}, и Р°1) есть л-арный предикатный символ из о, расположим в последовательность ^1, )? ..., ... и будем последовательно строить совокупности формул ©о. ©1) Пусть ©о = © и ©г+1 = ©; U {п если Для некоторой конеч-
ной подсистемы ©' из ©г система формул 1S' IJ несовместна,
OO
И ©г + 1 = ©г U {5г+і} в противном случае. Пусть ©00= U ©г- Пусть
г= О
А — множество термов, все функциональные символы которых принадлежат ст, а все предметные переменные содержатся в множестве {уі% ..., у г}. Для O1, а2 ? А полагаем O1 ~ а2, если (O1 = а2) ? ? iScc. Проверяется, что ~ есть отношение эквивалентности на А. Для а ? А через [а] обозначим класс эквивалентности, содержа-\ щий a, a через aj— — множество всех этих классов эквивалент-
ности для всевозможных о ? А. На множестве А/~ определяем операции /<"> и предикаты Pimi для всех /<п>, Р<т> из а, полагая
Im (Ы, Ы) = ^nHa1, ..., вв)];
PW ([O1], ..., [ат])=И Р<™> К.....ат) ? S00.
I
Легко проверяется, что на полученной системе сигнатуры ст при значениях Iyi] для уи [у2] для у%, . . . , [уг\ Для уг все формулы
! ИЗ © ИСТИННЫ.
и* 164
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
§ 7. Классификация формул
7.1. V-формулы и 3-формулы. Известно (см. Новиков [51], Клини [22], Гильберт и Аккерман [14]), что каждая формула прикладного исчисления предикатов сигнатуры о эквивалентна *) формуле той же сигнатуры, имеющей пренексный вид
(QiXi) . . . (QmXm) Ш (хи ¦ ¦ хт, уи . . ., уп),
где формула Я кванторов не содержит, а символы Qi обозначают кванторы V или 3. Основная классификация формул пренексного вида идет по виду ее префикса, т. е. кванторной части ((^.T1) . . . (Qmxm). А именно, говорят, что формула ПИП вида
