На правах рукописи

Максимовский Михаил Юрьевич

ПОЛИГОНЫ И МУЛЬТИПОЛИГОНЫ НАД ПОЛУГРУППАМИ

Специальность 01.01.06 – математическая логика,

алгебра и теория чисел

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

Казань – 2010 г.

Работа выполнена на кафедре высшей математики № 1 Московского государственного института электронной техники (национального исследовательского университета)

Научный руководитель: доктор физико-математических наук, профессор Кожухов Игорь Борисович

Официальные оппоненты: доктор физико-математических наук, профессор Тищенко Александр Владимирович, кандидат физико-математических наук, доцент Ильин Сергей Николаевич

Ведущая организация: Московский педагогический государственный университет

Защита диссертации состоится «25» ноября 2010 года в 16 часов на заседании диссертационного совета Д 212.081.24 при ФГАОУВПО «Казанский (Приволжский) федеральный университет» по адресу:

420008, г. Казань, ул. Кремлевская, д. 35, конференц-зал библиотеки им.

Н. И. Лобачевского КФУ.

С диссертацией можно ознакомиться в библиотеке им. Н. И.

Лобачевского по адресу: 420008, г. Казань, ул. Кремлевская, д. 35.

Автореферат диссертации опубликован на сайте ФГАОУВПО «КФУ»

(www.ksu.ru).

Автореферат разослан «_» 2010 г.

Ученый секретарь диссертационного совета к. ф.-м. н., доцент А. И. Еникеев

Общая характеристика работы

Актуальность темы исследования. Полигоны над полугруппой, т.е. множества, на которых действует полугруппа, возникают в разных разделах алгебры и ее приложений. Понятие полигона является алгебраическим выражением понятия автомата 1, (точнее, автомата Мура, т.е. автомата без выхода). Это означает, что все работы по алгебраической теории автоматов можно рассматривать как относящиеся к теории полигонов. Если обычный полигон над полугруппой является алгебраической интерпретацией автомата, то мультиполигоны можно интерпретировать как автоматы с несколькими входными алфавитами. Теория полигонов является довольно молодым разделом общей алгебры, имеющим гораздо менее богатую историю, чем многие другие разделы, а теория мультиполигонов вообще находится на начальной стадии развития. Поэтому разработка этих теорий представляется актуальной математической задачей.

Понятие полигона над полугруппой аналогично понятию модуля над кольцом, ввиду чего теория полигонов развивалась под большим влиянием теории колец и модулей. Гомологическая классификация колец, т.е. исследование свойств кольца по свойствам категории модулей над этим кольцом, вызвала аналогичные вопросы в теории полигонов. По аналогии с модулями рассматривались артиновы и нетеровы, инъективные и проективные, плоские и свободные полигоны и т.д. Этими вопросами занимались многие математики России и зарубежья: М. Кильп 3,5, В. Фляйшер 4, П. Нормак 5 (Эстония), Л. А. Скорняков 6, В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин, Введение в теорию автоматов. М.:Наука, 1985.

Ж. Лаллеман, Полугруппы и комбинаторные приложения. М.:Мир, 1985.

М. Кильп, Гомологическая классификация моноидов. Сиб. мат. журн., 13:578-586, 1972.

В. Г. Фляйшер, Об эндоморфизмах свободных полигонов. Уч. записки Тартус. ун-та, 1974, вып. 336, 189-105.

П. Нормак, О нетеровых и конечно представимых полигонах. Уч.

записки Тартус. ун-та, 1977, вып. 431, 37- Л. А. Скорняков, О гомологической классификации моноидов. Сиб.

мат. журн., 10:5 (1969), 1139–1143.

А. В. Михалев 7, И. Б. Кожухов 8 (Россия), У. Кнауэр 9, С. БуллманФлеминг 10, М. Петрич 11 и др. И. Б. Кожухов исследовал подпрямо неразложимые полигоны, т.е. полигоны, не разложимые в нетривиальное подпрямое произведение. Он доказал, что если порядки всех подпрямо неразложимых полигонов над полугруппой ограничены в совокупности, то полугруппа периодическая. Все подпрямо неразложимые полигоны состоят не более чем из двух элементов тогда и только тогда, когда полугруппа является полурешеткой 12.

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

В работе В. И. Кима 13 полугруппа изотонных отображений O ( X, Y ) конечной цепи X в конечную цепь Y рассматривалась как биполигон над полугруппами O ( X, X ) слева и O (Y, Y ) справа. Было доказано, что биполигон O ( X, Y ) порожден одним элементом.

