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

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

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

Введение

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]. В данной работе рассмотрено, как устроены отношения потенциальной левой и правой делимости, а также обобщённые отношения Грина в полугруппе матриц над дистрибутивными решётками для некоторых типов решёток.

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

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

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

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

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

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

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

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

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

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

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

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

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.