Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
(Q1X11 .. . xlhi) ... (QlXh ... xlkl) 91,
где Q1, . . ., Qi—чередующиеся кванторы, имеет тип Q1 ... Qi. Например, формулы
(Vxy) ху>х+ у, (Vx) (3yz) X = yz, (Зж) (Vyz) (Buv) у-и = z-v
имеют соответственно типы V, V3, 3V3.
Формула типа Qi ... Q1 называется также Q1 . . . . . . Qі-формулой. Префиксный тип формулы не инвариантен относительно эквивалентности: существуют эквивалентные формулы пренексного вида, имеющие различный префиксный тип. Например, все тождественно истинные формулы эквивалентны друг другу. В то же время существуют тождественно истинные формулы, имеющие любой заданный префиксный тип.
V-формулы называются универсальными, 3-формулы — экзистенциальными формулами.
Теорема 1. Пусть V-формула сигнатуры о
(Vx1 ... хт) 1 (Z1, . . ., хт, уи ..., уп), (1)
где Я кванторов не содержит, истинна на какой-то алгебраической системе Ж сигнатуры о для некоторых значений
*) Формулы Si и S2 второй ступени называются эквивалентными, если формула ©і ->- 3?2) & ©2 Si) является тождественно истинной. КЛАССИФИКАЦИЯ ФОРМУЛ
165
У і ~ У ioi ¦¦ -і- Уп — Упо в 9Л. Тогда для этих значений переменных у10, . . Упо формула (1) истинна и на любой подсистеме Зі S 3)?, содержащей элементы г/10, . . ., уп0. В самом деле, истинность формулы (1) в точке у{ =
— Ую7 --M Уп = Упо означает, что бескванторная формула її (xt, . . ., хт, у10, . . ., уп0) истинна для любых значений переменных Xi, . . ., хт в ЭЛ. Но тогда эта бескванторная формула истинна и для всех значений Xi, . . ., хт из 9Ї, т. е. формула (1) истинна на системе 9? в точке у10, . . ., уп0.
Как уже отмечалось в п. 6.3, формула (1) определяет на каждой алгебраической системе M сигнатуры о предикат Лщ ІУі, . • Уп), зависящий от строения системы в целом. Теорема 1 утверждает, что значение этого предиката в заданной точке не меняется при переходе к подсистемам, т. е. что
• ¦ •• Уп) = Amiy1' •• •> УJ
для каждой подсистемы 9? <= Sft, содержащей ylt . . . . . ., уп. Это свойство инвариантности иногда называют устойчивостью при переходе к подсистемам.
Теорема 1 при п = 0 обращается в следующее утверждение: если универсальная замкнутая формула истинна на какой-либо алгебраической системе, то она истинна и на любой ее подсистеме.
Переходя от V-формул к их отрицаниям, получаем Следствие 1. Пусть 3-формула
. . . Xm ) її (X1, . . . і Xm, у j, . . . , Уп ), (2)
где її — бескванторная формула сигнатуры а от свободных переменных X1, . . ., хт, г/t, . . ., уп, истинна на какой-то алгебраической системе 9? сигнатуры о в точке Ij1 =
— Ум» • • Уп — Упо¦ Тогда формула (2) истинна в точке У ioi - - м Упо и на каждой системе ЗЇІ, содержащей
в качестве своей подсистемы. Иными словами, каждый 3-предикат устойчив относительно перехода к надсистемам.
В самом деле, отрицание формулы (2) эквивалентно V-формуле
(Vxl . . . Xm) н її (Xi, ..., Xm, Уи . .., уп). (3) 166
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
Если бы формула (2) была ложна в точке у10, . . уп0 на системе ЯЛ, то V-формула (3) была бы истинна на SJi в точке у10, . . ., уп0. Тогда по теореме 1 формула (3) была бы истинна в точке у10, . . ., уп0 на системе 31, т. е. формула (2) была бы ложна в точке yi0, . . уп0 на 9І, что противоречит предположению.
Следствие 2. Существуют Ч-формулы (!-формулы), не эквивалентные никакой 3-формуле (V-формуле).
Рассмотрим, например, 3-формулу (Зж) P (х) и модель SJi = ({0, 1}; Р), где P (0) = Л, P (1) = И. Указанная формула истинна на модели SJi и ложна на подмодели <{0}, Р). Поэтому формула (3 х) P (х) не эквивалентна никакой V-формуле.
Ясно, что предикаты, определяемые бескванторными формулами, устойчивы в обе стороны: и при переходе к подсистемам, И при переходе к над системам. Покажем, что среди V-формул и 3-формул двусторонней устойчивостью обладают лишь формулы, эквивалентные бескванторным.
Теорема 2. Если 3-формула (2) устойчива относительно перехода к подсистемам, то она эквивалентна некоторой бескванторной формуле.
Пусть формула (2) истинна на какой-то алгебраической системе SJi сигнатуры а в точке у10, . . ., уп0. Берем подсистему 9?, порожденную в системе SJi элементами Ую, • • Упо¦ По условию формула (2) должна быть истинна в точке у10, . . ., уп0 на подсистеме 9?, т. е. в 31 ДОЛЖНЫ найтись элементы Xi, . . ., хт, для которых 2t (X1, . . ., хт, yl0, . . ., уп0) = И. Но каждый элемент системы 9? равен значению подходящего терма от У ют ¦ • -7 Упо (см. п. 6.1). Таким образом, для подходящих термов T01, . . ., T0m' от yiо, . . уп0 формула
Я (T01, ..., T0m, уі0, уп0) (4)
должна быть истинной.
Рассмотрим теперь систему формул которая
состоит из формулы % вида (2) и всех формул вида ПЯ(Г„ Tm, уи . . ., уп), где T1,..., Tm-
какие-нибудь термы от уи . . ., уп. Система <§ не может быть выполнимой. Действительно, пусть <& выполняется на какой-то алгебраической системе SJi сигнатуры g в точ- КЛАССИФИКАЦИЯ ФОРМУЛ
167
ке xjiQ, . . ., уп0. Тогда для каких-то термов Ti, . . ., Tm должна быть истинна формула (4), а это невозможно, поскольку в системе формул @ находится формула И St (Ti, . . ., Tm, уи . . ., уп).
