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

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

Полигоны и мультиполигоны над некоторыми классами полугрупп тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Максимовский, Михаил Юрьевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Полигоны и мультиполигоны над некоторыми классами полугрупп»

Автореферат диссертации на тему "Полигоны и мультиполигоны над некоторыми классами полугрупп"

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

005003209

МАКСИМОВСКИЙ Михаил Юрьевич

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

01.01.06 — математическая логика, алгебра и теория чисел'

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Казань - 2011

- 1 ДЕК 2011

005003209

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

Научный руководитель:

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

Кожухов Игорь Борисович

Официальные оппоненты: доктор физико-математических наук,

профессор

Молчанов Владимир Александрович,

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

Чермпых Василий Владимирович

Ведущая организация:

ГОУ ВПО «Московский Государственный Университет им. М.В. Ломоносова»

Защита диссертации состоится «{5"» 20Ц года в

часов на заседании диссертационного ЬЪвета Д 212.081.24 при ФГАО-УВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, д. 35, копферепц-зал библиотеки им. Н.И. Лобачевского КФУ.

С диссертацией можно ознакомиться в библиотеке им. Н.И. Лобачевского по адресу: 420008, г. Казань, ул. Кремлевская, д. 35. Автореферат диссертации опубликован па сайте ФГАОУВПО «КФУ» (www.ksu.su).

Автореферат разослан «_

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

А.И. Еникеев

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

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

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

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

1Б.И. Плоткин, Л.Я. Гринглаз, A.A. Гварамия. Элементы алгебраической теории автоматов // М.-.Высшая школа, 1994.

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

3Ляпин Е.С., Евсеев А.Е. Частичные алгебраические действия // СПб.: Образование, 1991.

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

Вышеназванными вопросами занимались многие математики России и зарубежья: М. Кильп, В. Фляйшер, П. Нормак, Л. А. Скорняков, А. В. Михалев, И. В. Кожухов, М.Я. Комарницкий, Г.В. Зе-лиско, У. Кнауэр, С. Булман-Флеминг, М. Петрич. A.A. Степановой5 изучались теоретико-модельные свойства полигонов. Т. С. Фофанова6'7'8 исследовала полигоны с заданной на них структурой полурешетки над дистрибутивной решеткой, булевой алгеброй или цепью. На полигоны в этих статьях накладываются дополнительные условия дистрибутивности. И. Б. Кожухов исследовал подпрямо неразложимые полигоны. Он доказал, что если порядки всех подпрямо неразложимых полигонов над полугруппой ограничены в совокупности, то полугруппа периодическая. Все подпрямо неразложимые полигоны состоят не более чем из двух элементов, тогда и только тогда, когда полугруппа является полурешеткой9.

В. И. Ким в своей работе10 рассматривал множество изотонных отображений О (X, Y) частично упорядоченного множества X в частично упорядоченное множество Y как биполигон над полугруппами О (X, X) слева и О (У, У) справа.

4Скорняков Л.А. О гомологической классификации моноидов // Сиб. мат. журн. 1969. Т. 10, № 5, - С. 1139-1143.

5Михалев A.B., Овчиникова Е.В., Палютин Е.А., Степанова A.A. Теоретико-модельные свойства регулярных полигонов // Фундаментальная и прикл. матем. -2004. Т. 10 № 4. - С. 107-157.

6Фофанова Т.С. Полигоны над дистрибутивными решетками // Сибирский математический журнал. 1971. Т. 11, № 5. - С. 1195-1199.

7Фофанова Т.С. Инъективность полигонов над булевыми алгебрами // Сибирский математический сборник. 1972. Т. 13, №2. - С. 452-458.

8Фофанова Т.С. Об инъективных полигонах над цепями // Mathematics Slovaca. 1978. Т. 28, № 1. -С. 21-33.

9I<ozhukhov I. One characteristical property of semilattices // Comm. In Algebra. 1997. T. 25, № 8. - C. 2569-2577.

10Kim V.l. On isotone mapping of partially ordered set // 6-th International Algebraic Conference in Ukraine. Kamenets-Podolsky, 2007. - C. 99-100.

Если полугруппы имеют простое строение, то полигоны или муль-типолигоны над ними могут быть описаны. В работе11 было приведено полное описание полигонов над прямоугольной группой. В другой статье этих же авторов12 были описаны все полигоны над вполне простыми и вполне 0-простыми полугруппами, из чего следует описание полигонов над полугруппами левых и правых нулей.

В настоящей работе некоторые из этих результатов переносятся на случай мультиполигонов над семействами полугрупп левых и правых нулей: получено полное описание мультиполигонов над семействами полугрупп, каждая из которых является полугруппой левых или правых нулей и, как следствие, выяснено строение (Li, L2), (ДьЛг), {Ь,Я), (R,L)-биполигонов, где L, Li, ¿2 — полугруппы левых нулей, R, R2 — полугруппы правых нулей. Доказана теорема о строении биполигонов над двумя рисовскими матричными полугруппами с нулями.

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

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

Личный вклад автора. В диссертации изложены результаты, полученные как лично автором, так и в соавторстве. В работах в соавторстве автору принадлежит 50% результатов

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

Научная новизна. В диссертации получен ряд результатов о

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

12Avdeyev A.Yu., Kozhukhov I.В. Acts over completely 0-simple semigroups // Acta Cybernet. 2000. T. 14, № 4. - C. 523-531.

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

Основные положения, выносимые на защиту.

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

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

3. Выяснение строения мультиполигонов над семейством моноидов.

4. Описание мультиполигонов над семействами полугрупп левых и правых нулей.

5. Доказательство того, что в общем случае 5 х Т-полигон не является (5, Т)-биполигоном.

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

МГУ, 2005); 6-й, 7-й и 8-й Международных алгебраических конференциях на Украине (Каменец-Подольский, 2007; Харьков, 2009; Луганск, 2011); Международной алгебраической конференции, посвященной 100-летию А. Г. Куроша (Москва, МГУ, 2008); 10-м международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 2010); 7-й Международной конференции "Алгебра и теория чисел" ( Тула, 2010).

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Правым полигоном над полугруппой 5 (или правым Б-полигоном) называется множество X, на котором действует полугруппа 51, причем (хзх)з2 = 2(5132) при х е X, 52 6 5. Левый полигон определяется двойственным образом. Частичный полигон — это множество X, для которого задано частичное отображение X х 5 —» X, причем для любых х е X, € Я произведения я^) и существуют или не существуют одновременно и х{зЬ) = {хв^ в случае, если оба этих выражения существуют. Полурешеткой называется частично упорядоченное множество, в котором любое конечное подмножество имеет точную нижнюю грань.

Нижним конусом элемента х частично упорядоченного множества X называется множество = {у € Х\у < а:}.

Установлен ряд свойств полигонов над полурешетками. А именно, доказано, что всякий полигон X над полурешеткой 5 является частично упорядоченным множеством относительно порядка

х < у х £ yS1

(предложение 1.3). Доказано, что нижний конус любого элемента является полурешеткой (предложение 1.4).

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

1. Как устроен полигон над данной полурешеткой 5"?

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

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

Для формулировки ответа на вопрос №2 введем следующее обозначение. Пусть X — произвольное частично упорядоченное множество. Обозначим через Ф(Х) множество отображений ip : X X, удовлетворяющих условиям:

(г) Vs, y(iXx<y=>xip<yip (т.е. ip изотопно); (ii) Vx £ X xip < х (<р — уменьшающее); (Hi) ip2 = ip (<p — идемпотентное); (iv) Vi, у G X(x = xtpky<x=>y = yip). Показано, что Ф(^) — полурешетка (следствие 1.8). Формулируется и доказывается теорема о необходимом и достаточном условии на частично упорядоченное множество, чтобы оно являлось полигоном над некоторой полурешеткой:

Теорема 1.9. Пусть X — частично упорядоченное множество. Тогда X является полигоном над некоторой полурешеткой в том и только том случае, если полугруппа Ф(Х) действует на X тран-зитивно, т.е.

Vx, у € X [х < у =*> 3<р в Ф(Х) (:х = yip)).

Как и в случае обычных полигонов, для частичного полигона X над полурешеткой 5 доказано (предложение 1.16), что X является частично упорядоченным множеством относительно порядка

х <у<=} х = у или х = уя при некотором в £ 5.

Пусть X — частичный полигон над полурешеткой 5. Мы будем говорить, что частичный полигон X продолжается до полного, если частичное отображение X х 5 -» X продолжается до обычного отображения X х Б X я выполняется аксиома полигона (хв^ — х(з<). Одно интересное свойство частичных полигонов над полурешетками отмечает следующее предложение.

Предложение 1.18. Пусть X — частичный полигон над полурешеткой 5. Если для каждого х е X нижний конус является полурешеткой, то для любых х, у е X, лежащих в одной компоненте связности и любого 5 е 5 произведение Х5 определено тогда и только тогда, когда уа определено.

Достаточное условие продолжаемости частичного полигона X над полурешеткой 5 до полного полигона дает -

Теорема 1.20. Пусть X — частично упорядоченное множество, являющееся частичным полигоном над полурешеткой 5. Если каждая компонента связности имеет наименьший элемент, то частичный полигон X продолжается до полного полигона.

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

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

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

пью в том и только том случае, если X — дерево.

Получен ответ на вопрос №1 в случае, если X — полигон над конечной цепью:

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

(г) X — дерево;

(п) X представимо в виде объединения попарно не пересекающихся подмножеств Хо, Х\,..., Хп;

(Ш ) Ха состоит из одного элемента (будем считать, что Хо =

Ы);

(гь) если х е Х{, у £ X] иг < з, то у ^ х.

Пусть Б — {ао, аь ...,ап_1} — цепь (а0 < а\ < ... < ап-\). Для элементов х € X и а^ € 51 положим

х ■ а.] = тах(жу П (Х0 и Хг и ... и X,)).

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

Для несвязных частично упорядоченных множеств получено достаточное условие того, что частично упорядоченное множество X является полигоном над цепью:

Предложение 2.8. Пусть X = и Ха — частично упорядо-

аеп

ченное множество, причём Ха — различные компоненты связности множества X и каждое Ха является полигоном над цепью Га. Предположим, что существует цепь С такая, что для каждого а € П определено сюръективное гомоморфное отображение Га. Тогда X можно сделать полигоном над цепью С.

Однако, как показано в дальнейшем, такая цепь Т не всегда существует даже для двух цепей Г*, Г 2 (пример 2.9). Теорема 2.11 дает необходимое и достаточное условие существование цепи Г для совокупности цепей, имеющих минимальные элементы.

Теорема 2.11. Пусть {Га | а 6 П} — совокупность цепей, имеющих минимальные элементы. Цепь Г, которая сюръективно и гомоморфно отображается на каждую цепь Га, существует тогда и только тогда, когда минимальные конфинальные подцепи каждой Га упорядочены по одному типу.

В третьей главе изучаются биполигоны и мультиполигоны над некоторыми классами полугрупп. Биполигон (или (£, Т)-бипо-

лигон) - это множество, на котором действуют полугруппа 5 слева и полугруппа Т справа, причем действия этих полугрупп перестановочны, т.е. (sz) t = s (xt) при x 6 X, s £ 5, í E Т. Мультиполигон над семейством {5¿|i £ /} полугрупп — это множество X, на котором действуют полугруппы Si, причем действия этих полугрупп перестановочны (т.е. (xsi)sj = (xsj)si при i 6 X, s¡ 6 Si, Sj & Sj, i ф j). Ясно, что понятие мультиполигона обобщает понятия полигона и биполигона.

Унитарный мультиполигон над семейством моноидов € I} — это такой {Sj|¿ 6 /}-мультиполигон, в котором единицы моноидов действуют тождественно. Категорию (S, Т)-биполигонов будем обозначать через S—Act — T, а категорию унитарных (5, Т)-биполигонов через S - UAct - Т.

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