M. Kilp, U. Knauer, A. V. Mikhalev, Monoids, Acts and Cathegories. De Gruyter Exp. Math., 29, Walter de Gruyter, Berlin, 2000.

И. Б. Кожухов, Условия конечности для подпрямо неразложимых полигонов и модулей. Фундамент. и прикл. матем., 4:2 (1998), 763–767.

U. Knauer, P. Normak, Hereditary endomorphism monoids of projective acts. Manuscripta math., 70:133-143, 1991.

S. Bulman-Fleming, Pullback-flat acts are strongly flat. Canad. Math.

Bull., 34:456-461, 1991.

U. Knauer, M. Petrich, Characterization of monoids by torsion-free, flat, projective, and free acts. Arch. Math., 36:289-294, 1981.

I. B. Kozhuhov, One characteristical property of semilattices.

Commutations In Algebra, 25(8), 2569-2577, 1997.

V. I. Kim, On isotone mappings of partially ordered set. 6-th International Algebraic Conference in Ukraine, 2007, 99-100.

Если полугруппа или семейство полугрупп имеют простое строение, то полигоны или мультиполигоны над ними могут быть описаны. В работе А. Ю. Авдеева и И. Б. Кожухова 14 было получено в теоретико-множественных терминах полное описание полигонов над прямоугольной связкой. В качестве следствий из этой теоремы получались описания полигонов над полугруппами левых и правых нулей. В другой работе этих же авторов 15 было приведено полное описание полигонов над прямоугольной группой. Позже авторам удалось получить описание полигонов над вполне простыми и вполне 0простыми полугруппами 16, что обобщало предыдущие результаты.

В настоящей работе некоторые из этих результатов переносятся на случай биполигонов и мультиполигонов над полугруппами левых и правых нулей: доказана теорема о строении биполигонов над двумя рисовскими матричными полугруппами с нулями, получено полное описание ( L1, L2 ), ( R1, R2 ), ( L, R ), ( R, L ) -биполигонов, где L, L1, L2 полугруппы левых нулей, R, R1, R2 полугруппы правых нулей. Получено полное описание мультиполигонов над семействами полугрупп, каждая из которых является полугруппой левых или правых нулей.

Цели и задачи исследования данной работы заключаются в исследовании алгебраического строения полигонов над полурешетками и мультиполигонов над семействами полугруппам специального вида (полугруппами левых и правых нулей и т.д.).

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

А. Ю. Авдеев, И. Б. Кожухов, Полигоны над полугруппами простого строения. Труды шестых математических чтений РГСУ, Москва, 1999, 103-107.

А. Ю. Авдеев, И. Б. Кожухов, Полигоны над прямоугольными группами. 12-я международная конференция “Проблемы теоретической кибернетики”, Нижний Новгород, 1999, стр. 5.

A. Yu. Avdeev, I. B. Kozhuhov, Acts over completely 0-simple semigroups. Acta Cybernetica, 14:4 (2000), 523-531.

Личный вклад автора. В диссертации изложены результаты, полученные как лично автором, так и совместно с научным руководителем проф. Кожуховым И. Б. Постановки задач выполнены совместно с научным руководителем.

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

Научная новизна. В диссертации получен ряд результатов о строении полигонов над цепями, биполигонов и мультиполигонов над полугруппами специального вида. Полученные результаты являются новыми.

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

2. Описание полигонов над конечной цепью и связных полигонами над какой-либо цепью.

3. Выяснение строения мультиполигона над семейством 4. Описание мультиполигонов над семействами полугрупп Практическая и теоретическая значимость. Работа носит теоретический характер. Полученные в ней результаты могут быть использованы в структурной теории полугрупп и (мульти)полигонов.

Апробация работы. Результаты диссертации неоднократно докладывались на научно-исследовательском семинаре “Кольца и модули” кафедры высшей алгебры МГУ, а также на следующих конференциях: 14-й и 15-й Международных конференциях “Проблемы теоретической кибернетики” (Пенза, 2005, Казань, 2008); 14-х и 15-х математических чтениях РГСУ (Москва, 2005, 2006); Международной алгебраической конференции, посвященной 100-летию И. Г.

Конторовича и 70-летию Л. Н. Шеврина (Екатеринбург, 2005); 12-й и 13-й Всероссийских межвузовских конференциях “Микроэлектроника и информатика” (Москва, МИЭТ, 2005, 2006); Международном семинаре по компьютерной алгебре и информатике (Москва, МГУ, 2005); 6-й и 7й Международных алгебраических конференциях на Украине (КаменецПодольский, 2007; Харьков, 2008); Международной алгебраической конференции, посвященной 100-летию А. Г. Куроша (Москва, МГУ, 2008); 1-м международном семинаре “Дискретная математика и ее приложения” (Москва, МГУ, 2010); 7-й Международной конференции “Алгебра и теория чисел” ( Тула, 2010).

