Полугруппы с финитно аппроксимируемыми полигонами

Математические заметки СВФУ Июль—сентябрь, 2014. Том 21, № 3

УДК 512.53

ПОЛУГРУППЫ С ФИНИТНО АППРОКСИМИРУЕМЫМИ ПОЛИГОНАМИ И. Б. Кожухов, А. Р. Халиуллина

Аннотация. Изучаются полугруппы, над которыми все правые полигоны финитно аппроксимируемы. Охарактеризованы группы с этим свойством. Доказано, что если все полигоны над полугруппой аппроксимируются конечными, порядки которых ограничены, то полугруппа равномерно локально конечна, т. е. существует функция f (п) такая, что порядок любой п-порожденной подполугруппы меньше

/ (п).

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

Хорошо известно, что категория полигонов над полугруппой несет большую информацию о строении полугруппы (см., например, [1, гл. 6]). В [2-4] исследовались полугруппы Б, удовлетворяющие следующим условиям на полигоны:

(*) все правые Б-полигоны финитно аппроксимируемы,

(**) все правые Б-полигоны аппроксимируются полигонами из п или меньшего числа элементов.

Напомним, что финитно аппроксимируемый полигон — это то же, что ре-зидуально конечный. В [2] доказано, что все полигоны над полугруппой Б аппроксимируются полигонами, содержащими не более двух элементов, в том и только том случае, если Б — полурешетка (коммутативная полугруппа идемпо-тентов). В [3] была установлена периодичность полугрупп, удовлетворяющих условию (**). В [3,4] исследовались коммутативные и нильполугруппы с условиями (*) и (**). Цель данной работы — продолжить исследования полугрупп с этими условиями. Мы докажем, что у полугруппы с условием (*) любая правая конгруэнция является пересечением правых конгруэнций конечного индекса. Для групп это условие оказывается и достаточным, т. е. группа удовлетворяет условию (*) в том и только том случае, если любая ее подгруппа является пересечением подгрупп конечного индекса.

Следуя А. Г. Пинусу [5], назовем универсальную алгебру равномерно локально конечной, если существует функция Ь,

© 2014 Кожухов И. Б., Халиуллина А. Р.

(наименьшее общее кратное). Кроме того, этот результат можно усилить, установив равномерную локальную конечность полугрупп с условием (**). Это выводится из доказанного в работе общего утверждения: универсальная алгебра конечной сигнатуры, аппроксимируемая конечными алгебрами ограниченных в совокупности порядков, равномерно локально конечна.

Основные сведения из теории полугрупп можно найти в [6], теории полигонов — в [1], универсальной алгебры — в [7]. Приведем некоторые из определений и обозначений. Если р — отношение эквивалентности на множестве X, то X/р обозначает множество р-классов (фактор-множество). Если a G X, то через ар обозначим р-класс, содержащий а. Таким образом, Х/р = {ар | a G X}. Далее, Ах = {(x,x) | x G X} — отношение равенства на X. Если р,а — отношения эквивалентности на множестве, то р V а обозначает точную верхнюю грань (супремум) элементов р, а в решетке отношений эквивалентности. Известно, что если р,а — конгруэнции универсальной алгебры, то супремум р,а в решетке конгруэнций совпадает с супремумом в решетке отношений эквивалентности.

Пусть Ж — класс универсальных алгебр. Будем говорить, что алгебра А аппроксимируется алгебрами из Ж, если существует множество конгруэнций {рг | i G I} алгебры A такое, что А/р,1 G Ж для всех i G I и р|{р^ | i G I} = Аa. Известно, что это равносильно тому, что алгебра А является подпрямым произведением алгебр из Ж (см. [7, следствие 7.2]).

Правым полигоном над полугруппой S (или правым S-полигоном) называется множество X, на котором действует полугруппа S, т. е. определено отображение X x S ^ X, (x, s) ^ xs, удовлетворяющее условию x(st) = (xs)t при всех x G X, s,t G S (см. [1]). Чтобы подчеркнуть, что X является правым S-полигоном, будем писать Xs. Так как левые полигоны рассматриваться не будут, вместо слов «правый полигон» будем писать просто «полигон». Сама полугруппа S является правым S-полигоном. Нетрудно видеть, что конгруэнции полигона Ss — это в точности правые конгруэнции полугруппы S. Пусть S — полугруппа с единицей е. Тогда S-полигон X называется унитарным, если xe = x для всех x G X. Если S-полигон X представим в виде дизъюнктного объединения подполигонов Xi, т. е. X = У {Xi | i G I} и Xi П Xj = 0 при i = j, то X будем называть копроизведением полигонов Xi и писать X = Ц{Xi | i G I}.

