Введение к работе
Актуальность исследования. Исследование полугрупп преобразований, сохраняющих структуру множества, является интересной и важной задачей общей алгебры. К таким полугруппам относятся, в частности, полугруппы эндоморфизмов графов, полугруппы непрерывных преобразований топологических пространств, полугруппы отображений частично упорядоченных множеств, сохраняющих порядок (т.е. изотонных).
Хорошо известно, что любая полугруппа вкладывается в полугруппу преобразований некоторого множества. Этот факт свидетельствует о важности полугруппы преобразований в теории полугрупп. Если на данном множестве задана некоторая структура (например, отношение порядка), то естественно рассматривать полугруппы таких отображений, которые сохраняют данную структуру. Данная диссертация посвящена изучению полугрупп изотонных частичных и многозначных преобразований частично упорядоченных и квазиупорядоченных множеств.
Свойства полугруппы изотонных преобразований Т<^(Х) изучались многими авторами. Л.М. Глускин1 доказал, что полугруппа Т<^(Х) определяет квазиупо-рядоченное множество X с точностью до изоморфизма или антиизоморфизма. А. Я. Айзенштат2 получила представление полугруппы Т^(Х) образующими элементами и определяющими соотношениями в случае, когда X — цепь из п элементов. В другой работе А. Я. Айзенштат3 получила описание частично упорядоченных множеств X, у которых полугруппа Т<^(Х) регулярна. В случае счетной цени X более прозрачные условия регулярности получили В. И. Ким и И. Б. Кожухов4. Комбинаторным аспектам полугруппы Т<^(Х) посвящена работа А. Умара и А. Ла-раджи5.
Возможны различные подходы к пониманию изотонности частичных преобразований. В работе предложены два неэквивалентных способа этого.
1ГлускинЛ.М. Полугруппы изотонных преобразований // Успехи мат. наук, 1961, 5 (101), 16, с.157-162.
2 Айзенштат А. Я. Определяющие соотношения полугруппы эндоморфизмов конечного ли
нейного упорядоченного множества // Сиб. мат. журн. 1962. т.З, №2. с.161-169.
3 Айзенштат А. Я. Регулярные полугруппы эндоморфизмов упорядоченных множеств // Уч.
зап. Ленинградского гос. пед. ин-та им. А.И.Герцена, 1968, т.387, с.3-11.
4 Ким В. И., Кожуховії. Б. Условия регулярности полугрупп изотонных преобразований счет
ных цепей // Фунд. и прикл. матем. 2006. 12, №8. с.97-104.
5LaradjiA., UmarA. Combinatorial results for semigroups of order-preserving partial transformations // King Fahd Univ. of Petroleum & Minerals (Sandi Avabia), Dept. Math. Sci. Technical Report Series. 2004. p. 1-18.
Хорошо известно6, что полугруппы полных преобразований Т(Х) и частичных преобразований РТ(Х) регулярны для любого множества X. Полугруппа бинарных отношений В(Х) регулярна при \Х\ ^ 2 и нерегулярна при \Х\ ^ 3. Известны7 условия регулярности отдельного элемента О" Є В(Х).
Естественно поставить вопрос о том, при каких условиях на частично упорядоченное множество (X, ^) (^ — отношение порядка) полугруппа частичных отображений, сохраняющих отношение ^, является регулярной. В работе получен исчерпывающий ответ для обоих вариантов сохранения ^ частичным отображением. Кроме этого, описание продолжено на случай, когда частичный порядок заменён квазипорядком.
Многозначные отображения — это в точности бинарные отношения на множестве X. Придерживаясь аналогии с Т(Х): можно сформулировать, что означает сохранение бинарного отношения а элементами из В{Х). В работе предложено два определения. Очевидно, что каждое из них сужает полугруппу В(Х) до некоторого подмножества. Оказывается, что в обоих случаях эти подмножества образуют полугруппы с единицей (т.е. моноиды).
Множество X с заданным на нём бинарным отношением а можно рассматривать как ориентированный граф с множеством вершин X. Из вершины х в вершину у идёт ребро тогда и только тогда, когда пара (ж, у) принадлежит а. Гомоморфизм графов (X, сг) и (У, т) — это отображение а множества вершин графа X в Y, сохраняющее рёбра (т.е., если пара (ж, х') принадлежит <т, то пара (ха, х'а) должна принадлежать г). Понятие гомоморфизма графов допускает усиления8.
В теории полугрупп важное значение имеют отношения Грина. Хорошо известно9, что в полугруппе полных преобразований неупорядоченного множества X отношения Грина М и можно выразить через ядра и образы этих преобразований. Интересно выяснить, что произойдёт, если вместо Т(Х) взять Т<^(Х) и РТ^(Х). Прежние утверждения в общем случае перестанут быть верными. В данной работе получены результаты для случая, когда X - цепь.
Отношения Грина непосредственно связаны с отношениями делимости одного
элемента на другой. Именно, Л можно выразить через отношения левой делимо-
6КлиффордА., ПрестонГ. Алгебраическая теория полугрупп, тт. 1,2 // М., «Мир», 1972. 7ЗарецкийК. А. Полугруппа бинарных отношений // Матем. сб., 1963, 61 (ЮЗ), 3, с.291-305. 8B6ttcherM., KnauerU. Endomorphism spectra of graphs // Discrete Mathematics 109 (1992) p.45-57, North-Holland.
9КлиффордА., ПрестонГ. Алгебраическая теория полугрупп, тт.1,2.2 // М., «Мир», 1972.
сти, а М — через отношение правой делимости.
Элемент а может не делиться на Ъ в полугруппе S: но делиться в какой-нибудь надполугруппе, содержащей S. Так возникает понятие потенциальной делимости. В данной работе доказано совпадение отношений делимости и потенциальной делимости в полугруппе В(Х).
Полугруппа В(Х) бинарных отношений на множестве X — это фактически полугруппа матриц X х X с элементами из булевой алгебры {0,1}. Можно рассматривать более общий случай матриц над дистрибутивной решёткой L. Для матриц конечного размера достаточно требования дистрибутивности решётки L, в противном случае необходимо условие типа бесконечной дистрибутивности. В ряде работ рассматривались матрицы конечных и бесконечных размеров не только над решёткой {0,1}, но и над другими дистрибутивными решётками. Теория булевых матриц обстоятельно изложена в известной монографии Кима10. Отношения Грина для матриц над булевыми алгебрами изучались В. Б. Поплавским11. В данной работе рассмотрено, как устроены отношения потенциальной левой и правой делимости, а также обобщённые отношения Грина J^1*\М* в полугруппе матриц над дистрибутивными решётками для некоторых типов решёток.
Объектом исследования в работе являются полугруппы частичных и многозначных изотонных преобразований частично упорядоченных, а также квазиупо-рядоченных множеств.
Описание классов отношений Грина, нахождение условий регулярности полугрупп частичных и многозначных изотонных преобразований различных частично упорядоченных и квазиупорядоченных множеств является предметом исследования.
Цели и задачи исследования данной работы заключаются в исследовании алгебраического строения полугрупп изотонных частичных и многозначных преобразований частично упорядоченных и квазиупорядоченных множеств.
Методы исследования. В работе использованы методы алгебраической теории полугрупп и теории частично упорядоченных множеств. Для проверки некоторых гипотез и получения информации о строении полугрупп был использован компьютер.
Научная новизна. В диссертации получен ряд результатов о строении полу-
10Кіт К. Н. Boolean matrix theory and applications // Marcel Dekker Inc., 1982. 11 ПоплавскийВ. Б. О рангах, классах Грина и теории определителей булевых матриц // Дискрета, матем., 2008, т.20, вып. 4, с.42-60.
групп изотонных частичных и многозначных преобразований множеств, на которых задано бинарное отношение, в частности, частично упорядоченных и квази-упорядоченных множеств. Полученные результаты являются новыми. Основные положения, выносимые на защиту
1. Определения понятия сохранения бинарного отношения а элементом полу
группы частичных отображений РТ(Х) [элементом полугруппы
В(Х) бинарных отношений] и связи между ними.
Необходимые и достаточные условия регулярности полугрупп РТ^(Х) и РТ^(Х) для квазиупорядоченного множества X и полугруппы В<^(Х) для частично упорядоченного множества X.
Связь между отношением левой [правой] делимости на полугруппах Та(Х): РТа(Х) и образами [ядрами] элементов из Та(Х), РТа(Х) для случая, когда сг — линейный порядок.
Совпадение отношений левой [правой] делимости и потенциальной левой [правой] делимости в полугруппе квадратных матриц над полной дистрибутивной решёткой.
Совпадение делимости и потенциальной делимости, а также совпадение отношений Грина &: Л и обобщённых отношений Грина М*, J* в полугруппе В(Х).
Практическая и теоретическая значимость. Габота носит теоретический характер. Её методы и результаты могут быть использованы для дальнейшего изучения изотонных полугрупп преобразований (в частности, полугрупп частичных преобразований, а также многозначных преобразований).
Личный вклад автора. В диссертации изложены результаты, полученные автором лично. Доказательства теорем и получение результатов численного моделирования получены автором самостоятельно. Постановка задачи выполнена совместно с научным руководителем.
Достоверность результатов полученных в данной работе, определяется обоснованными теоретическими выкладками и строгими доказательствами, опирающимися на методы алгебраической теории полугрупп и теории частично упорядоченных множеств.
Апробация работы. Результаты диссертации докладывались на научно-исследовательском семинаре «Кольца и модули» кафедры высшей алгебры МГУ им. М.В.Ломоносова, на Международной научной конференции «Современные проблемы дифференциальной геометрии и общей алгебры» (Саратов, СГУ, 2008 год), на 77th Workshop on General Algebra (Потсдам, 2009 год), на 16-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2009» (Москва, МИЭТ, 2009 год), на IV Всероссийской научно-методической конференции «Проблемы современного математического образования в вузах и школах России. Оценка качества математических знаний студентов и школьников» (Киров, ВятГГУ, 2009 год) и на Седьмой Международной Алгебраической Конференции в Украине (Харьков, 2009).
Публикации. По теме диссертации опубликовано 9 работ, из них 1 статья в журнале из списка ВАК.
Структура и объём диссертации. Диссертация состоит из введения и трёх глав, разбитых на 9 параграфов. Текст диссертации изложен на 91 странице, содержит 22 рисунка. Список литературы содержит 63 наименования.
