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

ВВЕДЕНИЕ.3

Глава I. УПОРЯДОЧЕННЫЕ МНОЖЕСТВА И ПОЛУГРУППЫ

ЭНДОМОРФИЗМОВ.13

§1. Основные определения и обозначения.13

§2. Максимальные упорядоченности некоторых полугрупп преобразований.20

Глава 2. МНОГООБРАЗИЯ О-ПОЛУГРУПП.35

§1. Основные определения.35

§2. Решетка многообразий ö-полугрупп.47

§3. О покрытиях в решетке Z . .53

§4. Тождества в о-полугруппе .65

Глава 3. ЗАДАНИЕ 0-ПОЛУГРУПП ОПРВДЕЯЯЮПрШ

СООТНОШЕНИЯМИ.73 - III

§1. Способы задания о-полугрупп определяющими системами соотношений.73

§2. Некоторые алгоритмические проблемы в с-полугруппах, заданных определяющими соотношениями. . 89 -

§3. о-полугруппы, заданные одним определяющим соотношением предшествования.106 - III

БМВЛИОГРАЗМЯ.112

В последние годы заметно увеличилось число работ, посвященных изучению упорядоченных полугрупп. Здесь и ниже под упорядоченной полугруппой будем понимать частично упорядоченную полугруппу, порядок в которой двусторонне стабилен относительно действия. Причина особого выделения в теории полугрупп этого направления заключается как в естественности аксиоматики, так и в том, что во многих случаях, когда возникает необходимость рассмотрения тех или иных полугрупп, в них естественным образом обнаруживается отношение упорядоченности, игнорировать которое бывает либо нецелесообразно, либо просто невозможно. В особенности это проявляется при изучении полугрупп преобразований. Полугруппы преобразований играют в общей теории полугрупп исключительно важную роль. С одной стороны, как известно, каждая полугруппа изоморфна некоторой полугруппе преобразований. Таким образом, в некотором смысле всю теорию полугрупп можно рассматривать как абстрактное учение о суперпозиции преобразований. С другой стороны, теория преобразований - один из общих разделов теории полугрупп. Создание общей теории для исследования преобразований и было одной из первых задач теории полугрупп. При изучении полугрупп преобразований в них естественным образом определяются некоторые упорядоченности. Основные результаты направления, посвященного изучению упорядоченных полугрупп преобразований, изложены в обзорной статье М.Г.Могилевского [34].

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

Важным способом задания полугруппы является задание ее определяющими соотношениями над порождающим множеством. Этот способ используется и для задания групп, и для задания колец. В [18] он обобщен для задания алгебраических систем произвольной сигнатуры. Он может быть использован и для задания упорядоченных полугрупп. Роль определяющих соотношений в упорядоченной полугруппе играют соотношения предшествования, они определяют и действие, и порядок.

Одним из направлений общей теории полугрупп является теория полугрупповых многообразий. Было бы естественно поставить вопрос о разработке аналогичного направления в теории упорядоченных полугрупп. Постановка этой проблемы закономерна и обусловлена, на наш взглдц, следующими причинами. Во-первых, при изучении алгебраических систем любой сигнатуры рассмотрение тождественных соотношений дает основание для удобной классификации однотипных алгебраических систем. Во-вторых, выполнимость в алгебраической системе тех или иных тождественных соотношений является одним из важных свойств, во многом характеризующим и остальные ее свойства /например, коммутативность, ассоциативность/. В-третьих, тождественные соотношения играют важную роль при описании алгебраической системы с помощью определяющих соотношений. В общем случае алгебраическая система- имеет сложную по виду и нередко бесконечную совокупность определяющих соотношений. Поэтому принципиально важно то, что иногда некоторые подсовокупности определяющих соотношений, часто бесконечные, можно заменить одним или несколькими тождественными соотношениями. Все это в полной мере справедливо и для упорядоченных полугрупп. Роль тождественных соотношений в упорядоченных полугруппах будут играть тождественные соотношения предшествования. Говоря об обосновании разработки теории многообразий упорядоченных полугрупп, следует иметь ввиду еще одно обстоятельство. В теории упорядоченных полугрупп имеются направления по изучению определенных классов упорядоченных полугрупп. Некоторые из этих классов, например, класс всех положительно упорядоченных полугрупп, удобно описываются на языке многообразий упорядоченных полугрупп.

