О некоторых результатах и нерешенных задачах теории унарных алгебр

ЧЕБЫШЕВСКИЙ СБОРНИК Том 12 Выпуск 2

Труды VIII Международной конференции Алгебра и теория чисел: современные проблемы и приложения, посвященной 190-летию Пафнутия Львовича Чебышева и 120-летию Ивана Матвеевича Виноградова

УДК 512.57

О НЕКОТОРЫХ РЕЗУЛЬТАТАХ И НЕРЕШЕННЫХ ЗАДАЧАХ ТЕОРИИ УНАРНЫХ АЛГЕБР

В. К. Карташов

ON SOME RESULTS AND UNSOLVED PROBLEMS OF THE THEORY OF UNARY ALGEBRAS

V. K. Kartashov

Аннотация

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

The paper is a brief survey of some results of investigations on algebras that are related to unary algebras as well as of results on different axiomatizable classes of unary algebras.

Необходимость исследований по этим двум направлениям для алгебраических систем произвольной сигнатуры обосновал А.И. Мальцев в докладе на международном конгрессе математиков в Москве в 1966 г. ([1]). Он подчеркнул, что в каждом из указанном направлений содержится "взаимно проникающая "информация о другом направлении, в том смысле, что любая из двух алгебраических систем (исходная и родственная ей) может быть носителем значительной информации о другой.

Ниже приводится краткий обзор результатов исследований по каждому из этих направлений.

1 Первое направление

Для произвольной алгебры A = (A, Q) к родственным алгебрам, в частности, относятся:

1. End A - моноид эндоморфизмов (алгебры A);

2. Aut A - группа автоморфизмов;

3. SubA - решетка подалгебр;

4. ConA - решетка конгруэнций;

5. Top A - решетка топологий.

В 1977 году на Международном коллоквиуме по универсальной алгебре в г. Эстергоме (Венгрия) Л.А. Скорняков представил обзор результатов исследований по каждому из двух указанных направлений в классе унаров, т. е. алгебр с одной унарной операцией ([2]). Им было проанализировано более 40 работ по унарам.

Основные вопросы:

1) Пусть A - алгебра, родственная алгебре A. Требуется описать класс, состоящий из всех алгебр A, для которых алгебра A обладает заданным свойством. Например, описать класс всех унаров, у которых моноид эндоморфизмов коммутативен, либо является группой и т. д.

2) Какие ограничения, наложенные на родственную алгебру A, "гаранти-

A

каких случаях из изоморфизма алгебр A и B следует изоморфизм исходных алгебр A и B?

3) Задача описания класса С алгебр, каждая из которых изоморфна алгебре A, родственной некоторой алгебре A заданного класса С, Например, описать

SubA

A

подунаров,

В числе работ, в которых решаются задачи первого типа и, частично, -третьего типа, можно назвать работы [3] [10].

В [3] описаны атомы в решетках конгруэнций унаров, охарактеризован класс унаров, решетка конгруэнций которых полумодулярна сверху.

В [4] описаны унары, моноид эндоморфизмов которых коммутативен.

Содержание работ [5] [8] достаточно четко отражает их название.

В [9] описаны классы унаров, у которых решетка конгруэнций модулярна, дистрибутивна, булева, либо является цепью.

В [10] аналогичные вопросы решены для решеток топологий унаров.

В работах [11], [12], [13] наряду с решением задач первого типа приводится решение задач второго типа. Здесь описаны, соответственно, группы автоморфизмов унаров, решетки подунаров и решетки с псевдодополнениями, реализуемые решетками конгруэнций унаров.

Наконец, в [14] найден класс унаров, каждый из которых определяется своей полугруппой эндоморфизмов.

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

Открытых вопросов типа 1) и 2) осталось очень мало. Не решены лишь некоторые задачи типа 3), К ним, в частности, относится задача описания класса полугрупп, реализуемых полугруппами эндоморфизмов унаров. Кроме того, автору неизвестны работы, которые содержали бы полное описание класса всех решеток конгруэнций или топологий унаров.

Для унарных алгебр, сигнатура которых содержит более одной операции, аналогичное утверждение было бы неправильным. Здесь еще остается много открытых вопросов типа 1) — 3), Однако, и для этого случая в настоящее время существует ряд содержательных работ. Среди них — работа Г, Гретцера и Е, Т. Шмидта ([15]), В ней содержится два очень важных результата:

Теорема 1. Для любой алгебры, A = (A, П) существует унарная алгебра, В та,кая, ч то Con A = ConB.

Теорема 2. Решетка, L изоморфна, решетке конгруэнций некоторой унарной алгебры, тогда, и только тогда, когда, L является, компактно порожденной решеткой.

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

