Научная литература
booksshare.net -> Добавить материал -> Математика -> Мальцев А.И. -> "Алгебраические системы" -> 51

Алгебраические системы - Мальцев А.И.

Мальцев А.И. Алгебраические системы — Наука, 1970. — 392 c.
Скачать (прямая ссылка): algebraicheskiesistemi1970.djvu
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 133 >> Следующая


Рассмотрим еще пример. Формула

(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. Для этой цели достаточно найти замкнутую формулу, истинную на одной системе и ложную на другой.
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 133 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed