авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |   ...   | 8 |

«Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет» ...»

-- [ Страница 3 ] --

i В качестве проекций берутся элементы pi,n = pn R(n). Проверим, что i выполнены свойства из определения клона. Начнем с ассоциативности.

Смысл обозначений тот же, что и в данном в начале параграфа опреде лении клона. При проведении преобразований используются свойства из определения операды.

[x[y1 z]... [y1 z]] = (x[y1 z]... [ym z])µm,k = (x((y1 z)µn,k )... ((ym z)µn,k ))µm,k = (x(y1 z)... (ym z))((µn,k... µn,k )µm,k ) = ((xy1... ym )z... z)((µn,k... µn,k )µm,k ).

В последнем выражении µn,k и z = z1... zn повторяются по m раз. С другой стороны, [[xy1... ym ]z] = [((xy1... ym )µm,n )z] = (((xy1... ym )µm,n )z)µn,k = ((xy1... ym )z... z)((µm,n ) )µn,k.

Здесь = (k n ) P (nk, k), и последнее выражение получено в результате применения свойства вида (f )1... k = (f (1)... f (l) )(f ) (3.1.1) из определения операды, в котором роль f играет µm,n : [nm] [n].

Строка zf (1)... zf (nm), согласно определению µm,n, есть сцепление z с самой собой m раз. Необходимое нам равенство получится, если будет доказано, что имеет место равенство морфизмов из F Setop :

(µn,k... µn,k )µm,k = ((µm,n ) )µn,k, или, что эквивалентно, равенство морфизмов в F Set:

µm,k (µn,k... µn,k ) = µn,k ((µm,n ) ).

Заметим сначала, что в любой категории с прямыми произведениями сле дующая диаграмма будет декартовым квадратом:

2, X Y Z Y Z 1,2 X Y Y Здесь буквой обозначены соответствующие проекции. Например, “по элементно”: 2,3 (x, y, z) = (y, z), 1 (y, z) = y, и т.п. Рассмотрим катего рию F Set и положим X = [k], Y = [n], Z = [m], тогда для приведенной выше диаграммы X Y Z = [knm], X Y = [kn], Y Z = [nm], 1 = µm,n, 2 = (k n ) =, 2,3 = (k nm ), 1,2 = µm,kn. Но так как 2,3 = (k nm ) — неубывающее отображение, то из декартовости квад рата и определения (µm,n ) следует, что (µm,n ) (k n ) = µm,kn. Таким образом, требуется установить равенство:

µm,k (µn,k... µn,k ) = µn,k µm,nk.

Чтобы убедиться в его справедливости, будем представлять [knm] как копроизведение mn экземпляров [k], [mk] — как копроизведение m эк земпляров [k], [nk] — как копроизведение n экземпляров [k], и рас смотрим ограничение отображений в левой и правой частях на какое либо “прямое слагаемое” [k] в [knm].

Сначала представим [knm] как копроизведение m экземпляров [kn]. По определению µn,k, отображение µn,k... µn,k переводит каждый экземпляр [k] из j -го экземпляра [kn], входящего в [kmn], тождественно на j -й экземпляр [k] из [km]. Затем µm,k отображает этот j -й экземпляр тождественно на [k]. С другой сто роны, µm,nk отображает каждый экземпляр [nk] из [kmn] (здесь [kmn] рассматривается как копроизведение m экземпляров [nk]) тождественно на [nk]. Следовательно, каждый экземпляр [k] из [kmn] тождественно отображается на соответствующий экземпляр “прямого слагаемого” [k] из [nk]. Затем µn,k вновь переводит этот экземпляр [k] тождественно на [k]. Таким образом, ограничение отображений в левой и правой час тях доказываемого равенства на каждое “прямое слагаемое” [k] из [knm] есть тождественное отображение, и равенство (а вместе с ним и ассоци ативность суперпозиции в абстрактном клоне) установлено.

Осталось проверить свойства pi,n = pn. Пусть x R(n). Тогда i [xp1,n... pn,n ] = x((pn )... (pn ))µn,n = 1 n (x... )(pn · · · pn )µn,n = x(pn · · · pn )µn,n.

1 n 1 n Отсюда следует, что (после перехода из F Setop в F Set) необходимое равенство будет следовать из тождества µn,n (pn... pn ) = 1[n], 1 n которое легко вытекает из определений. Далее, пусть = (nm ), x1,..., xm R(n). Тогда, используя свойство (3.1.1), получим [pi,m x1... xm ] = (pm )(x1... xm )µm,n = i (xi )((pm ) )µm,n = xi ((pm ) )µm,n.

i i Необходимое нам равенство получится, если будет доказано тождество (в F Set):

µm,n ((pm ) (nm )) = 1[n].

i Прямо из конструкции расслоенного произведения следует, что (pm ) (nm ) i есть сохраняющая порядок биекция [n] на i-е “прямое слагаемое” [n] в [nm]. Осталось еще раз использовать тот факт, что ограничение µm,n на каждое такое “прямое слагаемое” есть тождественное отображение. Это завершает построение клона. По определению, если R — операда, то F (R) — это только что построенный абстрактный клон. Легко убедить ся, что гомоморфизм операд h : R K таким же образом превращается в гомоморфизм клонов F (h) : F (R) F (K). Это завершает построение функтора F : F Set-Operads Clones. Из самого построения видно, что если UO : F Set-Operads Sets, UC : Clones Sets — забывающие функторы, то UC F = UO.

Построим обратный к F функтор G. Пусть K — абстрактный клон. Превратим соответствие [n] K(n) в контравариантный функ тор, определенный на категории F Setop, полагая для f : [n] [m] и x K(n) значение K(f )(x) = xf равным xf = [xpf (1),m... pf (n),m ].

Пусть дан еще один морфизм g : [m] [k] категории F Set. Проверим, что (xf )g = (gf )x, где gf — суперпозиция в F Set (в F Setop это будет означать (xf )g = x(f g)).

(xf )g = [[xpf (1),m... pf (n),m ]pg(1),k... pg(m),k ] = [x[pf (1),m (pg(1),k... pg(m),k )]... [pf (n),m (pg(1),k... pg(m),k )]].

Но, так как [pf (i),m (pg(1),k... pg(m),k )] = pg(f (i)),k, то последнее выраж нение есть x(gf ). Из определения клона также сразу следует 1[n] x = [xp1,n... pn,n ] = x. Это завершает проверку функториальности.

Установим некоторые необходимые для дальнейшего соотношения.

Пусть x K(m), xi K(n), 1 i m, f : [n] [k] — морфизм F Set.

Тогда [x(x1 f )... (xm f )] = [xx1... xm ]f (3.1.2) В самом деле, если p = pf (1),k... pf (n),k, то [x(x1 f )... (xm f )] = [x[x1 p]... [xm p]] = [[xx1... xm ]p] = [xx1... xm ]f.

Пусть = (n1,..., nm ) P (n, m). Определим отображения ri = ri () : [ni ] [n1 + · · · nm ] = [n], 1 i m, полагая ri (0) = 0, ri (j) = n1 + · · ·+ni1 +j при 1 j ni (подразумевается, что n0 = 0). Эти морфизмы образуют коконус, соответствующий разложению [n1 +· · · nm ] = [n1 ]...

[nm ]. Если для всех i заданы fi : [ni ] [ki ] из F Set, и = (k1,..., km ), то имеют место коммутативные диаграммы:

ri () [ni ] [n1 +... + nm ] m (3.1.3) f f j i j= ri () [ki ] [k1 +... + ki ] Определим композицию операды следующим образом:

xx1... xm = [x(x1 r1 )... (xm rm )] = [x[x1 p1,n... pn1,n ][x2 pn1 +1,n... pn1 +n2,n ]... [xm pn1 +···+nm1 +1,n... pn,n ]].

Здесь x K(m), x1 K(n1 ),..., xm K(nm ), n = n1 + · · · + nm1 + nm. Проверим сначала аксиомы F Set-операды, связанные с действием морфизмов F Set. При этом необходимо обращать внимание на то, что некоторые суперпозиции рассматриваются не в F Set, а в двойственной категории. Это издержки принятого нами определения операды.

x(x1 f1 )... (xm fm ) = [x(x1 f1 r1 ())... (x1 fm rm ())] = [x(x1 r1 ()(fi ))... (xm rm ()(fi ))] = [x(x1 r1 ())... (xm rm ())](fi ) = (xx1... xm )(f1... fm ).

Пусть теперь x K(k), xi K(ni ), 1 i m, и задан морфизм f : [k] [m] категории F Set. Положим = (n1,..., nm ), ri = ri (), и z = (x1 r1 )... (xm rm ). Тогда (xf )(x1... xm ) = [(xf )z] = [[xpf (1),m... pf (1),m ]z] = [x[pf (1),m z]... [pf (k),m z]] = [x(xf (1) rf (1) )... (xf (k) rf (k) )].

Вспоминая, что f = (nf (1),..., nf (k) ), и пользуясь легко проверяемым равенством rf (i) () = (f )ri (f ), получим следующую цепочку преоб разований:

[x(xf (1) rf (1) )... (xf (k) rf (k) )] = [x(xf (1) r1 (f )(f ))... (xf (k) rk (f )(f ))] = [x(xf (1) r1 (f ))... (xf (k) rk (f ))](f ) = (xxf (1)... xf (k) )(f ).

Кроме того, при x K(k), x1,..., xm K(n), f F Set([k], [m]) в клоне K имеет место тождество:

[(xf )x1... xm ] = [xxf (1)... xf (k) ] (3.1.4) В самом деле, [(xf )x1... xm ] = [[xpf (1),m... pf (k) ]x1... xm ] = [x[pf (1),m x1... xm ]... [pf (k),m x1... xm ]] = [xxf (1)... xf (k) ].

Единица строящейся операды — элемент = p1,1 K(1). Проверим определение. Пусть x K(n). Тогда x = [p1,1 x] = x по определению p1,1. С другой стороны, x... = [x[p1,1 p1,n ][p1,1 p2,n ]... [p1,1 pn,n ]] = [xp1,n p2,n... pn,n ] = x.

Завершая построение операды, покажем ассоциативность компози ции.

Пусть x K(m), yi K(ni ), 1 i m, z i = (zi,1... zi,ni ), zi,j K(ki,j ), 1 j ni. Положим ki = ki,1 +... + ki,ni, 1 i m, = (k1,..., km ), ri = ri () : [ki ] [k1 + · · · + km ], i = (ki,1,..., ki,ni ), ri,j = ri,j (i ) : [ki,j ] [ki ], = (n1,... nm ), ri = ri () : [ni ] [n1 + · · · + nm ], = (k1,1,..., k1,n1,..., km,1,..., km,nm ), ri,j = ri,j () : [ki,j ] [ ki j ].

i,j Легко проверяется, что ri ri,j. Будем писать ri z i вместо ri,j = (zi,1 ri,1 )... (zi,ni ri,ni ), и z вместо (z 1 r1 )... (z m rm ). Напомним также пра вило действия отображения f : [p] [q] на строку вида a = a1... aq :

af = af (1)... af (p). Мы будем применять его для сокращения записи. При этих обозначениях имеет место соотношение zri = z i ri В нижеследу ющих преобразованиях используются установленные ранее тождества, причем (3.1.4) можно записать в форме [(af )b] = [a(bf )].

x(y1 z 1 )... (ym z m ) = [x((y1 z 1 )r1 )... ((ym z m )rm )] = [x([y1 (z1,1 r1,1 )... (z1,n1 r1,n1 )]r1 )... ([ym (zm,1 rm,1 )... (zm,nm rm,nm )]rm )] = [x[y1 z1,1 (r1,1 r1 )... z1,n1 (r1,n1 r1 )]... [ym zm,1 (rm,1 rm )... zm,nm (rm,nm rm )]] = [x[y1 (z1,1 r1,1 )... (z1,n1 r1,n1 )]... [ym (zm,1 rm,1 )... (zm,nm )rm,nm ]] С другой стороны, (xy1... ym )(z 1... z m ) = [[x(y1 r1 )... (ym rm )](z 1 r1... z m (rm ] = [[x(y1 r1 )... (ym rm )]z] = [x[(y1 r1 )z]... [(ym rm )z]] = [x[y1 (zr1 )]... [ym (zrm ]] = [x[y1 (zr1 )]... [ym (zrm ]].

Таким образом, ассоциативность доказана. Построенную операду обо значим через G(K). Из приведенных выше соотношений легко следует, что для любого гомоморфизма клонов f : K H то же самое семей ство отображений {fn |n = 0, 1,... } становится гомоморфизмом операд G(K) G(H). Рассматривая его в этом качестве, обозначим его через G(f ). Таким образом, построен функтор G : Clones F Set-Operads.

Осталось проверить взаимную обратность функторов F и G, то есть взаимную обратность построенных переходов от операды к клону и от клона к операде. Пусть дана операда R с композицией xx1... xm, и пусть построен клон с суперпозицией [xx1... xm ]. Рассмотрим опера ду, строящуюся по этому клону так, как это было сделано выше. Преж де всего необходимо убедиться, что для любого морфизма из F Set ви да f : [n] [m] и любого x R(n) имеет место равенство f x = [xpf (1),m... pf (n),m ]. В самом деле, [xpf (1),m... pf (n),m ] = (x(pm(1) )... (pm(n) ))µm,n = f f (x... )(pm(1) · · · pm(n) )µm,n.

f f Следовательно (после перехода из F Setop в F Set), вопрос сводится к тождеству µm,n (pm(1)... pm(n) ) = 1[n], f f которое непосредственно вытекает из определений. Таким образом, обе операды, исходная и построенная по клону, совпадают как функторы.

Установим совпадение композиций. Пусть x R(m), = (n1,..., nm ), n = n1 + · · · + nm, ri = ri () : [ni ] [n], xi R(ni ), 1 i m. Тогда [x(x1 r1 )... (xm rm )] = (xx1... xm )(r1... rm )µm,n.

Необходимое нам равенство следует из легко проверяемого тождества µm,n (r1... rm ) = 1[n].

Обратно, пусть дан клон K с суперпозицией [xx1... xm ]. Построим, как было сделано выше, операду с композицией xx1... xm, и по ней — новую суперпозицию. Убедимся, что она совпадает с исходной. Пусть x K(m), xi K(n), 1 i m, = (nm ), ri = ri () : [n] [nm], 1 i m.

Тогда, используя (3.1.2), получим (xx1... xm )µm,n = [x(x1 r1 )... (xm rm )]µm,n = [x(x1 r1 µm,n )... (xm rm µm,n )].

Остается несложная проверка того, что (в F Set) µm,n ri = 1[n] для всех i. Очевидно также, что элементы pi,n одни и те же и в исходном клоне, и в построенном по операде.

Пусть R — операда над вербальной категорией W, и пусть A — некоторая R-алгебра. Рассматривая ограничение операций композиции R(n) An A на элементы r R(n), получаем интерпретацию этих элементов как n-арных операций на R-алгебрах. Положим n = R(n) для каждого n 0, и будем рассматривать семейство = {n |n 0} как множество символов n-арных операций, т.е. сигнатуру. Тогда Alg(R) естественным образом можно рассматривать как многообразие -алгебр, задаваемое всеми тождествами из определения алгебры над операдой.

Для произвольной сигнатуры обозначим через Alg() категорию всех -алгебр и их гомоморфизмов.

Напомним также определение “обычной” рациональной эквивалент ности многообразий (мы используем одну из эквивалентных форм этого определения, содержащуюся в [47, Определение 1.2.1 д), с. 26]). Мы при водим это определение сразу в виде, пригодном для многосортных алгебр.

Все определения и результаты из [47, глава 1], относящиеся к рациональ ной эквивалентности, почти дословно переносятся на случай произволь ного множества сортов.

Итак, пусть M1 и M2 — два многообразия алгебр с различными, вообще говоря, сигнатурами, но с одним и тем же классом сортов S.

Эти многообразия называются рационально эквивалентными, если су ществуют функторы F : M1 M2, G : M2 M1, обладающие сле дующими свойствами. Во-первых, F G = IdM2 (тождественный функтор категории M2 ), и GF = IdM1. Во-вторых, если Ui : Mi SetS — ес тественным образом определяемые забывающие функторы (i = 1, 2), то U2 F = U1, U1 G = U2. Напомним, что SetS есть категория всех функторов из дискретной категории S в категорию множеств, т.е. по-сути категория семейств множеств, индексированных элементами S с “покомпонентно” определяемыми морфизмамии.

Другие эквивалентные условия рациональной эквивалентности можно найти в [47, Теорема 1.2.1, с. 27].

Теорема 3.1.2. Пусть R — операда над вербальной категорией W, и для каждого n 0 задано подмножество n R(n). Допустим, что семейство = {n |n 0} порождает R как W -операду. Тогда мож но определить рациональную эквивалентность между многообразием Alg(R) (многообразием в описанном выше смысле) и некоторым много образем -алгебр, которое естественным образом задается выбором семейства (сигнатуры).

Доказательство. Отображения композиции R(n)An A огра ничиваются до n An A, что дает унивалентный функтор из Alg(R) в Alg(). Ввиду того, что порождает R, этот функтор будет также и полным. Образ Alg(R) в Alg(), очевидно, замкнут относительно пря мых произведений. Из условия, что порождает R, легко выводится, что -подалгебры R-алгебр, превращенных таким способом в -алгебры, также будут и R-подалгебрами. Применяя это к конгруэнциям, полу чаем замкнутость относительно гомоморфных образов. Таким образом, имеет место полный и унивалентный функтор, образ которого — под многообразие Alg(). Остальное очевидно.

Заметим, что при выборе различных семейств образующих в од ной и той же операде R будут получаться различные, но рационально эквивалентные многообразия, изоморфные категории Alg(R).

Напомним определение алгебр над клоном K (см., например, [43, Определение 3.1, с. 85-86].

Алгеброй над абстрактным клоном K называется множество B, снабженное семейством операций K(n) B n B, (x, y1,..., yn ) [xy1... yn ] = [xy], (x K(n), y1,..., yn B ), определенных для каждого n 0, и облада ющих следующими свойствами.

1) [[xx1... xm ]y] = [x[x1 y]... [xk y]] для всех возможных x K(m), xi K(n), y B n. Здесь, как и выше, через [xx1... xm ] обозначается результат действия операции K(m) K(n)m K(n) в клоне K.

2) [pi,n y1... yn ] = yi для всех n i 0, y1,..., yn B.

Гомоморфизм алгебр над клоном K определяется точно так же, как и для алгебр над операдами. Категорию (многообразие) алгебр над кло ном K будем обозначать через Alg(K).

Теорема 3.1.3. Пусть K — абстрактный клон, R — F Set-операда, соответствующая клону K при построенной в теореме 3.1.1 ра циональной эквивалентности. Тогда многообразия алгебр Alg(K) и Alg(RF Set ) рационально эквивалентны.

Доказательство. Построим два функтора, F : Alg(RF Set ) Alg(K), и G : Alg(K) Alg(RF Set ), взаимно обратные и коммутирующие с забывающими функторами.

Пусть A — алгебра над операдой R. Полагаем множество F (A) равным множеству A, и определим на этом множестве структуру алгеб ры над K. Пусть x K(m) = R(m), a1,..., am F (A) = A. Тогда положим по определению [xa1... am ] = xa1... am. Это означает, что ком позиция в F (A) как в алгебре над клоном K совпадает с композицией в A как в алгебре над операдой R.

Проверим, что F (A) действительно становится алгеброй над кло ном. Сначала рассмотрим элемент [pm,i a1... am ] = (pm )a1... am. По i свойству алгебр над F Set-операдами, (pm )a1... am = ()apm (1) = ai = ai.

i i Далее, [[xy1... ym ]a1... an ] = [xy1... ym ]a1... an = ((xy1... ym )µm,n )a1... an.

Напомним, что используется свойство: (f )c1... cl = cf (1)... cf (k).

В нашем случае f = µm,n, и применение такого f к a = a1... an дает строку a... a ( a повторяется m раз). В результате получаем выражение (xy1... ym )a... a, которое, согласно свойству ассоциативности для алгебр над операдами, равно x(y1 a)... (ym a) = [x[y1 a]... [ym a]], что и было нуж но показать. Таким образом, на множестве F (A) определена структура алгебры над клоном K. Очевидно, что гомоморфизмы из R-алгебры A1 в R-алгебру A2, и гомоморфизмы из алгебры F (A1 ) над клоном K в алгеб ру F (A2 ) — это одни и те же отображения. Следовательно, F является функтором, к тому же коммутирующим со стирающими функторами.

Обратно, пусть дана алгебра A над клоном K. Определим ал гебру G(A) над операдой R, совпадающую как множество c A, сле дующим образом: если a1,..., am G(A), x R(m) = K(m), то xa1... am = [xa1... am ]. Проверим свойства алгебры над операдой. Свой ство единицы очевидно: a = [p1,1 a] = a. Пусть x R(m), xi R(ni ), ai = ai,1... ai,ni Ani, 1 i m, n = n1 + · · · + nm. Положим yi = [xi pn1 +···+ni1 +1,n... pn1 +···+ni1 +ni,n ]. Тогда (xy1... ym )a1... am = [[xy1... ym ]a1... am ] = [[xy1... ym ]a1... am ] В свою очередь, [yi a1... am ] = [[xi pn1 +···+pni1 +1,n... pn1 +···+pni1 +ni,n ]a1... am ] = [xi [pn1 +···+pni1 +1,n a1... am ]... [pn1 +···+pni1 +ni,n a1... am ]].

Очевидно, что для 1 i m, 1 j ni имеет место равенство [pn1 +···+pni1 +j,n a1... am ] = ai,j.

В результате, [yi a1... am ] = [xi ai,1... ai,ni ] = xi ai,1... ai,ni = xi ai.

Отсюда немедленно следует, что (xx1... xm )a1... am = x(x1 a1 )... (xam ).

Наконец, пусть f : [k] [m] — морфизм из F Set, x R(k), a1,..., am G(A) = A. Рассмотрим элемент (xf )a1... am = (xf )a = [xpf (1),m... pf (k),m ]a = [[xpf (1),m... pf (1),m ]a] = [x[pf (1),m a]... [pf (k),m a]].

Ввиду того, что [pf (j),m a] = [pf (j),m a1... am ] = af (j), в результате получим [xaf (1)... af (k) ], то есть xaf (1)... af (k), что и было нужно.

Снова очевидно, что гомоморфизмы алгебр над клоном K и гомо морфизмы соответствующих алгебр над операдой R — это одни и те же отображения. Доказательство заверщается легкой проверкой взаимной обратности функторов F и G. Их перестановочность с забывающими функторами очевидна из построения.

§ 3.2. Свободные алгебры над операдами Определение 3.2.1. Пусть W — вербальная категория. Рассмот рим ковариантный функтор G из категории W op в категорию множеств.

Будем писать G(n) вместо G([n]), [n] Ob(W ), и f x вместо G(f )(x), где f W op ([m], [n]) = W ([n], [m]), x G(n). Градуированной W полугруппой будем называть такой функтор, обладающий следующими дополнительными свойствами:

1) для любых [n], [m] Ob(W ) определены операции G(n)G(m) G(n+m), (x, y) x·y, такие, что x·(y ·z) = (x·y)·z для всех возможных x G(n), y G(m), z G(k);

2) если даны f W op ([n ], [n]), g W op ([m ], [m]), то (f x) · (gy) = (f g)(x · y);

