Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Допустим, напротив, что в 95/= какое-нибудь из квазитождеств (14) ложно, т. е. что в 95/= существуют элементы hi=, . . ., hn = (ht, . . ., hn ? В), для которых
gc ос
формулы
Pat (f(h=)) (t=i,...,na) (17)
истинны в 25/=, а формула Pa0 (/ (/г.=)) ложна. Но истинность в системе 95/= формул (17) равносильна истинности формул
Putifm (t=l,...,na) (18)
в системе 25, а истинность формул (18) в 95 по определению означает, что они принадлежат совокупности <Ва и, следовательно, принадлежат (©„ для подходящего натурального п. В силу формулы (16) отсюда вытекает, что формула Pa0 (/ (h)) принадлежит <®п+1 и потому истинна в 95/=, в противоречие со сделанным допущением.
Итак, совокупность есть совокупность всех квазиатомарных формул от переменных Zi, вытекающих в классе й из совокупности (0. В частности, согласно исходным определениям, это означает, что система 95/== является системой, определяемой в классе К порождающими символами Zi и определяющими формулами (©. Изложенный процесс построения ®/= часто называется стандартным 288
КВАЗИМНОГООБРАЗИЯ
/
[Гл. V
процессом построения алгебраической системы по ее порождающим элементам и определяющим формулам.
Отметим, что решенная нами задача о нахождении процесса построения формул квазиатомарного вида, вытекающих из заданных квазитождеств й квазиатомарных формул, является частным случаем задачи о построении всех тождественно истинных формул языка 1-й ступени, решаемой с помощью алгоритма Гильберта. Однако благодаря тому, что нас здесь интересовали лишь формулы очень специального вида, найденный процесс оказался много более простым, чем общий алгоритм Гильберта.
В заключение рассмотрим несколько примеров фактического построения алгебраических систем по их определяющим формулам.
а) Пусть класс Ш есть квазимногообразие частично упорядоченных множеств, определяемое квазитождествами
ж<г/&г/<ж-^-ж = г/, х < у & г/< г. (19)
Сигнатура этого класса не содержит функциональных символов и квазиатомарные формулы могут иметь лишь вид Zi = Zj или Zi Zj. Поэтому, чтобы задать частично упорядоченное множество определяющими соотношениями, надо задать совокупность определяющих символов Zi (і Є I) и совокупность формул © вида
Zi = Zi, Zh < Z1 (i, 7, k, I 6 Г). (20)
Имея совокупность (20), далее применяем процессы С) и В), указанные выше. А именно, если в (20) есть равенства, то выделяем их систему, имеющую вид
Zi=Zh (i Є Iu ке h, AfU2= 0).
Все символы Zi (і Є Ii) исключаем из списка порождающих, а во всех формулах (20) заменяем каждое Z1 на соответствующее Zh.
Смотрим, есть ли в новой совокупности (20) пары формул вида Zi^Zj, Zj^zi или Zi^Zj, Zj ^ zk. Если есть, то к совокупности (20) добавляем формулы Zi = Zj или Zi ^ Zh и применяем снова процесс исключения.
Чтобы нормализовать эти процессы исключения, можно, например, совокупность индексов I вполне упоря- ,§ 11]
ОБЩИЕ СВОЙСТВА
289
ob
а
дочить и исключать символы с большими индексами. Совокупность всех оставшихся символов и совокупность всех полученных формул вида zi ^ zj, связывающих оставшиеся символы, и будут определять искомую модель.
б) Пусть класс S имеет сигнатуру, состоящую из предикатного символа , одноместного функционального символа и пусть 2 определяется аксиомами (19) и дополнительным квазитождеством
ж' < ж. (21)
Рассмотрим систему 21, определяемую в 2 порождающими символами a, b и определяющими формулами
І = 1,2,...). (22)
а'
b
b'
ц(П*1)
a(th,K
y^j
Легко видеть, что все соотношения системы, • • , .
изображенной на левой ' •
диаграмме (рис. 1), вы- Рис. 1.
текают из формул (22)
и что в этой системе квазитождества (19), (21) истинны. Поэтому указанная система определяется в 2 формулами (22).
Аналогичным образом убеждаемся, что изображенная на рис. 1 правая система определяется в классе 2 формулами
«(*)<&(*) (i = l,..., п)
Отсюда видно, что система 21, определяемая бесконечной системой формул (22), не может быть определена в 2 никакой конечной совокупностью квазиатомарных формул.
11.3. Реплики. Пусть й — произвольный класс алгебраических систем сигнатуры й и 1 — какая-нибудь система сигнатуры Q, не обязательно принадлежащая классу й. Гомоморфизм а системы 21 на некоторую
19 А. И. Мальцев 290
КВАЗИМНОГООБРАЗИЯ
[Гл. V
й-систему SI1 будем называть Аморфизмом, если для каждого гомоморфизма у системы 21 в произвольную й-систему © существует такой гомоморфизм І (рис. 1) системы SI1 на систему что у = а?. Каждый й-морфный образ системы Sl называется репликой SI в классе й (Й-репликой) и обозначается SI^.
Из этого определения вытекает, что тождественное отображение каждой й-системы на себя есть Й-морфизм, и потому каждая Й-система является своей собственной репликой в й.
Отметим еще несколько прямых следствий определения реплики. 1. Пусть й — какой-либо класс систем ?: ->- — Аморфизмы некоторых '.-реплики.; Если существует эпиморфизм существует и эпиморфизм ?: St^ —>¦ 95g, условию ос? =
