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

• Ким, Виктор Иргюевич
• кандидат физико-математических наук
• 2008

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

Введение.

Глава 1 Анализ теории полугрупп преобразований.

1.1 Предварительные сведения.

1.1.1 Полугруппы преобразований.

1.1.2 Полугрупповые приложения.

1.1.3 Отношения Грина.

1.1.4 Обобщенные отношения Грина.

1.2 Полугруппы преобразований с убывающим порядком.

1.3 Полугруппы изотонных преобразований.

1.3.1 Образующие множества.

Глава 2 Полугруппы изотонных преобразований цепей.

2.1 Полугруппы изотонных преобразований.

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

2.2.1 Рекуррентная формула.

2.2.2 Оценки мощности полугруппы Dn.

2.3 Связь полугрупп Оп и Dn.

2.4 Условия регулярности полугрупп изотонных преобразований счётных цепей.

Глава 3 Полугруппы изотонных преобразований НЕ-цепей.

3.1 Регулярность полугрупп изотонных преобразований НЕ-цепей. Теорема Айзенштат.

3.2 Слабо регулярные полугруппы изотонных преобразований НЕ-цепей.

3.2.1 Трёхдольные множества.

3.2.2 Двудольные множества.

3.3 Биполигон над полугруппами изотонных преобразований.

Глава 4 Полугруппы конечных и коконечных изотонных преобразований.

Введение диссертации (часть автореферата) на тему «Полугруппы изотонных преобразований частично упорядоченных множеств»

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

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

Полугруппа изотонных преобразований изучалась во многих работах. Так, А.Я.Айзенштат в [2] построила копредставление полугруппы изотонных преобразований конечной цепи, т.е. задание этой полугруппы образующими и соотношениями. Б.М.Шайн в [42] исследовал условия представимости элемента полугруппы изотонных преобразований произвольной цепи в виде произведения идемпотентов. Эквивалентность элементарных теорий полугрупп изотонных преобразований рассматривалась Ю.М.Важениным [5] и Л.А.Скорняковым [18]. Хиггинс, Митчелл и Рушкуц [26] для некоторых цепей находили ранг полугруппы преобразований относительно полугруппы изотонных преобразований. Перечислительно-комбинаторным вопросам полугруппы изотонных преобразований посвящена серия работ А.Умара (см., например, [35], [47]). А.Крохин [33] и Б.Ларуз [37] изучали клоны операций, сохраняющих порядок конечной цепи.

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

Полугруппа 0(Х) несёт большую информацию о частично упорядоченном множестве X: В [6] Л.М.Глускин доказал, что изоморфизм полугрупп 0(Х) и 0(Y) двух частично упорядоченных множеств X и Y (даже квазиупорядоченных) влечёт изоморфность или антиизоморфность этих множеств. Вопрос о том, для каких частично упорядоченных множеств х полугруппа 0(Х) является регулярной, исследовался в работе А.Я.Айзенштат [3]. Там были описаны частично упорядоченные множества X, не являющиеся цепями, имеющие регулярную полугруппу 0(Х).

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

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

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

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

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

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

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

2. Описаны счётные цепи, для которых полугруппа изотонных преобразований является регулярной.

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

4. Исследованы полугруппы конечных и коконечных изотонных преобразований (Ofm(X) и Осодп(Х)). Доказано, что полугруппа конечных изотонных преобразований произвольной цепи регулярна, а полугруппа коконечных изотонных преобразований бесконечной счётной цепи не регулярна.

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

Апробация результатов. Основные результаты диссертации докладывались на семинаре «Кольца и модули» кафедры высшей алгебры механико-математического факультета МГУ им. Ломоносова, на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (г. Москва, Зеленоград,

Московский институт электронной техники, 2004, 2005, 2006 гг., 3 доклада), на 6-й Международной алгебраической конференции в Украине (6th International Algebraic Conference in Ukraine, july, 2007).