(заметим, что здесь использовано произведение в W op, соответствующее копроизведению в W );

3) если даны g1 G(n1 ),..., gm G(nm ), и = (n1,..., nm ) — разбиение, то для любого f W op (m, k) имеет место равенство (f )(g1 ·... · gm ) = gf (1) ·... · gf (k).

Определим также гомоморфизм h : G1 G2 градуированных W полугрупп как естественное преобразование функторов (семейство ото бражений hn : G1 (n) G2 (n)), такое, что для всех x G(n), y G(m) имеет место равенство hn+m (x · y) = hn (x) · hm (y). Категорию градуированных W -полугрупп и их гомоморфизмов будем обозначать через GrW.

Пример 3.2.1. Зафиксируем множество X. Тогда соответствие [n] X n есть градуированная F Set-полугруппа в смысле только что данного определения. Функтор [n] X n как контравариантный функ тор на F Set действует следующим образом. Если дано отображение f : [n] [m], то отображение X f : X m X n сопоставляет стро ке x = (x1,..., xm ) X m строку xf = (xf (1),..., xf (n) ). Превращая этот функтор в ковариантный функтор из W op, будем записывать ре зультат рассмотренного только что отображения как f x. Умножение X n X m X n+m — это приписывание строк друг к другу. Все свойст ва из определения градуированной F Set-полугруппы проверяются непо средственно. Компоненты градуированной F Set-полугруппы, построен ной в этом примере, будем обозначать через T n (X), имея в виду аналогию с тензорными степенями модуля. Таким образом, T n (X) = X n. Вся гра дуированная полугруппа обозначается через T (X).

Пример 3.2.2. Пусть W =. Тогда определению градуированной -полугруппы удовлетворяют биоперады [54, с. 25].

Теорема 3.2.1. Пусть R — некоторая W -операда, G — градуирован ная W -полугруппа.

1) Рассмотрим множество RG = R(n) G(n). На нем естес n= твенным образом можно определить структуру алгебры над R как не симметрической операдой (в нашей терминологии — W Id-перадой).

2) Рассмотрим конгруэнцию в алгебре RG, порожденную всеми эквивалентностями вида (f x, g) (x, f g), где f W (n, m), x R(n), g G(m). Тогда факторалгебра RW G = RG/ обладает естественной структурой алгебры над W -операдой R.

3) При этом соответствие G RW G становится функтором из категории GrW в категорию Alg(RW ).

Доказательство. Все сводится к простым проверкам. Опишем чуть подробнее только способ задания структуры алгебры на RG. Зада ние отображений композиции вида R(m) (RG)m RG сводится к определению всевозможных отображений вида R(m)(R(n1 )G(n1 ))···(R(nm )G(nm ))R(n1 +···+nm )G(n1 +···+nm ) С точностью до очевидной перестановки сомножителей это равносильно заданию отображения из (R(m) R(n1 ) · · · R(nm )) (G(n1 )) · · · G(nm )) в R(n1 + · · · + nm ) G(n1 + · · · + nm ).

Искомое отображение определяется как произведение двух извест ных: отображения композиции в операде R R(m) R(n1 )... R(nm ) R(n1 + · · · + nm ), и умножения в градуированной W -полугруппе G(n1 ) · · · G(nm ) G(n1 + · · · + nm ).

Можно представлять себе элементы RG в виде ri gi, где ri R(ni ), gi G(ni ), 1 i m (точнее, ri gi — это сокращенное обозначение для пары (ri, gi )). Если r R(m), то r(r1 g1 )... (rm gm ) = (rr1... rm )(x1... xm ).

С помощью этого явного выражения для композиции легко проверяются все свойства алгебры над операдой. Константы RG — это подмножество R(0) X 0, которое естественным образом можно отождествить с R(0).

Замечание 3.2.1. Описанная в этой теореме конструкция алгеб ры RW G есть не что иное, как тензорное произведение функторов R и G в смысле [28], [132], [148, Chapter VII,§ 2]. В нашей работе используется упрощенная запись: RG (или RW G) вместо R G (или R W G), ввиду того, что рассматривается достаточно специфический частный случай.

Впрочем, “частность” этого случая относительна: ниже будет показа но, что, например, все свободные алгебры в многообразиях вида Alg(R) получаются именно таким способом.

Теорема 3.2.2. Пусть R — некоторая W -операда, X — множество.

Тогда RW T (X) есть свободная алгебра с базисом X в многообразии Alg(RW ).

Доказательство. Вместо RW T (X) будем всюду писать RW X.

Для -операд результат хорошо известен. Покажем, как устанавлива ется универсальное свойство в общем случае. Базисное множество X отображается в RW X следующим образом: берется композиция отобра жений X R(1) X RX RW X. Здесь левая стрелка отображает элемент x X в пару (, x), где R(1) — единица операды R. Правая стрелка RX RW X — проекция на факторалгебру.Если теперь задано отображение X A в R-алгебру A, то рассматриваются его степе ни X n An, затем произведение с тождественным отображением R(n), то есть R(n) X n R(n) An. По совокупности таких отображений строится отображение R(n) X R(n) An n RX = n=0 n= Совокупность операций композиции для алгебры A над операдой R позволяет построить отображение R(n) An A. Суперпозиция n= двух построенных отображений дает отображение RX A, кото рое, как легко проверить, является гомоморфизмом алгебр над R как W Id-операдой (ввиду того, что W Id W для любой вербальной ка тегории W, алгебры над W -операдой можно считать алгебрами и над W Id-операдой, т.е. несимметрической операдой в традиционной тер минологии). Но ввиду того, что для алгебры A выполнено тождество (f )a1... al = af (1)... af (k) из определения R-алгебры, в ядре гомо морфизма RX A содержится конгруэнция, по которой факторизует ся RX при построении RW X. Таким образом получается гомоморфизм RW X A со всеми необходимыми свойствами. Единственность следует, как обычно, из того, что образ X в RW X порождает всю эту алгебру.

В дальнейшем свободную алгебру с базисом X в многообразии Alg(RW ) мы чаще всего будем обозначать через F rR,W (X).

Напомним еще некоторые общие факты о тождествах и свободных алгебрах в произвольных -алгебрах. Они потребуются нам в § 3.5.

Для произвольной A Alg() положим A (X) = {(t1, t2 )|t1, t2 F r (X), h(t1 ) = h(t2 ) для любого гомомор физма h : F r (X) A}.

Это — конгруэнция на F r (X), то есть -подалгебра алгебры F r (X) F r (X), являющаяся отношением эквивалентности. Конгруэн ция A (X) вполне инвариантна, то есть если h : F r (X) F r (X) — какой угодно эндоморфизм, и (t1, t2 ) A (X), то (h(t1 ), h(t2 )) A (X).

Более того, если h есть гомоморфизм из F r (X) в F r (X), и (t1, t2 ) A (X), то (h(t1 ), h(t2 )) A (Y ). Элементы A (X) естественно назвать тождествами A в алфавите X. Обратно, пусть дано некоторое семей ство пар элементов (z1,i, z2,i ) F r (Xi ) F r (Xi ), i I. Определим V ar() как полную подкатегорию категории Alg(), объекты которой — все те алгебры, для которых элементы множества являются тождества ми. Нам будет удобно принять такое определение многообразия -алгебр:

это непустая полная подкатегория категории Alg(), замкнутая относи тельно взятия подалгебр, гомоморфных образов, и произвольных прямых произведений. Непустая полная подкатегорию M категории Alg() яв ляется многообразием -алгебр тогда и только тогда, если M = V ar() для некоторого (теорема Биркгофа). Положим M (X) = A (X).

AM Это — вполне инвариантная конгруэнция на свободной алгебре F r (X).

Соответствие X M (X) является функтором, и, более того, для каж дого гомоморфизма h из F r (X) в F r (X), если (t1, t2 ) M (X), то (h(t1 ), h(t2 )) M (Y ).

Свободная алгебра F rM (X) многообразия M с базисом X — это факторалгебра F r (X)/M (X). Каждое многообразие можно предста вить в виде V ar() для некоторого F r (X) F rZ, (X), причем множество X можно выбрать счетным. Для такого X задание F rM (X) (или, соответственно, M (X)) полностью определяет многообразие M.

§ 3.3. Многообразия многосортных алгебр и F Set-мультикатегории Сформулируем минимально необходимый набор понятий и обозна чений из теории многосортных (или многоосновных) универсальных ал гебр. Само понятие многосортных алгебр появилось в [128]. Из книг на русском языке, в которых имеется информация по данной теме, можно выделить [48], [26], [95], [16], [46, глава VI, § 1, с. 314].

Категория S -множеств (или многосортных множеств с множест вом или классом сортов S ), обозначаемая через SetS, имеет своими объектами семейства множеств A = {As |s S}. Морфизмы из A в B = {Bs |s S} суть семейства f = {fs |s S}, где fs — отображе ние из As в Bs для каждого s S. Далее отображениями будут иногда называться сами такие морфизмы f. Суперпозиции морфизмов опреде ляются покомпонентно.

Семейство (или класс) множеств = {s,t |s S, t S} будет называться сигнатурой. -алгебра — это S -множество A = {As |s S} вместе с семейством операций композиции вида s,t As1 · · ·Asn At, определенных для всех s = s1... sn S и t S (при n = 0 это отображения e,t At, причем образы в At элементов из e,t назы ваются константами сорта t), действие которых будет обозначаться так:

(, a1,..., an ) a1... an = a, где a = a1... an и ai Asi для всех i. Гомоморфизм h из -алгебры A в -алгебру B — это отображе ние (морфизм) S -множеств, переводящее константы A в одноименные константы B, а для всех n 0 должны выполняться обычные соотно шения: ht (a1... an ) = hs1 (a1 )... hsn (an ), где индексы у компонент h обычно определяются из контекста и не пишутся. Категорию -алгебр и их гомоморфизмов обозначим через Alg().

Многообразием -алгебр будем называть полную подкатегорию ка тегории Alg() c непустым классом объектов, замкнутую относительно взятия подалгебр, гомоморфных образов и прямых произведений. В от личие от традиционного определения мы сразу рассматриваем много образие как категорию, и за основу определения берется формулировка теоремы Биркгофа.

Лемма 3.3.1. Пусть R — мультикатегория над некоторой вербаль ной категорией. Тогда категория Alg(RW ) есть многообразие алгебр, где сигнатура определяется следующим образом: s,t = R(s, t) для всех s и t.

