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

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

Ким Виктор Иргюевич

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

Специальность 01 01 06 - математическая логика, алгебра и теория

чисел

Автореферат

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

Ульяновск -2008 г

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

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

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

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

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

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

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

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

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

Ведущая организация

ГОУ ВПО Московский педагогический государственный университет

Защита диссертации состоится «18» июня 2008 года в 13— часов на заседании диссертационного совета Д 212 278 02 при Ульяновском государственном университете по адресу ул Набережная р Свияги, 106, копр 1,ауд 703

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

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

Автореферат разослан « »_2008 г

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

M А Волков

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

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

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

Различные аспекты полугрупп преобразований можно найти в работах многих математиков, как российских, так и зарубежных А Я Айзенштат1 построила копредставление полугруппы изотонных преобразований конечной цепи, т е задание этой полугруппы образующими и соотношениями Б М Шайн2 исследовал условия представимости элемента полугруппы изотонных преобразований произвольной цепи в виде произведения идемпотентов Эквивалентность элементарных теорий полугрупп изотонных преобразований рассматривалась Ю М Важениным3 и Л А Скорняковым 4 П М Хиггинс, Ж Д Митчелл и Н Рушкуц 5 для

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

2 Schein В М Products of idempotent order-preserving transformations of arbitrary chains// Semigroup Forum 1975 Vll N1 P 297-309

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

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

некоторых цепей находили ранг полугруппы преобразований относительно полугруппы изотонных преобразований Перечислительно-комбинаторным вопросам полугруппы изотонных преобразований посвящена серия работ А Умара (см , например, [б]6, [7]7) А Крохин 8 и Б Ларуз 9 изучали клоны операций, сохраняющих порядок конечной цепи

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

В работе А Я Айзенштат" было получено исчерпывающее описание частично упорядоченных множеств X, не являющихся цепями и имеющих регулярную полугруппу 0(Х) Кроме того, в этой работе были сформулированы условия регулярности полугруппы 0(Г), где Г - цепь

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

5 Higgms Р М, Mitchell J D , RuSkuc N Generating the full transformation semigroup using order preserving mappings// Glasgow Math J 2003 V 45 P 557-566

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

7 Umar A On certain infinite semigroups of order-decreasing transformations 1// Communications m algebra, 25(9), pp 2987 - 2999,1997

8 Larose В A completeness criterion for isotone operations on a finite chain// Acta Sci Math (Szeged) 1994 V 59 N3-4 P 319-356

9 Krokhin A, Larose В A monoidal interval of isotone clones on a finite chain// Acta Sci Math (Szeged) 2001 V 68 N1-2 P 37-62

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

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

(те таких полугрупп что а е ЗаБаипри всех аеБ) Естественно спросить, для каких частично упорядоченных множеств их полугруппы изотонных преобразований будут обладать свойством слабой регулярности9 Кроме того, представляет интерес следующий вопрос- насколько изменятся условия (слабой) регулярности, если ослабить требование на множество X, а именно, считать X квазиупорядоченным множеством9

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

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

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

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

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

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

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

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

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

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

Достоверность результатов проведённых исследований.

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

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

Апробация результатов. Основные результаты диссертации докладывались на семинаре «Кольца и модули» кафедры высшей алгебры механико-математического факультета МГУ им Ломоносова, на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (г Москва, Зеленоград, Московский институт электронной техники, 2004, 2005, 2006, 2007 гг), на 6-й Международной алгебраической конференции на Украине (6th International Algebraic Conference in Ukraine, July, 2007).

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

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

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

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

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

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

преобразований конечных множеств Приводится краткий обзор работ по данной тематике

Вторая глава диссертации посвящена изучению строения полугруппы изотонных преобразований О(Х) и полугруппы изотопных преобразований с убывающим порядком 0(Х), т е полугруппы преобразований, являющихся изотонными и удовлетворяющих дополнительному условию ха < х при всех х е X, где X - конечная цепь