Публикации. По теме диссертации опубликовано 9 работ: [7], [8], [9], [10], [11], [12], [13], [14], [32].

Структура и объем работы. Диссертация состоит из введения, пяти глав, приложения и списка литературы. Содержит 94 страницы машинописного текста, список литературы из 50 наименований.

Список литературы диссертационного исследования кандидат физико-математических наук Ким, Виктор Иргюевич, 2008 год

1. Артамонов А., В.Н. Салий, Л.А. Скорняков. Общая Алгебра. Т.2 . М.: Наука. Гл. ред. Физ. Мат. Лит., 1991, 480 с.

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

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

4. Богомолов Ф.М., Салий В.Н. Алгебраические основы теории дискретных систем// М.: Наука. Физматлит, 1997. 368 с.

5. Важенин Ю.М. Элементарные свойства полугрупп преобразований упорядоченных множеств.// Алгебра и логика. 1970. Т. 7. N 3. С. 339-347.

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

7. Ким В.И. Полугруппы изотонных преобразований конечной цепи // Чебышевский сборник, Т. 6, вып. 4(16), 2005, с. 119-127.

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

9. Ким В.И., Кожухов И.Б. О полугруппах изотонных преобразований частично упорядоченных множеств.// Успехи математических наук, 2007, Т.62, вып. 5, с. 155-157.

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

11. Ким В.И. Полугруппы изотонных преобразований с убывающим порядком.// Микроэлектроника и информатика 2004. ОдиннадцатаяВсероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. М.: МИЭТ, 2004 - с. 178.

12. Ким В.И. Полугруппы изотонных преобразований цепей и не цепей.Микроэлектроника и информатика — 2005. Двенадцатая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. М.: МИЭТ, 2005 - с. 171.

13. Ким В.И. Регулярность полугрупп изотонных преобразований не цепей. // Микроэлектроника и информатика 2006. Тринадцатая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. -М.: МИЭТ, 2006 - с. 154.

14. Ким В.И. Отношения Грина на полугруппах изотонных преобразований. // Микроэлектроника и информатика — 2007. Четырнадцатая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. -М.: МИЭТ, 2007 с. 149.

15. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. Пер. с англ. -М.: Издательство «МИР», 1972. Т. 1. 286 е.; Т. 2. 422 с.

16. Лаллеман Ж. Полугруппы и комбинаторные приложения. Пер. с англ. -М.: Издательство «МИР», 1985. 439 с.

17. Ляпин Е.С. Абстрактная характеристика класса полугрупп эндоморфизмов систем общего вида.// Матем. сборник. 1966. Т. 70(112). N 2. С. 173-179.

18. Скорняков Л.А. О моноидах изотонных отображений.// Матем. сборник. 1984. Т. 123(165). N 1. С. 50-68.

19. Шеврин Л.Н. Что такое полугруппа. // Соровский Образовательный журнал, 1997 С. 99 -104.

20. Adams М.Е., Gould М. Posets whose monoids of order-preserving maps are regular.// Kluwer Academic Publishers. 1989, Order 6, p. 195-201.

21. Doroshenko V. Generators and relations for the semigroups of increasing functions on N and Z. Algebra and Discrete Math., 2005, № 4, p. 1-15.

22. Duffus D., Wille R. A theorem on partially ordered sets of order-preserving mappings.//Proc. Amer. Math. Soc., 76 (1979), p. 14-16.

23. El-Qallali A., Fountain J. Idempotent-connected abundant semigroups.// Proc. Roy. Soc. Edinburgh, 1981, 91 A, p. 79-90.

24. Fernandes V. A division theorem for the pseudovariety generated by semigroups of orientation preserving transformations on a finite chain.// Communication in algebra, 29(1), 2001, p. 451-456.

25. Fountain J. Adequate semigroups.// Proc. Edinburgh Math. Soc., 1979, 22, p. 113-125.