Доказательство. Очевидно.

Пусть M — некоторое многообразие -алгебр. Свободная алгебра этого многообразия с базисом X = {Xs |s S} Ob(SetS ) будет обозна чаться через F rM (X). Вместе с базисом предполагается заданным ото бражение S -множеств = X : X F rM (X), обладающее известным универсальным свойством: для любой алгебры A из M и произвольного отображения S -множеств : X A должен существовать один и только один гомоморфизм -алгебр h : F rM (X) A такой, что h =.

Доказательство следующей леммы аналогично доказательству тео ремы 3.2.2. В формулировке используются обозначения следующего типа.

Если A1,..., An — некоторые множества, ai Ai для всех i, то вместо (a1,..., an ) A1 · · · An пишется a = a1... an.

Лемма 3.3.2. Пусть R — мультикатегория над вербальной катего рией W, и пусть X = {Xs |s S} — некоторое S - множество. Сво бодная алгебра F rR (X) в многообразии Alg(RW ) устроена следующим образом. Для каждого t S рассмотрим множество R(s1... sn, t) Xs1 · · · Xsn.

Ft = s1,...,sn S Семейство F = {Ft |t S} обладает структурой алгебры над R как Id мультикатегорией. Эта структура такова. Если R(u1... um, t), wi Fui, 1 i m, wi = i xi, где i R(si, ui ), si = si,1... si,ni, xi = xi,1... xi,ni, xi,j Xsi,j, то w1... wm = (1... m )x1... xm.

Алгебра строится как факторалгебра по F rR (RW ) F конгруэнции, порожденной всеми парами элементов вида ((f )x1... xm, xf (1)... xf (k) ), где f : sf (1)... sf (k) s1... sm — мор физм категории WS, представленный отображением f : [k] [m], S = Ob(R), R(sf (1)... sf (k) ), xi Xsi.

Отображение S -множеств : X F rR (X) строится так: если x Xs, то s (x) = 1s x. Точнее, 1s x R(s, s) Xs Fs, и под s (x) подразумевается образ 1s x в факторалгебре.

Напомним, что в категории F Set для любой пары объектов [n] = {0, 1,..., n} и [m] существует прямое произведение [n] [m] = [nm]. Нам потребуется явный вид одной из проекций 1 : [nm] [n]. Эта проекция, которую мы обозначили как µm,n, действует по правилу: µm,n (i + n(j 1)) = i, где 1 i n, 1 j m.

Отображение µm,n представляет морфизм sm s (для любой стро ки s = s1... sn ). В частности, sµm,n = sm.

Для каждой строки s = s1... sn S определим S -множество X(s), объединение компонент которого есть {xs1,1,..., xsn,n }, причем xsi,i име ет сорт si. Иными словами, для каждого t S имеет место равенство X(s)t = {xsi,i |si = t}. Соответствие s X(s) есть ковариантный функ тор из категории F SetS в категорию SetS, действующий на морфизмах следующим образом. Если s = s1... sm, и дан морфизм f : sf s, представленный отображением f : [k] [m], то соответствующий ему морфизм S -множеств X(f ) : X(sf ) X(s) переводит элементы xsf (i),i в xsf (i),f (i) (1 i k ).

Теорема 3.3.1. Пусть R — W -мультикатегория, причем в число мор физмов W входят все µn,m, и пусть S = Ob(R). Рассмотрим произ вольную строку s = s1... sn S. Семейство {R(s, t)|t S} есть R алгебра, которая будет обозначаться через R(s) (так что R(s)t = R(s, t)). Если W = F Set, то эта алгебра является свободной алгеброй с базисом X(s) в Alg(RF Set ).

Доказательство. Структура R-алгебры на R(s) определяется с помощью семейства отображений — суперпозиций µ R(u1... um, t) R(s)u1 · · · R(s)um R(sm, t) R(s)t (3.3.1) m,n Здесь левое отображение есть композиция в мультикатегории R:

R(u1... um, t) R(s, u1 ) · · · R(s, um ) R(sm, t), (, r1,..., rm ) r1... rm Правое отображение существует по определению R: для каждого t S op соответствие v R(v, t) есть контравариантный функтор из WS в ка тегорию множеств. Напомним, что для морфизма категории F SetS, пред ставленного отображением f (и соответствующего морфизма двойствен op ной категории WS ) вместо R(f, t) используется запись f, а действие этого отображения записывается так: r rf. Таким образом, результат действия (3.3.1) будет записываться в виде:

(, r1,..., rm ) [r1... rm ] = (r1... rm )µm,n.

Необходимо помнить, что в выражении справа µm,n означает морфизм из op WS.

Проверим свойства из определения алгебры над мультикатегорией.

Пусть r R(s)t = R(s, t). Тогда [1t r] = (1t r)µ1,n. Здесь 1t r = r соглас но свойству единичных мультистрелок, а µ1,n = id по определению µ.

Проверим ассоциативность композиции (3.3.1). Пусть R(u1... um, t), и i R(v i, ui ) для 1 i m. Если v i = vi,1... vi,ki, то пусть ri,j R(s)vi,j для всех i и j, 1 j ki, и ri = ri,1... ri,ki. Положим также k = k1 + · · · + km. Далее, [(1... m )r1 · · · rm ] = ((1... m )r1 · · · rm )µk,n.

Круглые скобки означают композицию в R. С другой стороны, [[1 r1 ]... [m rm ]] = [((1 r1 )µk1,n )... ((m rm )µkm,n )] = (((1... m )r1 · · · rm )(µk1,n · · · µkm,n ))µm,n.

Сопоставляя левую и правую части предполагаемого равенства (т.е. [(1... m )r1 · · · rm ] = [[1 r1 ]... [m rm ]]), приходим к выводу, что оно будет доказано, как только будет установлено равенство морфизмов op (µk1,n · · · µkm,n )µm,n = µk,n в категории WS, или же равенство в кате гории WS :

µm,n (µk1,n · · · µkm,n ) = µk,n (3.3.2) Тождества такого вида доказываются в F SetS значительно проще, чем в F Set. И левая, и правая части доказываемого равенства есть морфиз мы из sk в s. Выберем класс S и строку s = s1... sn S так, чтобы все символы si были попарно различны. Тогда для любого w S может существовать самое большее один морфизм w s, причем представляю щий его морфизм F Set определен однозначно. Отсюда следует равенство (3.3.2) для F SetS с выбранными S и s, а также и для F Set. Из выпол нимости (3.3.2) для F Set следует его выполнимость для произвольных S и s.

Пусть теперь f : [l] [m] — морфизм W, u = u1... um и R(uf, t). Тогда f R(u, t). Пусть ri R(s)ui, 1 i m. Тогда [(f )r1... rm ] = ((f )r1... rm )µm,n = ((rf (1)... rf (l) )f )µm,n, (... ) где = us...usm. Равенство с [rf (1)... rf (l) ] получится при условии, что имеет место тождество в F SetS : µl,n = µm,n (f ). И левая, и правая части этого соотношения есть морфизмы из sl в s, и далее можно рассуждать так же, как и при доказательстве (3.3.2).

Итак, R(s) обладает структурой R-алгебры. Покажем, что если W = F Set, то это свободная алгебра с базисом X(s). Прежде всего, построим отображение S -множеств : X(s) R(s).

Пусть pn : [1] [n] — морфизмы в категории F Set такие, что i pn (1) = i, 1 i n. Для каждого i морфизм pn определяет ото i i бражение R(si, si ) R(s, si ), сопоставляющее R(si, si ) элемент pn R(s, si ) = R(s)si. Положим si (xsi,i ) = 1si pn. Далее нам потребу i i ется тождество в WS : µn,n (pn · · · pn ) = 1[n]. Оно доказывается легко 1 n (и использовалось уже в § 3.1). Теперь пусть r R(s)t = R(s, t). Тогда имеет место тождество:

r = [rs1 (xs1,1 )... sn (xsn,n )] (3.3.3) Доказательство таково:

в категории WS r = r1[n] = (r1s1... 1sn )(µn,n (pn · · · pn )) = 1 n op в категории WS (r1s1... 1sn )((pn · · · pn )µn,n ) = 1 n ((r1s1... 1sn )(pn · · · pn ))µn,n = 1 n (r(1s1 pn )... (1sn pn ))µn,n = [rs1 (xs1,1 )... sn (xsn,n )].

1 n Предположим, что дано отображение S -множеств : X(s) A, где A — некоторая R-алгебра, и пусть ai = si (xsi,i ). Если существует гомоморфизм R-алгебр h : R(s) A со свойством h =, из (3.3.3) следует, что для каждого r R(s)t = R(s, t) имеет место равенство:

ht (r) = ra1... an, и это означает, что если h существует, то определен однозначно.

Доказательство свободности завершается следующим образом.

Пусть дано отображение : X(s) A, и ai = si (xsi,i ). Определим h первоначально как морфизм S -множеств по уже найденной формуле:

ht (r) = ra1... an. Очевидно, что h =. Остается проверить, что h — гомоморфизм R-алгебр. Положим a = a1... an, u = u1... um, R(u, t), ri R(s)ui, 1 i m. Проделаем следующие выкладки:

h([r1... rm ]) = [r1... rm ]a = ((r1... rm )µn,m )a = m (r1... rm ) a... a = (r1 a)... (rm a) = h(r1 )... h(rm ).

Теорема 3.3.2. Пусть M — некоторое многообразие многосортных -алгебр, и S — класс его сортов. Положим R(s, t) = F rM (X(s))t для каждого s S и t S. Тогда на семействе R = {R(s, t)|s S, t S} определена структура F Set-мультикатегории.

Доказательство. Будем писать F r вместо F rM, так что R(s, t) = F r(X(s))t, где s = s1... sm. Пусть r R(s, t), wi R(ui, si ), 1 i m, ui = ui,1... ui,ni, u = u1... um. Построим отображения компо зиции:

R(s, t) R(u1, s1 ) · · · R(um, sm ) R(u, t), (r, w1,..., wm ) rw1... wm.

Пусть w = w1... wm, так что rw1... wm = rw. Положим rw равным hw (r), где hw есть гомоморфизм из -алгебры F r(X(s)) в -алгебру F r(X(u)), который определяется следующим образом. Сначала опреде лим отображения S -множеств pui : X(ui ) X(u), которое переводит u элемент xui,j,k в элемент xui,j,n1 +···+ni1 +k. Фактически pui = X(p ), где u i = (n1,..., nm ), и отображение p : [ni ] [n1 + · · · + nm ] переводит i элемент k (1 k ni ) в n1 + · · · + ni1 + k.

Тем же символом pui обозначим единственный гомоморфизм u алгебр из F r(X(ui )) в F r(X(u)), делающий коммутативной диаграмму:

F r(X(ui )) F r(X(u)) ui u p ui u X(ui ) X(u) В этой диаграмме через v обозначено отображение базиса X(v) в соот ветствующую свободную алгебру F r(X(v)). Далее из контекста всегда будет видно, в каком смысле употребляется pui.

u Теперь полагаем hw (xsi,i ) = pui (wi ) (3.3.4) u (Более формально: hw (s (xsi,i )) = pui (wi ).) Проверим ассоциативность.