Теорема 3.4. Категория унитарных {^г 6 /}- мультиполигона в изоморфна категории унитарных правых полигонов над дискретным прямым произведением Si моноидов S¡.

¿е/

С помощью теоремы 3.4 показано, что в случае унитарных би-полигонов над моноидами имеет место изоморфизм категорий Mi — UAct - М2 = UAct - (М°р х М2) (следствие 3.5).

Построен пример (пример 3.9) (S х Т)-полигона, который нельзя свести к (S, Т)-биполигону.

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

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

(a) {Yi\i Е 1} — семейство унитарных полигонов над моноидами {Mili е 1};

(b) Yj — подмножества множества X для всех г £ /;

(d) для каждого г £ I задано отображение tpi : X —> Yi, причем <p¡\y¡ — тождественное отображение множества Ye,

(e) tpi(ipj{x)mj) = <pj(<pi{x))mj для всех х € X, rrij е Mj.

Доопределим действия Y¡ х Mi —>• Yi до умножения других элементов из X на элементы моноидов Mi, полагая

xrrii = <pi{x)rrii

при ТТЦ € Mi, X e X. Тогда X станет {M<|i e 1}-мультиполигоном. Наоборот, всякий мулътиполигон над семейством моноидов устроен таким образом.

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

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

(a) MlY, Zm2 ~ унитарные полигоны над моноидами М\, М2\