Если множество X конечно и \Х\ = п, то полугруппу 0(Х) будем обозначать 0„, а полугруппу В(Х) - й„ £ - и классы полугруппы 0„ хорошо известны А именно, как и в полугруппе Т„ всех преобразований и-элементного множества, в полугруппе 0„ мы имеем а £ /? о т а = гтД а 1ЦЗ о кег а = кег /} (здесь для отображения <р X -> У образ шср и ядро кег ср определены обычным образом тср = Хср, кег$? = {(а,£)е X * X \ а<р = Ь<р}) В отличие от полугрупп Тп и Оп полугруппа Dn является £ - и ^ -тривиальной, т е справедливо следующее утверждение

Утверждение 1. Если а, р е А,, то а С р <=> ог =/7и а%,р о а=р

Ф4 1234

Фз

Ф2

1123 1124 1134 2234

1223 1224 1334 2334

1233 1244 1344 2344

1112 1113 1114 2223 2224 3334

1122 1133 1144 2233 2244 3344

1222 1333 1444 2333 2444 3444

1111 2222 3333 4444

Таблица 1. "egg-box" - картина для 04

Для краткости будем использовать лишь информативную часть общепринятого обозначения преобразования, т е преобразование

2 3 п^

а =

будем записывать в виде строки г,ад. i„

Таблица 1 является «egg-Ьохл-картиной полугруппы О4 Здесь в строках расположены преобразования, принадлежащие ^.-классам, а в столбцах L -классам © -классы выстроены по возрастанию ранга образов (классу принадлежат в точности те преобразования, образы которых одноэлементны, ©г - двухэлементны, ©3 - трёхэлементны, Ф4 - в образе четыре элемента) Идемпотенты и L -классов выделены жирным и курсивом

Полугруппа D„ при п > 3 не является регулярной В ней множество регулярных элементов совпадает с множеством идемпотентов, как показывает следующее утверждение

Утверждение 2 Элемент aeDn регулярен в том и только том случае, если а - идемпотент

Для количественной характеристики полугруппы D„ была выведена рекуррентная формула

п пнг}( п-1 к)

|А,| = где f(n' к) = Z Л"'1-1), причем

<t = i i = ]

f(n, п) =f(n, п- = - 1, 1)

1 =1

На основе этой рекуррентной формулы нетрудно произвести оценку мощности полугруппы D„

З"'2-\<\D„\<22"-'. В связи с L - и -тривиальностью полугруппы D„ для нее имеет смысл рассматривать обобщённые отношения Грина L и 11 Напомним определения этих отношений на произвольной полугруппе S (а, Ь)е£ (соотв, (а, Ь) б 5?, *) в том и только том случае, если (a, b)eL (соотв, (я, Ь)е (¡0 в некоторой надполугруппе Т э 5 Кроме того, если полугруппа Т регулярна, то ее £ -классы (соотв., 5?. -классы) «вырезают» на полугруппе 5 ¿'-классы (соотв, 5^-классы) Для полугруппы D„ в качестве такой полугруппы можно выбрать полугруппу 0„

12345

11234 11235 11245 11345

12234 12235 12245

12334 12335

12344

11123 11124 11125 11134 11135 11145

11223 11224 11225 11334 11335

11233 11244 11255 11344

12223 12224 12225

12233 12244 -

12333 '

11112 11113 11114 11115

11122 11133 11144

11222 11333

12222 1 -

11111

Таблица 2 £ и 11- отношения Грина

полугруппы !>„

Таблица 2 иллюстрирует строение классов обобщенных отношений Грина полугруппы Д, на примере полугруппы Ц>- Таблица получена из таблицы (Ц. -классов полугруппы 0} путем удаления элементов, не принадлежащих полугруппе Д По строкам расположены -классы, по столбцам - С -классы Как видно из таблицы 2, каждый чС - и £* -класс содержит ровно по одному идемпотенту и, если таблицы Фг-классов выстроены в лексикографическом порядке (каждый столбец и каждая строка), то идемпотенты образуют диагональ (в таблице выделены жирным и курсивом), отделяющую элементы полугруппы Д, от других элементов полугруппы 0„

Как уже было установлено, полугруппа 0(Х) регулярна для конечной цепи X Но она регулярна далеко не всегда, если X -бесконечная цепь Во второй главе диссертации получены необходимые и достаточные условия регулярности полугруппы 0(Х), если Х-счетная цепь Формулировку основной теоремы данной главы приведем после некоторых определений

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

