Содержание к диссертации
Введение
Глава 1 Анализ теории полугрупп преобразований 8
1.1 Предварительные сведения 8
1.1.1 Полугруппы преобразований 8
1.1.2 Полугрупповые приложения 13
1.1.3 Отношения Грина 15
1.1.4 Обобщенные отношения Грина 18
1.2 Полугруппы преобразований с убывающим порядком 20
1.3 Полугруппы изотонных преобразований 21
1.3.1 Образующие множества 21
Глава 2 Полугруппы изотонных преобразований цепей 23
2.1 Полугруппы изотонных преобразований 23
2.2 Полугруппы изотонных преобразований с убывающим порядком 27
2.2.1 Рекуррентная формула 32
2.2.2 Оценки мощности полугруппы Dn 34
2.3 Связь полугрупп Оп и Dn 37
2.4 Условия регулярности полугрупп изотонных преобразований счётных цепей 38
Глава 3 Полугруппы изотонных преобразований НЕ-цепей 46
3.1 Регулярность полугрупп изотонных преобразований НЕ-цепей. Теорема Айзенштат 46
3.2 Слабо регулярные полугруппы изотонных преобразований НЕ-цепей .49
3.2.1 Трёхдольные множества 51
3.2.2 Двудольные множества 58
3.3 Биполигон над полугруппами изотонных преобразований 68
Глава 4 Полугруппы конечных и коконечных изотонных преобразований 70
Приложение 84
Литература 90
- Полугруппы преобразований
- Полугруппы преобразований с убывающим порядком
- Полугруппы изотонных преобразований с убывающим порядком
- Слабо регулярные полугруппы изотонных преобразований НЕ-цепей
Введение к работе
Актуальность темы. Изучение полугрупп преобразований, сохраняющих структуру множества, является интересной и важной задачей общей алгебры. К таким полугруппам относятся, в частности, полугруппы непрерывных отображений топологических пространств, полугруппы эндоморфизмов графов, полугруппы отображений частично упорядоченных множеств, сохраняющих порядок (т.е. изотонных).
Любая полугруппа вкладывается в полугруппу преобразований некоторого множества. Этот факт свидетельствует о важности полугруппы преобразований в теории полугрупп. Если на данном множестве задана некоторая структура (например, топология, отношения порядка и т.д.), то естественно рассматривать полугруппы таких отображений, которые сохраняют данную структуру. Данная диссертация посвящена изучению полугрупп изотонных преобразований частично упорядоченных, а также квазиупорядоченных множеств.
Полугруппа изотонных преобразований изучалась во многих работах. Так, А.Я.Айзенштат в [2] построила копредставление полугруппы изотонных преобразований конечной цепи, т.е. задание этой полугруппы образующими и соотношениями. Б.М.Шайн в [42] исследовал условия представимости элемента полугруппы изотонных преобразований произвольной цепи в виде произведения идемпотентов. Эквивалентность элементарных теорий полугрупп изотонных преобразований рассматривалась Ю.М.Важениным [5] и Л.А.Скорняковым [18]. Хиггинс, Митчелл и Рушкуц [26] для некоторых цепей находили ранг полугруппы преобразований относительно полугруппы изотонных преобразований. Перечислительно-комбинаторным вопросам полугруппы изотонных преобразований посвящена серия работ А.Умара (см., например, [35], [47]). А.Крохин [33] и Б.Ларуз [37] изучали клоны операций, сохраняющих порядок конечной цепи.
5 Полугруппы изотонных преобразований не являются до конца
изученными. Хорошо известно, что полугруппа всех преобразований
произвольного множества является регулярной, и её алгебраическое строение
довольно прозрачно. Однако, строение полугрупп изотонных преобразований
далеко не ясно. В частности, интересен вопрос о регулярности этих
полугрупп.
Полугруппа 0{Х) несёт большую информацию о частично упорядоченном множестве X: В [6] Л.М.Глускин доказал, что изоморфизм полугрупп 0(Х) и 0(Y) двух частично упорядоченных множеств X и Y (даже квазиупорядоченных) влечёт изоморфность или антиизоморфность этих множеств. Вопрос о том, для каких частично упорядоченных множеств х полугруппа 0{Х) является регулярной, исследовался в работе А.Я.Айзенштат [3]. Там были описаны частично упорядоченные множества X, не являющиеся цепями, имеющие регулярную полугруппу 0(Х).
Одним из интересных классов полугрупп, включающих регулярные, является класс слабо регулярных полугрупп. Естественно спросить, для каких частично упорядоченных множеств их полугруппы изотонных преобразований будут обладать свойством слабой регулярности? Кроме того, представляет интерес следующий вопрос: насколько изменятся условия слабой регулярности, если ослабить требование на множество X, а именно, считать X квазиупорядоченным множеством X (т.е. на множестве X введено бинарное отношение, являющееся рефлексивным и транзитивным)?
Данная диссертация посвящена изучению полугрупп изотонных отображений частично упорядоченных, а также квазиупорядоченных множеств.
Цель работы заключается в исследовании алгебраического строения полугрупп изотонных преобразований частично упорядоченных и квазиупорядоченных множеств.
Методы исследования. В работе использованы методы алгебраической теории полугрупп и теории частично упорядоченных множеств. Для
проверки некоторых гипотез и получения информации о строении полугрупп был использован компьютер.
Научная новизна работы. В диссертации получен ряд результатов о строении полугрупп изотонных преобразований частично упорядоченных множеств и о строении квазиупордядоченных множеств со слабо регулярной полугруппой изотонных преобразований. Полученные результаты являются новыми.
Научные положения, выносимые на защиту.
Изучено строение полугруппы изотонных преобразований с убывающим порядком конечной цепи. Получено описание классов отношений Грина и обобщённых отношений Грина этой полугруппы.
Описаны счётные цепи, для которых полугруппа изотонных преобразований является регулярной.
Описаны квазиупорядоченные множества со слабо регулярной полугруппой изотонных преобразований.
Исследованы полугруппы конечных и коконечных изотонных преобразований (Ofm(X) и Осф,(Х)). Доказано, что полугруппа конечных изотонных преобразований произвольной цепи регулярна, а полугруппа коконечных изотонных преобразований бесконечной счётной цепи не регулярна.
Практическая и теоретическая ценность. Работа носит теоретический характер. Её методы и результаты могут быть использованы для дальнейшего изучения различных полугрупп преобразований (в частности, полугрупп частичных преобразований, а также многозначных преобразований).
Апробация результатов. Основные результаты диссертации докладывались на семинаре «Кольца и модули» кафедры высшей алгебры механико-математического факультета МГУ им. Ломоносова, на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (г. Москва, Зеленоград,
7 Московский институт электронной техники, 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 наименований.
Полугруппы преобразований
Теория полугрупп включает в себя множество разновидностей полугрупп (например, аддитивная и мультипликативная полугруппы натуральных чисел, полугруппы матриц, свободные полугруппы и т.д.). В область интересов данной работы входят полугруппы преобразований как конечных, так и бесконечных множеств. Пусть А, В - некоторые множества. Отображение/: А — В называют инъективным (инъекцией), если каждый элемент из области его значений имеет единственный прообраз, т.е. ffri) =f(x2) = xi= х2. Отображение f: А — В называют сюръективиым (сюръекцией), если область его значений совпадает со всем множеством В. Сюръективное отображение из А в В называют также отображением множества А на множество В. Отображение/: А — В называют биективным (биекцией), если оно одновременно инъективно и сюръективно. Таким образом, если отображение f. А — В биективно, то каждому элементу множества А отвечает единственный элемент множества В и наоборот. Тогда говорят, что множества А и В находятся между собой во взаимно однозначном соответствии. Взаимно однозначное отображение множества Хна себя будет называться подстановкой множества X, даже если X бесконечно. Множество Cjx всех подстановок множества X с операцией суперпозиции называется симметрической группой на X.
Пусть X — произвольное непустое множество. Преобразованием множества X называется всякое отображение / этого множества в себя (/: X — X) . Любой элемент х є X переводится преобразованием / в однозначно определенный элементах), называемый образом элемента х. При этом взаимооднозначность преобразования необязательна.
Множество всех преобразований множества X обозначим Тх. По определению, преобразования / и g из ҐХ равны, f=g, если f[x) = g(x) для любого х єХ. ТХявляется полугруппой относительно операции суперпозиции, определяемой следующим образом: произведением преобразований fug называется преобразование , заданное условием fg(x) =Мрс)) для любого х є X. Другими словами, fg есть результат последовательного выполнения сначала преобразования g, затем преобразования f. Легко убедиться в ассоциативности этого умножения. Полугруппу Их называют полугруппой всех преобразований (а также полной полугруппой преобразований) на множестве X. Кроме Тх можно указать различные другие естественные полугруппы относительно суперпозиции, состоящие из преобразований множества X, где X — либо произвольное множество, либо множество, наделенное какой-либо математической структурой: алгебраической, геометрической, топологической и т.п. Таковы, например, группа всех взаимно однозначных отображений произвольного множества X на себя {симметрическоая группа дх на множестве X — это один из важнейших примеров групп), многочисленные полугруппы операторов - для случая, когда X есть какое-либо из пространств, изучаемых в функциональном анализе, и многие другие полугруппы преобразований. Все такие полугруппы являются подполугруппами полной полугруппы преобразований.
Введём понятие изоморфизма. Пусть S и Г— полугруппы с операциями и соответственно. Изоморфизмом S на Т называется всякое взаимно однозначное отображение ф S на Т, удовлетворяющее условию: ф (х у) = ф (х) ф (у), для любых х, у є S. Взаимно однозначное отображение обладает обратным к нему отображением, и если ф есть изоморфизм S на Т, то обратное отображение Ф будет, как легко убедиться, изоморфизмом Т на S. Полугруппы, для которых существует изоморфизм одной на другую, называются изолюрфн ым и. Примером изоморфных полугрупп могут служить аддитивная группа Ш и мультипликативная группа положительных действительных чисел. Аддитивная полугруппа натуральных чисел изоморфна аддитивной полугруппе четных натуральных чисел, изоморфизм первой на вторую сопоставляет любому п число In. А вот мультипликативные полугруппы всех натуральных чисел и всех четных натуральных чисел неизоморфны: в первой есть нейтральный элемент (единица), а во второй такового нет.
В приведенных примерах фигурировали полугруппы, состоящие из элементов разной природы и изоморфные полугруппам, состоящим из преобразований. Эти примеры являются иллюстрацией принципиального общего факта: любая полугруппа обладает таким изоморфизмом. Это подчеркивает важность полугрупп преобразований в теории полугрупп. Теорема. Любая полугруппа изоморфна некоторой полугруппе преобразований. Прозрачное доказательство сформулированного факта можно найти, например, в [19]. Проблема изоморфизма полугрупп преобразований изучалась во многих работах. В частности, Торнтон в [46] исследовал изоморфизм полугрупп преобразований, сохраняющих топологию. Дюффус и Вилле в [22] рассматривали изоморфизм Т(Х) и T(Y), рассматриваемых как частично упорядоченные множества относительно порядка а /3 = УхеХ ха х/3: следует ли из изоморфизма этих частично упорядоченных множеств изоморфизм множеств X и Г? Схожей проблеме, но для полугрупп изотонных преобразований, посвящена работа [6] Л.М. Глускина: следует ли из изоморфизма полугрупп 0(Х) и 0(Y) изоморфность или антиизоморфность множеств X и У? Методы расширения группы преобразования до полугруппы преобразований, обладающей заданными свойствами рассматривались в [50].
Предметом исследований данной работы являются полугруппы изотонных преобразований. Изотонной будем называть такую полугруппу, которая сохраняет порядок, т.е. выполняется соотношение: х yz= a(x) а(у), \/х,у є X. Эта полугруппа изоморфно вкладывается в Хх Различные вопросы, связанные с полугруппами изотонных преобразований, были освещены в обзоре [39].
Основное внимание в работе уделяется важным характеристикам полугрупп преобразований, одной из которых является свойство регулярности. Элемент а полугруппы S называется регулярным, если аха = а для некоторого х є S . Полугруппа S называется регулярной, если все её элементы регулярны. Исследованию регулярности элементов посвящено множество работ. В частности, Б.М. Шайн в работе [43] проводит описание регулярных элементов полугруппы всех бинарных отношений. Адаме и Голд в [20] описали частично упорядоченные множества, для которых полугруппы преобразований, сохраняющих порядок, являются регулярными (т.е. все элементы полугруппы регулярны).
Некоторые последние результаты, касающиеся различных полугрупп преобразований, в том числе комбинаторные свойства, можно найти в [27], [35], [48]. Разделы теории полугрупп, связанные с теорией автоматов, алгебраической лингвистикой и комбинаторикой изложены в [16]. Большое число публикаций по указанным математическим дисциплинам содержит результаты и методы, свойственные алгебраической теории полугрупп. Это привело к значительному обогащению и расширению границ самой теории, проявило способность теории полугрупп обеспечить удобный общий
фундамент для унификации и прояснения целого ряда проблем в областях, которые на первый взгляд казались никак не связанными друг с другом. Примером таких областей может служить применение алгебраической теории полугрупп в теории автоматов и их непосредственная связь.
Действительно, каждому автомату V = (A, Q, 5), где А — входной алфавит, Q — множество состояний, 8: QxA — Q - функция переходов, можно поставить в соответствие его синтаксическую полугруппу S(V), которая определяется как подполугруппа полугруппы всех преобразований 1Ь , порождённая преобразованиями q — S(q, а) , а є А. По свойствам синтаксической полугруппы можно судить о свойствах самого автомата и наоборот. Этим вопросам посвящено большое количество литературы (см., например, [28], [29], [30], [40]). Приведём пример конечного автомата.
Полугруппы преобразований с убывающим порядком
Тот факт, что любая полугруппа изоморфно вкладывается в полугруппу всех преобразований Тх служит одной из основ для изучения различных полугрупп преобразований, в частности полугрупп изотонных преобразований. Полугруппа ҐХ обладает множеством интересных свойств и хорошо изучена (см., напр., [15], [34], [45]). Она является регулярной, у неё найдены все идемпотенты и классы отношения Грина.
Если множество X наделено некоторой структурой (например, на нём задана совокупность отношений, операции или топология), то естественно рассматривать такие преобразования, которые согласованы с этой структурой. Часто такие преобразования образуют полугруппу, и многие работы посвящены различным аспектам этих полугрупп. Е.С.Ляпин в [17] нашёл абстрактную характеризацию полугруппы всех преобразований, сохраняющих некоторую (произвольную) совокупность отношений.
Некоторые положения работы А. Умара о полугруппах преобразований с убывающим порядком S {X) послужили основой исследования полугруппы изотонных преобразований 0(Х) и полугруппы изотонных преобразований с убывающим порядком D(X). Полугруппа S (X) задаётся следующим соотношением: S (X) = {a eT(X):(VxeX)xa х} . Основное описание строения полугруппы S (X) с комбинаторными результатами даётся в серии работ А. Умара [36], [47], [49]. Там описываются необходимые и достаточные условия для идемпотентов, даётся подробное описание полугруппы в свете отношений Грина. Выявляются важные для описания полугруппы S (X) свойства: 1) S (X) - тривиально, т.е. для некоторых а,/3 eS (X) , для того, чтобы a 1(,/3 необходимо и достаточно чтобы а — Д 2) для L — эквивалентности, тривиальность отсутствует. Для частично упорядоченного множества X пусть О(Х) обозначает полугруппу изотонных преобразований множества X, т.е. полугруппу всех преобразований а є Т(Х), сохраняющих порядок: х у = ха уа для всех х,уєХ. Полугруппа изотонных преобразований изучалась во многих работах. А.Я.Айзенштат в [2] построила копредставление полугруппы 0(Х), где X - конечная цепь, т.е. задание этой полугруппы образующими и соотношениями. Б.М.Шайн в [42] исследовал условия представимости элемента из 0{Х), где X — произвольная цепь, в виде произведения идемпотентов. Псевдомногообразия полугрупп, порожденные полугруппами преобразований конечной цепи рассматриваются в [24]. Эквивалентность элементарных теорий полугрупп изотонных преобразований рассматривалась Ю.М.Важениным и Л.А.Скорняковым [5], [18]. Хиггинс, Митчелл и Рушкуц [26] для некоторых цепей X находили ранг полугруппы Т{Х) относительно О(Х). Перечислительно-комбинаторным вопросам полугруппы изотонных преобразований посвящена серия работ А.Умара (см., например, [35], [47]). А.Крохин и Б.Ларуз [37], [33] изучали клоны операций, сохраняющих порядок конечной цепи.
Полугруппа изотонных преобразований содержит информацию о множестве, на котором строятся её преобразования. Л.М.Глускин в [6] доказал, что из изоморфизма полугрупп 0(Х) и 0(Y) двух частично упорядоченных множеств X и Г (даже квазиупорядоченных) следует, что множества X и Y изоморфны или антиизоморфны. Т.е., рассматривая полугруппы изотонных преобразований, можно выделять частично упорядоченные множества с теми или иными свойствами и наоборот. Для семейства множеств (частично упорядоченных), не являющихся цепями, в данной работе используется понятие НЕ-цепей. Если X - частично упорядоченное множество такое, что х/ упри любых х,уеХ, то X будем называть антицепью. Исследование полугрупп преобразований не ограничивается конечными множествами. Пусть X - бесконечное линейно упорядоченное множество. Если множеству X можно поставить в соответствие множество натуральных чисел N , то X называют счётным множеством. Классическим примером счётного множества является множество рациональных чисел Ш. Во второй главе данной работы сформулированы и доказаны условия регулярности полугрупп изотонных преобразований счётных цепей. Данная глава посвящена изучению строения полугруппы изтонных преобразований 0(Х) и полугруппы изотонных преобразований с убывающим порядком D(X), где Х- конечная цепь. Пусть X - произвольное непустое линейно упорядоченное множество (цепь). Преобразованием множества X называется всякое отображение а этого множества в себя. Любой элемент хєХ переводится преобразованием а в однозначно определенный элемент а(х) или ха, который называется образом элемента х и обозначается Im а. Если множество X частично упорядочено, то естественно рассматривать такие преобразования X -» X , которые сохраняют порядок (т.е. являются изотонными). Рассмотрим случай, когда X — цепь (элементы цепи упорядочены следующим образом: 1 2 3 „ п)и пусть 0(Х) -полугруппа изотонных преобразований X — Х (сохраняющих порядок), то есть (убывающий порядок в прообразе влечёт убывание в образе) 0(Х) ={а:Х-+Х\х у а(х) а(у),\/х,у є X } Если множество X конечно и его мощность равна п, т.е. \Х\ = п (в этом случае будем использовать понятие размерности задачи п), то 0(Х) будем обозначать Оп. Нами был произведён поиск всех элементов полугруппы От вплоть до размерности задачи n = 7, всех регулярных элементов, и идемпотентов. Результаты сведены в таблицу 2.1.1, где \ Оп \ - число элементов в полугруппе От Idemp - количество идемпотентов в Оп , Reg - количество регулярных элементов. В результате поиска был установлен факт, что все элементы данной полугруппы регулярны.
Полугруппы изотонных преобразований с убывающим порядком
В отличие от полугруппы изотонных преобразований 0(Х), в данной полугруппе появляется дополнительное условие «убывающего порядка»: убывающий порядок в прообразе влечёт за собой убывание в образе. Обозначим данную полугруппу D(X) , для конечного случая (\Х\ = п) Dn. Таким образом, полугруппа изотонных преобразований с убывающим порядком определяется следующим образом: Dn = {а: X — Х\ х у = ха уос; ха х; Vx, у єX} Некоторые результаты поиска всех элементов полугруппы Dn , её идемпотентов и регулярных элементов отражены в следующей таблице: здесь Dn - число элементов в полугруппе Dm Idemp - количество идемпотентов в Оп, Reg - количество регулярных элементов. Сравнительный анализ всех регулярных элементов с идемпотентами показал, что в данной полугруппе идемпотенты совпадают с регулярными элементами. Это предположение нашло теоретическое обоснование в следующей теореме. Утверждение 2.2. Пусть Dn — полугруппа с убывающим порядком над множеством X, E(D„) - множество идемпотентов полугруппы Dn , Reg(Z)„) -множество регулярных элементов полугруппы Dn. Тогда верно следующее: aeE(D„)oaeReg(DH) Доказательство. = ) Пусть а- идемпотент, тогда а2 = а, а3— а2 = а. Следовательно, а-а-а = а , т.е. всегда найдётся элемент, удовлетворяющий условию регулярности: a-ft а= а. Следовательно, а - регулярный элемент. =) Пусть а - регулярный элемент полугруппы Dn, значит З/З є Dn: afta = а. Пусть хєХ, тогда xafta = ха. Обозначим ха — у. Тогда, yfta = у, т.е. y yft yfta = у (т.к. a, ft є Dn). Следовательно, у ft = у, значит yfta=y = у а - у. Вместо у подставляем ха, получим ха2 - ха = а2 — а. Проанализируем умножение справа и слева элементов из Dn на саму Dn. Умножение производилось для всех элементов при п є [1; 7], для простоты приведём результат для n = 4, в виде таблиц умножения справа и слева (главных левых и главных правых идеалов).
Наименьшая подполугруппа, получившаяся в результате умножения -полугруппа элемента а = 1111, наибольшая - а = 1234, она совпадает с D„. Естественно обозначить их соответственно нулём и единицей полугруппы D„. Как видно из таблицы, нет такого элемента, главный правый идеал которого совпал бы с главным правым идеалом другого элемента. Действительно, поиск всех — эквивалентных элементов показывает, что любой элемент полугруппы Dn (Jl - эквивалентен лишь сам себе, что говорит о -тривиальности Dn. На основе этой гипотезы, была сформулирована и доказана следующая теорема. Утверяедение 2.3. Пусть a,j3eDn . Тогда, для того, чтобы а %, /3 необходимо и достаточно чтобы а = Д Доказательство. Достаточность следует из определения отношения Грина, достаточно доказать необходимость, т.е. равенство а = (3. Поскольку ccR/З, то а- /Зу и /3 = ад для некоторых y,S Du. Отсюда, а = аду . Получаем, ха — хаду xaS ха , значит ха.8 = ха , для любого х. Поэтому, ад = а = /3 = а.
Подобно умножению справа, умножение слева также дает уникальные полугруппы для каждого элемента. Аналогично таблице главных правых идеалов, таблица главных левых идеалов свидетельствует об уникальности идеалов каждого элемента. L — тривиальность доказывается следующей теоремой. Утверждение 2.4. Пусть а, /3 є Dn. Тогда, для того, чтобы a L /3 необходимо и достаточно чтобы а = /? Доказательство. Достаточность следует из определения отношения Грина, достаточно доказать необходимость, т.е. равенство а — Д Поскольку a L [5 , то а = у/3 и J3 = 8а для некоторых y,S є Dn. Получаем, ха = ху/3 xfi , т.е. ха xfi . Аналогично доказывается, что xf5 ха . Поэтому, ха — х/3, для любых х. Следовательно, /?= а.
При исследовании главных идеалов полугруппы Dn, установлен общий вид наименьшего элемента не равного нулю (атома). При умножении справа, атом представляет собой последовательность единиц и следующих за ними двоек. При умножении слева, атом состоит из единиц, кроме последней п-й позиции, на которой стоит число от 1 до п. Этот факт наглядно представлен на следующем графе, построенном аналогично графу главных идеалов для полугруппы Оп. На рис. 2.2, 2.3 для каждого уровня проставлены (на рисунке справа) мощности полугрупп данного уровня. Самая большая полугруппа в данном случае — полугруппа элемента а = 1234, наименьшая - полугруппа элемента а = 1111 (соответственно единица и нуль полугруппы Dn). В отличие от Оп, в Dn правый и левый нули совпадают и, подобно Оп, двусторонний нуль является единственным.
Полугруппа Dn вкладывается в полугруппу всех преобразований Тх, мощность которой равна пп. Также очевидно, что при некотором п мощность Dn меньше мощности Оп . Дадим оценку зависимости Dn от п.
Оценка сверху. Прежде чем оценивать D„, проведём оценку f(n, к) из (2.2.1). Воспользуемся известной комбинаторной задачей с п — 1 шариками и к — 1 перегородками (см. рис. 2.5) и преобразуем её для нашего случая. Элементов из Dn с заданными свойствами столько же, сколько (х/, х2, .. ,хп) , в которых х/ = 1, Xj j, Xj Xj+i, xn = к.
Слабо регулярные полугруппы изотонных преобразований НЕ-цепей
Элемент а полугруппы S называется слабо регулярным справа {слева), если aeaSaS (соотв., a SaSa). Полугруппа S называется слабо регулярной справа {слева), если все её элементы слабо регулярны справа (слева). Назовём полугруппу слабо регулярной в широком смысле, если каждый её элемент слабо регулярен слева или справа. Понятно, что в любой полугруппе регулярный элемент является регулярным слева и справа, все регулярные полугруппы слабо регулярны слева и справа и тем более слабо регулярны в широком смысле. Примером слабо регулярной, но не регулярной полугруппы может служить простая справа полугруппа без идемпотентов. В конечной полугруппе понятия регулярного, слабо регулярного слева и слабо регулярного справа элемента совпадают (это нетрудно доказать, рассматривая главные факторы полугруппы.). Поэтому для конечной полугруппы слабая регулярность в широком смысле равносильна регулярности.
Для произвольного множества X и отображения а: X — X пусть \та = Ха = {ха\хеX} — образ, a kera -{{х,у)\ха = уа} — ядро отображения а. Если А с: X, то Аа = {аа \ а є А) — образ, а Аа х = {х ха є А] - полный прообраз множества А. Отображение а є Т{Х) назовём константой, если ха = уа при всех х,уєХ. Если а — константа и X — частично упорядоченное множество, то ясно, что а є 0{Х). Кроме того, а1 = а, поэтому а — регулярный элемент полугруппы 0{Х). В дальнейшем нами часто будет использоваться следующее очевидное утверждение. Лемма 3.1. Пусть а,/3 є Т(Х). Тогда: (1) если аР = а, то J3 тождественно на ima (т.е. х/3 = х при хєіта); (2) если pa = а, то отображение /? сохраняет отношение кега (т.е. KflczK для любого класса К отношения kem). На частично упорядоченном множестве X введём отношение , полагая а Ь, если существуют элементы х1,...,хпєХ такие, что а Xj х2 ... хп Ъ. Нетрудно видеть, что отношение эквивалентности. Классы этого отношения мы будем называть компонентами связности множества X. Они соответствуют компонентам связности графа данного частично упорядоченного множества X. Частично упорядоченное множество X называется связным, если оно состоит из одной компоненты связности, или, другими словами, если а b для любых а,ЬєХ. Лемма 3.2. Пусть X — частично упорядоченное множество. Если О(Х) слабо регулярная в широком смысле полугруппа, то либо X связно, либо X — антицепь.
Если х у для некоторых х,уеХ, то х,у принадлежат одной компоненте связности. Следовательно, ха = уа. Это доказывает, что а сохраняет порядок, т.е. а є О(Х). Для доказательства леммы нам достаточно доказать, что а & ajBay и а Ф /Зауа при любых fi,y є О(Х).
Итак, необходимым условием слабой регулярности в широком смысле полугруппы О(Х) является тот факт, что либо X — антицепь, либо X связное множество. Так как случай антицепи вполне ясен, то далее мы будем рассматривать лишь связные множества. В последующих двух леммах мы докажем, что либо X — цепь, либо X не содержит подцепей более, чем из 3 элементов (будем называть такие множества трёхдольными).
Для частично упорядоченного множества X дуальным к X мы будем называть множество X с инвертированным порядком, т.е. множество {X , ), где а Ъ Ъ а. Очевидно, полугруппы 0{Х) и 0(Х ) изоморфны друг другу. Лемма 3.3. Пусть X — частично упорядоченное множество. Если полугруппа О(Х) слабо регулярна в широком смысле и X содержит подграф, изоморфный графу, изображённому на рисунке 3.5, то существует элемент z є X такой, что z b,d. Доказательство. Напомним, что по определению подграфа элементы d и Ь, а также d и с не сравнимы друг с другом. Определим отображение а: X — X правилом с, если л; 6, ха = Ъ, если х ". Ь, но х d, а в остальных случаях. Докажем, что а сохраняет порядок. Пусть х у. Если х Ь, то ха = уа = с. Если х б, но x d, то ха = Ь, а _уає{,с}, и мы имеем: х 2 7#. Если же x Z и xibd, то ха-а, а з/ае{а,й,с}, поэтому также л:а _уа. Таким образом, а є О(Х). Так как 0{Х) слабо регулярна в широком смысле, то а = аРау или а - Раусе при некоторых /?, у є О(Х). Предположим вначале, что а = аРау. По лемме 3.1 отображение /?а;к тождественно на множестве \та. Следовательно, аРау = а, bpay = b, с pay = с. Так как аРа, ЬРа, с Ра — различные элементы из \та и / переводит их соответственно в а,Ь,с, то ара = а, Ъра — Ъ, сРа = с. Далее, так как элементы ар, Ър и сР различны и Р є 0(Х), ар Ър ср. Так как (ЬР)а = Ь, то bp d; так как {сР)а = с, то сР Ь. Следовательно, cp b,d.
Предположим вначале, что a = aj3ay. Тогда по лемме 3.1 отображение pay тождественно на множестве im а = {0,1,2,3}. Очевидно, элементы ОРа, \Ра, 2pa и Ъра различны и принадлежат множеству \та. Так как уєО(Х), то 0ра = 0, \ра = \, 2/ = 2 и 3/ = 3. Далее, так как Qfi)a = \, то \р =1; так как (2/?)а = 2, то 2/7 = 1 . Так как р є 0{Х) и 1 2, то 1/? 2/9, т.е. 1 1 , а это противоречит тому, что 1 и 1 —несравнимые элементы.
Пусть теперь а = Рауа. Элементы 0,1, Г, 2 отображаются с помощью а соответственно в 0,1,2,3, следовательно, отображение Рауа также переводит 0,1,1 ,2 соответственно в 0,1,2,3. Отсюда следует, что элементы 0Pa, ipa, Vpa и 2Ра различны. Так как im а = {0,1,2,3}, то {0Pa,ipa,l Pa,2pa} = {0,1,2,3}. Ввиду того, что уаєО(Х), мы получаем: 0Ра = 0, \ра = \, \ Ра = 2, 2Ра = 3. Далее, так как (\рау)а = 1, то \рау = 1, а так как (l pay)a = 2, то V Pay -1 . Наконец, так как у є 0{Х) и \ра У Ра, то \рау VPay, т.е. 1 1 , мы снова получаем противоречие. Лемма доказана.