Далее, следует отметить также работы [16] — [24], в которых задачи типа 1)

— 3) рассматривались для произвольных унарных алгебр,

2 Второе направление

А,И, Мальцев в упомянутом выше докладе [1] поставил проблему исследования универсально аксиоматизируемых классов алгебраических систем, а также

- свойств теоретико-модельного характера (разрешимость, полнота, категоричность теорий и т.д.).

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

Как известно, теорема Биркгофа о структурной характеристике многообразий, работа Хорна [25], а также - монография А,И, Мальцева [26] дали значительный толчок исследованию различных аксиоматизируемых классов алгебраических систем.

Все эти вопросы нашли естественное отражение в теории унарных алгебр.

Для унаров в рамках данного направления были поставлены многие традиционные вопросы, проводились исследования решеток многообразий и квазимногообразий, а также - базисов тождеств и квазитождеств, свойств различных теорий. При этом были получены содержательные алгебраические и теоретикомодельные результаты ([26, с. 351], [27]—[36]),

Для унарных алгебр более богатой сигнатуры также имеются значительные результаты (см., например, [26, с. 348], [37]—[42]). Однако в этом случае остается много открытых вопросов.

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

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

Пусть A = (A, Q) - произвольная унарная алгебра. Для любого a G A через

(a) обозначается подалгебра алгебры A, порожденная элементом a.

Элементы a,b G A называются взаимно достижимыми, если (a) = (b).

Очевидно, что отношение взаимной достижимости является эквивалентно-A

a b a b

валентны " и записью a ~ b.

Класс эквивалентности ~ с порождающим элементом a называется слоем этого элемента и обозначается через S (a).

Элемент a G A называется выводимым, если a = f (b) для некоторых f G Q и b G A, и - невыводимым, в противном случае.

Будем говорить, что a - базисный элемент, если подалгебра (a), порожденная им, максимальна по включению во множестве всех однопорожденных подалгебр A

(yb g A)((a) Ç (b) ^ (a) = (b)).

Лемма 1. ([22]) Пусть элем,ент a G A обладает одним из следующих свойств: выводимый, невыводимый, базисный. Тогда любой эквивалентный ем,у b

Лемма 2. ([22]) Отношение эквивалентности между элементами, сохраняется при гомоморфизме унарных алгебр, т.е. если, р : A ^ B - некоторый гомоморфизм, унарных алгебр A = (A, Q) и B = (B, Q), a,b G A u, a ~ b, то ap ~ bp.

Элементы a и b произвольной унарной алгебры A = (A, Q) называются независимыми, если каждый из них не принадлежит подалгебре, порожденной другим, т.е. если a G (b) a b G (a). Непустое подмножество S Ç A называется независимым, если оно либо одноэлементно, либо любые два его элемента независимы.

Система S порождающих алгебры A называется независимой (НСП), если S - независимое подмножество носителя этой алгебры.

Заметим, что унарная алгебра может не иметь независимой системы порождающих, К таким алгебрам относится, например, унар (Z, f ), где Z - множество целых чисел и f (z) = z + 1 для любо го z Є Z,

Лемма 3. ([22]) Любая независимая система порождающих унарной алгебры состоит из базисных элементов.

Лемма 4. ([22]) Если в независимой системе порождающих унарной алгебры некоторые элементы заменить эквивалентными, то получится, снова, независимая систем,а, порождающих этой алгебры.

Лемма 5. ([22]) Пусть a - базисный элемент унарной алгебры, A и S

S

найдется элемент с такой, что множество Si = (S \ {c}) U {a} также будет

A

Теорема 3. ([22]) Если унарная алгебра, обладает хотя, бы, одной, независимой систем,ой, порождающих, то любые две ее независимые системы порождающих имеют одинаковую мощность.

Следствие 1. ([22]) Если унарная алгебра, имеет хотя бы одну независимую систему порождающих, то любая, такая систем,а, представляет собой совокупность элементов, взятых по одному из каждого слоя, порожденного базисным элементом.

Пусть A - произвольная унарная алгебра. Через J и D обозначим, соответственно, множество всех ее невыводимых элементов и множество всех слоев, порожденных ее выводимыми базисными элементами. Пару (а, в)-, где а и в

JD

A

A

SS

ав

Очевидно, что если унарная алгебра конечно порождена, то она имеет ранг (а, в) а в

числами.

Свойства НСП могут быть использованы при исследовании:

_ i pviiu автоморфизмов и полугрупп эндоморфизмов унарных алгебр;

- решеток подалгебр и конгруэнций унарных алгебр;

- свойств аксиоматизируемых классов унарных алгебр.

Приведем несколько задач, при решении которых существенно было использовано понятие НСП,

1) Говорят, что алгебра обладает свойством Хопфа, если каждый ее эпиэндоморфизм является автоморфизмом.

Унарная алгебра {Л, О) называется коммутативной, если /д(а) = д/(а) для любых /,д Е О а Е Л.

Теорема 4. ([22]) Любая конечно порожденная, коммутативная унарная алгебра, обладает свойством, Хопфа.

Отметим, что каждое из условий коммутативности либо конечно порожденное! н унарной алгебры в формулировке теоремы 4 является существенным.

Действительно, пусть А = {N0, /), где N0 - множество целых неотрицательных чисел, и фупкция / определяется по правилу п — 1, если п > 0,

f (n) = 1 n n

I 0, если n = 0.

Очевидно, что алгебра A коммутативна и не является конечно порожденной, f - эпиэндоморфизм этой алгебры и f (0) = f (1) Это означает, что алгебра A не обладает свойством Хопфа.

Кроме того, автором доказано, что в многообразии Bll алгебр сигнатуры {f,g}, определенном тождеством

(Vx)fg(x) = x,

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

2) Унарная алгебра называется смлвно связной, если она порождается любым своим элементом.

A

влетворяет равенству

End A = Aut A.

Этим же свойством обладает и всякая коммутативная сильно связная алгебра

([17]).

Автором с использованием свойств НСП доказана следующая

Bi,i

удовлетворяет равенству (1).

3) НСП использованы также при доказательстве следующих двух утвержде-

нии.

Теорема 6. ([40]) Любое многообразие ком,м,ута,ти,вн,ы,х унарных алгебр конечной сигнатуры, имеет конечный базис тождеств.

Теорема 7. ([40]) Любая, конечная, коммутативная унарная алгебра, конечной сигнатуры, имеет конечный базис квазитождеств.

4) Далее нам понадобятся следующие обозначения. Пусть А = {А, О) - произвольная унарная алгебра и а Е А. Тогда О* - свободный моноид слов над алфавитом О;

в(т) - множество всех сигнатурных символов, входящих в слово т Е О*;

Оа = Ц Е О\!(а) ~ а}-

Теорема 8. Пусть A = (A, Q) - коммутативная унарная алгебра конечной сигнатуры Q, на которой истинно тождество w(x) = x (w Е Q*) и s(w) = Q.

A

образом другой, то EndA = AutA.

A=

= (A, Q) справедливы следующие утверждения:

1. если A содержит два независимых элемента a и Ъ, для которых Qa = Qb, Qa = Q, то решетка ConAKonrpysnHHй алгебры A не является дистрибутивной;

2. если A содержит трехэлементное независимое подмножество {a, Ъ, с} такое, что Qa = Qb = QC; Qa = Q, то решетка ConA не является модулярной.

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

[1] Мальцев А,И, О некоторых пограничных вопросах алгебры и математической логики // Труды международного конгресса математиков (Москва, 1966). М.: Мир, 1968. С. 217-232.

[2] Skornjakov L.A. Unars // Coll. Math. Soc. J. Bolyai. 1982. V. 29. Universal Algebra (Esztergom 1977). P.735-743.

[3] Berman J. On the congruence lattices of unary algebras // Proc. Amer. Math. Soc. 1972. V. 36. N 1. P. 34-38.

[4] Varlet J.C. Endomorphisms and fully invariant congruences in unary algebras (A,f) // Bull. Soc. Roj. Sci. liege. 1970. V. 39. N 11/12. P. 576-589.

[5] Skornjakov L.A. Unary algebras with regular endomorphism monoids // Acta. Sci. Math. 1978. V. 40. N 3/4. P. 17-21.

[6] Бочкин A.M. У нары с сепаративным моноидом эндоморфизмов / / Известия Вузов. Математика. 1983. N 5. С. 71-74.

[7] Hvman J. Automorphisms of 1-unarv algebras I. // Algebra Univers, 1974. V.

4. N 1. P. 61-77.

[8] Hyman J., Nation J.B. Automorphisms of 1-unarv algebras II. // Algebra Univers. 1974. V. 4. N 1. P. 127-131.

[9] Егорова Д.П. Структура конгруэнций унарной алгебры // Упорядоченные множества и решетки: Межвуз, науч. сб. Саратов, 1978. Вып. 5. С. 11-44.

[10] Kartashova А. V. On lattices of topologies of unary algebras // J. of Math. Sci. 2003. V. 114. N 2. P. 1086-1118.

[11] Фейенберг В.З. Унарные алгебры и их группы автоморфизмов // Докл. АН БССР. 1969. Т. 13. N 1. Р. 576-589.

[12] Bartol W, Subalgebra lattices of mono-unarv partial algebras // Algebra Univers. 1981. V. 12. N 1. P. 66-69.