26. Higgins P.M., Mitchell J.D., Ruskuc N. Generating the full transformation semigroup using order preserving mappings.// Glasgow Math. J. 2003. V. 45. p. 557-566.

27. Higgins P.M., Umar A. Semigroup of order decreasing transformations: some fundamental congruences. //Technical Report Series. TR 268, September 2001.

28. Imreh B. On finite nilpotent automata. // Acta cybemetica 5, p. 283 293. 1981.

29. Imreh B. On finite definite automata. // Acta cybemetica 7, p. 61 65. 1984.

30. Imreh В., Steinby M. Some remarks on directable automata.//Acta cybemetica 12(1), p. 23 35. 1995.

31. Kilp M., Knauer U., Mikhalev A.V. Monoids, acts and categories. //Berlin -New York: W.de Gruyter, 2000.

32. Kim V.I. On isotone mappings of partially ordered sets. //6th International Algebraic Conference in Ukraine, july, 2007, p. 99.

33. Krokhin A., Larose B. A monoidal interval of isotone clones on a finite chain //Acta Sci. Math. (Szeged). 2001. V. 68. N 1-2. p. 37-62.

34. Kunze M., Crevenkovic S. Maximal subsemilattices of the full transformation semigroup.// Semigroup forum 35, 1987, p. 245-250.

35. Laradji A., Umar A. Combinatorial results for semigroups of order-preserving partial transformations.// King Fahd Univ. of Petroleum & Minerals (Saudi Arabia). Dept. Math. Sci. Technical Report Series. 2004. p. 1-18.

36. Laradji A., Umar A. On certain finite semigroups of order-decreasing transformations I. // King Fahd Univ. of Petroleum & Minerals (Saudi Arabia). Dept. Math. Sci. Technical Report Series. 2003. p. 1-19.

37. Larose B. A completeness criterion for isotone operations on a finite chain // Acta Sci. Math. (Szeged). 1994. V. 59. N 3-4. p. 319-356.

38. LI Wei-min. Split graphs with completely regular endomorphism monoids, journal of mathematical research and exposition. May, 2006, vol.26, No.2.

39. Molchanov V.A. Semigroups of mappings on graphs. Semigroup Forum, 1983, 27, p. 155-199.

40. Petcovic Т., Ciric M., Bogdanovic S. Decomposition of automata and transition semigroup. // Acta cybernetica 13, 1998, p.385-403.

41. Plemmons R.J., West M.T. On the semigroup of binary relations.// Pacific journal of mathematics, vol. 35, No. 3, 1970, p. 743-753. ■

42. Schein B.M. Products of idempotent order-preserving transformations of arbitrary chains.// Semigroup Forum. 1975. V 11. N 1. p. 297-309

43. Schein B.M. Regular elements of the semigroup of all binary relations.// Semigroup Forum. 1976. V 13. N 1. p. 95-102

44. Saito T. Finite ^-trivial Transformations Semigroups// Semigroup Forum. 2000. V 60. pp. 470-477

45. Saito T. On ^£(££)4уре subsemigroups of the finite full transformation semigroup.// Scientiae Mathematicae Japonicae, 57, No. 1. 2003. p. 63-67.

46. Thornton M.C. Semigroups of isotone selfmaps on partially ordered sets // J. London Math. Soc. 1976. Y. 14. N 3. p. 545-553.

47. Umar A. On certain infinite semigroups of order-decreasing transformations I.// Communications in algebra, 25(9), p. 2987 2999, 1997.

48. Umar A. On the ranks of certain finite semigroups of order — decreasing transformations/ZPortugaliae mathematica. Vol. 53, Fasc. 1 1996. p. 23-34.

49. Umar A. On the semigroups of order-decreasing finite full transformations. //Proc. Roy. Soc. Edinburgh Sect. A 120, 1992, p. 129-142.

50. You Tai-jie. An extending method in transformation semigroups.//.!, of Math (PRC), vol. 21, No. 4, 2001, p. 397-402.