Публикации. По теме диссертации опубликовано 17 работ, в том числе 2 в рецензируемых научных журналах, рекомендованных ВАК.

Структура диссертации. Диссертация состоит из введения, трех глав, разбитых на параграфы, списка литературы и списка публикации автора по теме диссертации. Общий объем работы составляет 88 страниц. Список литературы включает 49 наименований.

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

Первая глава посвящена изучению полигонов над полурешетками.

Правым полигоном над полугруппой S (или правым S полигоном) называется множество X, на котором действует полугруппа S, причем ( xs1 ) s2 = x ( s1 s2 ) при x X, s1, s2 S. Левый полигон определяется двойственным образом. Нижним конусом элемента x частично упорядоченного множества X называется множество x = { y X | y x}.

Установлен ряд свойств полигонов над полурешетками. А именно, доказано, что всякий полигон X над полурешеткой S является частично упорядоченным множеством относительно порядка (предложение 1.2). Доказано, что нижний конус любого элемента является полурешеткой (предложение 1.3).

Естественным образом возникают 2 вопроса:

1) как устроен полигон над данной полурешеткой S ?

упорядоченное множество, чтобы оно являлось полигоном над какой-нибудь полурешеткой?

Необходимые условия (т.е. частичный ответ на 1-й вопрос) дают уже упомянутые предложения 1.2, 1.3. Однако, эти условия не являются достаточными: в работе приведен пример 7-элементного частично упорядоченного множества, которое удовлетворяет вышеприведенным условиям, но не является полигоном ни над какой полурешеткой.

Важным частным случаем полурешетки является линейно упорядоченное множество, т.е. цепь. Для полигонов над цепями можно поставить такие же вопросы 1 и 2, какие были сформулированы для полурешетки. Доказано, что если частично упорядоченное множество X является полигоном над цепью, то нижний конус любого его элемента является деревом (предложение 1.6). Доказана теорема о строении полигонов над конечной цепью:

Теорема 1.7. Пусть п натуральное число и X частично упорядоченное множество, обладающее свойствами:

пересекающихся подмножеств X 0, X 1,..., X n ;

(3) X 0 состоит из одного элемента (будем считать, что X 0 = {u0 }) ;

Тогда X является полигоном над цепью S. Наоборот, всякий связный полигон над конечной цепью устроен таким образом.

В случае произвольных цепей (не обязательно конечных) полный ответ на вопрос №2 получен для связных частично упорядоченных множеств. При помощи леммы Цорна получено необходимое и достаточное условие того, что связное частично упорядоченное множество является полигоном над некоторой цепью:

Теорема 1.13. Связное частично упорядоченное множество X является полигоном над некоторой цепью в том и только том случае, если X дерево.

Для несвязных частично упорядоченных множеств получены некоторые достаточные условия того, что данное множество является полигоном над цепью (предложения 1.14, 1.15, 1.16, 1.17).

Обозначим категорию левых полигонов над полугруппой S через S Act, а категорию правых S -полигонов через Act S. Автором отмечено, что категории левых полигонов над полугруппой изоморфна категории правых полигонов над дуальной полугруппой:

над свободными комутативными полугруппами (теорема 1.21).

Вторая глава посвящена изучению биполигонов над полугруппами специального вида.

Биполигон S X T (или ( S, T ) -биполигон) – это множество, на котором действуют полугруппа S слева и полугруппа T справа, причем действия этих полугрупп перестановочны, т.е. ( sx ) t = s ( xt ) при x X, s S, t T. Унитарный биполигон над моноидами S и T – это такой ( S, T ) -биполигон, в котором единицы моноидов действуют тождественно. Категорию ( S, T ) -биполигонов будем обозначать через S Act T, а категорию унитарных ( S, T ) -биполигонов через Из упомянутого ранее изоморфизма категорий полигонов легко получается следующий результат:

Теорема 2.1. Для произвольных моноидов M 1, M 2 имеет место следующий изоморфизм категорий В теоретико-множественных терминах описано строение произвольных биполигонов над двумя моноидами:

Теорема 2.4. Пусть выполнены условия:

(a) M Y, Z M унитарные полигоны над моноидами M1, M 2 ;

(b) C = Y Z – биполигон, являющийся подполигоном полигонов Y и Z ;

|Y тождественные отображения множеств Z и Y ;

умножения других элементов из X на элементы моноидов M 1 слева и элементы из M 2 справа, полагая при m2 M 2, x X \ Z. Тогда X станет ( M 1, M 2 ) -биполигоном.