[13] Бощенко А.П. Псевдодополнения в решетке конгруэнций унаров // Меж-вуз. сб. науч. работ ВГПИ, Волгоград, 1989. С. 23-26.

[14] Popov B.V. On characterization of monounarv algebras by their endomorphism semigroups // Semigroup Forum. 2006. V. 73. P. 444-456.

[15] Gratzer G,, Shmidt E.T. Characterizations of congruence lattices of abstract algebras // Acta Sci. Math. 1963. V. 24. P. 34-59.

[16] Johnson J., Seifert E.L. A survey of multi-unarv algebras. Mimeographed seminar notes. U.C. Berkeley, 1967.

[17] Esik Z,, Imreh B. Remarks on finite commutative automata. // Acta Cvber-netica. 1981. V. 5. N 3. P. 143-146.

[18] Bogdanovic S., Ciric М., Imreh B,, Petrovic Т., Steinbv M. On local properties of unary algebras // Algebra Colloq, 2003. V. 4. N 10 P. 461-478.

[19] Bogdanovic S., Ciric М., Petrovic Т., Imreh B,, Steinbv M. Subdirect Decompositions of unary Algebras // Fundamenta Informaticae. 1999. V. 38. P. 31-40.

[20] Салий B.H. Каркас автомата // Прикладная дискретная математика. 2010. Т. 1. N 7. С. 63-67.

[21] Богомолов А.М., Салий В.Н. Алгебраические основы дискретных систем. М.: Физматлит, 1997.

[22] Карташов В.К. Независимые системы порождающих и свойство Хопфа для унарных алгебр // Дискретная математика. 2008. Т. 20. N 4. С. 79-84.

[23] Карташова А.В. О конечных решетках топологий коммутативных унарных алгебр // Дискретная математика. 2009. Т. 21. N 3. С. 119-132.

[24] Molchanov V.A. A universal planar automation is determined by its semigroup of input symbols // Semigroup Forum. 2011. V. 82. P. 1-9.

[25] Horn A. On sentences which are true of direct unions of algebras // J. Svmb, Logic. 1951. V. 16. P. 14-21.

[26] Мальцев А.И. Алгебраические системы. М.: Наука, 1970.

[27] Wenzel G.H. Subdirect irredueibilitv and equational compactness in unary

[28] Сизый С,В, Финитно аппроксимируемые унары // Мат, заметки, 1988, Т. 43. N 3. С. 401-406.

[29] Карташов В.К. Квазимногообразия унаров // Мат. заметки. 1980. Т. 27. N 1. С. 7-20.

[30] Карташов В.К. Квазимногообразия унаров с конечным числом циклов // Алгебра и логика (Новосибирск). 1980. Т. 19. N 2. С. 173-193.

[31] Карташов В.К. О решетках квазимногообразий унаров // Сиб. мат. ж. 1985. Т. 26. N 3. С. 49-62.

[32] Мартынова Т.А. Группоид многообразий унаров с конечным числом циклов // Докл. Международ, семип., посвящ. памяти Л.А. Скорнякова, Волгоград, 1999. С. 191-195.

[33] Шишмарев Ю.Е. О категоричных теориях одной функции // Мат. заметки. 1972. Т. 2. N 1. С. 89-98.

[34] Иванов A.A. Полные теории унаров // Сиб. мат. ж. 1984. Т. 23. N 1. С. 48-74.

[35] Иванов A.A. О полных теориях унаров // Сиб. мат. ж. 1986. Т. 27. N 1. С. 57-69.

[36] Сизый С.В. Критические теории некоторых классов графов и унарных алгебр // Алгебра и логика. 1989. Т. 28. N 4. С. 454-462.

[37] Jezëk J. Primitive classes of algebras with unary and nullarv operations // Colloq, Math. 1969. V. 20. P. 159-179.

[38] Бесценный 11.11. Квазитождества конечных унарных алгебр // Алгебра и логика. 1990. Т. 28. N 5. С. 493-512.

[39] Смирнов Д.М. О соответствии между регулярно определимыми многообразиями унарных алгебр и полугруппами // Алгебра и логика. 1978. Т. 17. N 4. С. 468-477.

[40] Кравченко A.B. Сложность решеток квазимногообразий для многообразий унарных алгебр // Матем. тр. 2001. Т. 4. N 2. С. 113-127.

[41] Esik Z., Imreh В. Subdireetly irreducible commutative automata // Acta Cybernetiea. 1981. V. 5. P. 251-260.

[42] Карташов В.К. О конечной базируемое™ многообразий коммутативных унарных алгебр // Фундаментальная и прикладная математика. 2008. Т. 14. N 6. С. 85-89.

Волгоградский государственный социально-педагогический университет. Поступило 14.10.2011