Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
T (alr . . ., ат) а = T (^1 а, . . ., ага), (3)
где слева и справа от знака равенства стоят значения терма T при указанных значениях переменных в системах St и 95.
Доказательство проводится индукцией по числу п вхождений функциональных символов в Т. Если п = 0 или п = 1, то терм T имеет один из видов
Xi, Ff, F^iSi, ...,Sm).144 ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
где J1, . . ., Zm 6 {zj, • . Жг}. В каждом из этих случаев равенство (3) совпадает с равенством (1) в определении гомоморфизма в п. 2.2.
Пусть теперь терм T имеет п >¦ 1 вхождений функциональных символов и для термов с меньшим числом вхождений равенство (3) справедливо. Терм T имеет вид
fT° (Ti, . . ., Tm.), где T1, . . ., Tm. — некоторые термы с меньшим значением числа п. Из определения гомоморфизма получаем
Fi (Tu . . ., Tm.) а = Gi (TiOL, . . Тт.а). Согласно индуктивному предположению
Tj (аи . . ., аг) а = Tj (ata, . . ., аТа)
и потому
F1 (Tu . . ., Tm.) а = = Gi (Ti (а%а, . . ., ага), . . Тщ (а&, . . ., ага)) =
= T (Ctiа, . . ., ага),
что и требовалось.
В п. 2.3 было введено понятие порождающей совокупности элементов S подсистемы Sti некоторой алгебраической системы SI. Это понятие можно сделать более конкретным при помощи понятия терма. Условимся говорить, что некоторый терм T имеет сигнатуру системы Sf (см. также п. 6.3), если каждому функциональному переменному, участвующему в записи терма Т, поставлена в соответствие в качестве его значения в SI некоторая главная операция системы Si. Мы будем говорить, что тёрм T есть терм OT элементов 01,...,0,. системы Si, если каждому предметному переменному, входящему в запись Т, поставлен в соответствие один из элементов аи . . ., аг в качестве значения этого переменного. Тогда значением каждого терма сигнатуры системы St от некоторых элементов этой системы будет какой-то элемент той же системы St.
Теорема 2. Для того чтобы подсистема Sl1 порождалась совокупностью S элементов некоторой алгебраической системы SI = (A, Q), необходимо и достаточно,СИНТАКСИС И СЕМАНТИКА
145
чтобы каждый элемент Sl1 равнялся значению подходящего терма сигнатуры 21 от некоторых элементов S.
В самом деле, подсистема SI1, порожденная совокупностью S, содержит S и замкнута относительно главных операций. Поэтому, вычисляя значение какого-нибудь терма от элементов совокупности S, мы будем оставаться внутри SI1, и окончательное значение терма также будет в SI1. Обратно, пусть 9)? — множество значений всевозможных термов от элементов совокупности S. Множество SJi замкнуто относительно любой главной операции F^, так как, если U1, . . ., Um^ — значения каких-то термов
Ti, . . ., Tm^ от некоторых элементов S, то F^ (Ui, . . ., будет значением терма F^ (T1, . . ., Tm^ от тех же элементов и потому Fi {ии . . ., Um^ 6 9JL Согласно определению SI1 есть наименьшее множество, содержащее S и замкнутое относительно всех главных операций. Множество ШЇ содержит S и замкнуто относительно главных операций. Поэтому SI1 s SJi. Однако выше было установлено, что SJi с SI1. Следовательно, SI1 = 3Ji, что и требовалось.
Следствие 1. Если гомоморфизмы а, ? какой-нибудь алгебраической системы Sl в систему S3 совпадают на некоторой совокупности элементов S, порождающей St, то а = ?.
Согласно теореме 2 произвольный элемент х Q SI есть значение подходящего терма T [аи . . ., аг), где «і, . . ., аТ — некоторые элементы S. По условию
ata — ?;? (і = 1, . . ., г).
В силу теоремы 1 отсюда получаем
T (аи . . ., ат) а = T [аи . . ., ат) ?,
т. е. ха. = для любого х ? Si.
Итак, чтобы задать гомоморфизм SI в 95, достаточно указать лишь элементы atа (аг Q S). Каким же условиям должны удовлетворять произвольно заданные элементы аа, чтобы это отображение Sb® можно было продол?кить до гомоморфизма Sl в 53?
Теорема 3. Пусть S — совокупность элементов, порождающая алгебру Si, и а* — отображение S в какую-то
10 а. И. Мальцев146
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
алгебру 95, однотипную с И. Для того чтобы отображение а* могло быть продолжено до гомоморфизма SI б 95, необходимо и достаточно, чтобы
Ti{au ...,аГ) = Т2{а1,...,аТ)=$
=^ T1 (ata*, . .., ara*) = T2 • • •, ата*) (4)
для любых термов Ti, T2 сигнатуры SC и любых сь\, . . ., аг из S.
Из теоремы 1 следует, что условие (4) необходимо. Пусть оно выполнено. Берем произвольный элемент а ? SL Согласно теореме 2 найдется терм T [X1, . . ., хТ) такой, что а — T . . ат) для подходящих alt ... . . ., ат из S. Полагаем по определению
аа = T (aja*, . . ., аГa*). (5)
Условие (4) гарантирует, что аа не зависит от выбора соответствующего терма Т, т. е. что а есть однозначное отображение Ив®. Беря произвольные Z1, . . ., Zmt в S и представляя их в виде термов от элементов S, из (5) получаем соотношение
F1 (Z11 . .., zmJ a = Gg (Z1Ci, ..., Zm а),
¦в 1 ?
означающее., что a — гомоморфизм 21 в 95.
В теореме 3 рассматриваются гомоморфизмы алгебр. Для гомоморфизмов систем к условию (4) надо добавить условие (2) из п. 2.2, принимающее здесь следующий вид: