Алгебра и логика, 40, N 2 (2001), 158-173
УДК 512.57:512.565.7
ВНУТРЕННИЕ ГОМОМОРФИЗМЫ И ПОЗИТИВНО-УСЛОВНЫЕ ТЕРМЫ*) А. Г. ПИНУС
Понятия условного терма и условно термальной функции были вве дены в [1]. Условный терм соответствует понятию программы вычислений на универсальной алгебре. В силу этого, универсальные алгебры, которые заданы на одном и том же основном множестве и совокупности условно термальных функций которых совпадают, суть алгебры с равными про граммно вычислительными возможностями. В работах автора [2—12] (об зор полученных результатов см. [13]) рассмотрен целый ряд естественных вопросов, связанных с понятием условного терма. В частности, в [3] по казано, что для конечных алгебр (для равномерно локально конечных ал гебр конечной сигнатуры — в [12]) полугруппы внутренних изоморфизмов играют роль инвариантов отношения условно рациональной эквивалент ности на этих алгебрах (т.е. совпадения их программно вычислительных потенциалов). В силу этого результата возникал естественный вопрос о по лугруппах внутренних гомоморфизмов алгебр и связанном с совпадением этих полугрупп отношении "близости" между алгебрами. Решению этой проблемы и посвящена данная работа. Напомним, что внутренним изоморфизмом алгебры А = (А;сг) на зывается любой изоморфизм между ее подалгебрами. Совокупность всех внутренних изоморфизмов алгебры Л (включая сюда и пустое отображе ние 0 ) образует полугруппу (относительно естественным образом опреде** Работа выполнена при финансовой поддержке Российского фонда фундаменталь ных исследований, проект N 96-01-01675.
©
Сибирский фонд алгебры и логики, 2001
159
Внутренние гомоморфизмы и позитивно-условные термы
ленной операции суперпозиции), обозначаемую как IsoA. Понятие услов ного терма сигнатуры а базируется на понятии условия 7(х) сигнатуры а — конечной конъюнкции равенств и неравенств между термами сигна туры а. Конечное множество {7\(х),...
к
,7k(x)} условий назовем полной
_
системой условий, если формула V 7i(x) общезначима, а для различных р и q формулы 7р(х)к7д(х)
невыполнимы. Понятие условного терма сиг
натуры а определяется стандартной индукцией (как и понятие терма) с дополнительным индукционным шагом: если £i(#),... ,£&(#) — условные термы сигнатуры <7, а множество {7\(х),...
,Tfc(af)} — полная система условий этой сигнатуры, то и ( 7{(х) ->ti(S),
W
-
<
(i)
[ 7к(х) -* tk(x) будет условным термом этой сигнатуры. Каждому условному терму t(W) сигнатуры а на произвольной уни версальной алгебре Л = (А; а) соответствует условно термальная функция (также обозначаемая через t(x)), определяемая естественной индукцией по длине условного терма для тех индуктивных шагов, которые соответ ствуют стандартному определению терма; если же t(x) определен согласно правилу (1), для элементов о, Ь алгебры Л равенство t(a) = b соответствует тому, что Л |= 7i(a) и U(a) = b для некоторого г ^ к. Совокупность всех усдовных термов сигнатуры а будем обозначать как СТ(о), а всех условно термальных функций на алгебре Л — как СТ(А). Более подробно введен ные понятия описаны в указанных выше работах автора. Процитируем результат, явившийся отправным для данной работы: Т Е О Р Е М А [3, 12]. Для любых конечных алгебр (равномерно ло кально конечных алгебр конечной сигнатуры) А\ = (А; о{) и A
следую
160
А. Г. Пинус Эта теорема эквивалентна следующему утверждению: для любой алгебры Л, удовлетворяющей условиям теоремы, для лю
бой функции f : Ап -> А эквивалентны следующие условия: 1') / 6 СТ(Л); 2') подалгебры алгебры А замкнуты относительно функции f, и f коммутирует
со всеми отображениями из к о Л.
Внутренним
гомоморфизмом алгебры А называется гомоморфизм
между любыми подалгебрами алгебры Л. Совокупность всех внутренних гомоморфизмов алгебры Л (с добавлением к ним пустым отображением 0 ) образует полугруппу относительно естественным образом определенной операции суперпозиции: если h,g — внутренние гомоморфизмы алгебры Л,
а б Л, то
(hg)(a) = h(g(a)), когда (/(a) G Dom/i, и {hg)(a) не определено в противном случае. Полугруппу внутренних
гомоморфизмов алгебры Л будем обозна
чать IhmA. Таким образом, полугруппа внутренних изоморфизмов IsoA алгебры Л является подполугруппой полугруппы 1ЬтЛ и состоит из обра тимых элементов полугруппы IhmA, т.е. из тех h £ ШтЛ, что hgh == h для некоторого # из ГЬтЛ. В частности, из равенства ИипЛх = ИипЛг для алгебр Л ь Л2 вытекает равенство коЛх = коЛг. Основным вопросом исследований в данной работе является описа ние пар универсальных алгебр А\ = (A;ai) и Ач = (Л; 02), для которых имеет место равенство ГЬтЛг = НнпЛг, а также описание полугрупп ча стичных преобразований множеств, являющихся полугруппами внутрен них гомоморфизмов универсальных алгебр, определенных на этих множе ствах. ОПРЕДЕЛЕНИЕ 1. Позитивным условием сигнатуры а называется конечная система равенств термов этой сигнатуры:
*1(г) = «?(*), 9(х) = {
(
ti(x)=t2n(x).
ОПРЕДЕЛЕНИЕ 2. Позитивно-условные термы для алгебры Л =
Внутренние гомоморфизмы и позитивно-условные термы
161
= (А; а) определим индукцией по их длине: а) любая переменная и константа сигнатуры а являются позитивноусловными термами для алгебры Л; б) если t\ ( х ) , . . . , ti(x) — позитивно-условные термы для алгебры Л и f(xi,...
, xi) 6 сг, то и / ( ^ ( ж ) , . . . , tt(x)) будет позитивно-условным термом
для алгебры Л; в) если *i(«),... ,£fc(^) — позитивно-условные термы для алгебры Л, {'^(ж),... , Ук(х)} ~ некоторая система позитивных условий сигнатуры а, Л \= Vx I V 9i(x))
и Л |= Уж (У{(х) k?j{x)
-> tt-(a) = tj(x)) для любых
i , j ^ &, то f ^ ( ж ) - > «.-(ас),
(
9k(x)-+tk(x)
будет позитивно-условным термом для алгебры Л. Здесь и далее каждый позитивно-условный терм t(x) для алгебры Л определяет на Л позитивно-условную
термальную функцию. В п. а,
б из определения 2 построение позитивно-условной термальной функции на Л соответствует стандартному определению для термальных функций; если t{x) определен согласно п. в определения 2, то для а, Ь Е Л равенство t('a) =: & соответствует тому, что Л |= 7,(а) и £,(а) = Ь для некоторого г ^С &. Через РСТ(Л) обозначается совокупность всех позитивно-условных термальных функций на алгебре Л. Если Т(Л)(СТ(Л))
— совокупность
всех термальных (условно термальных) функций на алгебре Л, то очевид ны включения Т(А) С РСТ(Л) С СГ(Л). Как и для условных термов (см. [1]) будем говорить, что позитивноусловный терм t(lx) для алгебры Л имеет нормальную форму, если либо t(x) -- терм сигнатуры алгебры Л, либо правило из п. в определения 3 применялось при построении t(x) лишь на последнем шаге построения t(x). Без труда (так же как и для условных термов) замечается, что справедлива следующая
162
А. Г. Пину с Л Е М М А , Для любого позитивно-условного терма t(x)
сигнатуры
алгебры А существует позитивно-условный терм t!{x) указанной сигна туры в нормальной форме такой, что t(x) и tl(Jc) определяют на А одну и ту же позитивно-условную
термальную
функцию.
Непосредственно проверяется, что подалгебры произвольной алге бры Л замкнуты относительно позитивно-условных термальных функций алгебры Л, что вычисление этих функций коммутирует с переходом к по далгебрам и с внутренними гомоморфизмами алгебры Л. В то же время вычисление позитивно-условно термальных функций алгебры Л не обяза тельно коммутирует с произвольными гомоморфизмами алгебры Л (пре жде всего потому, что позитивно-условная термальная функция для алге бры Л может не быть таковой для некоторого гомоморфного образа алге бры Л). Т Е О Р Е М А 1. Для любой конечной алгебры (равномерно локально конечной алгебры конечной сигнатуры) А = (А; а), для любой функции / : Ап —> А эквивалентны следующие условия: 1) / G РСТ(Л); 2) подалгебры алгебры А замкнуты относительно функции f, и f коммутирует
со всеми внутренними гомоморфизмами алгебры А.
ДОКАЗАТЕЛЬСТВО. 1) -4 2) В силу замеченного выше имплика ция справедлива. 2) —> 1) Поскольку / коммутирует со всеми внутренними изоморфиз мами алгебры Л, то, как отмечено выше, справедливо / Е СТ(А).
Пусть
t(x) — условный терм, который в нормальной форме определяет на алгебре Л функцию /(ж), и 7г{х)
->tx(x),
t(x)
{ 7п(х) ->tn(x). Здесь 7{(х) — условия сигнатуры алгебры Л, а *,-(г) — термы этой сигна туры. Предположим теперь, что Л — конечная алгебра. Пусть х
=
= ( # ! , . . . jXm). Для любого а £ А™ через D±(x) обозначается позитив-
Внутренние гомоморфизмы и позитивно-условные термы
163
ная диаграмма подалгебры (а) алгебры Л, порожденная совокупностью элементов кортежа а (при этом Л \= Di(a)). На элементах множества Ат введем отношение эквивалентности: а\ ~ а2 тогда и только тогда, когда D±(x) = D±2(x). Заметим, что если Щ ~ а2 и для некоторого г ^ п верно Л f= Tj(ai), то Л [= Т г (а 2 ). Поскольку множество Ат конечно, существуют конечные подмножества Ра (ж) С С±(з?) такие, что для любых ai,a 2 € Ат включения Рах (ж) С Рд2 (ж) и £)± (ж) С D~2 (ж) равносильны. Для d G A m / ~ полагаем 1Р<*(ж) = 1Ро(ж), где а/ ~ = d. Определим отображение (р множества Ат/ ~ во множество {£ ь . . . , tn} так, что 9*(а/ ~)(ж) = ti(x) &A\=
7i(a).
Пусть Ат/ ~ ~ { d i , . . . , d,}. Рассмотрим следующую схему: PdAx) -+ 4>(di)(z)i
(2)
t'(x) = j (
f
J>de(x)-+cp(d8)(x).
Покажем, что £'(ж) является позитивно-условным термом, определяющим на алгебре Л функцию / . Действительно, в силу равенства Ат/
~ = { d i , . . . ,d e } на Л ис~
тинна формула Уж ( V 3^.(5;)). Пусть теперь для а 6 Л т верно Л (= (= У^. (а) & У^.(а). Тем самым, если dx; = а х / ~, dj = а 2 / ~ , то Л [= |= D ^ (а)&1)± (а), и значит, существуют гомоморфизмы V^ {i = 1,2) под алгебр (аг) на подалгебру (а) такие, что ^ ( а , ) = а. В силу определения функции (р выполняются равенства
(dj)(a2) ~ tt-2 (a 2 ), где п,г 2 ^ п таковы, что Л |= T t l (ai) & 7i2(a2). Поскольку функция /(ж) коммутирует с внутренними гомоморфизмами алгебры Л и определена на Л условным термом t(x), имеем цепочку равенств: / ( a ) = /(ф,(Щ)) = ^;(/(а;)) - ^ ( ^ ( ^ ) ) = М ^ ' ( « ; ) ) = М « ) = ¥>(<*,)(*) для j = 1,2. Тем самым, y?(di)(a) =
164
А. Г. Пинус
равенство f(a) = t'(a). Иначе говоря, функция /(af) является позитивноусловно термальной для алгебры Л, и утверждение теоремы для конечных алгебр Л доказано. Если Л -- равномерно локально конечная алгебра конечной сигнату ры, то, с точностью до эквивалентности на Л, число n-местных позитивноусловных термов £i(af),... ,£*(#) конечно. При этом на каждой конечнопорожденной подалгебре алгебры Л функция / совпадает с позитивноусловно термальной функцией, задаваемой одним из позитивно-условных термов *i(aF),... ,ts(x).
Выбирая соответствующее кофинальное подмно
жество в совокупности конечно-порожденных подалгебр алгебры Л, полу чаем существование г ^ s такого, что Л (= Уж (/(ж) = U{x)). Значит, и для равномерно локально конечных алгебр Л конечной сигнатуры имеет место импликация 2) —> 1). Теорема доказана. Непосредственно из теоремы 1 вытекает, что справедливо С Л Е Д С Т В И Е 1. Для любых конечных или равномерно
локально
конечных алгебр конечных сигнатур А\ = (А\а\) и Л2 = (А;а2) с одним и тем же основным множеством А эквивалентны следующие условия: 1) РСТ(Аг)
=
РСТ(А2);
2) IhmuAi = IhmA 2 . Сформулируем понятие позитивно-условно рационально эквивалент ных алгебр, аналогичное понятиям рационально и условно рационально эквивалентных. ОПРЕДЕЛЕНИЕ 3. Алгебры Аг = (Ai;ax) позитивно-условно
и Л 2 = {А2\а2)
назовем
рационально эквивалентными, если существует алге
бра Лз = {А\\ст2) с основным множеством алгебры А\ сигнатуры алгебры Л2 и такая, что: 1) Лз изоморфна алгебре А2\ 2) существуют отображения F\ : о\ ~> РСТ(А2), F2 : с2 —>•
РСТ(А\),
сохраняющие арности функций и для которых выполняются а) А\ — (Ai\(7i) = Fi(A3) = (Ах; F ^ a i ) ) , где ai-функции алгебры Fi(As) определяются на А\ с помощью их F\-образов как РСТ-функции алгебры Лз,
Внутренние гомоморфизмы и позитивно-условные термы 6)A3
= (Al;a2)
= F2(Al) =
165
(Al;f2(a2)).
Очевидно, что позитивно-условно рациональная эквивалентность ал гебр Л\ = (Ai; <Ti) и Л 2 = (А2\ #2) равносильна существованию <Т2-алгебры As с основным множеством Ai, изоморфной алгебре Л 2 и такой, что PCT{Ai)^PCT{A3). Из следствия 1 вытекает следующее С Л Е Д С Т В И Е 2. Конечные или равномерно локально конечные ал гебры конечной сигнатуры А\ = {А\\ а\) и Л2 = (A2; сг2) позитивно-услов но рагщонально эквивалентны тогда и только тогда, когда существует биекция 7Г множества А\ на множество А2, которая сопрягает совокуп ность отображений ШтЛх с совокупностью отображений 1Ъ.тА\. Заметим, что ограничения конечными и равномерно локально ко нечными алгебрами конечной сигнатуры в формулировках теоремы 1 и следствий 1, 2 существенны, ПРИМЕР 1. Действительно, пусть ро>Ръ*" »?*»»••• ~~ простые на туральные числа, множества А; (г Е w) дизъюнктны и |А,| = р,-. Пусть А = IJ А,-. Рассмотрим сигнатуру <7, состоящую из одной одноместной функции / , причем (А,;/) является циклом длины р^. Для алгебры Л = = (А; / ) , как нетрудно заметить, имеет место равенство РСТ\(А)
= Ti (Л),
где РСГа(Л) (соответственно Т1(Л)) — совокупность одноместных пози тивно-условно термальных (термальных) функций алгебры Л. Определим теперь функцию g на алгебре А следующим образом: ,
ч
I /(ж),
если я G А \ А Ь
2
I / (ж), если ж е Аь Нетрудно заметить, что # коммутирует со всеми внутренними гомомор физмами алгебры Л. С другой стороны, в силу замеченного выше g $ $РСТг{А). Положим теперь А\ = (А;/,#). Тогда ШтЛ = ПипЛх, кроме того, РСТ\(А)
ф PCTi(A\))
поэтому алгебры Л, А\ не являются позитивно-
условно рационально эквивалентными. ПРИМЕР 2. Пусть Ai (i G w) дизъюнктны и |А,| = 2. Пусть А =
166
Л. Г. Пинус
= U Л,. Рассмотрим сигнатуру а, состоящую из одноместных функций /,-, причем (Л,; /;) является циклом длины 2 и /,- — тождественная функция на Л^ при г\ф j . Пусть Л = (Л; <т). Для любой h £ Р С Т ^ Л ) существует
new
такое, что для всех га ^ п и а £ Л т выполняется Д(а) = а. Определим g на Л следующим образом:
9(*) = {
я,
если ж £ Ai при г четном,
/,(ж),
если х £ Л, при г нечетном.
Функция ^ коммутирует со всеми внутренними гомоморфизмами алге бры Л, а в силу замеченного выше д $ РСТ\{А).
Положим теперь
Ai = (Л; а,д). Тогда 1ЬтЛ = 1 Ь т Л ь кроме того, РСТг(А)
ф
PCTx{Ai).
Так как для наследственно простой алгебры Л совокупность 1ЬтЛ однозначно определяется совокупностью ЬзоЛ, то имеет место С Л Е Д С Т В И Е 3. Для наследственно простых и либо конечных, либо равномерно локально конечных алгебр конечной сигнатуры А\, А<г эквивалентны следующие условия: 1) алгебры А\ и Аъ условно рационально
эквивалентны;
2) алгебры А\ и Л2 позитивно-условно рационально
эквивалентны.
В частности, на двухэлементных алгебрах условно рациональная эк вивалентность равносильна позитивно-условно рациональной эквивалент ности, и в силу [4] существуют лишь пять классов позитивно-условно ра ционально эквивалентных двухэлементных алгебр. Рассмотрим теперь характеризацию конечных алгебр, полугруппы внутренних гомоморфизмов которых изоморфны. В [3] было введено по нятие схожести алгебр: алгебры Л, Ъ называются схожими, если для неко торых натурального числа п и идемпотентного обратимого терма rj(x) ма тричной степени Л ^ алгебры Л, алгебры А^(г])
и Ъ являются условно
рационально эквивалентными. Там же доказано, что конечные алгебры Л и Ъ схожи тогда и только тогда, когда Ьо*Л = Iso*B. Здесь ко*Л — обо гащение полугруппы IsoA одноместным предикатом, выделяющим идемпотенты ЬоЛ, соответствующие одноэлементным подалгебрам алгебры Л. ОПРЕДЕЛЕНИЕ 4. Алгебры Л и Ъ назовем сильно схожими, если для некоторых натурального числа п и идемпотентного обратимого терма
Внутренние гомоморфизмы и позитивно-условные термы
167
т](х) матричной степени Л ^ алгебры Л, алгебры А\п^(т)) и Ъ являются позитивно-условно рационально эквивалентными. Через 1Ьт*Л обозначается обогащение полугруппы 1ЬтЛ одномест ным предикатом, выделяющим идемпотенты 1ЬтЛ, которые соответству ют одноэлементным подалгебрам алгебры Л. Т Е О Р Е М А 2. Для любых конечных алгебр А иЪ равносильны сле дующие условия: 1) Л и Ъ сильно схожи; 2) IhmVi £ I b m * ^ ДОКАЗАТЕЛЬСТВО. 1) -> 2) В [14] показано, что отображения Л -* Л ^ , Л.—* Л(т?) (где т/(ж) — обратимый идемпотентный терм алгебры Л) коммутируют с отображением Л -» 1ЬтЛ, а значит и с отображением Л -* Шт*Л. В силу следствия 3 получаем требуемое. 2) -> 1) Пусть (р ~- изоморфизм 1Ьт*Л на Ihm""B для конечных ал гебр Л и *В. В частности, изоморфизм <р определяет изоморфизм полугрупп 1зо*Л и Iso*S, Отсюда и в силу [3], найдутся i £ w, обратимый идемпо тентный терм т](х) алгебры Л ^ и биекция основного множества алгебры на основное множество алгебры Ъ такие, что для любого h E Ьо*Л имеем
v(hln\ri))n-1.
Здесь ftM иfeW(?/) — естественно определенные образы гомоморфизма h из ИипЛ при изоморфизмах 1ЬтЛ £ 1ЬтЛМ и 1ЬтЛ[п1(г/) = П и п Л К Заме тим, что идемпотенты полугруппы Иш1*Л со стандартным (абстрактным образом, а значит, коммутирующим с отображением (р) определенным на них порядком соответствуют решетке подалгебр алгебры Л. Тем самым, частичные отображения Съ алгебры Ъ такой, что у>(Л) = а-7г(Л[п1(т/))?г"1. При этом для h = i d d выполняются V ( i d d ) = i d c 2 и тг^^^т?))^" 1 = idc 2 ,
168
А. Г. Пинус
поэтому а = idc2 и
Следовательно, полугруппы
сопряжены отображением
7г. В силу следствия 3 алгебры A^n\rj) и S позитивно-условно рационально эквивалентны, теорема доказана. В связи со следствием 2 представляет интерес описание полугрупп частичных преобразований множеств, являющихся полугруппами вну тренних гомоморфизмов универсальных алгебр. Подобное описание полугрупп внутренних изоморфизмов универ сальных алгебр впервые было дано в [15]. В [3] эти полугруппы представ лены в терминах пар (S,H),
где 5 — некоторая алгебраическая решет
ка подмножеств множества А (решетка подалгебр некоторой универсаль ной алгебры А = (А; а)), а Я — некоторая совокупность биекций между подмножествами из 5 . Приведем, в аналогичных терминах, описание по лугрупп внутренних гомоморфизмов наследственно сильно проективных универсальных алгебр. Говоря о том, что совокупность 5 подмножеств некоторого множе ства А образует решетку, будем иметь в виду, что 5 является решеткой относительно порядка, определенного как теоретико-множественное отно шение "быть подмножеством", и решеточная операция Л на элементах S представляет собой теоретико-множественное пересечение этих элементов, как подмножеств множества А (в то время как решеточная операция V не обязана быть теоретико-множественной операцией объединения), при этом супремум любой направленной вверх системы подмножеств из 5 совпадает с теоретико-множественным объединением этих подмножеств. Алгебру А назовем сильно проективной
в классе К, если Л 6 А',
для любых алгебр А\, А^ из Л', любого эпиморфизма h алгебры А\ на Лг, любого гомоморфизма д<± алгебры Л в алгебру Лг, для любых попарно раз личных элементов а = ( a i , . . . , ап) из Л и любых элементов Ъ — (&i,... , Ьп) из А\ таких, что h(b) = (72(a), существует гомоморфизм д\ алгебры Л в ал гебру А\ такой, что #i (a) = 6 и hg\ — #2- Алгебру Л назовем наследственно
Внутренние гомоморфизмы и позитивно-условные термы
169
сильно проективной, если алгебра А является сильно проективной в клас се SukA. ОПРЕДЕЛЕНИЕ 5. Пусть S С Р(А) — некоторая алгебраическая ре шетка подмножеств множества А, включающая и само множество. Пусть Я — некоторая совокупность отображений множеств из 5 на множества из 5 . Через dg и гд обозначим соответственно область определения и область значений отображения д из Я . Для С С dg через д\с обозначается ограни чение отображения д на множество С. Для С С А через S(C) обозначается наименьшее подмножество множества А, входящее в 5 и содержащее С. а) Принципом проективности
для Я и 5 называется следующее
свойство: для любых Ci,C2,C 3 € S и
,ап) е Ci,b=
( Ь ь . . . , Ьп) G С2 и р х (а) = 02(Ь)>
вытекает существование h £ Я такого, что cfo = С 2 , r^ = C\,g\h = #2 и Л(Ь) = а. б) Принципом композиции для Я называется следующее свойство: для любых #, /i £ Я из r/i = dg вытекает h о g £ Я . в) Принципом общности для S и Я называется следующее свойство: для любых <7i, 02 £ Я , если множество {а 6 А | а £ dgi Ddg2 и #i(a) = 52(a)} непусто, то оно входит в 5 . г) Принципом ограничения для S и Я называется следующее свой ство: для любых g £ Н и С € S из С С dg вытекает д\с £ Я , а из С С г^ вытекает ^*"1(С) € 5 . д) Принципом согласованности S и Я называется следующее свой ство: для любого С £ 5 имеет место включение idc € Я , для любого д £ Я имеют место включения <^, г 5 £ 5 . Здесь idc — тождественное отображе ние множества С на себя. е) Принципом глобализации называется следующее свойство: для лю бых С £ S и F : PW(C) ~» Я таких, что 1) для D € PW(C) выполняется dp(D) = 5(D), 2) для любых D b D 2 6 Ли (С) справедливо F(Di)|5(D 1 ) n s(D2)
=
= P{D2)\s(Dx)nS(D2b существует h £ Я такое, что cfo = С, и для любого D € ЛЛС) имеет ме-
А. Г. Пинус
170
сто h\s(D) = F{D)- Здесь Р^ДС) — совокупность конечных подмножеств множества С, a 5(D) — наименьшее множество из 5 , содержащее подмно жество D. ж) Принципом одноэлементных подалгебр называется следующее свойство: для любых C E S H O E A
из {а} Е S вытекает существова
ние h Е Н такого, что dh = С и гд = {а}. ТЕОРЕ1МА 3. Длл любых алгебраической решетки S подмножеств множества А, включающей и само А, и системы Н отображений под множеств из S друг на друга таких, что S и Н удовлетворяют пам а—ж; существует наследственно сильно проективная
принци
универсаль
ная алгебра А} определенная на основном множестве А и такая, что S — SnhA и Н — IhraA. Верно и обратное: для любой наследственно силь но проективной универсальной алгебры А системы подалгебр алгебры А и гомоморфизмов этих подалгебр друг на друга обладают указанными выше свойствами а—ж. ДОКАЗАТЕЛЬСТВО. Для любых элементов а\, . . . , а„ Е А и любо го а Е 5({a i ? .... , а„}) введем в рассмотрение n-местную функцию fa,a{%) на А; здесь а — ( а 1 } . . . , ап) и х — (xi,...
, хп). Функция fa,a{%) определя
ется следующим образом:
{
д(а)у
если существует д Е Н такое, что Ь\ = д(аг),...
Ь\
, Ь„ =
д{ап),
в противном случае.
Корректность определения функции /a, a на множестве А следует из прин ципа общности для 5 и Я . Пусть Л = (A; /offl | а ь . . . , ап Е А и а Е S({ai,...
, а п })). Из прин
ципа ограничения очевидно вытекает, что 5 = Sub Л, т. е. системой основ ных множеств подалгебр алгебры Л является совокупность S. Докажем, что система внутренних гомоморфизмов алгебры Л совпадает с Н. Пусть В, С Е 5 и h — гомоморфизм подалгебры Ъ с основным множеством В на подалгебру G с основным множеством С. Отображение F : PW{B) —> Н определим следующим образом: пусть F(D) = /i|s(£>) П Р И -D E PW(B).
В
Внутренние гомоморфизмы и позитивно-условные термы
171
силу принципа глобализации для доказательства включения h £ Я до статочно показать, что для любого D £ PW(B) отображение ho = ^|s(D) принадлежит Я . Пусть D = { a i , . . . , a n }. Е^сли |/&(J9)| Ф 1, то возьмем а\,а2 £ D такие, что ho(ai) ф hD(a2). Тогда /o, a2 («) = a 2 , а значит, fa,a2(hD(a)) =
ho(a2)
и ho((i\) ф ho(a2). Тем самым по определению функции /a, a2 найдется <7 £ Я такое, что
е
Я . Покажем, что для любого с £ 5 ( { a i , . . . , a n } ) \ { a i } имеет
место равенство ho{c) = 5|8({аь...,ап})(с)- Действительно, так как /i# ™внутренний гомоморфизм алгебры Л, то /a,c(^D(^)) = ho (с). С другой стороны, (7(a) = /^£)(а), и тогда по определению функции fa}C имеет место равенство fatC(ho(a)) = /a,c(^(«)) = flf(c). Таким образом, hD(c) = #(с), т.е. ^£>
=
#L({ab.,.,<*„}) и> т е м
когда \h(S(D))\
самы
м , ho £ Я . Если |/&(D)| = 1, ТО В случае,
> 1, вместо D используем D\ ='{61,62} Q S(D) такое,
что h(bi) ф h(b2). Если же \h(S(D))\ = 1, то ho £ Я в силу принципа одноэлементных подалгебр. Таким образом, h £ Я , т.е. любой внутренний гомоморфизм алгебры Л принадлежит Я . Покажем, что отображения из Я являются внутренними гомомор физмами алгебры Л. В силу принципа глобализации, имеющего место для 5 и Я , достаточно установить, что для любых 6 i , . . . ,6„ £ А и любого h £ Я , для которого dh = 5 ( { 6 i , . . . ,6 n }), отображение h является вну тренним гомоморфизмом алгебры Л. Обозначим dh как С\ и гн как СгПусть i7i,... , Vk £ C i , a i , . . . , a*. £ А и a £ 5 ( { a i , . . . , а*;}). Покажем, что / a , a ( M v l ) > " - >M V *)) = Л ( / а , а ( « 1 , . . . ,Vfc))-
В случае, когда отсутствует д2 £ Н такой, что д2(а) = (/i(ui),... . . . , h(vk)) = /i(U), по определению /a>a имеем равенство fa,a{h(v)) = fr(t>i). В силу принципа композиции нельзя найти #i £ Я , для которого бы # l ( a ) = V, ПОЭТОМУ fa,a(v)
=
'^Ь И равеНСТВО fa,a{h{v))
=
h(fa,a{v))
ДО-
казано. Допустим теперь, что существует #2 £ Я , для которого #2 (a) • = h(Щ. Следовательно, fafQ(h(v)) =
а
значит,
172
А. Г. Пину с
h(fa,a(v))
= hgi{a) = # 2 (а). С другой стороны, fa,a(h(v))
— 92{о). Поэтому равенство fa,a(h(v))
= h(fa,a(v))
= кЛ92{о))
=
имеет место и в этом
случае. Итак, отображения из Я являются внутренними гомоморфизмами алгебры Л , т. е. 5 = SutxA, Я = 1 Ь т Л . Утверждение о том, что д л я любой наследственно сильно проектив ной универсальной алгебры Л пара (SutxA, 1 Ь т Л ) удовлетворяет принци пам а—е также очевидно. Теорема доказана. Представляется интересным найти описание совокупности пар ( 5 , Я ) таких, что 5 = ЗиЬЛ Й Я = 1 Ь т Л для произвольных универсальных ал гебр Л . В заключение автор выражает свою благодарность Е. А. Палютину, указавшему на ошибку в первоначальном варианте работы и предложив шему пример 2.
ЛИТЕРАТУРА 1. А. Г. Пинус, Об условных термах и тождествах на универсальных алгебрах, в сб. "Структурные алгоритмические свойства вычислимости" (Вычислит, системы, 156), Новосибирск, Ин-т матем. СО РАН, 1996, 59—78. 2. А. Г. Пинус, Характеризация условно термальных функций, Сиб. матем. ж., 38, N 1 (1997), 161-165. 3. А. Г, Пинус, Исчисление условных тождеств и условно рациональная экви валентность, Алгебра и логика, 37, N 4 (1998), 381—408. 4. А. Г. Пинус, Об условно рационально эквивалентных алгебрах, в сб. "Струк турные и сложностные проблемы вычислимости" (Вычислит, системы, 165), Новосибирск, Ин-т матем. СО РАН, 1999, 3-30. 5. А, Г. Пинус, Об алгебрах условно рационально эквивалентных полурешет кам и булевым алгебрам, Сиб. матем. ж., 39, N 1 (1998), 121—128. 6. А. Г. Пинус, Йонссоновские локально конечные условные многообразия и условно рациональная эквивалентность, Сиб. матем. ж., 39, N 4 (1998), 942-948. 7. А. Г. Пинус Об условно рационально эквивалентных дискриминаторных многообр>азиях, Изв. вузов. Матем., 8(447), 1999, 54—59.
Внутренние гомоморфизмы и позитивно-условные термы
173
8. A. G.Pinus, Conditional terms and Skolem-functions, in: "Contributions to general algebra 11", Verlag Johannes Heyn, Klagenfurt, 1999, 155—160. 9. А. Г. Пинус, Внутренние изоморфизмы и условно рациональная эквива лентность у нарам и полям, в сб. "Алгебра и теория моделей", Новосибирск, Изд~во НГТУ, 1997, 131-142. 10. А.Г.Пинус,
Об алгебрах условно термальных функций, в сб. "Алгебра и
теория моделей", Новосибирск, Изд-во НГТУ, 1997, 123—130. 11. А. Г. Пинус, Об определимости конечных алгебр производным структурам, Изв. вузов. Матем. (в печати). 12. A. G.Pinus, The conditionally rational equivalence of uniformly locally finite algebras, Тезисы алгебр, конф. памяти А. Г. Куроша, М., 1998, 104—105. 13. A. G.Pinus, Conditional terms and its applications, in: "Algebra", Proceedings of Kurosh conference, Berlin-New York, Walter de Gruyter, 2000, 291-299. 14. R. McKenzie, An algebraic version of categorical equivalence for varieties and more general algebraic categories, in: "Logic and algebra" (Lect. Notes Pure Appl. Math., 180), New York a.o., Marcel Dekker, 1996, 211-243. 15. Д. А. Бредихин, Инверсные полугруппы локальных автоморфизмов, Успехи матем. наук, 34, N 4 (1979), 181-182.
Адрес автора: П И Н У С Александр Георгиевич, РОССИЯ, 630099, г. Новосибирск, ул. Революции, д. 10, кв. 15. e-mail: [email protected]
Поступило 24 ф е в р а л я 1999 г.
