Полугруппы частичных и многозначных изотонных преобразований

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

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

Ярошевич, Владимир Александрович АВТОР

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

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

2009 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Полугруппы частичных и многозначных изотонных преобразований»

Автореферат диссертации на тему "Полугруппы частичных и многозначных изотонных преобразований"

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

ЯРОШЕВИЧ Владимир Александрович

ПОЛУГРУППЫ ЧАСТИЧНЫХ И МНОГОЗНАЧНЫХ ИЗОТОННЫХ ПРЕОБРАЗОВАНИЙ

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

АВТОРЕФЕРАТ

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

-3

ДЕН 2009

Ульяновск — 2009

003486564

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

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

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

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

Официальные оппоненты:

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

Вечтомов Евгений Михайлович,

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

Поплавский Владислав Брониславович

Ведущая организация: ГОУ ВПО «Московский Государственный

Университет имени М.В. Ломоносова»

Защита диссертации состоится «16» декабря 2009 года в Ю00 часов на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном ушши>-ситете по адресу: ул. Набережная р. Свияги, 106, копр. 1, ауд. 703.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, с авторефератом — на сайте вуза http://www.uni.ulsu.ru

Автореферат разослан «14» ноября 2009 г.

Отзывы по данной работе просим направлять по адресу: 432000, г. Ульяновск, ул. Л.Толстого, д. 42, УлГУ, Управление научных ипледотшиП

Ученый секретарь диссертационного совета

М.Л Волков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Свойства полугруппы изотонных преобразований Т^(Х) изучались многими авторами. JI.M. Глускин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. Sei. Technical Report Series. 2004. p.1-18.

Хорошо известно6, что полугруппы полных преобразований Т(Х) и частичных преобразований РТ(Х) регулярны для любого множества X. Полугруппа бинарных отношений В{Х) регулярна при |Х| ^ 2 и нерегулярна при |Л"| > 3. Известны7 условия регулярности отдельного элемента сг £ В(Х).

Естественно поставить вопрос о том, при каких условиях на частично упорядоченное множество (X, $:) — отношение порядка) полугруппа частичных отображений, сохраняющих отношение является регулярной. В работе получен исчерпывающий ответ для обоих вариантов сохранения ^ частичным отображением. Кроме этого, описание продолжено на случай, когда частичный порядок заменён квазипорядком.

Многозначные отображения — это в точности бинарные отношения на множестве X. Придерживаясь аналогии с Т(Х), можно сформулировать, что означает сохранение бинарного отношения а элементами из В(Х). В работе предложено два определения. Очевидно, что каждое из них сужает полугруппу В(X) до некоторого подмножества. Оказывается, что в обоих случаях эти подмножества образуют полугруппы с единицей (т.е. моноиды).

Множество X с заданным на нём бинарным отношением а можно рассматривать как ориентированный граф с множеством вершин X. Из вершины х в вершину у идёт ребро тогда и только тогда, когда пара (х,у) принадлежит п. Гомоморфизм графов (X, <т) и (У,т) — это отображение о. множества вершин графа X в У, сохраняющее рёбра (т.е., если пара (х,.?;') принадлежит и, то пара (ха, х'а) должна принадлежать т). Понятие гомоморфизма, графов допускает усиления8.

В теории полугрупп важное значение имеют отношения Грина. Хорошо известно9, что в полугруппе полных преобразований неупорядоченного множества X отношения Грина М и JS? можно выразить через ядра и образы этих преобразований. Интересно выяснить, что произойдёт, если вместо Т(Х) взять Т^(Х) и РТ^{Х). Прежние утверждения в общем случае перестанут быть верными. В данной работе получены результаты для случая, когда X - цепь.

Отношения Грина непосредственно связаны с отношениями делимости одного элемента на другой. Именно, 5£ можно выразить черед отношения левой делимо-

еКлиффорцА., ПрестонГ. Алгебраическая теория полугрупп, тт. 1,2 Ц М., «Мир», 1972.

7ЗарецкпйК. А. Полугруппа бинарных отношений // Матем. сб., 1963, 61 (103), 3, с.291-305.

8DdttcherМ., KnauerU. Endomorphism spectra of graphs // Discrete Mathematics 109 (1992) p.45-57, North-Holland.

9КллффордА., ПрестонГ. Алгебраическая теория полугрупп, тт.1,§2.2 // М., «Мир», 1972.

сти, a M -- через отношение правой делимости.

Элемент а может не делиться на b в полугруппе S, но делиться в какой-нибудь надполугруппе, содержащей S. Так возникает понятие потенциальной делимости. В данной работе доказано совпадение отношений делимости и потенциальной делимости в полугруппе В(Х).

Полугруппа В(Х) бинарных отношений на множестве X — это фактически полугруппа матриц X х X с элементами из булевой алгебры {0,1}. Можно рассматривать более общий случай матриц над дистрибутивной решёткой L. Для матриц конечного размера достаточно требования дистрибутивности решётки L, в противном случае необходимо условие типа бесконечной дистрибутивности. В ряде работ рассматривались матрицы конечных и бесконечных размеров не только над решёткой {0,1}, но и над другими дистрибутивными решётками. Теория булевых матриц обстоятельно изложена в известной монографии Кима10. Отношения Грина для матриц над булевыми алгебрами изучались В. Б. Поплавским11. В данной работе рассмотрено, как устроены отношения потенциальной левой и правой делимости, а также обобщённые отношения Грина в полугруппе

матриц над дистрибутивными решётками для некоторых типов решёток.

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

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

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

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

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

10Ют К. Н. Boolean matrix theory and applications // Marcel Dekker Inc., 1982.

"ПоплавскипВ. Б. О рангах, классах Грима и теории определителей булевых матриц // Дискрета. матем., 2008, т.20, вып. 4, с.42-60.

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

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

1. Определения понятия сохранения бинарного отношения а элементом полугруппы частичных отображений РТ(Х) [элементом полугруппы

В(Х) бинарных отношений] и связи между ними.

2. Необходимые и достаточные условия регулярности полугрупп РТ^(Х) и РТ^(Х) для квазиупорядоченного множества X и полугруппы Вц{Х) для частично упорядоченного множества X.

3. Связь между отношением левой [правой] делимости на полугруппах Та[Х), РТ„(Х) и образами [ядрами] элементов из Т„(Х), РТа(Х) для случая, когда а — линейный порядок.

4. Совпадение отношений левой [правой] делимости и потенциальной левой [правой] делимости в полугруппе квадратных матриц над полной дистрибутивно('| решёткой.

5. Совпадение делимости и потенциальной делимости, а также совпадение отношений Грина и обобщённых отношений Грина М*, Л?* в полугруппе В{Х).

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

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

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

Апробация работы. Результаты диссертации докладывались на научно-исследовательском семинаре «Кольца и модули» кафедры высшей алгебры МГУ им. М. В. Ломоносова, на Международной научной конференции «Современные проблемы дифференциальной геометрии и общей алгебры» (Саратов, СГУ, 2008 год), на 77th Workshop on General Algebra (Потсдам, 2009 год), на 16-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2009» (Москва, МИЭТ, 2009 год), на IV Всероссийской научно-методической конференции «Проблемы современного математического образования в вузах и школах России. Оценка качества математических знаний студентов и школьников» (Киров, ВятГГУ, 2009 год) и на Седьмой Международной Алгебраической Конференции в Украине (Харьков, 2009).

Публикации. По теме диссертации опубликовано 9 работ, из них 1 статья в журнале из списка ВАК.

Структура и объём диссертации. Диссертация состоит из введения и трёхглав, разбитых на 9 параграфов. Текст диссертации изложен на 91 странице, содержит 22 рисунка. Список литературы содержит 63 наименования.

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

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

Для изложения результатов введём определения. Пусть X — произвольное множество, Т(Х) — полугруппа всех отображений а : X —» X с умножением x(aß) = [xa)ß (х 6 X, a,ß е Т(Х)). Далее, РТ(Х) — множество частичных отображений а : X —> X, т.е. отображений, определённых, возможно, не для всех х £ X. Обозначим через domo область определения отображения о. Множество РТ(Х) также является полугруппой: умножение в ней производится по правилу

Пусть а С X х X — бинарное отношение на множестве X и а £ Т{Х). Мы

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

(xa)ß, если х £ doma и xa £ dom/3, не определено в противном случае.

будем говорить, что отображение а сохраняет а, если

Ух, у £ X (:х, у) £ <7 => (xa, ya) е <т. (1)

Предложение 1.1 Отобраокение а £ Т(Х) сохраняет отношение а в том и только в том случае, если

а а С аа. (2)

Для частичного отображения а £ РТ(Х) квазиупорядоченного (даже частично упорядоченного) множества. X предложение, аналогичное предложению 1.1, неверно, и можно определить двумя различными неэквивалентными способами, что означает фраза «а е РТ(Х) сохраняет а С X х Хъ. А именно,

Определение 1.2 а £ РТ(Х) допустимо для а с X х X, если

Ух, у £ dorn а (.т, у) £ а (a-a, уа) £ а. (3)

Определение 1.3 а £ РТ(Х) согласуется с а С X х X, если

аа С аа. (4)

Пусть РТа(Х) = {а£ РГ(ЛГ)| а допустимо для <т}, РТП(Х) = {а 6 РТ{Х)\ а согласуется с er}. Очевидно, РТ„(Х) и РТа{Х) — моноиды, являющиеся подмо-ноидами моноида РТ{Х). Следующее предложение показывает, что РТ<,(Х) С РТа{Х).

Предложение 1.4 Для любого а £ РТ(Х) справедлива импликация (4) => (3), но существуют примеры таких а £ РТ(Х), для которых (3) (4).

Лемма 1.5 Из условия (4) следует условие

Ух,у £ X ((х,у) £ a k у £ doma => х £ doma). (5)

Предложение 1.6 Для любого а £ РТ(Х) имеет место импликация (3)&(5)

(4).

Для элементов полугруппы В(Х) введём два неэквивалентные определения сохранения а:

Определение 1.7 Элемент а £ В(Х) сохраняет а в узком смысле, если Vx, у £ X V«, V £ X (и £ xa k v 6 ya к {х,у) £ а => (u,v) £ а).

Определение 1.8 Элемент а £ В(Х) сохраняет а в широком смысле, если

Положим Ва(Х) = {а € В(Х) | а сохраняет а в узком смысле} и В^{Х) — {а £ В{Х) | а сохраняет а в широком смысле}.

Предложение 1.9 Ва{Х) и В'а(Х) — моноиды.

Ни одна из полугрупп В„(Х) и В'„{Х) в общем случае не содержит другую (найдены соответствующие примеры).

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

Разберём сначала случай, когда X — частично упорядоченное множество.

Теорема 2.1 Если (X, — частично упорядоченное множество, то полугруппа В^(Х) регулярна в том и только 7пом случае, когда X — цепь или антицепь.

Пусть теперь X — квазиупорядоченное множество.

Теорема 2.2 Пусть (Х,^) — квазиупорядоченное множество. Тогда РТ^{Х) регулярна тогда и только тогда, когда выполняется хотя бы одно из следующих условий: (а) X — антицепь; (б) X — цепь; (в) х ^ у при всех х, у.

Следствие 2.3 Пусть (X, — частично упорядоченное множество. Тогда полугруппа РТ^(Х) регулярна, если и только, если выполняется хотя бы одно из следующих условий: (а) X — антицепь; (б) X — цепь.

Для произвольного множества I пусть G[ = {х'о} U {ж;|г 6 /} — множество с отношением порядка таким, что Хо < ж,- при всех г £ I, а элементы а:, (г £ I) несравнимы (рис. 1).

Vz, у 6 X (з;, у) £ а => (3и е ха Эг) 6 уа : {и, v) £ а).

я;,

Рис. 1: Множество G;

Теорема 2.4 Пусть (X, — квазиупорядочепное множество, не являющееся линейно упорядоченным. Полугруппа РТ^(Х) регулярна в том и только том случае, если выполняется хотя бы одно из следующих условий: (а) X — антицепь; (б) X = б/ при некотором I; (в) х ^ у для любых х,у € X.

Следствие 2.5 Пусть (X, — частично упорядоченное множество, не являющееся линейно упорядоченным. Полугруппа РТ^(Х) регулярна в том и только том случае, если выполняется хотя бы одно из следующих условий: (а) X — антицепь; (б) X = й] при некотором I.

Рассмотрим теперь такие бинарные отношения а на множестве X = {1,2,... ,77.}, что Д С а С ш, где и — линейный порядок и а1 = ш (здесь а* обозначает транзитивное замыкание отношения а). Пример такого а представлен на рис. 2. Далее будут приведены некоторые необходимые и некоторые достаточные условия регулярности полугруппы Т„(Х) всех полных отображений а : X —> X, сохраняющих отношение а.

Рис. 2: Пример бинарного отношения а (Д С а С ш, <т( = и)

Теорема 2.6 Если ТП(Х) при га ^ 4 регулярна, то (1,п) £ <т.

Назовем весом отношения а количество таких пар (г,£ а, что г < и г+1 ^ j (на рис. 2 вес равен количеству рёбер, которые не являются прямыми отрезками). Обозначим (То = {(к,к + 1)|1 < к < п - 1}.

Теорема 2.7 (а) Если вес а равен 1 при п > 4, то Та{Х) регулярна тогда и только тогда, когда (1 , п) £ а; (б) если вес а равен 2 и п нечётно, то Та{Х) нерегулярна; (в) если вес а равен 2 и п четно, то Т„{Х) регулярна тогда и только тогда, когда существует такое г, что а = {(1, п), (г, г + §)} и <хо-

Найдена серия отношений а (рис. 3), для которых Та{Х) регулярна. Это

а ={(1,п)} и {(»,»-[—])} и <го,

Теперь уберём условие конечности множества X и рассмотрим частичные отображения.

Предложение 2.8 Пусть сг — бинарное отношение на множестве X такое, что А С а С и а1 = ш, где ш — линейный порядок. Если полугруппа РТ„(Х) регулярна, то а = и.

Рис. 3: Пример <х, когда Та — регулярная полугруппа (п = 6)

Третья глава диссертации посвящена исследованию свойств отношения левой [правой] делимости и потенциальной левой (правой] делимости, а также отношений Грина М, Л£ и обобщённых отношений Грина SI* ^ Л£*.

Для произвольной полугруппы S положим S1 = S U {1}. Отношения левой и правой делимости в S можно записать так:

a^ib <=> S1 а С S'b, а 6 <» aS1 С bS\

Эти отношения рефлексивны и транзитивны, т.е. являются квазипорядками. Отношения Грина Л?, M на полугруппе S определяются обычным образом12:

(а, Ь) в Л? а b и b а; (а, 6) € M О а Ь и b о.

Дадим определения потенциальной левой делимости и обобщённого отношения Грина Jz?*. Для элементов а, 6 е S положим

a sÇ(* b а b в некоторой надполугруппе Т О 5;

(а,Ь) € Л?" о (a, b) S ЛС в некоторой надполугруппе TOS.

Отношения SÎ* определяются двойственным образом.

Строение отношений Грина на полугруппе Т(Х) всех преобразований хорошо известно. А именно:

12КлнффордА., ПрестонГ. Алгебраическая теория полугрупп, ттЛ,§2.2 // М., «Мир», 1972.

(i) если a,ß £ T(X), то (a,ß) e & kera = ker/3;

(ii) если a,ße T(X), то (a,ß) £ i? ima = im/?.

Если вместо T(X) взять Та(Х), то утверждения (i), (ii) в общем случае перестанут быть верными. Разумеется, остаются справедливыми импликации =>. Выясним, в каких случаях верны импликации <=.

Предложение 3.1 Пусть X — произвольная цепь. Если a,ß е TQ{X), то а ß ima с \mß.

Следствие 3.2 Пусть X — произвольная цепь. Если а,ß £ Та(Х), то (a,ß) € 5£ <=> ima = \mß.

Предложение 3.3 Пусть X — конечная цепь. Если a, ß £ Т„(Х), то а ß kera Э ker/3.

Следствие 3.4 Пусть X — конечная цепь. Если a,ß zTa(X), то (а, ß) £ Ш О kera = ker/3.

Найдены контрпримеры, где не выполняются следствия 3.2 и 3.4:

1. бесконечная цепь X и элементы a,ß £ %[Х) такие, что kera = ker/З, но [a.ß)iS в TAX);

2. конечное частично упорядоченное множество X и элементы a,ß £ %{Х) такие, что ima = im/?, но (a,ß) $ Jz? в Т<,(Х);

3. конечное частично упорядоченное множество X и элементы а,/? £ Т„[Х) такие, что kera = ker/З, но (a,/3) ^ ^ в Т^Х).

В следующих двух предложениях рассмотрим более общий случай. Вместо одного множества (X, а) возьмём пару множеств (Л',а) и (У,г). Аналогично (3) считаем, что отображение а из X в У допустимо для пары (<т, г), если

Va\у е dorn а (х, у) £ а (ха, уа) £ т.

Предложение 3.5 Пусть Гь Гг и Гз — произвольные цепи, а € РТ^Г^Гг), ß £ РТ^(Гз, Г2). Отображение у е РТ^(Г], Гз) такое, что а = 7/?, существует а теш и только в том случае, если im а С im /3.

Следствие 3.6 Л' — произвольная цепь и а,ß £ РТ^(Х), то а <<

ß о ima С im/?; (ii) если X — произвольная цепь и a,ß £ РТ^(Х), то a&ß о im а = im ß.

Предложение 3.7 Пусть Гь Гз, Гз — произвольные цепи, а £ РТ$(ГьГг), ß £ РТц(ГьГз). Отображение 7 £ РГ^(Гз,Г2) такое, что а = ß~f, существуют в том и только в том случае, если dorn а С dorn ß и

kevß С кега U ((ГДёота) х (redoma)) (6)

Следствие 3.8 Если X — произвольная цепь и ct,ß £ РТ^(Х), то aMß кега = кег/3.

Перейдём теперь к обобщённым отношениям делимости и обобщённым отношениям Грина на полугруппах матриц над дистрибутивными решётками.

Пусть L — полная дистрибутивная решётка со следующим свойством: для любых элементов Xi (г £ I),y £ L

у A \>XÍ= Vfj/AXi). (7)

iei 1el

Умножение матриц a = \\сщ\\iejjej и т = |(ijjfc Jfce/c (возможно, бесконечных)

над L осуществляется по правилу ат = р = ||p;t||;en-ejí , где pik = V (<т,3- Л т>).

' jeJ

Пусть a и ß — I х J- и К х ./-матрицы над L. Полагаем a </ /?, если а =-yß для некоторой / х /{"-матрицы 7 над L, и a <,* ß, если Vp, р' (/Зр = ßp' => ар — ар'), где р,р' — J х 1-матрицы (столбцы).

Теорема 3.9 ^сла a <1 ß a. <¡ ß для любых матриц а, ß, то L — решётка с относительнъти дополнениями.

Замечание 3.10 Теорема 3.9 остаётся справедливой, если ограничиться матрицами размера 2x1.

Теорема 3.11 Если L — решётка всех подмножеств некоторого множества, то a<i ß a <¡ ß.

Теорема 3.12 Если L — полная подрешётка решётки L подмножеств некоторого мноокества и а, ß — матрицы над L, то а <\ ß в том и только том случае, если a = 7ß для некоторой матрицы 7 над L.

Матрицы размера 1x1 над полной дистрибутивной решёткой L с условием (7) образуют полугруппу, будем обозначать её через B](L).

Теорема 3.13 Если L - решётка всех подмножеств множества, то в полугруппе B]{L) имеют место равенства = Jf" (а значит, Я = £»,*).

Следствие 3.14 В полугруппе В(Х) бинарных отношений на множестве X справедливы равенства = X и М* = ¿9..

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

1. Предложены определения понятия сохранения бинарного отношения а элементом полугруппы частичных отображений РТ{Х) [элементом полугруппы В(Х) бинарных отношений] и установлены связи между ними.

2. Для квазиупорядоченного множества X найдены необходимые и достаточные условия регулярности полугрупп РТ^{Х) и РТ^(Х), а для частично упорядоченного множества X — необходимые и достаточные условия регулярности полугруппы В^(Х).

3. Установлена связь между отношением левой [правой] делимости на полугруппах Та(Х), РТа(Х) и образами [ядрами] элементов из Т<,(Х), РТ„(Х) для случая, когда <т — линейный порядок.

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

5. В полугруппе В(Х) доказано совпадение делимости и потенциальной делимости, а также совпадение отношений Грина .5? и обобщённых отношений Грина ¿Г, У .

Полученные результаты позволяют более полно судить о свойствах изотонности в полугруппах частичных и многозначных изотопных преобразований частично упорядоченных и квазиулорядочеиных множеств. Для квазиупорядоченного множества X найдены необходимые и достаточные условия регулярности полугрупп частичных и многозначных изотопных преобразований. Причём соответствующие утверждения для частичного порядка получаются автоматически, так как частичный порядок есть частный случай квазипорядка. Был обобщён известный факт того, что в полугруппе Т(Х) .¿'-классы связаны с образами отображений, а классы с ядрами. В частности, рассматривались полугруппы Т%{Х), РТ^(Х). Установлена связь между отношением левой [правой] делимости на упомянутых полугруппах и образами [ядрами] элементов из этих же полугрупп. Рассматривая

полугруппу квадратных матриц над полной дистрибутивной решёткой, удалось доказать, что отношение левой [правой] делимости и потенциальной левой [правой) делимости в этой полугруппе совпадают. Несмотря на то, что полугруппа В(Х) нерегулярна при 1X1 ^ 3, было доказано, что в ней, как и в регулярных полугруппах, совпадают отношения левой [правой] делимости и потенциальной левой [правой) делимости. Из последнего следует, что в В(Х) также совпадают отношения Грина с обобщёнными отношениями Грина 3&*, -2".

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

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

1. КожуховИ. Б., Ярошевич В. А. Отношения Грина и обобщённые отношения Грина на некоторых полугруппах преобразований // Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика. Саратов: Издательство Саратовского университета, 2009, т. 9, вып.З, с. 33-37.

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

2. Ярошевич В. А. Отображения, согласующиеся с бинарными отношениями // «Математический вестник педвузов и университетов Волго-Вятского региона», Киров, 2009. Вып. 11, с. 135-142.

3. КожуховИ. В., ЯрошевичВ.А. Полугруппы отображений, сохраняющих бинарное отношение // Фундамент, и прикл. матем., 2008, т. 14, №7, с. 129-135.

4. КожуховИ. В., Ярошевич В. А. О полугруппах частичных и полных изотопных преобразований // Материалы Международной научной конференции «Современные проблемы дифференциальной геометрии и общей алгебры», Саратов, 2008, с. 115-116.

5. Ярошевич В. А. О потенциальной делимости матриц над решётками // Материалы 16-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика — 2009», Москва, 2009, с. 144.

6. Yatoshevich V. Maps which are Concordant with Binary Relations // Materials of 77th Workshop on General Algebra, Institute of Mathematics Potsdam, Germany, 2009, p. 41.

7. Кожухов И. Б., ЯрошевичВ.А. Делимость и потенциальная делимость матриц над решётками // Материалы IV Всероссийской научно-методической конференции «Проблемы современного математического образования в вузах и школах России. Оценка качества математических знаний студентов и школьников», Киров, 2009, с. 63-64.

8. ЯрошевичВ.А. Полугруппы частичных изотопных преобразований квазиу-порядоченных множеств // МИЭТ - Москва, 2009. 21с. Деп. в ВИНИТИ 03.07.09, №443-В2009.

9. Yaroshevich V. A. On the divisibility of partial isotone transformations //' Materials of 7th International Algebraic Conference in Ukraine, Kharkov, 2009, p. 152-153.

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

Формат 60x84 1/16. Уч.-изд.л.^. Тираж¡0 0 экз. Заказ /г* ^

Отпечатано в типографии И ПК МИЭТ.

124498, Москва, г.Зеленоград, проезд 4806, д.5, МИЭТ.

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

Введение

1 Изотонные преобразования и их обобщения

1.1 Сохранение бинарного отношения а в полугруппах Т(Х) и РТ(Х).

1.2 Сохранение бинарного отношения а элементами полугруппы В(Х).

1.3 Гомоморфизмы графов

2 Регулярность полугрупп изотонных преобразований

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

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

2.3 Регулярность Та(Х), где = ш.

3 Отношения делимости и отношения Грина

3.1 . Связь отношений делимости с ядрами и образами изотонных преобразований.

3.2 Потенциальная делимость.

3.3 Делимость матриц над дистрибутивными решётками

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

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

Свойства полугруппы изотонных преобразований изучались многими авторами. Л.М. Глускин [5] доказал, что полугруппа Т<-(Х) определяет квазиупорядоченное множество X с точностью до изоморфизма или антиизоморфизма. А. Я. Айзенштат [1] получила представление полугруппы Т^(Х) образующими элементами и определяющими соотношениями в случае, когда X — цепь из п элементов. В другой работе А. Я. Айзенштат [2] получила описание частично упорядоченных множеств X, у которых полугруппа Т^(Х) регулярна. В случае счетной цени X более прозрачные условия регулярности получили В. И. Ким и И. Б. Кожухов [10]. Комбинаторным аспектам полугруппы Т^(Х) посвящены работы А. Умара и А. Лараджи [40, 42].

Хорошо известно (см. [11]), что полугруппы полных преобразований Т(Х) и частичных преобразований РТ(Х) регулярны для любого множества X. Полугруппа бинарных отношений В(Х) регулярна при \Х\ ^ 2 и нерегулярна при |Х| ^ 3. Известны [7] условия регулярности отдельного элемента а 6 В(Х).

Естественно поставить вопрос о том, при каких условиях на частично упорядоченное множество (X, — отношение порядка) полугруппа частичных отображений, сохраняющих отношение является регулярной. В работе получен исчерпывающий ответ для обоих вариантов сохранения ^ частичным отображением. Кроме этого, описание продолжено на случай, когда частичный порядок заменён квазипорядком.

Многозначные отображения — это в точности бинарные отношения на множестве X. Придерживаясь аналогии с Т(Х), можно сформулировать, что означает сохранение бинарного отношения а элементами из В{Х). В работе предложено два определения. Очевидно, что каждое из них сужает полугруппу В(Х) до некоторого подмножества. Оказывается, что в обоих случаях эти подмножества образуют полугруппы с единицей (т.е. моноиды).

Множество X с заданным на нём бинарным отношением а можно рассматривать как ориентированный граф с множеством вершин X. Из вершины х в вершину у идёт ребро тогда и только тогда, когда пара (.т, у) принадлежит а. Гомоморфизм графов (X, а) и (У, т) — это отображение а множества вершин графа X в У, сохраняющее рёбра (т.е., если пара (ж, х') принадлежит а, то пара (ха, х'а) должна принадлежать г). Понятие гомоморфизма графов допускает усиления [21].

В теории полугрупп важное значение имеют отношения Грина. Хорошо Ч известно [11, т. 1, § 2.2], что в полугруппе полных преобразований неупорядоченного множества X отношения Грина и ££ можно выразить через ядра и образы этих преобразований. Интересно выяснить, что произойдёт, если вместо Т{Х) взять Т^(Х) и РТ^(Х). Прежние утверждения в общем случае перестанут быть верными. В данной работе получены результаты для случая, когда X - цепь.

Отношения Грина непосредственно связаны с отношениями делимости одного элемента на другой. Именно, ££ можно выразить через отношения левой делимости, а & — через отношение правой делимости.

Элемент а может не делиться на Ъ в полугруппе но делиться в какой-нибудь надполугруппе, содержащей Б. Так возникает понятие потенциальной делимости. В данной работе доказано совпадение отношений делимости и потенциальной делимости в полугруппе В(Х).

Полугруппа В(Х) бинарных отношений на множестве X — это фактически полугруппа матриц X х X с элементами из булевой алгебры {0,1}. Можно рассматривать более общий случай матриц над дистрибутивной решёткой Ь. Для матриц конечного размера достаточно требования дистрибутивности решётки Ь, в противном случае необходимо условие типа бесконечной дистрибутивности. В ряде работ рассматривались матрицы конечных и бесконечных размеров не только над решёткой {0,1}, но и над другими дистрибутивными решётками. Теория булевых матриц обстоятельно изложена в известной монографии Кима [38]. Отношения Грина для матриц над булевыми алгебрами изучались В. Б. Поплавским [14]. В данной работе рассмотрено, как устроены отношения потенциальной левой и правой делимости, а также обобщённые отношения Грина в полугруппе матриц над дистрибутивными решётками для некоторых типов решёток.

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

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

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

Публикации. По теме диссертации опубликовано 9 работ ([55]-[63]), из них 1 статья [55] в журнале из списка ВАК.

Структура и объём диссертации. Диссертация состоит из введения и трёх глав, разбитых на 6 параграфов. Текст диссертации изложен на 91 странице. Список литературы содержит 63 наименования.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Ярошевич, Владимир Александрович, Москва

1. АйзенштатА.Я. Определяющие соотношения полугруппы эндоморфизмов конечного линейного упорядоченного множества // Сиб. мат. журн. 1962. Т. 3, №2. 161-169.

2. АйзенштатА. Я. Регулярные полугруппы эндоморфизмов упорядоченных множеств // Уч. зап. Ленинградского гос. пед. ин-та им. А.И.Герцена, 1968, т. 387, 3-11.

3. Богомолов A.M., СалийВ.И. Алгебраическая теория управляющихсистем // М., Наука, 1997.

4. Вагнер В. В. Теория отношений и алгебра частичных отображений //Сб. «Теория полугрупп и её приложения», вып. 1, 1965, изд-во Саратовского ун-та, 3-178.

5. ГлускинЛ. М. Полугруппы изотонных преобразований // Успехи мат.наук, 1961, 5 (101), 16, 157-162.

6. ГретцерГ. Общая теория решёток // М., «Наука», 1982.

7. ЗарецкийК.А. Полугруппа бинарных отношений // Матем. сб., 1963,61 (103), 3, 291-305.

8. Жучок Ю. В. Полугруппы эндоморфизмов 2-нильпотентных бинарных отношений // Фундамент, и прикл. матем., 2008, т. 14, №6, с. 75-83.

9. Ким В. И. Полугруппы конечных и коконечных изотонных преобразований // МИЭТ. Москва, 2007. 15с. Деп. в ВИНИТИ 29.06.2007 685В2007. Литература 86

10. Ким В. И., Кожухов И. В. Условия регулярности полугрупп изотонныхпреобразований счетных цепей // Фунд. и прикл. матем. 2006. 12, №8. 97-104.

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

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

13. ЛяпинЕ. Полугруппы // М., Физматлит, 1960.

14. ПоплавскийВ. Б. О рангах, классах Грина и теории определителейбулевых матриц // Дискретн. матем., 2008, т. 20, вып. 4, с. 42-60.

15. Скорняков Л. А. Элементв теории структур // М., «Наука», 1970.

16. ШевринЛ.Н. Полугруппы // Сб. СМБ, «Общая алгебра», М., «Наука», 1991, т. 2, 11-191.

17. Шутов Э. Г. Потенциальная делимость элементов в полугруппах //Уч. зап. Ленингр. гос. пед. ин-та им. Герцена, 1958, 166, с. 75-103.

18. Adams М. Е., Bulman-FlemingS., Gould М. Endomorphism properties ofalgebraic structures // Order, 1989, 6, 195-201.

19. Adams M.E., Gould M. Posets whose monoids of order-preserving mapsare regular // Order, 1989, 6, 195-201.

20. Adams M.E., Gould M. Finite posets whose monoids of order-preservingmaps are abundant // Acta Sci. Math. (Szeged) 67 (2001), 3-37.

21. Botcher M., KnauerU. Endomorphism spectra of graphs // DiscreteMathematics 109 (1992) 45-57, North-Holland.

22. BotcherM., KnauerU. Postscript «Endomorphism spectra of graphs» //Discr. Math., 2003, 270, 329-331.

23. Catarino P. Complete semigroups of transformations on a finite chain //1.ternational Conference on Semigroups and related topics, Porto, July 6-11, 2009, p. 19-20. Литература 87

24. Chajdal. Homomorphisms of directed posets // Asian-European Journalof Mathematics, 2008, Vol. 1, No. 1, 45-51.

25. ChanmuangPh., ChinramR. Some remarks on regularity of generalizedtransformation semigroups // International Journal of Algebra, 2008, Vol. 2, No. 12, p. 581-584.

26. ChinramR. Regularity and Green's relations of generalized partialtransformation semigroups // Asian-European Journal of Mathematics, 2008, Vol. 1, No.3, p. 295-302.

27. Clark C.E., CarruthJ.H. Generalized Green's theories // SemigroupForum, 1980, 20, p. 95-127.

28. Clifford A. H., Miller D.D. Union ans symmetry preservingendomorphisms of the semigroup of all binary relations on a set // Czechoslovak Mathematical Journal, 1970, 20, 303-313.

29. DuffusD., WilleR. A theorem on partially ordered sets of order-preservingmappings // Proceedings of the American Mathematical Society, 1979, vol. 76, num. 1, p. 14-16.

30. Femandes V.H., Gomes G.M.S. Presentations for some monoids of partialtransformations on a finite chain // Communications in Algebra, 2005, 33, 587-604.

31. Femandes V.H. Semigroups of Order Preserving Mappings on a FiniteChain: A New Class of Divisors // Semigroup Forum, 1997, 34, p. 230236.

32. Fountain J. B. Abundant semigroups // Proc. London Math. Soc, 1982,44, No.3, p. 103-129.

33. Gallagher P., RuskucN. Generation of diagonal acts of some semigroups oftransformations and relations // Bull. Austral. Math. Soc, 2005, Vol.72, p. 139-146. Литература 88

34. Gomes G. M. S., Howie J. M. On the ranks of certain semigroups of orderpreserving transformations // Semigroup Forum, 1992, 45, 272-282.

35. Hardy D., Pastijn F. The maximal regular ideal of the semigroup of binaryrelations // Czechoslovak Mathematical Journal, 1981, 31, 194-198.

36. HuishengP., DingyuZ. Green's equivalences on semigroups of transformations preserving order and an equivalence relation // Semigroup Forum, 2005, 71, 241-251.

37. Jackson M. Semigroups of relations // International Conference onSemigroups and related topics, Porto, July 6-11, 2009, p. 33-34.

38. KimK. H. Boolean matrix theory and applications // Marcel Dekker Inc.,1982.

39. KnauerU., NieporteM. Endomorphisms of graphs // Arch. Math., 1989,52, 607-614.

40. LaradjiA., UmarA. Combinatorial results for semigroups of orderpreserving partial transformations // King Fahd Univ. of Petroleum & Minerals (Sandi Avabia), Dept. Math. Sci. Technical Report Series. 2004. p. 1-18.

41. LaradjiA., UmarA. On certain finite semigroups of order-decreasingtransformations // King Fahd Univ. Petroleum & Minerals. Tech. Rep. Ser., 2003, 1-19.

42. LaradjiA., UmarA. On the number of nilpotents in the partial symmetricsemigroup // Communications in Algebra, 2004, 8, 3017-3032.

43. Levi I. Nilpotent ranks of semigroups of partial transformations //Semigroup Forum, 2006, 72, 459-476.

44. LiW. Split graphs with completely regular endomorphism monoids //Journal of mathematical research and exposition, 2006, Vol.2, No.2, 253263. Литература 89

45. MarkowskyG. Ordering D-classes and computiry Schein rank is hard. //Semigroup Forum, 1992, v. 44, p. 373-375.

46. MaeulovicD., PoschelR. Lifted transformation monoids and theircharacterization by relations and co-relations // Contributions to general algebra 12 Proceeding of the Vienna Conference, June 3-6, 1999, Verlag Johannes Heyn, Klagenfurt 2000, 273-287.

47. MolcanovV.A. Concrete characterization of partial cndomorphismsemigroups of graphs // Acta Sci. Math., 1987, 51, 349-363.

48. MolchanovV. A. Semigroups of mappings on graphs // Semigroup Forum,1983, 27, 155-199.

49. PlemmonsR.J., WestM.T. On the semigroup of binary relations // Pacificjournal of mathematics, 1970, Vol. 35, No. 3 p. 743-753.

50. Quinteiro Т. M. Bilateral semidirect product decompositions oftransformation monoids // International Conference on Semigroups and related topics, Porto, July 6-11, 2009, p. 71-72.

51. SchwarzS. On the semigroup of binary relations on a finite set //Czechoslovak Mathematical Journal, 1970, 20, p. 632-679.

52. Schein B.M. A construction for idempotent binary relations // Proc.Japan Acad., 1970, Vol.46, p.246-247.

53. WilkeitE. Graphs with a regular endomorphism monoid // Arch. Math.,1996, 66, 344-352.

54. YangX. Extensions of Clifford subsemigroups of the finite symmetricinverse semigroup // Communications in Algebra, 2005, 33, 381-391. Литература 90 Работы автора по теме диссертации

55. ЯрошевичВ. А. Отображения, согласующиеся с бинарными отношениями // «Математический вестник педвузов и университетов ВолгоВятского региона», Киров, 2009. Вып. 11, с. 135-142.

56. Кожухов И. В., ЯрошевичВ. А. Полугруппы отображений, сохраняющих бинарное отношение // Фундамент, и прикл. матем., 2008, т. 14, №7, с. 129-135.

57. Кожухов И. В., ЯрошевичВ. А. О полугруппах частичных и полныхизотонных преобразований // Материалы Международной научной конференции «Современные проблемы дифференциальной геометрии и общей алгебры», Саратов, 2008, с. 115-116.

58. ЯрошевичВ. А. О потенциальной делимости матриц над решётками// Материалы 16-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2009», Москва, 2009, с. 144.

59. Yaroshevich V. Maps which are Concordant with Binary Relations // Материалы конференции 77th Workshop on General Algebra, Institute of Mathematics Potsdam, Германия, 2009, с. 41.

60. ЯрошевичВ. А. Полугруппы частичных изотопных преобразованийквазиупорядоченных множеств // МИЭТ - Москва, 2009. 21 с. Деп. в ВИНИТИ 03.07.09, №443-В2009.

61. Yaroshevich V. A. On the divisibility of partial isotone transformations //Материалы 7 t h International Algebraic Conference in Ukraine, Харьков, 2009, с. 152-153.