Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Рассмотрим, например, модели
Я = <{0, 1, 2, . ..}; <), SB = <{0, -1, -2, ...}; < >,
где ^ — обычное отношение порядка. Замечаем, что в первой модели существует наименьший элемент 0, а во второй модели его нет. Первое утверждение можно записать формулой
(3s) (Vy) X < у,
которая, таким образом, истинна на первой модели и ложна на второй. Следовательно, модели не изоморфны. CIIIifTAKGliC й сёМайтййа
159
Сравним теперь модель SI с моделью
К _/1 П123 4 3 9 3 1 .
u^M ' У' "J' T' • • • • T' ~2' ** o' • ¦ ¦ J ' ^ / •
-S
Если мы попытаемся различить модели 21, (5 при помощи замкнутых формул, не содержащих связанные предикатные или функциональные переменные, то скоро заметим, что наши попытки не увенчаются успехом. Однако разница между абстрактными свойствами моделей 21 И (5 есть. Мы видим, что каждый элемент х той и другой модели имеет непосредственно следующий за ним элемент х' Связь между X и х' можно выразить формулой
5 (k, х') =
: = ж< х' & X ф х' & (Vy) (ж< у& г/< х' —> х = y\jу = х').
Символ == здесь и всюду далее означает, что стоящее слева слово есть обозначение для выражения, стоящего справа.
Далее, в моделях 21, © есть наименьший элемент х, описываемый формулой
T(X) = (Vy)XKy.
Наконец, видим, что, переходя от наименьшего элемента ж к следующему за ним х', от х' к ж" и т. д. в модели 21, мы исчерпаем всю модель. В виде формулы это свойство можно записать следующим образом:
(VP) (Vx) (Т (X) & P (X) & (Vyz) (Р (у) &S (у, Z)-+ P (z))
-+(Vu)P(Ii)). (8)
Ясно, что, применяя те же переходы в модели мы
г 12 1
исчерпаем лишь ее подмодель -J 0, -j, у, ... J- . Таким
образом, формула (8) истинна на модели 21 и ложна на модели Поэтому модели 21 и S не изоморфны.
Существует глубокое различие между свойствами формул, содержащих связанные предикатные или функциональные переменные, и свойствами формул, не содержащих таких переменных. Формулы языка 2-й ступени, не содержащие связанных предикатных и функциональных 160
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
переменных, называются формулами прикладного исчисления предикатов, сокращенно — формулами ПИП или ТІШІ-формулами. ПИП-формула, не содержащая функциональных переменных, называется формулой узкого исчисления предикатов или формулой УИП. Формула УИП, не содержащая знака равенства, называется формулой чистого исчисления предикатов (ЧИП).
Основным формальным языком теории алгебраических систем служит ПИП, а основным языком теории моделей является УИП. Языки ПИП, УИП и ЧИП в основном равносильны друг другу. Эти языки называются языками 1-й ступени. Напротив, язык 2-й ступени много более мощный. Весьма тонкие и логически сложные свойства обычно нетрудно записать в виде формулы 2-й ступени с предикатными связанными переменными. Напротив, ряд даже самых обычных понятий, например понятие подсистемы, невозможно записать на языке ПИП. Однако много определений и свойств легко записывается и на языке ПИП и, что самое главное, из самого факта запи-сываемости некоторого утверждения на языке ПИП уже следует много важнейших свойств этого утверждения. Эти свойства ПИП и будут постепенно далее изложены.
6.4. Элементарные теории и аксиоматизируемые классы. Пусть задан какой-нибудь класс К алгебраических систем сигнатуры о. Замкнутая формула S сигнатуры о называется истинной на классе A, если S истинна на каждой системе класса Ш. Формула g называется выполнимой на классе й, если в St существует система, на которой g истинна.
Понятия истинности и выполнимости на классе R распространяют и на незамкнутые формулы следующим образом. Пусть формула % содержит свободные предикатные переменные P1, . . ., Pr, свободные функциональные переменные Z1, ..., fS и свободные предметные переменные X1, . . ., xt, не входящие в сигнатуру а, a все остальные свободные переменные § пусть входят в or. Рассмотрим какую-нибудь алгебраическую систему sJJl класса й. Чтобы можно было говорить об истинности или ложности формулы S на 5Ш, надо задать на Ш значения переменных fb Pj, xk (i, j, к — 1, 2, . . .) (см. п. 6.2). Формула S называется истинной на классе E1, если она СИНТАКСИС И СЕМАНТИКА
161
истинна на каждой системе SDi из St при любом задании в 9JI всех свободных переменных формулы ^1, не входящих в сигнатуру St. Формула % называется выполнимой на классе St, если в Jt существует система SR, на которой возможно так задать значения всех свободных переменных формулы не входящих в сигнатуру Ж, чтобы при этих значениях формула g- была истинной на ЯК.
Из этих определений непосредственно следует, что формула % со свободными внесигнатурными переменными P1, . . ., Pr, . . ., /s, X1,. . ., Xt тогда и только тогда истинна на классе St, когда на классе St истинна замкнутая формула
(VP1 ...Pr) (V/, .../,) (Vx1 ...Xt)
Аналогично формула % р указанными свободными вне-сигнатурными переменными тогда и только тогда выполнима на классе St, когда на классе St выполнима замкнутая формула
(BP1... Pr) (Э/4 • • ¦ fs) (Ixi... Xi)^-.
Формула 2-й ступени % называется тождественно истинной, если она истинна на любом недустом множестве M при любых значениях на M всех входящих в $ свободных переменных. Формула % называется выполнимой, если существуют такое непустое множество M и такие значения на M для всех входящих в g- свободных переменных, при которых формула § становится истинной.