u Пусть для всех i, j, 1 i m, 1 j ni заданы строки v i,j S, и элементы ri,j R(v i,j, ui,j ). Положим v i = v i,1... v i,ni, v = v 1... v m, ri = ri,1... ri,ni. Необходимо убедиться, что имеет место равенство:

(rw1... wm )r1... rm = r(w1 r1 )... (wm rm ) (3.3.5) Его левая часть, согласно (3.3.4), равна hr1...rm (hw1...wm (r)), а правая равна h(w1 r1 )...(wm rm ) (r). Отсюда следует, что (3.3.5) эквивалентно равенству:

hr1...rm hw1...wm = h(w1 r1 )...(wm rm ) (3.3.6) Левая и правая части (3.3.6) — гомоморфизмы из F r(X(s)) в F r(X(v)), поэтому для доказательства (3.3.6) достаточно установить, что зна чения обеих частей совпадают на всех xsi,i X(s). С одной сторо ны, hr1...rm (hw1...wm (xsi,i )) = hr1...rm (pui (wi )). Далее, h(w1 r1 )...(wm rm ) (xsi,i ) = u pvi (wi ri ) = pvi (hri (wi )). Это означает, что (3.3.6) эквивалентно тождест v v ву:

hr1...rm pui = pvi hri (3.3.7) u v Достаточно проверить совпадение значений левой и правой частей (3.3.7) на xui,j,k X(ui ). Так как hr1...rm (pui (xui,j,k )) = pvi,j (ri,j ), а pvi (hri (xui,j,k )) = u v v pvi (pvii,j (ri,j )), равенство (3.3.7) эквивалентно равенству гомоморфизмов v v -алгебр:

pvi,j = pvi pvii,j (3.3.8) v vv Рассмотрим следующую коммутативную диаграмму:

v pvi pvi v F r(X(v i,j )) F r(X(v i )) F r(X(v)) i,j vi,j vi v v pvi pvi v i,j X(v i,j ) X(v i ) X(v) Суперпозиция гомоморфизмов верхней строки есть правая часть (3.3.8).

Из универсальных свойств отображений следует, что равенство (3.3.7) для гомоморфизмов алгебр следует из равенства pvi,j = pvi pvii,j отобра v vv жений из X(v i,j ) в X(v), правая часть которого есть суперпозиция ото бражений нижней строки диаграммы. Это равенство легко проверить, используя определения входящих в него отображений.

Определим единицы мультикатегории R. Пусть s S, X(s) = {xs }, s : {xs } F r(X(s))s = R(s, s) — отображение базиса в свободную алгебру. Положим 1s = s (xs ), и проверим свойства единиц из определе ния. Если r R(s1... sm, t), то r1s1... 1sm = h1s1...1sm (r), и достаточно убе диться, что h1s1...1sm : F r(X(s1... sm )) F r(X(s1... sm )) есть тождест венное отображение. Это будет следовать из равенства h1s1...1sm s = s (где s = s1... sm ), которое устанавливается следующим вычислением:

h1s1...1sm (s (xsi,i )) = psi (si (xsi )) = s (psi (xsi )) = s (xsi,i ).

s s С другой стороны, пусть w R(u, s) = F r(X(u))s. Тогда 1s w = hw (1s ) = hw (s (xs )), где hw : F r(X(s)) F r(X(u)). При этом hw (s (xs )) = pu (w). Но pu, как легко убедиться, является тождествен u u ным отображением.

Покажем, что для каждого t S соответствие s R(s, t) мож op но продолжить до структуры контравариантного функтора из WS в категорию множеств. Прежде всего, контравариантным функтором из op WS в SetS можно считать определенный выше функтор s X(s).

Рассмотрим суперпозицию этого контравариантного функтора с кова риантным функтором X(s) F r(X(s)). Действие этого функтора на морфизм f : sf s обозначим через hf. Таким образом, hf однозначно определяется из коммутативности диаграммы:

hf F r(X(sf )) F r(X(s)) sf s X(f ) X(sf ) X(s) Если теперь w R(sf, t), и f имеет тот же смысл, что и выше, положим wf = hf (w). Неформально говоря, если представлять себе w как своего рода моном w = w(xsf (1),1,..., xsf (k),k ) от переменных из X(sf ), то wf есть моном w(xsf (1),f (1),..., xsf (k),f (k) ) от переменных из X(s) = {xs1,1,... xsm,m }.

Таким образом, требуемый функтор — суперпозиция:

s X(s) F r(X(s)) F r(X(s))t = R(s, t).

Проверим два оставшихся свойства из определения 1.2. Пусть r R(s, t), s = s1... sm, fi : ui = v i f vi — морфизмы из F SetS, представ ленные отображениями fi : [li ] [ni ] (так что длина v i равна ni ), wi R(v i f, si ), 1 i m. Положим f = f1 · · · fm, w = w1... wm, wf = (w1 f1 )... (wm fm ), v = v 1... v m и vf = (v 1 f1 )... (v m fm ). Тогда r(w1 f1 )... (wm fm ) = hwf (r), (w1... wm )(f1 · · · fm ) = hf (rw1... wm ) = hf (hw (r)), и первое из требуемых равенств равносильно соотношению hwf = hf hw. Левая и правая части этого предполагаемого равенст ва — гомоморфизмы из F r(X(s)) в F r(X(v)), так что достаточно показать, что для каждого i, 1 i m, имеет место равенство hwf (s (xsi,i )) = hf (hw (s (xsi,i ))). Но так как hwf (s (xsi,i )) = pvi (hfi (wi )), v а hf (hw (s (xsi,i ))) = hf (pvffi (wi )), то все сводится к доказательству (для vi всех i) тождеств hf pvffi = pvi hfi. Здесь и слева и справа стоят гомо v vi морфизмы -алгебр из F r(X(v i fi )) в F r(X(v)), и поэтому достаточно доказать совпадение суперпозиций левой и правой частей с vi fi. Вспо миная соглашение о зависимости смысла обозначения pvffi от контекста, vi получаем hf pvffi vi fi = hf vf pvffi = v X(f )pvffi, где последнее выраже vi vi vi ние pvffi означает отображение из X(v i fi ) в X(vf ). С другой стороны, vi pvi hfi vi fi = pvi vi X(fi ) = v pvi X(fi ). Все получится, если установить v v v равенство: X(f )pvffi = pvi X(fi ). Отображения, входящее в это пред v vi полагаемое равенство, имеют своей областью определения множество X(v i fi ), а областью значений — множество X(v). Далее, вспоминаем, что pvi = X(p ), где = (n1,..., nm ), и отображение p : [ni ] [n1 +· · ·+nm ] v i i переводит элемент k (1 k ni ) в n1 + · · · + ni1 + k, и аналогично pvffi = X(p ), где = (l1..., lm ), и p : [li ] [l1 + · · · + lm ]. Соответствие i i vi u X(u) есть ковариантный функтор на WS, так что соотношение X(f )X(p ) = X(p )X(fi ) следует из тождества (f1 · · · fm )p = p fi в i i i i F Set, проверка которого выполняется без труда.

Покажем, наконец, что (rf )w1... wm = (rwf (1)... wf (m) )(f ). Здесь морфизм f : sf s представлен отображением f : [k] [m], r R(sf, t) = F r(sf )t, (так что rf R(s, t)), wi R(ui, si ) для каж ( ) дого i, 1 i m, и = u1...um. Положим, как и выше, w = m s1...s w1... wm, wf = wf (1)... wf (k), u = u1... um. uf = uf (1)... uf (m). С од ной стороны, (rf )w1... wm = hw (rf ) = hw (hf ()). С другой стороны, (rwf (1)... wf (m) )(f ) = hf (hwf (r)). Отсюда следует, что вопрос сво дится к доказательству равенства hw hf = hf hwf.

Так как обе части предполагаемого равенства — гомоморфизмы алгебр из F r(X(sf )) в F r(X(u)), то достаточно показать, что hw hf sf = hf hwf sf, или, менее формально, что значения левой и правой частей совпадают на всех xsf (i),i X(sf ). Прежде всего, hw hf sf = hw s X(f ).

Далее, hw (s (X(f )(xsf (i),i ))) = hw (s (xsf (i),f (i) )) = puf (i) (wf (i) ).

u Вычислим другую часть: hf (hwf (sf (xsf (i),i ))) = hf (puf(i) (wf (i) )). Все uf сводится к доказательству равенства: puf (i) = hf puf(i). Правая часть это u uf равенства — суперпозиция гомоморфизмов верхней строки следующей коммутативной диаграммы:

puf hf u F r(X(uf (i) )) F r(X(uf )) F r(X(u)) f (i) uf (i) uf u puf X(f ) u f (i) X(uf (i) ) X(uf ) X(u) Если обозначить тем же символом разбиение (n1,..., nm ) (это впол не естественно, т.к. морфизм f : uf u представлен отображением f : [nf (1) + · · · + nf (k) ] [n1 + · · · + nm ]), то puf(i) из нижней строки диа uf граммы есть X(pf ), и равенство суперпозиции гомоморфизмов верхней f (i) строки гомоморфизму puf (i) будет следовать из равенства суперпозиции u отображений нижней строки отображению X(p(i) ) (которое ранее также f обозначалось через puf (i) ). Остается только проверить равенство отобра u жений — морфизмов F Set: p(i) = (f )pf для всех i, 1 i k.

f f (i) Записывая это соотношение в виде диаграммы, в которой отображения p(i) и pf интерпретируются как вложения “прямых слагаемых” в ко f f (i) произведения (в категории F Set), легко увидеть, что коммутативность всех таких диаграмм представляет собой, по сути, определение отобра жения f.

Теорема 3.3.3. Пусть M — многообразие -алгебр, и пусть R есть F Set-мультикатегория, определенная в теореме 3.3.2. Тогда многооб разия M и Alg(RF Set ) рационально эквивалентны.

Доказательство. Построим функтор G : M Alg(R) Alg(RF Set ). Сначала превратим каждую алгебру из M в алгебру из Alg(RF Set ). Для этого надо определить семейство отображений вида:

R(s1... sm, t) As1 · · · Asm At, (r, a1,..., am ) ra1... am, где r R(s1... sm, t) = F rM (X(s))t = F r(X(s))t, ai Asi для всех i, 1 i m. Сначала определим гомоморфизм ga1...an : F r(X(s)) A, такой, что ga1...an (s (xsi,i )) = ai (менее формально: ga1...an (xsi,i ) = ai ). Как и прежде, пусть a = a1... an. Тогда положим ra1... an = ga (r).

Проверим, что на A таким образом определяется структура R-алгебры.

Начнем с проверки тождества (rw1... wm )a1... am = rw1 a1... wm am. Здесь r R(s, t), s = s1... sm, wi R(ui, si ), 1 i m, ui = ui,1... ui,ni, a = ai,1... ai,ni, ai,j Aui,j для всех i, j. Пусть также w = w1... wm, u = u1... um, a = a1... am.

С одной стороны, (rw1... wm )a1... am ga (hw (r)), а с другой = rw1 a1... wm am = g(w1 a1 )...(wm am ) (r), так что требуемое равенство эквивалентно соотношению: ga hw = gw1 a1...wm am.

