Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
153
Например, . вместо того чтобы сказать: рассмотрим значения формулы
(Vx2) (Ff (хи х2) =хг& Ff (X1, X2) — X1)
на натуральном ряде N = {0, 1, 2, . . .}, когда Ff обозначает операцию сложения, Ff — операцию умножения, a X1 принимает различные значения в N, говорят: рассмотрим значения формулы
(Vy) (х + у = у&ху = х) (10)
на натуральном ряде, где +, • есть обычные операции сложения и умножения чисел. Из правил вычисления значений формулы непосредственно получаем, что формула (10) истинна тогда и только тогда, когда х = 0. Аналогично легко убеждаемся, что формула
(3 г)(х-\-г = у&хфу) (И)
истинна тогда и только тогда, когда х < у. Легко также убеждаемся, что формула
('Vyz) (уу ф у & ZZ ф Z —> X ф yz) & XX ф X (12)
истинна тогда и только тогда, когда число х простое.
Обозначим формулу (12) через В (х) и рассмотрим формулу
(Vx) (XX Ф X (3yz) (В (у) & В (z) & X + ж = у + z)). (13)
Эта формула истинна тогда и только тогда, когда каждое четное число, большее двух, есть сумма двух простых чисел. Верно это утверждение или нет — пока открытая проблема. Таким образом, сегодня пока неизвестно значение формулы (13).
Если в качестве основного множества взять не множество натуральных чисел, а множество всех вещественных чисел, то значения формул (10)-(13) будут иными, хотя формула (10) и на множестве вещественных чисел будет по-прежнему «определять» число 0. А именно, формула (11) будет истинна для всех х Ф у, формулы (12) и (13) — ложны для всех х. Чтобы определить с помощью операций сложения и умножения отношение X -< у для действительных чисел, вместо формулы (11) можно 154 ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
воспользоваться формулой
(3z) (ж + (zz) = у &z + z^z),
так как квадрат любого отличного от нуля вещественного числа есть число положительное.
6.3. Свойства 2-й ступени. Многие важные свойства алгебраических систем допускают вполне естественную формулировку на языке 2-й ступени. Ряд проблем также может быть совершенно естественно сформулирован на этом языке. Простым примером этого рода может служить упомянутая выше проблема Эйлера о представлении четных чисет суммой двух простых. Общая идея применения языка 2-й ступени в теории алгебраических систем состоит в следующем.
Рассмотрим произвольный класс Я алгебраических систем заданного типа (т0, . . . , . . .; «0» • • • . . щ, ...)(? <С а, т| < ?). Этому типу ставим в соответствие набор а каких-то функциональных и предикатных символов .F0, . . ., Fі, . . ., P0, . . ., P11, . . ., арности которых равны числам тй, . . ., т%, . . ., п0, . . . ..., пц, ... На символы F0, . . ., Fb . . ., P0, . . ., P11, . . . мы будем смотреть как на общие имена соответствующих операций и предикатов систем класса Я. Совокупность указанных символов мы будем называть сигнатурой класса Я. Пусть задана произвольная система 5R класса Я. Значениями символов Fi, P11 на 9? называются ?-я операция и г]-й предикат этой системы. Таким образом, задать на данном множестве А систему St сигнатуры о — это значит задать некоторое непустое множество А и каждому сигнатурному знаку сопоставить в качестве его значения некоторую операцию или предикат на А соответствующей арности.
Формула языка 2-й ступени называется формулой сигнатуры о, если все свободные функциональные и предикатные символы этой формулы принадлежат а. Формула, не содержащая свободных предметных переменных, называется замкнутой или закрытой. Формула, не содержащая ни предметных, ни функциональных, ни предикатных свободных переменных, называется абсолютно замкнутой.
Для каждой абсолютно замкнутой формулы % и для каждого множества А можно поставить вопрос, истинна СИНТАКСИС И СЕМАНТИКА
155
или ложна формула % на А. При этом никаких дополнительных сведений о значениях свободных переменных не требуется, так как в формуле ^ их нет. Например, формулы
(VP) (Vr) (Р (х) у н P (х)), (VF) (Vx) (F (х) = F (х)),
где P1F — унарные предикатный и функциональный символы, истинны на любом непустом множестве.
Напротив, если формула ^ не абсолютно замкнута, то, спрашивая об ее истинности или ложности, предварительно надо задать значения ее свободных переменных. Однако все свободные переменные замкнутой формулы сигнатуры о имеют фиксированные значения на каждой алгебраической системе сигнатуры а. Следовательно, в этом случае мы снова можем говорить об истинности или ложности формулы но только не на множестве, а на системе сигнатуры а. Например, формула
(yxyz) (х-(у + z) = (x-y)-t(x-z)) (1)
— замкнутая формула сигнатуры о = (+, • >, где • есть бинарные функциональные символы. Натуральный ряд с обычными операциями сложения и умножения есть алгебра сигнатуры о. Ясно, что формула (1) истинна на этой алгебре. Напротив, формула
(Vor) (х-х = х) (2)
ложна на ней.
Обозначим через S (х) число х + 1 и рассмотрим алгебру (N, S), где N — натуральный ряд. Формула
(VP) (Vx) ((Vy) (х Ф S(у)) & Р(х) & (Vz) (P(z) -> P (S (Z))) ->
(Vu) Р(и)) (3)
выражает принцип полной' индукции и потому истинна на алгебре (N, S).