(b) С — YDZ — биполигон, являющийся подполигоном полигонов У и Z\

(c)А — множество такое, что А П (У U Z) = 0;

(d) Х = AUYUZ]

(e) I/J : X Z и ip X Y — такие отображения, что <p\z и ф\у — тождественные отображения множеств Z и У;

(f) <f(miip(x)) = mii>(v{x)) и iр(<р(х)т2) = tp(rp(x))m2 при х 6 X, mi е Mi, т2 € Mi-

Доопределим действия Mi х У Y и Z х М2 Z до умножения других элементов из X на элементы моноидов М\ слева и элементы из М2 справа, полагая

mix = miip{x)

при mi е Mi, х 6 X\Y и

ХГП2 - <p{x)ni2

при т2 е М2, х е X\Z. Тогда X станет (Мь М2)-биполигоном. Наоборот, каждый биполигон над моноидами М\,М2 изоморфен би-полигону, полученному таким образом.

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

Теорема 3.15. Пусть S = M°(G, /, Л, Р) и S' = М°(С, /', Л', Р') — рисовские матричные полугруппы и X — множество с некоторым элементом 0 (который назовем нулем). Далее, пусть (На) и (Н'д) - семейства подгрупп групп G и G' соответственно, Q =

Ц(С/Яа)ПО- = П(С'/^)110 - копроизведения унитарных лесе р

вых С- и правых полигонов соответственно. Наконец, пусть для любых { е I, X в А, j £ Г, ц е Л', существуют отображения к\ : <] 4 : $ X, т : X -> С}, тг} : X ->■ <?', удовлетворяющие условиям: (1) Ока = Оя» = 0/см = Оя^- = 0; (2) = 9 * рлг, = о ¿кя любых д е д' е <Э'; (3,) (((5 * хщ)кх)ъ] о 5')/4и = (5 * ((хтг^ о для есеэ: х € X, 9 е О, д' е С.

Положим для х е X, (д)г\ € £ 5

за; = {д)^х = (5 * хв' = х{д').^ = (жтг^ о = = 0,

где в, в1 — нули 5 и 5' соответственно. Тогда X — (5,5') - бипо-лигон. Кроме того, любой биполигон над рисовскими матричными полугруппами с нулем устроен таким образом.

Получено полное описание мультиполигонов (теоремы 3.18, 3.21, 3.24) и биполигонов (теоремы 3.19, 3.22, 3.25) над семействами полугрупп левых и правых нулей. В частности, над семейством полугрупп правых нулей.

Теорема 3.18. Пусть X, {Д|г £ 1} - произвольные непустые множества, о-, — отношение эквивалентности на X для каждого 16 I и С7{: - Бир{(Т;,для всех 1,3 £1,1 ф 3- Для каждого г е Яг положим Уг* — множества представителей каждого С; соответственно, т.е. для всех г £ /, г е Щ, х € X

|У;П1С7<| = 1.

Пусть для каждого х е X, для всех г,;' 6 I г ф з существует элемент а € Кц (где ЛТу - -класс элемента х) такой, что выполняются условия

У; П Кц С ааь

У; П аог = {а}.

Для г и г2 6 Дг положим гхг2 = г2. Тогда будут полугруппами правых нулей для всех г 6 I. Положим

ХТ - X1 в УГ' П X СТг

(х £ X, г £ В^. Тогда X будет мультиполигоном над семейством полугрупп правых нулей {Я;|г 6 !}• Наоборот, всякий муль-типолигон над семейством полугрупп правых нулей будет изоморфен мультиполигону, полученному таким способом.

Теорема 3.19. Пусть Х,С^,В — множества, а\, а2 — отношения эквивалентности на множестве X и т = зир(сг1,сг2). Для любых 9 £ <2, г £ Я пусть У9, Уг — подмножества множества X, являющиеся множествами представителей классов отношений а\, <72 соответственно, т.е. для любых д € г £ В., х Е X

|У9 П азс71| = 1 и |УгПжсг2| = 1-

Пусть при этом для любого т-класса К существует а £ К такое, что при любых г 6 Я, ? £ <? выполняются условия:

Уг П К С ааи УЯГ)К С аа2

Уг П а(Т2 = {«}, Уд П а<71 = {а}.

Определим на множествах <2 и В. операции, полагая Тхг2 = г2 при гьг2 6 В. и 91 <72 = ?2 при 91,92 6 Я- Тогда С) и В. будут являться полугруппами правых нулей. Определим действия этих полугрупп на множестве X, полагая

хг = х 1 6 Уг Л ха2 {х £ X, г 6 Я)

хд = х2 € У9 П х<тх (х £ X, д €

Тогда X будет являться (Ь, В)-биполигоном (где Яор = Ь). Наоборот, любой (£,, Я)-биполигон, где Ь — полугруппа левых нулей, а В — полугруппа правых нулей, изоморфен биполигону, построенному таким способом.

Понятие подбиполигона может быть определено двумя не эквивалентными друг другу способами, причем оба определения естественны. А именно, непустое подмножество У (5, Т)-биполигона X называется подбиполигоном биполигона X в узком смысле, если 5У С У и УТ С У; У - подбиполигон в широком смысле, если 5УГ СКВ случае унитарных биполигонов эти-опредеяения-еоеттад-ают:--

При помощи теоремы 3.11 описаны (с точностью до унитарных подбиполигонов) все подбиполигоны (в узком и широком смыслах) биполигона над моноидами (теоремы 3.29 и 3.30).

Теорема 3.29.Пусть X - (М\,М2)-биполигон, где Мг, М2 -моноиды. Подмножество Р С X будет подбиполигоном в узком смысле в том и только том случае, если Р можно представить в виде Р = и С?2 и Н, где Н С А, С?1 — подполияон унитарного полигона <32 — подполигон унитарного полигона Zм1, П<32 — унитарный подбиполигон биполигона (см- теорему 3.9) и

выполнены условия: и Н) С вг, и Я) С С2.

Теорема 3.30. Пусть X - (Мь М2)-биполигон, где М\, М2 — моноиды. Подмножество Р С X будет подбиполигоном в широком смысле в том и только том случае, если Р можно представить в виде Р = 01иС2иН, где Н С А, С У, 02 С 2 - подмножества такие, что ОС?2 — унитарный подбиполигон биполигона м^Мг (см. теорему 3.9) и выполнено условие <р(т/>(Р)) СС[П £?2.

Наконец, с помощью теорем о строении биполигонов над полугруппами левых и правых нулей (теоремы 3.19, 3.22, 3.25) получено полное описание всех подбиполигонов (в узком и широком смыслах) этих биполигонов (теоремы 3.31, 3.32, 3.33, 3.34, 3.35, 3.36). Для биполигонов над полугруппами правых нулей результат выглядит следующим образом.

Теорема 3.31. Пусть X — {С}, В)-биполигон, где £> и Я. - полугруппы правых нулей. Подмножество АС X будет подбиполигоном

X в узком смысле тогда и только тогда, когда х^П (и Уч) С А и

960

х&2 П ( и Уг) С А. гея

Теорема 3.32. Пусть X - (<?, В)-биполигон, где Ц ий- полугруппы правых нулей. Подмножество А С X будет подбиполигоном X в широком смысле тогда и только тогда, когда и (жо^ПУ^сгП

У Уг С А для всех х € А. т-еЯ

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ В журналах из списка ВАК

1. Максимовский М.Ю. О полигонах над полурешетками // Фундамент. и прикл. матем. 2008. Т. 14, № 7. - С. 151-156.

2. Максимовский М.Ю. О биполигонах и мультиполигонах над полугруппами // Матем. заметки. 2010. Т. 87, № б. - С. 855-866.

3. Апраксина Т.В., Максимовский М.Ю. Полигоны и частичные полигоны над полурешетками // - Москва. МИЭТ. 2011. - 10с. Деп. в ВИНИТИ 17.10.2011, №454-В2011

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

4. Кожухов И.Б., Максимовский М.Ю. Об автоматах над полурешетками // "Системный анализ и управление", сборник научных трудов под ред. проф. В.А. Бархоткина. - Москва. 2006. -С. 19-34.

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

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

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

8. Кожухов И.Б., Максимовский М.Ю. О мультиполигонах над полугруппами // Материалы Международной алгебраической конференции, поев. 70-летию Л.Н. Шеврина и 100-летию И.Г. Конторовича. - Екатеринбург. 2005. -С. 12-13.

9. Максимовский М.Ю. Биполигоны и мультиполигоны над полугруппами определенного вида // Материалы докладов 12-й Всероссийской межвузовской конференции "Микроэлектроника и информатика". - Москва. МИЭТ. 2005. -С. 180.

10. Кожухов И.Б. О полигонах над цепями // Материалы 15-х математических чтений РГСУ. - Москва. 2006. -С. 67-71.

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

12. Maksimovskiy M. Yu. Biacts over Rees matrix semigroups // Материалы 6-й межд. алг. конф. на Украине. Каменец-Подольский. 2007. -С. 133-134.

13. Кожухов И.Б., Максимовский М.Ю. О полигонах над полурешетками // Материалы международной алгебраической конференции, посвященной 100-летию А. Г. Куроша. - Москва. МГУ. 2008. - С. 125-126.

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

15. Maksimovskiy M.Yu. On multiacts over right zero semigroups // Материалы 7-й межд. алг. конф. на Украине. Харьков. 2009. -С. 94-95.

16. Максимовский М.Ю. О подбиполигонах биполигонов // Материалы 10-го Международного семинара "Дискретная математика и ее приложения". - Москва. МГУ. 2010. - С. 189-190.

17. Максимовский М.Ю. О мультиполигонах над полугруппами // Материалы 7-й Международной алгебраической конференции "Алгебра и теория чисел". - Тула. 2010. - С. 126-127.

18. Кожухов И.Б., Максимовский М.Ю. Действия коммутативных полугрупп идемпотентов на множествах // Вестник МГАДА. 2010. № 5. - С. 84-90.

19. Кожухов И.Б., Макашовский М.Ю., Ревякин A.M. Частично упорядоченные множества, являющиеся полигонами над полурешетками // Материалы 10-й М1жвуз1вський науково-прак-тичний семшар "Комбшаторш конф1гурацп та ix заслосування - 2010". - Кировоград. 2010. - С. 81-89.

20. Лукиных И.А., Максимовский М.Ю. Минимальное частично упорядоченное множество, не являющееся полигоном ни над какой полурешеткой // Материалы 18-й Всероссийской мужву-зовской научно-технической конференции "Микроэлектроника и информатика - 2011". - Москва. МИЭТ. 2010. - С. 126.

21. Kozhuhov I.B., Maksimovskiy M.Yu. On the connections of acts with biacts // Материалы 8-й межд. алг. конф., поев, памяти проф. В.М. Усенко. - Луганск. 2011. - С. 262.

Подписано в печать: Заказ № щ . Тираж 100 экз. Уч.-изд.л. 0,9. Формат 60x84 1/16 Отпечатано в типографии МИЭТ (НИУ). 124498, Москва, МИЭТ (НИУ).

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Максимовский, Михаил Юрьевич

Введение

1 Полигоны и частичные полигоны над полурешетками

1.1 Основные понятия теории полигонов и частичных полигонов

1.2 Свойства полигонов над полурешетками.

1.3 Условия для полигона над полурешеткой.

1.4 Частичные полигоны над полурешетками.

2 Полигоны над цепями

2.1 Свойства полигонов над цепями.

2.2 Деревья с условием минимальности.'

2.3 Полигоны над конечными цепями.

2.4 Несвязные полигоны над цепями.

3 Мультиполигоны над некоторыми классами полугрупп

3.1 Унитарные биполигоны и мультиполигоны.

3.2 Связь полигонов с биполигонами.

3.3 Неунитарные биполигоны и мультиполигоны.

3.4 Биполигоны и мультиполигоны над полугруппами левых и правых нулей.

3.5 Подбиполигоны биполигонов.

Введение диссертация по математике, на тему "Полигоны и мультиполигоны над некоторыми классами полугрупп"

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

Актуальность темы исследования. Полигоны над полугруппой, т.е. множества, на которых действует полугруппа, возникают в разных разделах алгебры и ее приложений. Понятие полигона является алгебраическим выражением понятия автомата [9, 11] (точнее, автомата Мура, т.е. автомата без выхода). Это означает, что все работы по алгебраической теории автоматов можно рассматривать как относящиеся к теории полигонов. Если обычный полигон над полугруппой является алгебраической интерпретацией автомата, то мультиполигоны можно интерпретировать как автоматы с несколькими входными алфавитами. Кроме того, полигон над полу- ,, группой является универсальной алгеброй, операции в которой — унарные (умножения на элементы полугруппы). Частичный полигон является частичной универсальной алгеброй [12].

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

Понятие полигона над полугруппой аналогично понятию модуля над кольцом, ввиду чего теория полигонов развивалась под большим влиянием теории колец и модулей. Гомологическая классификация колец, т.е. исследование свойств кольца по свойствам категории модулей над этим кольцом, вызвала аналогичные вопросы в теории полигонов. По аналогии с модулями рассматривались артиновы и нетеровы, инъективные и проективные, плоские и свободные полигоны и т.д. Этими вопросами занимались многие математики России и зарубежья: М. Кильп [4, 28], В. Фляйшер [19, 20], П. Нормак [16, 31] (Эстония), Л. А. Скорняков [17], А. В. Михалев [3, 13, 28], И. Б. Кожухов [1, 2, 6, 24, 30] (Россия), М.Я. Комарницкий, Г.В. Зелиско [7] (Украина), У. Кнауэр [28, 31, 32], С. Булман-Флемипг [26], М. Петрич [32] и др. В работах [3, 13, 18] исследовались теоретико-модельные свойства полигонов. И. Б. Кожухов исследовал подпрямо неразложимые полигоны, т.е. полигоны, не разложимые в нетривиальное подпрямое произведение. Он доказал, что если порядки всех подпрямо неразложимых полигонов над полугруппой ограничены в совокупности, то полугруппа периодическая. Все подпрямо неразложимые полигоны состоят не более чем из двух элементов тогда и только тогда, когда полугруппа является полурешеткой [30].

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

В работе В. И. Кима [29] множество изотонных отображений О (X, У) частично упорядоченного множества X в частично упорядоченное множество У рассматривалась как биполигон над полугруппами О (X, X) слева и О (У, У) справа. Было доказано, что в случае, когда X и У — конечные цепи, биполигон О (X, У) порожден одним элементом.

Т. С. Фофанова [21, 22, 23] исследовала полигоны с заданной на них структурой полурешетки над дистрибутивной решеткой, булевой алгеброй или цепью. На полигоны в этих статьях накладывались дополнительные условия дистрибутивности.

Аналогия теории полигонов над полугруппами с теорией модулей над кольцами хорошо прослеживается в работе В. В. Неклюдовой [14]: там рассматривались прямые пределы семейств полигонов над полугруппами с системой локальных единиц, доказано их существование и получены представления полигонов и полугрупп в виде прямых пределов. В ее же статье [15] было доказано, что две полугруппы с системой локальных единиц обладают эквивалентными категориями нечетких полигонов над ними тогда и только тогда, когда полугруппы Морита-эквивалентны.

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

В настоящей работе некоторые из этих результатов переносятся на случай биполигонов и мультиполигонов над полугруппами левых и правых нулей: доказана теорема о строении биполигонов над двумя рисовскими матричными полугруппами с нулями, получено полное описание (1/1,1,2), (^1,-^2), (Ь, Л), (Я, 1/)-биполигонов, где 1/1, Ь2 — полугруппы левых нулей, /?,, /?2 — полугруппы правых нулей, а также полное описание мультиполигонов над семействами полугрупп, каждая из которых является полугруппой левых или правых нулей.

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

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Максимовский, Михаил Юрьевич, Москва

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

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

3. Гоулд В., Михалев A.B., Палютин Е.А. Теоретико-модельные свойства свободных, проективных и плоских S-полигонов // Фундаментальная и прикл. матем. 2008, Т. 14, № 7. С. - 63-110.

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

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

6. Кожухов И.Б. Условия конечности для подпрямо неразложимых полигонов и модулей // Фундаментальная и прикл. матем. 1998. Т. 4 № 2. С. 763-767.

7. Комарницький М.Я. Елементи теори нашвгруп та полшошв. Курс лек-щй // Лыпв, 2011.

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

9. Кудрявцев В.Б., Алешин С.В., Подколзин A.C. Введение в теорию автоматов // М.:Наука, 1985.

10. Курош А.Г. Теория групп // М.:Наука, 1969.

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

12. Ляпип Е.С., Евсеев А.Е. Частичные алгебраические действия // СПб.: Образование, 1991.

13. Михалев A.B., Овчиникова Е.В., Палютии Е.А., Степанова A.A. Теоретико-модельные свойства регулярных полигонов // Фундаментальная и прикл. матем. -2004. Т. 10 № 4. С. 107-157.

14. Неклюдова В.В. Полигоны над полугруппами с системами локальных единиц // Фундаментальная и прикладная математика. 1997. Т. 3, N° 3. С. 879-902.

15. Неклюдова В.В. Морита-эквивалентность моноидов и эквивалентность категорий нечетких полигонов // Фундаментальная и прикладная математика. 1997. Т. 3, № 1. С. 179-194.

16. Нормак П. О нетеровых и конечно представимых полигонах // Уч. записки Тартус. ун-та. 1977. № 431. С. 37-46.

17. Скорняков Л.А. О гомологической классификации моноидов // Сиб. мат. журн. 1969. Т. 10, № 5, С. 1139-1143.

18. Степанова A.A. Аксиоматизируемость и модельная полнота класса регулярных полигонов // Сиб. матем. журн. 1994. Т. 35, № 1. С. 181-193

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

20. Фляйшер В.Г. Определяемость свободного полигона его полугруппой эндоморфизмов // Уч. записки Тартус. ун-та. 1975. Na 366. С. 27-41.

21. Фофанова Т.С. Полигоны над дистрибутивными решетками // Сибирский математический журнал. 1971. Т. 11, № 5. С. 1195-1199.

22. Фофанова Т.С. Инъективность полигонов над булевыми алгебрами // Сибирский математический сборник. 1972. Т. 13, №2. С. 452-458.

23. Фофанова Т.С. Об инъективных полигонах над цепями // Mathematica Slovaca. 1978. Т. 28, № 1. -С. 21-33.

24. Avdeev A.Yu., Kozhuhov I.B. Acts over completely 0-simple semigroups // Acta Cybernet. 2000. Т. 14, № 4. С. 523-531.

25. Bogdanovic S., Ciric M., Petkovic T. Decomposition of automata and transition semigroup // Acta Cybernet. T. 13 № 4. C. 385-404.

26. Bulman-Fleming S. Pullback-flat acts are strongly flat // Canad. Math. Bull. 1991. № 34. C. 456-461.

27. Esik Z., Imreh B. Subdirectly irreducible commutative automata // Acta Cybernet. 1981. T. 5, № 3. C. 251-260.

28. Kilp M., Knauer U., Mikhalev A.V. Monoids, Acts and Cathegories // Berlin. Walter de Gruyter. 2000.

29. Kim V.l. On isotone mapping of partially ordered set // 6-th International Algebraic Conference in Ukraine. Ukraine, 2007. C. 99-100.

30. Kozhuhov I. One characteristical property of semilattices // Comm. In Algebra. 1997. T. 25, № 8. C. 2569-2577.

31. Knauer U., Normak P. Hereditaly endomorphism monoids of projective acts // Manuscripta math. 1991. № 70. C. 133-143.

32. Knauer U., Petrich M. Characterisation of monoids by torsion-free, flat, projective, and free acts // Arch. Math. 1981. № 36. C. 289-294.

33. Mach A., Moszner Z. Translation equation on monoids // Annales Polonici Matematici. T. 84, № 2. C. 137-146.

34. Wang Q.,Wismath S.L Generalized inflation and null extensions // Discuss. Math. Gen. Algebra Appl. 2004. T. 24, № 2. C. 225-249Работы автора по теме диссертации

35. Кожухов И.Б., Максимовский М.Ю. Об автоматах над полурешетками // "Системный анализ и управление", сборник научных трудов под ред. Бархоткина. Москва. 2006. - С. 19-34.

36. Максимовский М.Ю. Биавтоматы над рисовскими матричными полугруппами // Сборник научных трудов "Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем", под ред. Бархоткина. Москва. 2008. -С. 104109.

37. Максимовский М.Ю. О полигонах над полурешетками // Фундамент, и прикл. матем. 2008. Т. 14, № 7. С. 151-156.

38. Максимовский М.Ю. О биполигонах и мультиполигонах над полугруппами // Матем. заметки. 2010. Т. 87, № 6. С. 855-866.

39. Апраксина Т.В., Максимовский М.Ю. Полигоны и частичные полигоны над полурешетками // Москва. МИЭТ. 2011. - 10с. Деп. в ВИНИТИ 17.10.2011, №454-В2011

40. Кожухов И.В., Максимовский М.Ю. Биполигоны и мультиполигоны над некоторыми классами полугрупп // Материалы 14-й Международной конференции "Проблемы теоретической кибернетики". Пенза. 2005. - С. 64.

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

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

43. Максимовский М.Ю. Биполигоны и мультиполигоны над полугруппами определенного вида // Материалы докладов 12-й Всероссийской межвузовской конференции "Микроэлектроника и информатика". -Москва. МИЭТ. 2005. -С. 180.

44. Кожухов И.В., Максимовский М.Ю. О полигонах над цепями // Материалы 15-х математических чтений РГСУ. Москва. 2006. -С. 67-71.

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

46. Maksimovskiy М. Yu. Biacts over Rees matrix semigroups // Материалы 6-th International Algebraic Conference in Ukraine. Украина. 2007. -С. 133-134.

47. Кожухов И.Б., Максимовский М.Ю. О полигонах над полурешетками // Материалы международной алгебраической конференции, посвященной 100-летию А. Г. Куроша. Москва. МГУ. 2008. - С. 125-126.

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

49. Maksimovskiy M.Yu. On multiacts over right zero semigroups // Материалы 7-th International Algebraic Conference in Ukraine. Украина. 2009. С. 94-95.

50. Максимовский М.Ю. О подбиполигонах биполигонов // Материалы 10-го международного семинара "Дискретная математика и ее приложения". Москва. МГУ. 2010. - С. 189-190.

51. Максимовский М.Ю. О мультиполигонах над полугруппами // Материалы 7-й Международной алгебраической конференции "Алгебра и теория чисел". Тула. 2010. - С. 126-127.

52. Кожухов И.Б., Максимовский М.Ю. Действия коммутативных полугрупп идемпотентов на множествах // Вестник МГАДА. 2010. № 5. -С. 84-90.

53. Kozhuhov I.B., Maksimovskiy M.Yu. On the connections of acts with biacts // Материалы 8-th International Algebraic Conference in Ukraine dedicated to the memory of Professor V.M Usenko. Луганск. 2011. - С. 262.