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

• Автор: Ярошевич, Владимир Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 91 с. : ил.

Содержание
Введение

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

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

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

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

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

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

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

2.3 Регулярность Та(Х), где Д С о С ш и а1 — и>

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

3.1 . Связь отношений делимости с ядрами и образами изотопных преобразований
3.2 Потенциальная делимость
3.3 Делимость матриц над дистрибутивными решётками
Литература

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

Введение
бинаторным аспектам полугруппы Т(Х) посвящены работы А. Умара и
А. Лараджи [40, 42].
Возможны различные подходы к пониманию изотонности частичных преобразований. В работе предложены два неэквивалентных способа этого.
Хорошо известно (см. [11]), что полугруппы полных преобразований Т(X) и частичных преобразований РТ(Х) регулярны для любого множества X. Полугруппа бинарных отношений В(Х) регулярна при |АГ| < 2 и нерегулярна при |Х| 3. Известны [7] условия регулярности отдельного элемента а € В(Х).
Естественно поставить вопрос о том, при каких условиях на частично упорядоченное множество (X, — отношение порядка) полугруппа
частичных отображений, сохраняющих отношение является регулярной. В работе получен исчерпывающий ответ для обоих вариантов сохранения частичным отображением. Кроме этого, описание продолжено на случай, когда частичный порядок заменён квазипорядком.
Многозначные отображения — это в точности бинарные отношения на множестве X. Придерживаясь аналогии с Т(Х), можно сформулировать, что означает сохранение бинарного отношения а элементами из В{Х). В работе предложено два определения. Очевидно, что каждое из них сужает полугруппу В(Х) до некоторого подмножества. Оказывается, что в обоих случаях эти подмножества образуют полугруппы с единицей (т.е. моноиды).
Множество X с заданным на нём бинарным отношением а можно рассматривать как ориентированный граф с множеством вершин X. Из вершины х в вершину у идёт ребро тогда и только тогда, когда пара (ж, у) принадлежит а. Гомоморфизм графов (X, а) и (У, г) — это отображение а множества вершин графа X в У, сохраняющее рёбра (т.е., если пара (х,х') принадлежит а, то пара (ха, х'а) должна принадлежать т). Понятие гомоморфизма графов допускает усиления [21].
В теории полугрупп важное значение имеют отношения Грина. Хорошо

Глава 2. Регулярность полугрупп изотонных преобразований
и только том случае, если X — антицепь или X изоморфно какому-либо из множеств 1д, Гу у, Су,г
Регулярность полугруппы ТДХ) в случае, когда X - цепь, в работе [2] также была исследована. Однако, полученные там необходимые и достаточные условия регулярности оказались довольно громоздки и трудны для использования. Для случая, когда X — цепь, в [19] получены более прозрачные условия. Случай, когда X — счётная цепь лучше представлен в [10].
2.1 Регулярность полугрупп преобразований частично упорядоченных множеств
Для элементов х, у частично упорядоченного множества X положим х ~ У, если существует последовательность элементов «1, М2, - , и2п-1 с X такая, что х < щ > < щ > < иоп-1 > У- Нетрудно видеть, что
отношение ~ является отношением эквивалентности на множестве X, а значит, множество X разбивается на классы эквивалентности. Будем называть эти классы компонентами связности множества X. Множество X, состоящее из одной компоненты связности, назовем связным. Ясно, что разбиения на компоненты связности множества X — это в точности разбиение на компоненты связности графа, соответствующею этому множеству '(его диаграммы Хассе).
Частично упорядоченное множество X называется цепью, если любые два элемента сравнимы, и антицепью, если никакие два различные элемента не сравнимы. То есть:
А" — цепь -Ф4> Ух, у & X (х < у или у < х),
X — антицепь Ух, у 6 X (х < у => х — у).
Лемма 2.2. Пусть X — частично упорядоченное множество. Если полугруппа РТДХ) регулярна, то X связно или X — антицепь.
Доказательство. Пусть X не является антицепью и X несвязно. Докажем, что полугруппа РТДХ) нерегулярна. Так как X не антицепь, то