Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
где Fi— некоторый сигнатурный функциональный символ, a X1, . . ., Xm+!— символы, не участвующие в записи термов /, g. Число функциональных знаков, участвующих в записи каждой из подформул
хт+1 = h, Xx = h (Я = 1, . . ., т.)
меньше v. Поэтому каждая из этих подформул эквивалентна формуле вида (6). Заменяя в формуле (8) указанные подформулы формулами вида (6) и вынося знаки существования, получим формулу вида (6), эквивалентную формуле / = g.
Чтобы привести формулу f = g к виду (7), замечаем сначала, что формула / = g эквивалентна формуле
(Vx1 .. ) (X1 = Z1 & . . .
... & Xm = Zm & %т+1 Fі (X1, . . . , Xm) > xm+1 = h).
Заменяя здесь подформулы х% = f% (X = 1, . . ., т) эквивалентными им формулами вида (6), подформулу %т+1 — h эквивалентной формулой вида (7) и вынося кванторы, получим формулу вида (7), эквивалентную формуле Z = g- Теорема 4 доказана.
Итак, термальное равенство f — g можно привести к абсолютному Э-виду и к абсолютному V-виду. Спрашивается, можно ли его привести к абсолютной бескванторной форме? Ответ в общем случае отрицательный. Рассмотрим, например, формулу
F (х, F (х, ж)) = х. (9)
Допустим, что она эквивалентна какой-нибудь абсолютно бескванторной формуле Ф (х, у, . . ., z). В последней формуле могут встречаться, помимо функционального знака F, и другие функциональные знаки Fi, а также предикатные символы Pj. Так как значения формул F (х, F (х, х)) = X и Ф (х, у, . . ., z) должны быть равны при любых значениях у, . . ., z, Fi, Pj, то, не нарушая' эквивалентности, мы можем в формуле Ф положить у ~ х, . . ., z = х, Fi (х, х, . . .) = X и Pj (х, х, . . .) = = И. В результате получим эквивалентность вида
F (х, F (ж, ж)) = W (ж), КЛАССИФИКАЦИЯ ФОРМУЛ
171
где 1F (X) образовано из атомарных формул х = х, F (х, х) =хс помощью знаков &, \/, п. Но каждая из формул ? этого вида эквивалентна одной из формул
х = х, х Ф х, X = F (х, х), X Ф F (х, х),
из которых ни одна не эквивалентна формуле (9).
7.2. Универсально аксиоматизируемые подклассы. Ввиду большой логической простоты утверждений, выражаемых V-формулами, нетрудно решается и задача об описании свойств тех классов алгебраических систем, которые можно задать совокупностью V-формул (см. п. 7.1). Предварительно введем несколько определений.
Пусть §1 = (A, Q) — произвольная алгебраическая система. Заменяя в ее сигнатуре Q функциональные символы соответствующими предикатными символами (см. п. 2.2), получим новую сигнатуру Qm. При этом алгебраическая система (А, Q) превращается в модель SIm = (A, Qm)- Всевозможные подмодели модели Им называются (п. 2.3) подмоделями и алгебраической системы Я. Существенно помнить, что хотя каждая подсистема SI является ее подмоделью, но не всякая подмодель SI является ее подсистемой (п. 2.3).
Если Q' — какая-нибудь непустая часть сигнатуры Q, то алгебраическая система {A, Q') называется Q'-обеднением (иногда Q'-редукцией или Q'-проекцией) системы SI = {A, Q). Если сигнатура Q' конечна, то Q'-обедне-ние называется конечным обеднением системы Si. Например, пусть
SI = (R-, V~\, VП. ¦••>.
где R — совокупность всех вещественных чисел, V \ \ — одноместная операция извлечения (арифметического) корня п-й степени из абсолютной величины числа. Тогда алгебры
Sti = <Л; VU Ml. УП)
будут конечными обеднениями алгебры Si.
Конечные обеднения конечных подмоделей алгебраической системы называются локальными подмоделями этой системы. 172
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
G понятием подмодели алгебраической системы тесно связано понятие диаграммы модели. Пусть Я — = (A, Q) — какая-нибудь модель. Каждому ее элементу а ? А поставим в соответствие особый символ Za, не входящий ни в А, ни в Q. Рассмотрим всевозможные формулы вида
zan)i P (za1? • ¦ • > Zan) (Яі €4), (1)
где P — предикатный символ из й или знак = . Совокупность тех формул вида (1), для которых соответствующее выражение P (аи . . ., ап) или Hi5 (аи . . ап) истинно в Я, называется диаграммой модели Я и обозначается через D (Я). Например, диаграмма модели ({0, 1, 2}, состоит из формул
zO=zOi zl = zb Z2~Z2> 2O Ф zIt zI=^zOf 2оФ22т
Z2=^=Z0, zI Ф z2i z2 "Ф1 zI? zO < z0» zI4CzIi z2C^z2i Z0<Z1, Hz1CzO, Z0 < z2, nz2<zo, zi<22, Hz2Cz1.
Если сигнатура модели Я содержит предметные символы Ci и в модели Я Ci = Ui (at Є А), то в диаграмму модели Я, помимо формул (1), включаются формулы
Ci = Za., сіфга (афаь а?А).
Наконец, если Я — не модель, а алгебраическая система, сигнатура которой ?3 содержит функциональные символы F^1 то диаграммой Я называется диаграмма соответствующей модели Ям- Иначе говоря, в этом случае диаграмма системы Я состоит из формул вида (1), где P — предикатный символ из ?2, и формул вида
F (zai, . . ., Zam) = Zao (Ov = Fia1, . . ., ат)),
& (zai) • • ¦ і zain) zT^zGo
(а0фР(аи . . ., ат)) (а0, ..., атЄ A, Fe^).
Например, диаграмма обедненной подмодели {{1, 2}, • ) кольца (.{0, ±1, +2, . . .}; +,'-•) состоит из формул
Z1 = Zl) z2~z2; Z1 Z2T Z2 ^Ф1 zIу zI ' zI = 2It Z1-Z2 = Z2, Z2-Zi=Z2, Zi-Z2=T^Z1, Z1-Z1-=^Z2, Zg-Zj=^=Z1, Z2-Z^ -ф-Z1, Z2-Z3^Zg. КЛАССИФИКАЦИЯ ФОРМУЛ