Левая и правая части этого соотношения — гомоморфизмы из F r(X(s)) в A, и поэтому достаточно вычислить значения на элементах базиса xsi,i. Так как ga (hw (xsi,i )) = ga (pui (wi )), и gw1 a1...wm am (xsi,i ) = u wi ai = gai (wi ), то все сводится к равенству: ga pui = gai, кото u рое сводится к ga pui ui = ga u pui = gai ui, и достаточно сопоставить u u значения левой и правой частей на элементах xui,j,j X(ui ). Во первых, gai (ui (xui,j,j )) = ai,j по определению gai. С другой стороны, ga (u (pui (xui,j,j ))) = ga (u (xui,j,l )), где l = n1 + · · · + ni1 + j. Согласно u определению гомоморфизма ga, последнее выражение также равно ai,j.

Пусть a As. Рассмотрим 1s R(s, s) = F r(X(s))s, где X(s) = {xs }. Как известно из доказательства теоремы 3.3.2, 1s = s (xs ). Отсюда 1s a = s (xs )a = ga (s (xs )) = a по самому определению ga.

Теперь рассмотрим морфизм f : sf s категории F SetS, пред ставленный отображением f : [k] [m], и пусть r R(s, t) = F r(X(s))t.

Тогда (rf )a1... am = ga (rf ) = ga (hf (r)), raf (1)... af (k) = gaf (r) и, что бы установить последнее свойство R-алгебры, необходимо убедиться, что ga hf = gaf. Так как речь идет о гомоморфизмах -алгебр из F r(X(sf )) в A, необходимо вычислить значения обеих частей в sf (xsf (i),i ) для всех i, 1 i k. С одной стороны, gaf (sf (xsf (i),i )) = af (i). С другой стороны, ga (hf sf (xsf (i),i )) = ga (s (X(f )(xsf (i),i ))) = ga (s (xsf (i),f (i) )) = af (i). Здесь использовано определение гомоморфизмов ga и gaf.


Определим G(A) как S -множество A с введенной выше структу рой R-алгебры. Чтобы сделать G функтором, необходимо убедиться, что любой гомоморфизм : A B между алгебрами из многообразия M, рассматриваемый как отображение S -множеств, является гомоморфиз мом из R-алгебры G(A) в R-алгебру G(B). Фактически это следует из тождества: ga1...am = g(a1 )...(am ). По определению ga1...am получим (ga1...am (s (xsi,i ))) = (ai ). Также по определению g(a1 )...(am ) (s (xsi,i )) = (ai ).

Теперь рассмотрим r R(s, t), и вычислим (ra1... am ). Как следует из определения ra1... am, и доказанного только что тождества, (ra1... am ) = (ga1...am (r)) = g(a1 )...(am ) (r) = r(a1 )... (am ).

Также без труда проверяется, что отображает константы в кон станты. Из всего этого следует, что если положить G() =, расмат риваемый как гомоморфизм R-алгебр, то G становится функтором. Оче видно, что этот функтор унивалентен. Из построения также видно, что UAlg(R) G = UM, где UM : M SetS — забывающий функтор.

Покажем теперь, что для любой строки s = s1... sn S имееет место равенство: G(F rM (X(s))) = F rR (X(s)).

Напомним, что для каждого t S уже установлено (теорема 3.3.1) равенство: F rR (X(s))t = R(s, t) = F rM (X(s))t, так что необходимо толь ко убедиться в совпадении той структуры R-алгебры, которая была определена на G(F rM (X(s))) выше, и той, которая определялась в теоре ме 3.3.1 Необходимо установить тождество: [rw1... wm ] = gw1...wm (r) = rw1... wm. Здесь r R(u1... um, t) = F r(X(u))t, wi R(s, ui ), 1 i m, s = s1... sn. Поскольку [rw1... wm ] = (rw1... wm )µm,n = hµm,n (hw1...wn (r)), то вопрос сводится к проверке равенства hµm,n hw1...wm = gw1...wm. Речь идет о гомоморфизмах -алгебр из F r(X(u)) в F r(X(s)), поэтому надо вычислять значения левой и правой частей на u (xui,i ), xui,i X(u). С одной стороны, gw1...wm (u (xui,i )) = wi. Рассмотрим m hµm,n (hw1...wm (u (xui,i ))) = hµm,n (ps(i) (wi )). Здесь s(i) означает i-е подслово s s в слове sm. Ввиду того, что выбор wi произволен, достаточно доказать, m что суперпозиция hµm,n ps(i) равна тождественному отображению. Пример s но так же, как это уже делалось выше, можно убедиться, что все сводится m к равенству отображений из F Set: = 1[n], где = (n,..., n). Для µm,n p i каждого j, 1 j n, суперпозиция в левой части действует следующим i образом: j n + · · · + n +j = j + n(i 1) j.

Построим теперь функтор H : Alg(R) = Alg(RF Set ) Alg().

Для этого определим структуру -алгебры на произвольной алгебре B Alg(R). Сначала рассмотрим отображения:

s,t F r (X(s))t F rM (X(s))t = R(s, t), t где левая стрелка отображает символ операции n в элемент xs1,1... xsn,n абсолютно свободной -алгебры F r (X(s)). Отображе ние — естественная проекция на факторалгебру. Положим = t (xs1,1... xsn,n ).

Пусть B — некоторая R-алгебра. Определим для bi Bsi, i n, действие операции следующим образом: b1... bn = b1... bn.

Правая часть понимается как результат действия отображения компо зиции для R-алгебры R(s, t) Bs1 · · · Bsn Bt. Через H(B) обо начим S -множество B, наделенное определенной только что структурой -алгебры. Очевидно, что гомоморфизмы R-алгебр превращаются в го моморфизмы -алгебр, так что H является функтором из Alg(RF Set ) в Alg(). Ясно, что и этот функтор унивалентен.

Обозначим через IM : M Alg() полный и унивалентный функ тор естественного вложения многообразия M в категорию всех -алгебр, и покажем, что HG = IM. Так как все рассматриваемые функторы дейст вуют лишь на структуру алгебры на данном множестве, не меняя самого множества, достаточно убедиться, что если A M, то H(G(A)) — это то же самое множество с теми же операциями из сигнатуры. Пусть s,t, где s = s1... sn, A M, ai Asi, 1 i n. Все, что нам необходимо, следует из тождества:

a1... an = ga1...an () = a1... an, где в правой части стоит результат действия операции на элементы -алгебры A. Согласно определению получаем равенство: ga1...an () = ga1...an (xs1,1... xsn,n ).

Так как есть гомоморфизм то ga1...an = ga -алгебр, Но по определению, ga (xs1,1... xsn,n ) = ga (xs1,1 )... ga (xsn,n ).

ga1...an (xsi,i ) = ai для всех i.

Из HG = IM, унивалентности G, H и IM и полноты IM следует полнота G. Остается показать, что G биективен на объектах. Основным моментом доказательства этого является тот факт, что для любого S множества Y алгебра G(F rM (Y )) является свободной в Alg(R) с базисом Y. Выше это было показано для всех Y = X(s), где s S. Каждое S множество Y, у которого все Ys, s S, конечны, изоморфно (в категории SetS ) одному из X(s).

Из доказанного выше уже следует, что каждая свободная алгебра с конечным базисом из Alg(R) будет свободной алгеброй в M (фактически это алгебры вида F rM (X(s))). Покажем, что это верно для свободных алгебр с произвольными базисами.

Рассмотрим произвольное S -множество Y. Очевидно, что Y = Colim Y, где Y Y — конечные S -подмножества Y. Конечность здесь означает, что для каждого s S компонента Ys конечна, и конечно мно Ys. Условие Y Y означает, что для каждого s S имеет жество sS место включение Ys Ys. Можно также предполагать, что для тех s S, для которых Ys =, выполняется и Ys =, это не повлияет на равен ство Y = Colim Y. Далее, для каждого такого конечного Y найдется строка s S такая, что Y X(s) (изоморфизм в категории SetS ).