(минимальности), если в ней нет бесконечных возрастающих (соотв, убывающих) последовательностей элементов Сечением (А, В) называется разбиение Г = А и В цепи Г на два непустых подмножества А и В таких, что а < b при всех а е А, be В Если Г не полна, то существует сечение (А, В) такое, что не существуют sup А и mf В В этом случае сечение (А, В) называется дырой

Для частично упорядоченного множества X и элемента хеХ положим = {у \ у < х} (нижний конус элемента х), xv = {у | у > х} (верхний конус)

Теорема 1. Пусть Г - счетная цепь Тогда полугруппа 0(Г) регулярна в том и только том случае, если выполнено одно из следующих условий

(1) Г - полная цепь, имеющая минимальный и максимальный элементы,

(2) Г не имеет максимального, но имеет минимальный элемент и для любого х е Г множество хЛ удовлетворяет условию максимальности,

(3) Г не имеет минимального, но имеет максимальный элемент и для любого х е Г множество xv удовлетворяет условию минимальности,

(4) r = Z,

(5) Г имеет минимальный и максимальный элементы, Г = АиВ и (А, В) - дыра, причем для любого х е А множество хЛ удовлетворяет условию максимальности и для любого хе В множество xv удовлетворяет условию минимальности

Третья глава диссертации посвящена изучению полугруппы изотонных преобразований О(Х), где X - частично упорядоченное множество, не являющееся цепью (будем называть такие множества НЕ-цепями)

Полугруппу S будем называть слабо регулярной в широком смысле, если а б SaSa u aSaS для любого а € S Класс таких полугрупп существенно шире класса регулярных полугрупп

Если X - антицепь, то О(Х) = Т(X), поэтому О(Х) -регулярная полугруппа Вопрос о том, для каких частично упорядоченных множеств X полугруппа 0(Х) является регулярной, исследовался А Я Айзенштат Ею было получено прозрачное описание частично упорядоченных множеств X, не являющихся цепями и

имеющих регулярную полугруппу О(Х) Цель данной главы -обобщить теорему Айзенштат с регулярного случая на слабо регулярный Приведем основные теоремы главы, предварительно определив некоторые классы частично упорядоченных множеств

Для произвольного множества 1 пусть Ь, - {а, с} и {¿, | / е /} с отношением порядка таким, что а < Ъ1 <с при всех ; € I (см рисунок 1) Если / - конечное множество и \1\=п, то вместо Ь, мы будем писать I

п

С

и

Рисунок 1

Пусть У, 2 - произвольные непустые непересекающиеся множества Положим 2 = У и 2 Отношение порядка- на Рг г определим следующим образом у <2 при уеУ, г е 2, остальные пары элементов не сравнимы Граф этого множества - полный двудольный граф (см рисунок 2)

Рисунок 2

Для произвольных непустых непересекающихся множеств У, 2 с выделенными в них элементами у0 е У, г0 е 2 положим Оу 2 = У 2 и определим порядок следующим образом у0 < г, у < г0 уеУ, г € 2, остальные пары элементов не сравнимы (см рисунок 2) Если У и 2 -

конечные множества и | У |= т, \1\ =п, то вместо Ру 2 мы будем писать Ртп, а вместо Оу 2 будем писать Стп

Наконец, пусть С6 = {1,2,3,4,5,6}, где 1<4, 1<5, 2 <5, 2 <6, 3 <6, 3 < 4 (см см рисунок 2)

Теорема 2. Пусть X - частично упорядоченное множество, не являющееся цепью Тогда полугруппа О(Х) слабо регулярна в широком смысле в том и только том случае, если выполняется хотя бы одно из условий (1) X - антицепь, (2) Х = Ь¡, (3) Х = Еуг, (4)

Х = Огг, (5)Х = С6

Пусть (Х,<) - квазиупорядоченное множество (те бинарное отношение х рефлексивно и транзитивно) Для множества X вопрос о слабой регулярности полугруппы 0(Х) решается, за одним исключением, так же, как для частично упорядоченных множеств А именно, справедлива следующая теорема

