Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Рассмотрим еще пример. Формула
(Vz) (х + Ij-Z = х) (4)
есть формула сигнатуры •, но не замкнутая. Истинна она или ложна на алгебре {N; • ) — зависит от значений предметных переменных х, у в N. Если X = 1, у = 0, то формула (4) истинна, если х = 1, у — 1, то156
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
формула (4) ложна, и т. д. Мы видим, что каждой паре чисел х, у формула (4) сопоставляет один из элементов множества {И, Л) и, таким образом, определяет бинарный предикат на N.
Значения формулы (4) можно исследовать не только на алгебрах сигнатуры -f, -, но и на алгебрах более узкой сигнатуры, например на алгебре (N, • ). В этом случае значение формулы (4) будет зависеть не только от значений предметных переменных х, у, но и от выбора функции +. Иначе говоря, значение формулы (4) будет предикатом, определенным на декартовом произведении N X N X T, где T —¦ совокупность всех бинарных операций на N. Такого рода предикаты называются предикатами 2-го порядка. В отличие от них, обычные предикаты, которые мы только и будем рассматривать, иногда называются предикатами 1-го порядка.
Как уже говорилось, истинность или ложность замкнутой формулы сигнатуры о на системе сигнатуры о не зависит от каких-либо дополнительных данных и потому является свойством самой этой системы. Свойство системы 21 сигнатуры а, состоящее в том, что на 21 истинна какая-то данная замкнутая формула % сигнатуры о, называется свойством 2-й ступени.
Покажем, что свойства 2-й ступени абстрактные, т. е. что если на какой-нибудь системе 21 сигнатуры о некоторая замкнутая формула % сигнатуры о истинна или ложна, то на каждой системе 35, изоморфной 2t, формула % имеет то же значение. На самом деле мы докажем, что верна следующая более общая
Теорема 1. Пусть а — изоморфное отображение алгебраической системы 21 сигнатуры а на систему 33. Обозначим через % [Ui, . . ., ип) какую-нибудь формулу сигнатуры сг, имеющую свободные предметные переменные Ui, . . ., Un. Тогда для любых щ, ..., Un из 2t
% (и и . . ., ип) <=> % (Ui а, . .., ип<х). (5)
Эту теорему удобнее всего доказывать индукцией по числу г вхождений в формулу логических знаков &, V, Н, —З, V, — и знаков предикатных переменных. Если г—1, то g имеет один из видов
Oj = Oll O1 = O81 Р(0), Р(П)(O1, ...,O71), (6)СИНТАКСИС И СЕМАНТИКА
157
где аь . . ., а„— термы от и}, . . ., ип. В этом случае соотношение (5) следует из определения изоморфного отображения (см. п. 2.2) и из теоремы 1 п. 6.1.
Пусть теперь для формулы S имеем г>1 и для формул с меньшим значением г теорема 1 верна. Следуя определениям формулы, рассмотрим все способы, при помощи которых S может возникнуть- из формул с меньшим г.
а) S имеет вид И Si- По условию Si (и) Si (иа) и потому П Si (и) S1 (иа).
б) S имеет один из видов
Sl&S2, SlV02,
где Si! $2—формулы, имеющие меньшие значения г, чем формула S- По условию
g, (и) <=> % (иа) (І= 1,2)
и, следовательно, соотношение (5) справедливо.
в) S имеет вид (Vjc)S1 (щ, . ., ип, х). По условию
Si ("і. • • •> ип, х) <=^ ^1 (ща, .. ., ипа, ха) (7)
для каждого х из 21. Если формула (Vx) S1 (щ, ..., ип, х) истинна, то левая, а значит, и правая формулы в (7) истинны при каждом значении х в И. Но для любого элемента у системы 95 существует такой элемент х Q 21, что ха = у. Поэтому формула Si (uia> • • •» ипа, у) истинна для каждого у в 95, т. е, формула (Vz) Si (ща, .. ., ипа, х) истинна и соотношение (5) доказано. Если же формула (Vz) Si (щ, • • •, ип, х) ложна, то формула Si (Щ, ..., ип, х) ложна При некотором х ?21. Из (7) заключаем, что формула Si (^iaJ • - • і ипа, у) ложна при у — ха, и потому формула (Vr) Si (uta, ..., ипа, х) ложна на 95. Итак, и в этом случае соотношение (5) справедливо.
г) Формула S имеет один из видов
(Зж) Si» (VjP) Si, (3F)Si> (W)S,, (ЗР) Si-
В каждом из этих случаев соотношение (5) доказывается при помощи тех же рассуждений, что и в случае в).
Теорема доказана. В условии теоремы сказано, что рассматривается изоморфизм системы 21 на систему 33. Для изоморфизма 21 в 95 утверждение теоремы может158 ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
оказаться неверным. Рассмотрим, например, модель St = = ({1, 2}, <) и модель 95 = {{1, 2, а}, <), где и в первом и во втором случае предикат <С истинен лишь для пары (1, 2). Тождественное вложение
а: X -V X (х = 1, 2)
есть изоморфизм St в 95. Тем не менее формула
(Vxy) (х Ф у X < у\! у < х),
истинная на модели St, очевидно, ложна на модели 35.
Легко построить пример, показывающий, что при гомоморфизме SI на 55 утверждение теоремы 1 также может оказаться неверным. Пусть 95 — {{1, 2}, SI = = {<1, 2, o}, где отношение ^ состоит из пар (1, 1), (2, 2), (а, а) и пары (1, 2). Отображение
а: 1-»-1, 2 2, а ~> 2
есть гомоморфизм SI на 95. Однако формула
(Э ху) (~1 ж<г/&~!г/<ж)
истинна на SI и ложна на 95.
Из теоремы 1 при п = 0 получаем, что для изоморфизма систем SI и 95 необходимо, чтобы каждая замкнутая формула данной сигнатуры, истинная на одной из систем, была истинна и на другой. Из простых соображений относительно мощностей систем вытекает, что приведенное условие недостаточно для изоморфизма систем SI и 95. Однако его часто удобно использовать для доказательства неизоморфности систем Si, 93. Для этой цели достаточно найти замкнутую формулу, истинную на одной системе и ложную на другой.