= Тогда G(F rM (Y )) G(F rM (X(s)) = F rR (X(s)), и поэтому можно счи = тать, что G(F rM (Y )) = F rR (Y ). Ясно, что F rM (Y ) = Colim F rM (Y ) и F rR (Y ) = Colim F rR (Y ), где копределы берутся по всем рассмот ренным выше конечным Y. Допустимо писать равенства вместо изо морфизмов, так как при сделанных предположениях у гомоморфизмов F rM (Y ) F rM (Y ), соответствующих включениям Y Y, имеются левые обратные, и, следовательно, эти гомоморфизмы также можно счи тать включениями, а Colim фактически есть объединение, и аналогично для F rR. Существует единственный гомоморфизм F rR (Y ) G(F rM (Y )) такой, что коммутативны все диаграммы:

F rR (Y ) G(F rM (Y )) F rR (Y ) G(F rM (Y )) Легко убедиться, что этот гомоморфизм является изоморфизмом.

Пусть B Alg(R). Рассмотрим сюръективный гомоморфизм R алгебр F rR (Y ) B, и его суперпозицию с построенным только что изоморфизмом F rM (Y ) F rR (Y ). Функтор H отображает сюръекции = в сюръекции, так что в Alg() будет иметь место сюръективный гомо морфизм вида F rM (Y ) H(B). Это значит, что H(B) принадлежит M как полной подкатегории Alg() (если отождествить M с образом функтора IM ). Отсюда, в свою очередь, следует, что существует функ тор F : Alg(RF Set ) M такой, что H = IM F. Теперь из IM = HG получаем IM = IM F G, откуда следует, что F G = IdM.

Покажем, что и GF = IdAlg(R). Вопрос сводится к следующему. Все рассматриваемые функторы не меняют S -множества, а меняют лишь структуры алгебр. Если B Alg(R), то функтор F превращает S множество B в -алгебру из M, а функтор G вводит на том же множес тве новую структуру R-алгебры. Необходимо убедиться, что эта новая структура совпадает с исходной структурой R-алгебры. Из предыдущего уже ясно, что это верно для свободных алгебр.

Пусть r R(s, t), s = s1... sn, bi Bsi, 1 i n, b = b1... bn, и rb1... bn Bt — результат выполнения операции композиции в исход ной структуре R-алгебры на B. Утверждается, что rb1... bn = qb (r), где qb : F rR (X(s)) B — гомоморфизм R-алгебр, определяемый условиями:

qb (xsi,i ) = bi. В самом деле, в доказательстве теоремы 3.3.1 было показа но, что в алгебре F rR (X(s)) для выбранного r имеет место тождество:

r = [rxs1,1... xsn,n ] (напомним, что здесь квадратные скобки обознача ют операцию композиции в F rR (X(s)), и ради простоты вместо s (xsi,i ) пишется xsi,i ). Применяя гомоморфизм R-алгебр к этому тождеству, по лучим: qb (r) = qb ([rxs1,1... xsn,n ]) = rqb (xs1,1 )... qb (xsn,n ) = rb1... bn.

После применения функтора F алгебра F rR (X(s)) превращается в -алгебру F rM (X(s)), а отображение qb превращается в гомоморфизм -алгебр из F rM (X(s)) в F (B), причем, так как само отображение не изменилось, то по-прежнему qb (xsi,i ) = bi. Но в таком случае qb = gb, и тогда для композиции в R-алгебре G(F (B)) получаем: rb1... bn = gb (r) = qb (r) = rb1... bn.

Итак, G(F (B)) — это в точности та же алгебра, что и B. Действие GF на гомоморфизмах, очевидно, также является тождественным. По по строению, UM F = UAlg(R), где UAlg(R) : Alg(RF Set ) SetS — забывающий функтор. Таким образом, многообразия M и Alg(RF Set ) рационально эк вивалентны.

Замечание 3.3.1. Опишем мультикатегорию, строящуюся по не которому многообразию многосортных алгебр, несколько менее формаль ным способом, чем это было сделано выше (но фактически способ тот же самый). Пусть через F r(x1,..., xm ) обозначается свободная алгебра данного многообразия с базисом x1,..., xn, а через F r(x1,..., xm )s — ее компонента сорта s. Мультикатегория, которая строится по многообра зию, это мультикатегория R с множеством объектов S (это множество сортов данного многообразия), в которой R(x, y) = F r(x1,..., xm )y. Опе рации композиции устроены следующим образом: это отображения вида R(x, y) R(z 1, x1 )... R(z m, xm ) R(z 1... z m, y), где z i = zi,1... zi,ni, 1 i m, и если a = a(x1,..., xm ) R(x, y) = F r(x1,..., xm )y, bi = bi (zi,1,..., zi,ni ) R(z i, xi ) = F r(zi,1,..., zi,ni )xi, то ab1... bm = a(bi (z1,1,..., z1,n1 ),..., bm (zm,1,..., zm,nm )) (3.3.9) Суть в том, что элементы свободных алгебр допускают возможность “подстановок” вместо “входящих” в них “переменных” элементов из дру гих свободных алгебр того же самого многообразия. Выше, в теореме 3.3.2, это было проделано с соблюдением всех формальностей, но в даль нейшем будет полезна интуитивно более ясная, хотя и менее формальная запись (3.3.9). Структура F Set-операды задается следующим образом:


если a = a(x1,..., xm ) R(x, y) = F r(x1,..., xm )y, f : [m] [n] — морфизм из F Set, то af = a(xf (1),..., xf (m) ) F r(x1,..., xn )y (3.3.10) § 3.4. Некоторые примеры операд и мультикатегорий В этом параграфе будет показано, что по каждой вербальной ка тегории естественным образом можно построить W -операду (или WS мультикатегорию, если добавить произвольный класс объектов S ). Ме тод построения будет также использован в следующем параграфе для построения свободных W -операд.

Пусть W — произвольная вербальная категория. Для каждого m 0 положим OW (m) = W (k, m) (3.4.1) k Теорема 3.4.1. Семейство OW = {OW (n)|n 0} обладает естест венной структурой W -операды.

Доказательство. Опишем, как устроена операдная композиция в OW. Пусть f OW (m), gi OW (ni ), 1 i m. Это означает, что за даны морфизмы категории W, имеющие вид: f : [k] [m], gi ;

[li ] [ni ].

Положим = (n1,..., nm ) P (n1 + · · · + nm, m). Тогда, по определению, f g1... gm = (f )(gf (1) · · · gf (k) ) (3.4.2) Согласно определению вербальной категории, в правой части равенст ва (3.4.2) получается морфизм категории W, имеющий вид [lf (1) + · · · + lf (k) ] [n1 + · · · + nm ], т.е. элемент OW (n1 + · · · + nm ). Единица операды OW — это тождественный морфизм из W (1, 1) OW (1).

Структура W -операды задается следующим образом. Пусть w OW (m), т.е. фактически w : [k] [m] — морфизм категории W. Рас смотрим морфизм категории W вида f : [m] [n]. Тогда суперпозиция f · w будет морфизмом [k] [n], т.е. элементом OW (n). Однако, в со ответствие с принятыми в данной работе обозначениями, мы должны превратить соответствие [n] OW (n) в контравариантный функтор на категории W op, двойственной к категории W. А это значит, что “умно жение” f на w должно производиться справа. Таким образом, wf = f · w (3.4.3) причем в левой части этого равенства f понимается как морфизм кате гории W op.

Доказательство того, что таким образом получается W -операда, использует тождества, сформулированные в следствии 1.1.1, и еще ряд подобным им тождеств, которые будут установлены в процессе доказа тельства теоремы.

Начнем с ассоциативности композиции (3.4.2). Пусть даны морфиз мы W вида: f : [k] [m], gi : [li ] [ni ], hi,j : [vi,j ] [ui,j ], 1 i m, 1 j ni. Это означает, что f OW (m), gi OW (ni ), hi,j OW (ui,j ).

Положим = (n1,..., nm ) P (n1 + · · · + nm, m), i = (ui,1,..., ui,ni ) P (ui,1 + · · · + ui,ni, ni ), = 1 · · · m, hi = hi,1... hi,ni. Требуется доказать равенство:

(f g1... gm )h1... hm = f (g1 h1 )... (gm hm ) (3.4.4) Вычислим левую и правую части (3.4.4). Пусть r = f g1... gm. Согласно (3.4.2), правая часть равна (r )h, где явный вид h будет уточнен ниже.

Явный вид r таков: r = pq, где p = f, q = gf (1) · · · gf (k). Тогда по следствию 1.1.1 (pq) = (p )(q (p)). Далее, по тому же следствию 1.1.1, p = (f ) = f (). Пусть =, это разбиение, которое n1 nm можно записать в виде ( um,j ). Далее, p = f (1) · · ·f (k).

u1,j,..., j=1 j= Таким образом, q (p) = (gf (1) · · · gf (k) ) (f (1) · · · f (k) ). Теперь нам необходимо тождество:

(gf (1) · · · gf (k) ) (f (1) · · · f (k) ) = ((gf (1) ) f (1) ) · · · ((gf (k) ) f (k) ) (3.4.5) Это равенство есть следствие более общего факта: в категории множеств копроизведение (т.е. несвязное покомпонентное объединение) декартовых квадратов снова является декартовым квадратом. Доказательство прово дится непосредственной проверкой определения расслоенного произведе ния (в категории множеств;

в произвольной категории это не обязательно так). Затем надо вспомнить, что выражения вида (gf (i) ) f (i) опреде ляются с помощью декартовых квадратов вида (1.1.1), и что согласно лемме 1.1.3 имеет место единственность проекций в декартовых квадра тах такого вида при определенных условиях, которые в данном случае выполняются очевидным образом.

Далее прямым вычислением можно убедиться, что определенное по (3.4.2) отображение h таково:

h = hf (1),gf (1) (1) · · · hf (1),gf (1) (lf (1) ) · · · hf (k),gf (k) (1) · · · hf (k),gf (k) (lf (k) ).

Собирая все результаты вычислений вместе, получаем, что левая часть (3.4.4) равна следующему:

(f )(d1 · · · dk ) (3.4.6) где di = ((gf (i) ) f (i) )(hf (i),gf (i) (1) · · · hf (i),gf (i) (lf (i) ) ) при всех i, 1 i k.

Займемся правой частью (3.4.4). По определению (3.4.2), ci = gi hi,1... hi,ni = ((gi ) i )(hi,gi (1) · · · hi,gi (li) ) )).

Это отображение из [vi,gi (1) + · · · + vi,gi (li ) ] в [ui,1) + · · · + ui,ni ]. Поэтому то разбиение, которое возникает вследствие применения (3.4.2) к правой части (3.4.4), есть (u1,1) + · · · + u1,n1,..., um,1) + · · · + um,nm ). Это не что иное, как уже появившееся ранее разбиение =. Отсюда f c1... cm = (f )(cf (1) · · · cf (k) ) Вспоминая выписанный выше явный вид ci, убеждаемся, что получи лось то же самое выражение, что и (3.4.6). Ассоциативность операдной композиции тем самым доказана. Свойства операдной единицы — тож дественного отображения [1] [1] — проверяются очень легко.

Перейдем к свойствам, определяющим OW как W -операду. Для удобства различения элементов OW и морфизмов W несколько изме ним обозначения. Пусть : [k] [m] (морфизм из W ) рассматривается как элемент OW (m), и аналогично i : [si ] [li ] (также морфизмы W ) рассматриваются как элементы OW (li ), 1 i m. Рассмотрим также fi : [li ] [ni ] — морфизмы W, которые понимаются только как морфиз мы W. Обозначим через разбиение (n1,..., nm ), и через — разбиение (l1,..., lm ). Необходимо доказать равенство:

(1 f1 )... (m fm ) = (1... m f )(f1 · · · fm ) (3.4.7) Здесь выражения вида i fi понимаются в смысле (3.4.3), т.е. i fi = fi · i — суперпозиция отображений [si ] [li ] [ni ]. Аналогично надо пони мать и правую часть (3.4.7). Сделав все замены согласно (3.4.3), получим в левой части:

(1 f1 )... (m fm ) = ( )((f(1) · (1) ) · · · (f(m) · (m) )) = (3.4.8) ( )(f(1) · · · f(m) )((1) ) · · · (m) ) Второй и третий члены этой цепочки равенств — обычные морфизмы W с обычными суперпозициями (т.е. не надо ничего переворачивать).

Теперь надо воспользоваться непосредственно проверяемым тождеством:

( )(f(1) · · · f(m) ) = (f1 · · · fm )( ) (3.4.9) С учетом этого тождества (а также (3.4.3)) будем иметь следующее про должение равенства (3.4.8):

(1 f1 )... (m fm ) = (f1 · · · fm )( )((1) ) · · · (m) ) = (f1 · · · fm ) · (1... m ) = (1... m )(f1 · · · fm ) Таким образом, равенство (3.4.7) доказано. Последнее равенство, которое необходимо установить, выглядит так:

(f )1... m = (f (1)... f (k) )(f ) Здесст : [l] [k] — элемент OW (k), f : [k] [m] — морфизм W, i : [si ] [ni ] — элементы OW (ni ), 1 i m, = (n1,..., nm ), и выражения вида f понимаются в смысле равенства (3.4.3), т.е. f = f ·.

С учетом этого проведем следующие преобразования:

(f )1... m = ((f · ) )(f ((1)) · · · f ((l)) ) = (f ) · ( (f )) · (f ((1)) · · · f ((l)) ) = (f ) · (f (1)... f (k) ) = (f (1)... f (k) )(f ).

Теорема доказана.

Замечание 3.4.1. Заметим, что если W =, то получается дав но и хорошо известная операда симметрических групп, если W = W Id, то получается также хорошо известная операда, все компоненты кото рой — одноэлементные множества. В остальных случаях, по-видимому, получаются новые операды.

Сформулируем многосортный аналог теоремы 3.4.1. Пусть W — произвольная вербальная категория, S — множество сортов. Для каждо го m 0 и произвольных s1,..., sm, t S положим OWS (s1... sm, t) = WS (u1... uk, s1... sm ) (3.4.10) u1,...,uk S Заметим, что правая часть (3.4.11) не зависит от t S. Мы использу ем обозначение OWS (“O ” как “операда”), поскольку мультикатегориии также называются S -операдами (S — класс объектов).

Опишем, как устроена операдная композиция в OWS.

Пусть a OWS (s1... sm, t), что означает a W (u1... uk, s1... sm ), что, в свою очередь, означает, что a представляется некоторым мор физмом f : [k] [m] категории W, для которого ui = sf (i), i k. Аналогично, пусть для каждого i, 1 i m, даны элементы bi OWS (vi,1... vi,ni, si ), то есть морфизмы из WS (ri,1... ki,li, vi,1... vi,ni ), представленные морфизмами gi ;