Наоборот, каждый биполигон над моноидами M 1, M 2 изоморфен биполигону, полученному таким образом.

Понятие подбиполигона может быть определено двумя не эквивалентными друг другу способами, причем оба определения естественны. А именно, непустое подмножество Y ( S, T ) -биполигона X называется подбиполигоном биполигона X в узком смысле, если SY Y и YT Y ; Y – подбиполигон в широком смысле, если SYT Y.

При помощи теоремы 2.4 описаны все подбиполигоны (в узком и широком смыслах) биполигона над моноидами (теоремы 2.9 и 2.10).

M1, M 2 моноиды. Подмножество F X будет подбиполигоном в узком смысле в том и только том случае, если F можно представить в виде F = G1 G2 H, где H A, G1 подполигон унитарного G1 G2 унитарный подбиполигон биполигона CM 2 (см. теорему 2.4) M1, M 2 моноиды. Подмножество F X будет подбиполигоном в широком смысле в том и только том случае, если F можно подбиполигон биполигона CM 2 (см. теорему 2.4) и выполнено условие Используя результаты, полученные И. Б. Кожуховым и А. Ю.

Авдеевым15, автор доказывает теорему о строении биполигонов над двумя рисовскими матричными полугруппами с нулем.

X множество с некоторым элементом 0 (который назовем нулем).