Теорема 3 Пусть (Х,-<) - квазиупорядоченное множество, не являющееся линейно упорядоченным Полугруппа 0(Х) = 0(Х,-<) слабо регулярна в широком смысле в том и только том случае, если выполнено хотя бы одно из следующих условий

(1) х<у для любых х.уеХ,

(2) X - частично упорядоченное множество, являющееся антицепью или изоморфное какому-либо из множеств Ь,, Ру г,

С,

Следствие. Пусть (Х,<) - квазиупорядоченное множество, не являющееся линейно упорядоченным Полугруппа О(Х) регулярна в том и только том случае, если выполнено хотя бы одно из следующих условий

(1) х<у для любых х,уеХ,

(2) X - частично упорядоченное множество, являющееся антицепью или изоморфное какому-либо из множеств Ь,, 0Г2,

С6

Пусть X, У - частично упорядоченные множества и 0(Х,У) -множество всех изотонных отображений Х—+У Множество 0(Х,У)

полугруппой, вообще говоря, не является, но оно является биполигоном над полугруппами О(Х) и О (У), причем О(Х) действует на 0(Х, У) слева, а 0(У) справа Следующее утверждение показывает, что в случае конечных цепей этот биполигон является моногенным, т е порождается одним элементом

Теорема 4. Если Х,У - конечные цепи, то 0(Х, У) = 0(Х)Р0(У) при некотором реО(Х,У) Более того, имеет место одно из равенств 0(Х,У) = 0(Х)Р или 0(Х, У) = рО(У)

Четвёртая глава диссертации посвящена изучению двух интересных подполугрупп полугруппы 0(Х), а именно полугруппы 0/т(Х) конечных изотонных преобразований и полугруппы Осо/т{Х)

коконечных изотонных преобразований. Пусть X, У - частично упорядоченные множества, О(Х) - полугруппа изотонных преобразований а X X Конечным назовем такое преобразование а Х->Х, что \Ха\<оэ Преобразование а XX называется коконечным, если | X \ Ха \ < оо Обозначим через 0}т (X) множество всех конечных, а через ОсоГт (X) - множество всех коконечных изотонных преобразований а.Х->Х Множества 0}т(X) и Осфп(Х) являются подполугруппами полугруппы О(Х) Если X - конечное множество, то Ом(Х) = 01оГш(Х) = 0(Х)

Основной результат главы сформулируем в виде следующей теоремы

Теорема 5. (1) Для любой цепи Г полугруппа Орп (Г) регулярна (2) Если Г - бесконечная счетная цепь, то полугруппа (Г) не регулярна

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

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

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

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

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

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

Орп{Х) произвольной цепи X регулярна, а полугруппа

коконечных изотонных преобразований Осо/ш (X) бесконечной счетной цепи X не регулярна

Полученные результаты позволяют более полно судить о строении полугрупп изотонных преобразований частично упорядоченных и квазиупорядоченных множеств Если частично упорядоченное множество является линейно упорядоченным, то в конечном случае полугруппа изотонных преобразований данного множества регулярна В случае бесконечной счетной цепи, регулярность полугруппы изотонных преобразований имеет место в том и только том случае, если цепь удовлетворяет условиям, сформулированным в работе Для частично упорядоченных, а также квазиупорядоченных множеств, не являющихся цепью, получены условия слабой регулярности полугруппы изотонных преобразований, что обобщает условия регулярности данной полугруппы частично упорядоченного множества, полученные в 1968 г А Я Айзенштат Однозначно можно сказать, что доя произвольной цепи полугруппа всех изотонных преобразований, имеющих конечный образ, регулярна, а для бесконечной счетной цепи полугруппа всех изотонных преобразований, образ которых имеет конечное дополнение, не регулярна

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

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ.

Публикации в журналах из списка ВАК

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

Публикации в прочих изданиях

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

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

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

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

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

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

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

[9] Kim VI On isotone mappings of partially ordered sets. //6th International Algebraic Conference in Ukraine, July, 2007, p 99

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

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

Отпечатано в типографии МИЭТ (ТУ) 103498, Москва, МИЭТ (ТУ)

Введение.

Глава 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 наименований.

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.