[li ] [ni ] категории W. Положим = (v1,...,vm ) PS (v, s), где v i = vi,1... vi,ni, 1 i m, v = v 1... v m, s1,...,sm s = s1... sm. Тогда, по определению, ab1... bm = (a )(bf (1) · · · bf (k) ) (3.4.11) Напомним, что все подробности о действиях с морфизмами категории WS содержатся в § 1.3.

Структура WS -операды задается следующим образом. Пусть a OWS (s1... sm, t) есть морфизм из u1... uk в s1... sm, представленный морфизмом g : [k] [m] категории W. Пусть WS (s1... sm, t1... tn ) представлен морфизмом f : [m] [n]. Тогда a есть морфизм категории WS из v1... vk в t1... tn, представленный отображением f g, и рассмат риваемый как элемент OWS (t1... tn, t).

Теорема 3.4.2. Семейство {OW (s1... sm, t)|m OWS = обладает естественной структурой 0, s1,..., sm, t S} W мультикатегории.

Доказательство. Из определения опреаций композиции и ум ножения элемента на морфизм WS видно, что проверка свойств W мультикатегории полностью сводится к проверкам, уже выполненным в ходе доказательства теоремы 3.4.1.

Теорема 3.4.3. Пусть W — произвольная вербальная категория.

Многообразие Alg(OWW ) рационально эквивалентно многообразию всех полугрупп с единицей.

Если S — произвольное множество (или класс), то многообразие Alg(OWS ) рационально эквивалентно многообразию всех многосортных алгебр с классом сортов S, кстроенному следующим образом: алгебра данного многообразия — семейство множеств A = {A(s)|s S}, при чем для каждой тройки сортов s, u, t определено отображение A(s) A(u) A(t), действие которого обозначается так: (as, bu ) (ss · bu )t.

При этом должны выполняться все тождества вида:

((as · bu )t · cv )w = (as · (bu · cv )r )w Кроме того, в каждой компоненте A(s) содержится константа es, обладающая следующими свойствами:

(as · eu )s = as = (ev · as )s.

Доказательство. Докажем первую часть теоремы. Опишем сначала, как по OW -алгебре A строится полугруппа с единицей. Как множество, эта полугруппа совпадает с A. Чтобы описать операцию умножения, сделаем несколько замечаний о структуре OW. В каждой компоненте OW (m) присутствует элемент, который мы обоначим через n. Это — тождественное отображение 1[n] : [n] [n]. 1 есть единица операды. Имеет место легко проверяемое соотношение:

m n1... nm = n1 +···+nm (3.4.12) Из него следует, в частности, что 2 2 1 = 2 1 2 = 3 (3.4.13) Если f : [m] [n] — морфизм из W, то m f = f, где в правой час ти равенства f понимается как элемент OW (n). Определим бинарную опреацию умножения на A, полагая a1 · a2 = 2 a1 a2. Правая часть этого равенства есть огранияение отображения OW (2) A2 A, являющегося часть структуры OW -алгебры на A. Из равенства (3.4.13) следует, что введенное только что умножение ассоциативно. В самом де ле, (a1 · a2 ) · a3 = 2 (2 a1 a2 )(1 a3 ) = (2 2 1 )a1 a2 a3 = (2 1 2 )a1 a2 a3 = 2 (1 a1 )(2 a2 a3 ) = a1 · (a2 · a3 ).

Из равенства (3.4.12) теперь легко выводится, что m a1... am = a1 ·... am.

Более общим образом, из определения алгебры над W -операдой OW не посредственно вытекает, что для произвольного f W ([m], [n]), рас сматриваемого как элемент OW (n), имеет место равенство:

f a1... an = af (1) ·... · af (m) (3.4.14) Определение структуры алгебры над операдой OW включает также ото бражение OW (0) A0 A, что эквивалентно существованию отобра жения OW (0) A. Но OW (0) — это множество, состоящее из единст венного элемента 0. Его образ в A и будет единицей полугруппы. Свой ства единицы легко проверяются с помощью (3.4.12). Очевидно также, что гомоморфизмы OW -алгебр становятся гомоморфизмами полугрупп с единицей. Тем самым определен функтор из Alg(OWW ) в категорию полугрупп с единицей, коммутирующий с забывающими функторами в категорию множеств.

Обратно, пусть дана полугруппа с единицей A. Определим опера ции OW (n) An A, согласно равенству (3.4.14) при n 0, а при n = 0 пусть это будет отображение OW (0) A, переводящее 1 в единицу полугруппы A.

Непосредственная проверка показывает, что этим действительно опре деляется алгебра над W -операдой OW. Построенное таким образом со ответствие, как легко увидеть, есть функтор из категории (многообра зия) полугрупп с единицей и их гомоморфизмов, сохраняющих единицу, в категорию Alg(OWW ). Из построения ясно, что этот функтор коммути рует с забывающими функторами. Равенство (3.4.14) гарантирует, что описанные выше функторы взаимно обратны.

Доказательство второй части теоремы происходит по той же схе ме. Сначала определим элементы s1...sm,t OWS (s1... sm, t), пола гая их равными тождественным морфизмам s1... sm s1... sm из WS (s1... sm, s1... sm ) OWS (s1... sm, t). Ясно, что s,s — тождествен ный морфизм объекта s. Легко проверяется, что s,t u1,s1... um,sm = u1...um,t (3.4.15) Отсюда следует, что tv,w su,t v,v = sr,w s,s uv,r = suv,w (3.4.16) для всех s, u, v, w, t, r S. Пусть A = {A(s)|s S} есть OWS -алгебра, as A(s), bu A(u). Положим (as · bu )t = su,t as bu A(t). Тогда из (3.4.16) получаем следующее:

((as · bu )t · cv )w = tv,w (su,t as bu )(v,v cv ) = (tv,w su,t v,v )as bu cv = (sr,w s,s uv,r )as bu cv = sr,w (s,s as )(uv,r bu cv ) = (as · (bu · cv )r )w.

Константы es A(s) являются образами единственных элементов мно жеств OWS (e, s) при отображениях OWS (e, s) A(s), входящих в опре деление структуры OWS -алгебры. Исппользуя (3.4.15) и определение ал гебры, легко получить требуемое соотношение (as · eu )s = as = (ev · as )s.

Заметим, что здесь через e (без индексов) обозначается пустая строка (в алфавите S ). Таким образом, как и в односортном случае, получается функтор из категории OWS -алгебр в многообразие многосортных алгебр, описанное в формулировке теоремы. Очевидно, что функтор этот комму тирует с забывающими функторами в категорию SetS.

Отметим, что из (3.4.15) вытекает следующее равенство:

u1...uk,t au1... auk = s1 s2,t (u1...ul,s1 au1... aul )(ul+1...uk,s2 aul+1... auk ).

Это означает, что любое “умножение” на u1...uk,t элементов алгебры A можно представить как итерацию бинарных операций вида (as · bv )w. Далее, пусть : sf (1)... sf (k) s1... sm — морфизм категории WS, представленный морфизмом f : [k] [m] категории W. Тог да sf (1)...sf (k),t =, причем правая часть этого равенства понимается как элемент OWS (s1... sm, t). Тогда по определению алгебры над WS мультикатегорией, имеет место равенство:

as1... asm = sf (1)...sf (k),t asf (1)... asf (k) (3.4.17) Отсюда, с учетом предыдущего, можно сделать вывод, что структура OWS -алгебры полностью определяется заданием умножений (as · bu )t и констант es. Используя это, можно, аналогично односортному случаю, по многосортной алгебре описанного в формулировке теоремы вида по строить OWS -алгебру. Это определяет функтор, коммутирующий с за бывающими функторами, и обратный к построенному выше функтору из Alg(OWS ).

§ 3.5. Свободные операды Пусть = {n |n = 0, 1,... } — некоторая сигнатура. Будем пред полагать известной стандартную конструкцию алгебры -слов с базисом X, т.е. свободной алгебры F r (X) в многообразии Alg() всех -алгебр.

Будем предполагать также известным следующее свойство -слов. До пустим, что для данного слова z F r (X) взяты все слова из, входя щие в запись z, и из них составлено слово w, порядок следования симво лов в котором тот же самый, что и их вхождений в слово z. Если это слово окажется пустым, то обозначим его через. Допустим также, что ана логичным образом (т.е. с сохранением порядка следования) из входящих в запись w символов из множества X составлено слово x. Тогда по па ре слов (w, x) слово z восстанавливается однозначно. Это легко следует из представления -слов виде помеченных корневых деревьев (набросок такого представления для многосортного случая можно найти в [7, глава 2]). Назовем слово w -компонентой слова z, а x — X -компонентой z.

Таким образом, можно даже использовать для слова z альтернативный способ записи в виде wx. Мы будем (явно или неявно) часто пользоваться этой возможностью.

Положим множество FO (n) состоящим из всех элементов z F r (x1,..., xn ), в которых после описанной выше процедуры x = x1... xn. В этом случае слово z однозначно восстанавливается по сло ву w в алфавите. Будем использовать запись вида z = z(x1,..., xn ) = z(x), чтобы иметь возможность делать подстановки вместо “перемен ных” x1,..., xn других -слов. Пусть a = a(x1,..., xm ) FO (m), bi = bi (x1,..., xni ) FO (ni ), 1 i n. Положим ab1... bm = ab1... bm (x1,..., xn1,..., xn1 +···+nm1 +1,..., xn1 +···+nm1 +nm ) = = a(b1 (x1,..., xn1 ),..., bm (xn1 +···+nm1 +1,..., xn1 +···+nm1 +nm )) (3.5.1) Легко заметить, что результат этой операции принадлежит множеству FO (n1 + · · · + nm ) Теорема 3.5.1. Определенное выше семейство FO = {FO (m)|m = 0, 1,... } с операцией композиции (3.5.1) является свободной W Id операдой с базисом.

Доказательство. То, что FO является W Id- операдой, лег ко проверяется с помощью (3.5.1). Роль единицы играет элемент x FO (1) F r (x1 ). Этот элемент при описанном выше разделении слов на -компоненты и на X -компоненты можно отождествить с.

Рассмотрим для каждого n отображение n : n FO (n), сопостав ляющее элементу сигнатуры слово x1... xn. Покажем, что для каж дой W Id-операды R и любого семейства отображений n : n R(n), n = 0, 1, 2,..., существует однозначно определенный гомоморфизм опе рад : FO R, такой, что = (то есть n n = n для каждого n).

Рассмотрим свободные в Alg(R) алгебры R(k) {x1,..., xn }k.

F rR (x1,..., xn ) = k= Элементы r R(n) можно отождествлять с элементами rx1... xn = (r, x1... xn ) R(n) {x1,..., xn }n F rR (x1,..., xn ), так что R(n) F rR (x1,..., xn ). Семейство отображений n : n R(n) вместе с известными отображениями вида F rR (x1,..., xn ) An A, (u(x1,..., xn ), a1,..., an ) u(a1,..., an ), где A есть R-алгебра, позволяет определить на каждой R-алгебре струк туру -алгебры. Используя включения {x1,..., xn } F r (x1,....xn ) и {x1,..., xn } F rR (x1,....xn ), получаем однозначно определенные гомо морфизмы -алгебр F r (x1,....xn ) F rR (x1,....xn ). Ограничения этих гомоморфизмов на FO (n) и будут искомыми компонентами n гомомор физмами операд FO R, удовлетворяющего требуемым условиям.



Pages:     | 1 | 2 || 4 | 5 |   ...   | 8 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.