Далее, пусть ( H ) и ( H ' ) семейства подгрупп групп G и G ' копроизведения унитарных левых G - и правых G ' - полигонов соответственно. Наконец, пусть для любых i I,, j I ', i : X Q, ' j : X Q ', удовлетворяющие условиям:

где, ' нули S и S ' соответственно. Тогда X ( S, S ' ) - биполигон.

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

Получено полное описание ( L1, L2 ), ( R1, R2 ), ( L, R ), ( R, L ) L, L1, L2 полугруппы R, R1, R2 полугруппы правых нулей (теоремы 2.16, 2.20, 2.14), а также их подбиполигонов в широком и узком смыслах (теоремы 2.18, 2.19, 2.22, 2.23, 2.26, 2.27). В частности, доказаны следующие теоремы.

отношения эквивалентности на множестве X и = sup( 1, 2 ). Для любых q Q, r R пусть Yq, Yr подмножества множества X, являющиеся множествами представителей классов отношений 1, соответственно, т.е. для любых q Q, r R, x X Пусть при этом для любого -класса K существует a K такое, что при любых r R, q Q выполняются условия:

Определим на множествах Q и R операции, полагая r1r2 = r2 при r1, r2 R и q1q2 = q2 при q1, q2 Q. Тогда Q и R будут являться полугруппами правых нулей. Определим действия этих полугрупп на множестве X, полагая Тогда X будет являться ( L, R ) -биполигоном (где Q op = L). Наоборот, ( L, R ) -биполигон, где L полугруппа левых нулей, а R любой полугруппа правых нулей, изоморфен биполигону, построенному таким способом.

Теорема 2.18. Пусть X ( Q, R ) -биполигон, где Q и R полугруппы правых нулей. Подмножество A X будет подбиполигоном X в узком смысле тогда и только тогда, когда Теорема 2.19. Пусть X ( Q, R ) -биполигон, где Q и подбиполигоном X в узком смысле тогда и только тогда, когда В третьей главе изучаются мультиполигоны. Мультиполигон над семейством {Si | i I } полугрупп – это множество X, на котором Ясно, что понятие мультиполигона обобщает понятия полигона и биполигона.

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

Вначале отмечено, что в унитарном случае мультиполигон над моноидами может быть сведен к обычному полигону:

Теорема 3.1. Категория унитарных {Si | i I } мультиполигонов изоморфна категории унитарных правых полигонов над В неунитарном случае также можно сводить мультполигоны к обычным полигонам, но здесь формулировка выглядит сложнее.

Теорема 3.2. Пусть выполнены условия:

(a) {Yi | i I } семейство унитарных полигонов над моноидами являющийся подполигоном полигонов Yi и Y j ;

i |Y тождественные отображения множеств Yi ;

Доопределим действия Yi M i Yi до умножения других элементов из X на элементы моноидов M i, полагая при mi M i, x X i. Тогда X станет Наоборот, всякий мультиполигон над семейством моноидов устроен таким образом.

На основе теорем главы 2 доказываются теоремы о строении мультиполигонов над семействами полугрупп левых и правых нулей (теоремы 3.3, 3.4, 3.5). В частности, доказана следующая теорема.

Теорема 3.3. Пусть X, {Ri | i I } произвольные непустые множества, i отношение эквивалентности на X для каждого i I и ij = sup{ i, j } для всех i, j I, i j. Для каждого r Ri положим Yri множества представителей каждого i соответственно, т.е.

Пусть для каждого x X, для всех i, j I i j существует элемент a Kij (где K ij ij -класс элемента x ) такой, что выполняются условия Для r1, r2 Ri положим r1r2 = r2. Тогда Ri будут полугруппами правых нулей для всех i I. Положим ( x X, r Ri ). Тогда X будет мультиполигоном над семейством полугрупп правых нулей {Ri | i I }. Наоборот, всякий мультиполигон над семейством полугрупп правых нулей будет изоморфен мультиполигону, полученному таким способом.

Автор выражает глубокую благодарность своему научному руководителю – доктору физико-математических наук, профессору Игорю Борисовичу Кожухову за постановку задач и постоянному вниманию к работе.

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В

СЛЕДУЮЩИХ РАБОТАХ:

[1] М. Ю. Максимовский, О полигонах над полурешётками.

Фундаментальная и прикл. матем., 14:7 (2008), 151–156.

[2] М. Ю. Максимовский, О биполигонах и мультиполигонах над полугруппами. Матем. заметки, 87:6 (2010), 855–866.

В прочих изданиях:

(в работах в соавторстве соискателю принадлежит 50% результатов) [3] И. Б. Кожухов, М. Ю. Максимовский, Об автоматах над полурешетками. “Системный анализ и управление”, сборник научных трудов под ред. В. А. Бархоткина, Москва, 2006 г., 19-34.

[4] М. Ю. Максимовский, Биавтоматы над рисовскими матричными полугруппами. Сборник научных трудов “Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем”, под ред. В. А. Бархоткина, Москва, 2008 г., 104-109.

[5] И. Б. Кожухов, М. Ю. Максимовский, Биполигоны и мультиполигоны над некоторыми классами полугрупп. Материалы 14-й Международной конференции “Проблемы теоретической кибернетики”, Пенза, 2005, 64.

[6] И. Б. Кожухов, М. Ю. Максимовский, О биполигонах и мультиполигонах над полугруппами. Материалы 14-х математических чтений РГСУ, Москва, 2005, 39-43.

[7] И. Б. Кожухов, М. Ю. Максимовский, О мультиполигонах над полугруппами. Материалы Международной алгебраической конференции, Екатеринбург, 2005, 12-13.

[8] М. Ю. Максимовский, Биполигоны и мультиполигоны над полугруппами определенного вида. Материалы докладов 12-й Всероссийской межвузовской конференции “Микроэлектроника и информатика”, Москва, МИЭТ, 2005, 180.

[9] И. Б. Кожухов, М. Ю. Максимовский, О полигонах над цепями.

Материалы 15-х математических чтений РГСУ, Москва, 2006, 67-71.

[10] И. Б. Кожухов, М. Ю. Максимовский, О строении счетных полигонов над цепями. Материалы 13-й Всероссийской межвузовской конференции “Микроэлектроника и информатика”, Москва, МИЭТ, 2006, 155.

[11] M. Yu. Maksimovskiy, Biacts over Rees matrix semigroups.

Материалы 6-th International Algebraic Conference in Ukraine, 2007, 133И. Б. Кожухов, М. Ю. Максимовский, О полигонах над полурешетками. Материалы международной алгебраической конференции, посвященной 100-летию А. Г. Куроша, Москва, МГУ, 2008, 125-126.

[13] И. Б. Кожухов, М. Ю. Максимовский, Автоматы над свободными коммутативными полугруппами. Материалы 15-й международной алгебраической конференции “Проблемы теоретической кибернетики”, Казань, 2008, 50.

[14] M. Yu. Maksimovski, On multiacts over right zero semigroups.

Материалы 7-th International Algebraic Conference in Ukraine, 2009, 94М. Ю. Максимовский. О подбиполигонах биполигонов.

Материалы 10-го международного семинара “Дискретная математика и ее приложения”, Москва, МГУ, 2010г., с 189-190.

[16] М. Ю. Максимовский, О мультиполигонах над полугруппами.

Материалы 7-й Международной алгебраической конференции “Алгебра и теория чисел”, Тула, 2010, 126-127.

[17] И. Б. Кожухов, М. Ю. Максимовский, Действия коммутативных полугрупп идемпотентов на множествах. Вестник МГАДА, 2010, вып. 5.

Подписано в печать:

Заказ № Тираж 100 экз. Уч.-изд.л. 0,8. Формат 60х84 1/ Отпечатано в типографии МИЭТ (НИУ).

124498, Москва, МИЭТ (НИУ).