При изучении многообразий упорядоченных полугрупп возникает еще один вопрос. Известно, что любая полугруппа полугруппового многообразия может быть получена факторизацией свободной полугруппы этого многообразия. Для получения всех полугрупп многообразия упорядоченных полугрупп, как показано в этой работе, факторизации свободных полугрупп недостаточно, необходимо еще всевозможное продолжение получившихся в результате факторизации отношений в факторах до стабильных порядков. Отметим, что вопрос о продолжении порядка в полугруппе представляет и самостоятельный интерес. В частности, интересно выяснить, когда заданный в полугруппе порядок продолжим до линейного стабильного. В теории групп этот вопрос довольно подробно исследовался /см., например, [81, [10], [17]/. В общем случае и для групп и для полугрупп он решается отрицательно. Однако, известно, что любая упорядоченность полугруппы продолжила до максимальной ее упорядоченности /см. [14]/. Говоря о максимальных упорядоченностях, следует иметь ввиду следующий факт. Так как полугруппа - более простое алгебраическое образование, чем упорядоченная полугруппа, а также в связи с тем, что общая теория полугрупп более детально разработана, чем теория упорядоченных полугрупп, то возникает естественный вопрос: когда изучение упорядоченной полугруппы можно свести к изучению полугруппы, другими словами, когда упорядоченность полугруппы полностью определяется действием в ней. В частности, это оказывается так, если упорядоченность полугруппы является единственной, с точностью до направления, максимальной стабильной упорядоченностью. Поэтому, говоря о максимальной упорядоченности полугруппы, важно выяснить, не является ли она единственной, с точностью до направления, максимальной стабильной упорядоченностью.

Следует отметить, что в математической литературе тлеется ряд работ, непосредственно касающихся или близких по тематике к перечисленным выше направлениям. Важную роль в формировании общей теории упорядоченных полугрупп сыграли монографии Л.Фукса [28] и Г.Биркгофа [3]. Способ задания упорядоченных полугрупп определяющими соотношениями предшествования рассматривался, например, К.Торкалановым /см. [27], [35]/, однако, в его работах ставились в основном вопросы алгоритмического характера. При рассмотрении такого способа задания упорядоченной полугруппы важно поставить и другие вопросы: рассмотрение абстрактных упорядоченных полугрупп, заданных определяющими соотношениями предшествования над порождающим множеством, отыскание порождающих множеств и определяющих соотношений для некоторых конкретных упорядоченных полугрупп. Насколько нам известно, работа по изучению упорядоченных полугрупп с этой точки зрения не велась.

Что касается другого направления - направления по исследованию многообразий упорядоченных полугрупп, то задача построения этой теории ранее не ставилась, поэтому работ, непосредственно связанных с этой проблематикой, нет. Однако, следует отметить ряд работ, в которых исследуются сходные вопросы. В первую очередь к ним относятся работы по изучению полугрупповых многообразий. Основные результаты этого направления изложены в монографии Е.С.Ляпина [33] и обзорных статьях Т. Эванса [31] и А.Я.Айзенштат, Б.К.Богуты [I]. Тождественные соотношения предшествования рассматривал У.К.Куспанов в связи с изучением квазимногообразий упорядоченных полугрупп /см. [II]/. Вопросами, связанными с построением теории многообразий упорядоченных полугрупп, занимается В.Б.Репницкий /см. [24]/. К числу работ, связанных с данной проблематикой, относится также работа Л.Стефена [36], в которой рассматриваются многообразия упорядоченных алгебраических систем произвольной сигнатуры и дается их структурная характеристика. К числу работ данного направления можно отнести также все работы по изучению положительно упорядоченных полугрупп: класс всех положительно упорядоченных полугрупп образует многообразие упорядоченных полугрупп.

Целью настоящего диссертационного исследования является решение ряда вопросов в направлениях, указанных выше: рассмотрение некоторых конкретных упорядоченных полугрупп, развитие метода задания упорядоченных полугрупп порождающими множествами и определяющими отношениями, построение основ теории многообразий упорядоченных полугрупп. Для достижения данной цели в работе решаются следующие задачи. Выясняются вопросы, связанные с продолжимостью порядков в некоторых конкретных упорядоченных полугруппах. Формулируются исходные положения и общие первоначальные свойства теории многообразий упорядоченных полугрупп, поскольку ранее в литературе это не появлялось. Исследуются некоторые свойства решетки многообразий упорядоченных полугрупп: описываются ее атомы, выясняется ее связь с решеткой полугрупповых многообразий, решаются вопросы о покрытиях в ней. Способ задания упорядоченных полугрупп определяющими соотношениями рассматривается в связи с вопросами, которые ранее в литературе не ставились.

Все результаты диссертации являются новыми.

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

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

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

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

Вторая глава посвящена разработке исходных положений теории многообразий упорядоченных полугрупп, а также более детальному рассмотрению одного из ее направлений - изучению решетки многообразий упорядоченных полугрупп. Роль тождеств в упорядоченных полугруппах выполняют тождественные соотношения предшествования И^ТУ . В первом параграфе введены основные определения для построения теории многообразий упорядоченных полугрупп и приведены аналоги наиболее общих теорем из теории полугрупповых многообразий: аналог теоремы Биркгофа о структуре многообразий упорядоченных полугрупп, доказан аналог теоремы Бирюкова о следствиях, неоднократно применяющийся при доказательстве дальнейших результатов.

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

Множество многообразий упорядоченных полугрупп образует решетку по включению. Обозначим ее И . Она обладает некоторыми особенностями по сравнению с решетками многообразий других алгебраических систем. Например, наибольший ее элемент - многообразие всех упорядоченных полугрупп - порождается конечным числом своих собственных подмногообразий. Как известно /см. [20], [30] /, ни решетка групповых многообразий, ни решетка полугрупповых многообразий, ни решетка многообразий структур этим свойством не обладают. Другой особенностью решетки Т. является то, что в ней отрицательно решается вопрос о покрытиях /не всякое многообразие обладает покрытием/, тогда как в решетках полугрупповых и групповых многообразий этот вопрос решен положительно /см. [21], [25]/. Решетка многообразий упорядоченных полугрупп изучается во втором и третьем параграфах второй главы.

Каждое полугрупповое тождество можно рассматривать как пару тождественных соотношений предшествования: 11*1?, И . В множестве всех многообразий упорядоченных полугрупп выделим совокупность всех многообразий, которые могут быть заданы совокупностями полугрупповых тождеств. Множество таких многообразий образует подрешетку решетки 21, она изоморфна решетке полугрупповых многообразий. Обозначим ее . Представляет интерес выяснение вопроса о том, когда многообразие упорядоченных полугрупп содержится в А, , или, что то же самое, когда оно может быть задано совокупностью полугрупповых тождеств. Для случая одного тождественного соотношения предшествования этот вопрос решен полностью.

Решетка £ обладает атомами. Все ее атомы описаны. Показано, что каждое многообразие упорядоченных полугрупп содержит атом. Антиатомами решетка И не обладает.

Третий параграф посвящен решению некоторых вопросов о покрытиях в решетке 21 . Найдено многообразие упорядоченных полугрупп, не имеющее покрытий в 21 . Оно задается бесконечной системой тождественных соотношений предшествования, не эквивалентной никакой неприводимой системе. Здесь же положительно решаются вопросы о существовании покрытий в Т. для многих важных многообразий упорядоченных полугрупп: конечно базируемых, надкоммутативных, всех многообразий коммутативных упорядоченных полугрупп, всех многообразий положительно упорядоченных полугрупп, всех многообразий из Ь .

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

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

Во и качестве следствии из. этой теоремы и при помощи работ других авторов строятся совокупности определяющих соотношений для некоторых упорядоченных полугрупп преобразований. В этом же параграфе приводится еще один способ задания упорядоченных полугрупп - при помощи некоторой совокупности соотношений предшествования слов над порождающим множеством и некоторой совокупности тождественных соотношений предшествования. Целесообразность использования второго способа задания показана на конкретном примере: дан пример целого класса тождественных соотношений предшествования, каждое из которых задает упорядоченную полугруппу, которую нельзя задать никакой конечной совокупностью соотношений над порождающим множеством. Во втором параграфе рассматриваются алгоритмические вопросы: построен алгоритм, решающий проблему предшествования слов в некоторых классах упорядоченных полугрупп, в частности, в коммутативных упорядоченных полугруппах с одним или двумя определяющими соотношениями предшествования, в коммутативных конечно определенных упорядоченных полугруппах, если в них равны лишь слова, отличающиеся только перестановкой букв. В третьем параграфе исследуется полугруппа, заданная одним соотношением предшествования. В ней вопрос о равенстве слов решается тривиально: равны лишь графически равные слова. Проблема предшествования слов в ней также решена. Описываются все товдественные соотношения предшествования, выполняющиеся в ней. Дается полное описание группы ее автоморфизмов. Интересно отметить, что решение аналогичных вопросов для полугруппы с одним определяющим соотношением равенства представляет большие трудности, ни один из них полностью не решен, хотя имеется много работ, посвященных их решению.

1. Айзенштат А.Я., Богута Б.К. О решетке многообразий полугрупп. - В сб.: Полугрупповые многообразия и полугруппы эндоморфизмов. - Л.: ЛГПИ, 1979, с. 3 - 46.

2. Аршон С.Е. Доказательство существования -значных бесконечных асимметрических последовательностей. "Математический сборник". Т. 2, /44/, 1937, Р4, с. 769-777.

3. Биркгоф Г. Теория структур. М.: Иностранная литература, 1952. - 107 с.

4. Бирюков А.П. Полугруппы,зададнные тождествами. Уч. зап. Новосиб. гос. пед. ин-та, физика и математика, 1963, вып. 18, с.139-169.

5. Габович Е.Я. Линейно упорядоченные полугруппы и их приложения. "Успехи математических наук", 1976 /31/, №1,с. 137-201.

6. Зыбина Л.Д. О соотношениях, определяющих упорядоченность некоторых эндоморфизмов упорядоченного множества. Уч. зап. Ленинград, гос. пед. ин-та, т. 274, 1965, с. 106-121.

7. Зыбина Л.Д. Совокупности соотношений, определяющие упорядоченность частичных эндоморфизмов. Уч. зап. Ленинград, гос. пед. ин-та, т.274, 1965, с. 122-142.

8. Каргаполов М.И. Доупорядочизаемые группы. Алгебра и логика,1963, т. 2, №6, с. 5-14.

9. Клиффорд Л., Престон Г. Алгебраическая теория полугрупп. -М.: Мир, 1972. 288 с.

10. Кокорин А,И. К теории доупорядочиваемых групп. Алгебра и логика, 1963, т. 2, Р6, с. 15-20.

11. Куспанов У.К. О квазимногообразиях упорядоченных полугрупп. Мат. зап. Уральск, ун-та, 1974, т. 9, Р1, с. 30-39.

12. Ляпин Е.С. Соотношения, определяющие упорядоченность в упорядоченных полугруппах. Известия АН СССР, сер. "Математика", 1961, № /25/,с. 671-684.

13. Ляпин Е.С. Некоторые эндоморфизмы упорядоченного множества. Известия ВУЗов, сер. "Математика", 1962, №2 /27/,с. 87-94.

14. Ляпин Е.С. О максимальных двусторонне стабильных упоря-доченностях в полугруппах. Известия ВУЗов, сер. "Математика", 1963, №23, с. 88-94.

15. Ляпин Е.С. Направленные эндоморфизмы упорядоченных множеств. Сибирский математический журнал, 1970, PI, с.217-221.

16. Ляпин Е.С., Евсеев А.Е. Алгебра и теория чисел. 4.II. М„: Наука, 1978, - 448 с.

17. Мальцев А.И. О доупорядочивании групп. Труды математического ин-та им. В.Й.Стеклова, 1951, т. 38, с. 173-175.

18. Мальцев А.И. Алгебраические системы.-М.: Наука, 1970. -392 с.

19. Могилевский М.Г. Замечание об упорядочениях полугрупп полных преобразований. В сб.: Упорядоченные множества и решетки.- Саратов, СГУ, 1974, с. 24-25.

20. Нейман X. i,Многообразия групп. М.: Мир, 1969. - 264 с.

21. Ольшанский А.Ю. О некоторых бесконечных системах тождеств.- В кн.: Тр. семинара им. И.Г.Петровского. МГУ, 1978, вып.З, с. 139-146.

22. Попова Л.М. Определяющие соотношения полугруппы частичных эндоморфизмов конечного линейно упорядоченного множества. -Уч. зап. Ленинград, гос. пед. ин-та, 1962, т. 238, с. 72-86.

23. Попова Л.М. Определяющие соотношения полугруппы частичных преобразований конечного множества. Уч. зап. Ленинград, гос. пед. ин-та, 1961, т.218, с. 39-44.

24. Репницкий В.Б. О базисах многообразий ctt¿-полугрупп.В кн.: Тезисы WI Всесоюзной алгебраической конференции. Ч. 2, Л.: Ленинград, отдел. Математического ин-та АН СССР,1981, с.112,

25. Трахтман А.Н. О покрывающих элементах в структуре многообразий алгебр. Математические заметки, 1974, Р2, с.307-312.

26. Ляпин Е.С. Полугруппы М.: Физматгиз, i960. - 592 с.

27. Торкаланов Кр. Один класс частично упорядоченных полугрупп с разрешимой проблемой неравенства. Доклады Болгарской АН, 1970, №2 /23/, с. 129-132.

28. Уз'лрСп S. ô. Угт.Сдгоир$ . 5-ed dim. cMaftt bot, /m

29. Steptbcn. L. Vcurietie& of ordered, a/geétщ, У Cotvfuí, tuitcm. {9?6, noZ, Z00-Z09.