Если G — группа и H — ее подгруппа (не обязательно нормальная), то через G/H будем обозначать множество правых смежных классов Hg. Множество G/H является унитарным правым G-полигоном относительно действия Hg  g' = Hgg'. Нетрудно проверить, что любой циклический унитарный G-полигон изоморфен одному из полигонов G/H.

Если S — полугруппа, то S1 = S U{1} — полугруппа, полученная присоединением единицы к полугруппе S (даже если S уже имела единицу).

Универсальная алгебра называется подпрямо неразложимой, если она не разлагается в нетривиальное подпрямое произведение алгебр. Интерес к под-прямо неразложимым алгебрам объясняется известной теоремой Биркгофа о том, что любая алгебра является подпрямым произведением подпрямо неразложимых алгебр (см. [7, теорема 7.3]). Ввиду этой теоремы можем утверждать, что для любой полугруппы S условие (*) эквивалентно следующему условию:

(*') все подпрямо неразложимые S-полигоны конечны, а условие (**) равносильно условию

(**') |X| < n для любого подпрямо неразложимого S-полигона X.

Следующая теорема показывает, что теорему 2 из [3] можно усилить, заменив n! на HOK(1, 2,..., n), при этом доказательство из [3] сохраняется почти дословно.

Теорема 1. Если S — полугруппа, удовлетворяющая условию (**), то в полугруппе S выполняется тождество x2m = xm, где m = HOK(1, 2,..., n).

Доказательство. Предположим, что в полугруппе S тождество x2m = xm не выполняется. Тогда существует такое a £ S, что a2m = am. Используя лемму Цорна, нетрудно показать, что существует конгруэнция р полигона (S1)^, максимальная относительно условия (a2m,am) £ р. Стандартные рассуждения показывают, что S1 /р — подпрямо неразложимый S-полигон. Тогда ввиду (**') |S 1/р| < n. Покажем, что элементы 1, а, а2,..., an лежат в разных р-классах. Действительно, если (о1,оР) £ р при каких-нибудь i < j < n, то (al,al+k) £ р при некотором k < n, а значит, (al,al+kl) £ р при всех l £ N. Так как m = HOK(1, 2,..., n), то m = kt при некотором t £ N. Отсюда (о1, ai+m) £ р. Умножив справа на am-i, получим (am,a2m) £ р, что противоречит выбору элемента a.

В теории групп широко известно утверждение о том, что всякая подгруппа конечного индекса содержит нормальную подгруппу конечного индекса. В теории полугрупп аналогичное утверждение также имеет место.

Лемма 2 [2, лемма 7]. Если р — правая конгруэнция полугруппы S, имеющая конечный индекс, то существует двусторонняя конгруэнция р' С р, также имеющая конечный индекс. При этом если | S/р | = n, то р' может быть выбрана так, что | S/р' | < nn+1.

Лемма 3. Если полугруппа S удовлетворяет условию (*), то любая ее правая конгруэнция является пересечением правых конгруэнций конечного индекса.

Доказательство. Пусть р — правая конгруэнция полугруппы S. Ввиду

(*) полигон S/р финитно аппроксимируем. Отсюда вытекает, что отношение равенства Аs/p является пересечением конгруэнций конечного индекса полигона S/р. А это означает, что р является пересечением правых конгруэнций конечного индекса полугруппы S.

Следующее утверждение отмечено в [2]. Приведем его доказательство для полноты изложения.

Лемма 4. Если полугруппа S удовлетворяет условию (*), то все ее гомоморфные образы финитно аппроксимируемы.

Доказательство. Пусть р — конгруэнция полугруппы S. Рассмотрим фактор-полугруппу Т = S/р как правый S-полигон. Ввиду условия (*) полигон Т финитно аппроксимируем. Стало быть, существуют конгруэнции р^ этого

полигона такие, что |Т/р^ < ж и р| р^ = Ат. Отсюда следует, что полугруппа S

i

имеет правые конгруэнции ai конечного индекса такие, что р| ai = р. По лемме 2

i

существуют двусторонние конгруэнции конечного индекса ai С ai. Имеем

р СП (р V ai ) СП (р V ai ) = R ai = р.

iii

Отсюда

р =f> V ai).

i

Так как конгруэнции р V ai имеют конечные индексы, полугруппа S/р финитно аппроксимируема.

Для дальнейшего нам понадобится описание подпрямо неразложимых полигонов над группой. Докажем вначале одну лемму о подпрямо неразложимых полигонах над моноидом.

Лемма 5. Пусть S — моноид с единицей е. Всякий подпрямо неразложимый неунитарный S-полигон X представим в виде X = Y U {a}, где Y = Xe — унитарный подпрямо неразложимый S -полигон и aS С Y.

Доказательство. Пусть полигон X удовлетворяет условию леммы. Очевидно, Y = Xe = XS — унитарный подполигон. Докажем, что Y подпрямо неразложим. Пусть это не так. Тогда существует семейство {р,1 | i G I} кон-груэнций полигона Y таких, что рi = Ах и р| {р,1 | i G I} = Ах. Положим рi = U Ах. Тогда рi — конгруэнция полигона X и р| | i G I} = Ах. Однако это противоречит неразложимости X в подпрямое произведение. Осталось доказать, что |X\Y| = 1.

Пусть a,b G X\Y и a = b. Тогда ae = a и be = b. Очевидно, отношения ра = {(a, ae), (ae, a)} U Ах и ръ = {(b, be), (be, b)} U Ах являются конгруэнциями полигона X и ра П ръ = Ах. Это противоречит тому факту, что X подпрямо неразложим.

Пусть X — полигон над группой G с единицей e. Тогда X = Xe U (X\Xe), где Xe — (максимальный) унитарный подполигон, а A = X\Xe — «неунитарная часть». Унитарный подполигон Xe является объединением попарно не пересекающихся орбит: Xe = Ц xiG, при этом xiG = G/Hi, где Hi = {g | xig = xi}.

i ei

Таким образом,

X = Ц (G/Hi )Ц A, iei

где AG С Xe.

Теорема 6. Правый полигон X над группой G подпрямо неразложим в том и только том случае, если |X | = 1 или X изоморфен одному из следующих полигонов:

(1) {x, a}, где xG = aG = {x};

(2) G/H, при этом группа G имеет наименьшую подгруппу H ' D H ;

(3) (G/H) Ц{z}, где H — такая, как в (2), и zG = {z}. Доказательство. Тот факт, что полигоны вида (1)-(3) подпрямо неразложимы, проверяется непосредственно.

Пусть X — подпрямо неразложимый G-полигон и |X | > 2. Предположим вначале, что X унитарный. Тогда X = |J{xiG | i G I}, где xiG = G/Hi — орбиты. Покажем, что |I| < 2. Пусть |I| > 3. Выберем различные элементы i\,i2,iri G I. Множества

P = x4G, Q = xi2G, R = {xiG | i = ii,i2} непусты. Положим

р1 = ((P U Q) x (P U Q)) U Ах, р2 = ((R U Q) x (R U Q)) U Ах,

рз = ((P U R) x (P U R)) U Ах.

Тогда р1, р2, рз — нетривиальные конгруэнции полигона X и р1 П р2 П рз = Ах, что невозможно для подпрямо неразложимого полигона.

Таким образом, имеем X = xG или X = x1 G U x2G. Если X = xG, то X = G/H, а так как нетривиальный подпрямо неразложимый полигон должен содержать наименьшую нетривиальную конгруэнцию, существует наименьшая подгруппа H' D H. Это означает, что X имеет вид (2). Пусть теперь X = x1 G U x2G. Если |x1G|, |x2G| > 2, то р1 = (x1G x x1 G) U Ах и р2 = (x2G x x2G) U Ах — нетривиальные конгруэнции такие, что р1 П р2 = Ах; противоречие. Таким образом, можем считать, что |x2G| = 1. Следовательно,

X = x1G U {z} ^ (G/H) Ц{z}.

Нетрудно проверить, что получили полигон вида (3).

Пусть X неунитарный. Тогда по лемме 5 X = Xe U {a}. Покажем, что |Xe| = 1. Действительно, пусть |Xe| > 1. Тогда р1 = {(a, ae), (ae,a)}U Ах и р2 = (Xe x Xe) U Ах — нетривиальные конгруэнции полигона X и р1 П р2 = Ах, и также получаем противоречие. Если |Xe| = 1, то X имеет вид (1).

Если S — бесконечная циклическая полугруппа, то все ее гомоморфные образы финитно аппроксимируемы (вообще, нетривиальные гомоморфные образы конечны). Однако, как показывает пример из [2], над S существует бесконечный подпрямо неразложимый полигон. Следовательно, обратное к утверждению леммы 4 неверно. Данный пример показывает также, что и обратное к утверждению леммы 3 неверно. Однако в случае, когда S — группа, лемма 3 допускает обращение.

Теорема 7. Группа G удовлетворяет условию (*) в том и только том случае, если каждая ее подгруппа является пересечением подгрупп конечного индекса.

Доказательство. Необходимость следует из леммы 3. Докажем достаточность. Ввиду эквивалентности условий (*) и (*') достаточно доказать (*'). Пусть X — подпрямо неразложимый G-полигон. По теореме 5 он имеет вид (1), (2) или (3). Полигон вида (1) конечен. Докажем конечность полигона X, если он имеет вид (2). Итак, X = G/H и существует наименьшая подгруппа H' D H. По условию H является пересечением подгрупп конечного индекса, т. е. H = р| Ha и [G : Ha] < ж при всех а. Кроме того, для любого а или

Ha 2 H', или Ha = H. Следовательно, Ha = H при некотором а, а значит, H конечного индекса. Таким образом, X — конечный полигон. Если X имеет вид (3), то аналогично устанавливаем, что подгруппа H конечного индекса, а значит, X = (G/H) U {z} — конечный полигон.

Перейдем к условию (**). Докажем равномерную локальную конечность полугрупп, удовлетворяющих этому условию. Для этого понадобится одно утверждение общего характера. Следующая теорема может быть выведена из теоремы 0.1 в [8]. Приведем доказательство, так как оценка сверху порядков i-порождающих подалгебр в нашем случае может быть несколько уменьшена.

Теорема 8. Пусть A — универсальная алгебра конечной сигнатуры. Если A аппроксимируется алгебрами Ai, i G I, конечных ограниченных в совокупности порядков, то A равномерно локально конечна. При этом если |Ai| < n при всех i G I, то подалгебра, порожденная t элементами, имеет не более exp(^(n) • n* • ln n) элементов, где ^(n) — количество неизоморфных алгебр данной сигнатуры порядков, не превосходящих n.

Доказательство. Пусть £ = {/i,...,/k} — сигнатура алгебры A. По условию алгебра A является подпрямым произведением алгебр Ai сигнатуры £ таких, что |Ai| < n. Следовательно, алгебра A изоморфна подалгебре алгебры

A = П Ai (прямого произведения). Поэтому достаточно доказать равномерную

i ei

локальную конечность алгебры A.

Так как сигнатура £ конечна, имеется лишь конечное число ^(n) попарно не изоморфных алгебр из n или меньшего числа элементов. Поэтому

A = Bi х B2 х • • • х

где Ba = П(Са), Са — алгебры мощности не более n, а = 1, 2,..., ^(n). Так

la

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

Итак, нужно показать, что алгебра В = П C равномерно локально конеч-

jeJ

на, если C — конечная алгебра конечной сигнатуры.

Пусть b(1), b(2),..., b(t) G В. Рассмотрим подалгебру (b(1), b(2),..., b(t)), порожденную этими элементами. Имеем b(s) = (bsj)jej, s = 1, 2,..., t, где bsj G C. Для каждого набора £ = (c1;...,ct) G C* положим Jç = {j G J | b1j- = ci,. .., btj = ct}. Некоторые из этих множеств могут быть пустыми. Очевидно, что Jç П Jn = 0 при £ = п. Следовательно, те из множеств Jç, которые непусты, образуют разбиение множества J, т. е. J = У{Jç | £ G C*}. Пусть в — соответствующее этому разбиению отношение эквивалентности на множестве J.

Пусть В' = {(cj)jej | Cj = Cj', (j, j') G в}. Очевидно, что В' — конечная подалгебра, ее порядок равен |C|p, где p = | J/в|. Кроме того, b(1), b(2),..., b(t) G В'. Следовательно, подалгебра (b(1), b(2),..., b(t)) конечна.

Оценим сверху порядок этой подалгебры. Так как p < |C*| < n*, то

| (b(1), b(2),___, b(t)) | < |В'| = |C|p < exp(n* ln n).

Итак, в каждом Ba подалгебра, порожденная t элементами, имеет не более exp(n* lnn) элементов. Учитывая формулу (о), получим, что в алгебре A любая t-порожденная подалгебра имеет порядок, не превосходящий числа exp(^(n) • nt • ln n).

С помощью только что доказанной теоремы можно доказать равномерную локальную конечность одного класса полугрупп, содержащего полугруппы, удовлетворяющие условию (**).

Теорема 9. Пусть S — полугруппа такая, что полигон Ss аппроксимируется S-полигонами порядков, ограниченных сверху одним и тем же натуральным числом. Тогда S равномерно локально конечна.

Доказательство. По условию

As = П{Pi I i G I}

где Pi — правые конгруэнции такие, что S/pi — подпрямо неразложимый полигон и IS/p-il < n. По лемме 2 pi содержит двустороннюю конгруэнцию pi индекса, не превосходящего nn+1. Таким образом,

AS = П{Pi I i е I}

где |S/pi I < nn+1. Так как pi — двусторонняя конгруэнция, S/pi — полугруппа. Следовательно, полугруппа S аппроксимируется полугруппами из nn+1 или меньшего числа элементов. По теореме 8 она равномерно локально конечна. Порядок t-порожденной подполугруппы не превосходит exp(^(nn+1) • nt(n+1) • (n + 1) • ln n), где ф(к) — количество неизоморфных полугрупп из к или меньшего числа элементов.

Следствие 10. Полугруппа, удовлетворяющая условию (**), равномерно локально конечна.

Замечание. Из равномерной локальной конечности следует равномерная периодичность полугруппы. Однако оценка порядка циклической подполугруппы, получающаяся с помощью теоремы 9, хуже, чем в теореме 1. Действительно, если в формуле, полученной в теореме 9, взять t = 1, то получим для любого элемента a данной полугруппы неравенство

|<a> | < exp(^(nn+1) • nn+1 • (n + 1) • ln n). Между тем по теореме 1 получаем |<a>| < 2 • HOK(1, 2,... ,n) — 1.

ЛИТЕРАТУРА

1. Kilp M., Knauer U., Mikhalev A. V. Monoids, acts and categories. New York; Berlin: W. de

Gruyter, 2000.

2. Kozhukhov I. B. One characteristical property of semilattices // Commun. Algebra. 1997.

V. 25, N 8. P. 2569-2577.

3. Кожухов И. Б. Условия конечности для подпрямо неразложимых полигонов и модулей //

Фундамент. и прикл. математика. 1998. Т. 4, № 2. С. 763-767.

4. Кожухов И. Б. Полугруппы, над которыми все полигоны резидуально конечны // Фундамент. и прикл. математика. 1998. Т. 4, № 4. С. 1335-1344.

5. Пинус А. Г. Внутренние гомоморфизмы и позитивно-условные термы // Алгебра и логика. 2001. Т. 40, № 2. С. 158-173.

6. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. М.: Мир, 1972. Т. 1.

7. Кон П. Универсальная алгебра. М.: Мир, 1968.

8. Хобби Д., Маккензи Р. Строение конечных алгебр. М.: Мир, 1993. Статья поступила 15 сентября 2014 г.

Кожухов Игорь Борисович, Халиуллина Айгуль Римзиловна Национальный исследовательский университет МИЭТ, Москва Зеленоград, проезд 4806, дом 5, Москва 124498 когЬиЬо¥_з._Ь@таз.1. ги, Ьа1з.и11з.пааг(^таз.1. сот