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

■ / 7 ' О.....- У

/

Уральский государственный университет имени А.М.Горького

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

Жильцов Илья Юрьевич

ПСЕВДООПЕРАЦИИ И ПСЕВДОСВОБОДНЫЕ ПОЛУГРУППЫ

01.01.06 — Математическая логика, алгебра и теория чисел

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

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

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

доцент Коряков И. О.

Екатеринбург, 1999

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ................................... 3

ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ..................... 13

1. Комбинаторика слов ....................... 13

2. Переписывающие системы.................... 15

3. Проблема равенства слов в бернсайдовых многообразиях . . 16

4. Полугруппы ............................ 19

5. Унарные слова и унарно-полугрупповые тождества ..... 19

6. Псевдосвободные полугруппы .................. 20

Глава 1. У.П.-ТОЖДЕСТВА НА МНОГООБРАЗИИ § 22

§1. УНАРНЫЕ СЛОВА ВЫСОТЫ <1 ................... 23

1.1. Связь с бернсайдовыми многообразиями............ 23

1.2. О зацеплении под с лов..............................................25

1.3. Нормальные унарные слова высоты <1........................28

1.4. Доказательство теоремы 1.1.................. . 29

§2. ПРИМИТИВНЫЕ УНАРНЫЕ СЛОВА ................. 34

2.1. Факторизации 2-слов..............................................34

2.2. 2-слова, определяемые нормальными унарными словами . . 36

2.3. Доказательство критерия примитивности......................40

§3. ВПОЛНЕ ПРИМИТИВНЫЕ УНАРНЫЕ СЛОВА......................45

§4. НОРМАЛЬНЫЕ УНАРНЫЕ СЛОВА ВЫСОТЫ <2..................50

4.1. Леммы о ¿-образах нормальных унарных слов................54

4.2. Доказательство предложения 4.4................. 63

§5. ¿-ПРИВЕДЕННЫЕ ФОРМЫ ¿-ОБРАЗОВ..............................76

§6. ПРИВЕДЕННЫЕ ФОРМЫ ¿-ОБРАЗОВ................................88

6.1. Структура Г-образа..................................................88

6.2. Слова ер и их свойства............................92

6.3. Структура Г-образа.........................102

6.4. Доказательство предложения 6.1.................114

6.5. Доказательства теорем......................119

Глава 2. АРХИМЕДОВЫ ПОЛУГРУППЫ 122

§7. СТРОЕНИЕ ПОЛУГРУПП ЩШт...................122

7.1. Конструкция специальной архимедовой полугруппы.....123

7.2. Свойства специальных архимедовых полугрупп........130

7.3. Комментарии............................139

§8. ПРИЛОЖЕНИЕ..............................141

8.1. ИДт-распознаваемые языки...................141

8.2. Псевдосвободные полугруппы ранга 1 .............142

БИБЛИОГРАФИЯ................................145

АЛФАВИТНЫЙ УКАЗАТЕЛЬ........................148

ВВЕДЕНИЕ

1° Псевдомногообразием называется класс конечных универсальных алгебр, замкнутый относительно взятия подалгебр, гомоморфных образов и конечных прямых произведений. Большой интерес к изучению псевдомногообразий полугрупп и моноидов связан с одним из центральных результатов теории автоматов и формальных языков — теоремой Эйленберга [18]. В этой теореме устанавливается взаимно однозначное соответствие между псевдомногообразиями полугрупп (или моноидов) и так называемыми потоками рациональных языков, что позволяет использовать при изучении формальных языков методы теории полугрупп. При этом псевдомногообразия полугрупп [соотв., моноидов] возникают, если формальный язык определяется как подмножество свободной полугруппы [соотв., свободного моноида].

Несмотря на всю схожесть структурных определений псевдомногообразий и многообразий, долгое время методы исследования этих объектов значительно разнились. В первую очередь это связано с тем, что для псевдомногообразий неверен прямой аналог теоремы Биркгофа об аксиоматизируемости тождествами любого многообразия, а также с тем, что псевдомногообразия, как правило, не содержат даже конечнопорожденных (относительно) свободных алгебр. Положение дел начало меняться, когда в 1982 году Я. Рейтерман [29] предложил использовать для задания псевдомногообразий введенные им псевдооперации.

Поскольку в диссертации затрагиваются только псевдомногообразия полугрупп, приведем основные определения, ограничиваясь лишь полугрупповым случаем. Для натурального числа п и псевдомногообразия полугрупп V п-арной псевдооперацией (или неявной операцией) над V называется такое семейство отображений 7г = {7Г5 | ¿'бУ}, что:

• 7Г5 — всюду определенное отображение из в™ в 5;

• 7г устойчиво относительно гомоморфизмов из V, т. е. для каждой пары 5", Т полугрупп из V, любого гомоморфизма (р : Я Т и любых элементов ах,..., ап^3 имеет место равенство

тгтО^Ю, • • •, <р(ап)) = <р(кз(аъ ап)).

На множестве 0„¥ всех п-арных псевдоопераций над V задают операцию умножения, сопоставляя каждым 7Г, <т £ элемент тта £ О.„V, определяемый следующим условием: для любой полугруппы б'бУ и любых элементов а1? а2,..., ап£3

(тгст)5(а1, ...,ап)= 7Г 5(аь ..., ап)ег5(а1,..., ап).

Отметим, что данная операция ассоциативна. Полугруппу Г2ПУ наделяют инициальной топологией относительно семейства всех гомоморфизмов в полугруппы

из V (как в дискретные полугруппы), т. е. наименьшей топологией, при которой все указанные гомоморфизмы непрерывны. После введения такой топологии полугруппа 0ПУ становится топологической полугруппой. Она называется псевдосвободной полугруппой ранга п псевдомногообразия V. Псевдотождеством над V называют формальное равенство псевдоопераций над V. (Для обозначения всевозможных формальных равенств всюду далее используется символ =.) Говорят, что конечная полугруппа б'СЕУ удовлетворяет псевдотождеству 7г=ст над V, если 7Г5=сг5. Множество псевдотождеств П над V называют базисом псевдотождеств подпсевдомногообразия V/ в V, если конечная полугруппа из V принадлежит Щ тогда и только тогда, когда она удовлетворяет всем псевдотождествам из П. В своей работе Я. Рейтерман, существенно используя топологию, показал, что любое подпсевдомногообразие произвольного псевдомногообразия V имеет базис псевдотождеств над V ([29, теорема 3.1], см. также [16], [6, теорема 3.5.1.], [22]). Именно этот результат предоставил принципиальную возможность применить к теории псевдомногообразий богатый арсенал синтаксических методов исследования из теории многообразий. Первым успехом можно считать работу Алмейды и Азеве-до [12], в которой вычислено решеточное объединение псевдомногобразий К и I всех конечных ^-тривиальных и, соответственно, ^-тривиальных полугрупп. Отметим также два наиболее ярких последних достижения, полученных при помощи псевдоопераций:

• Марголис, Сапир и Вейль [25] доказали, что псевдомногобразие 8 всех конечных полугрупп и псевдомногобразие А всех конечных апериодических полугрупп не представимы в виде объединения, прямого произведения и мальцевского произведения собственных подпсевдомногообразий;

• Алмейда [9] нашел способ определения экспоненты неперестановочного апериодического псевдомногообразия, т. е. числа применений оператора степени, достаточного, чтобы получить из исходного псевдомногообразия псевдомногообразие 8 (под степенью псевдомногообразия мы подразумеваем псевдомногообразие, порожденное глобальными надполугруппами полугрупп исходного псевдомногообразия);

Только что перечисленные, а также многие другие результаты склоняют к мысли, что столь полезные инструменты, как псевдооперации и псевдосвободные полугруппы (и моноиды) достойны изучения сами по себе. Более того, в настоящее время этой проблематике посвящено уже, достаточно много работ. Этой же теме посвящена и данная диссертация.

Конкретно, нас будут интересовать следующие два направления:

• изучение некоторых наиболее часто используемых псевдоопераций псевдомногообразия так называемых иьпсевдоопераций (определение ниже);

• изучение псевдосвободных полугрупп псевдомногообразия 1Ь(Стот всех конечных расширений вполне простых полугрупп посредством нильпотентных полугрупп ступени <т (т. е. удовлетворяющих тождеству хгх2 •• - хт = 0).

Остановимся на каждом из них отдельно.

2° Первая глава диссертации посвящена задачам первого направления. Его важность объясняется тем, что обычно псевдомногообразие полугрупп пытаются задать именно псевдотождествами на 8. При этом из всего континуального разнообразия псевдоопераций на 8, как правило, бывает достаточно использовать лишь счетное число псевдоопераций специального вида, которые определяются следующим образом.

Унарным словом высоты 0 над алфавитом А назовем (возможно пустое) слово над А. Унарным словом высоты к + 1 над А назовем выражение

где I > 1. каждое (г является унарным словом над А высоты /г, и каждое является унарным словом над А высоты < к. Для элемента 5 конечной полугруппы 5 обозначим через единственный идемпотент из циклической подполугруппы, порожденной з. Пусть А — п-буквенный алфавит, скажем, А = {жх, ж2,..., ж„}, и пусть С — унарное слово над А. Для конечной полугруппы $ определим отображение : $п Я так, что для з2,..., элемент (5(51, з2,..., является значением выражения ( после подстановок хг = зг. Легко проверить, что семейство (С5)5е§ является псевдооперацией, которую будем называть ассоциированной с унарным словом И, наконец, под ш-псевдооперацией будем подразумевать псевдооперацию, ассоциированную с некоторым унарным словом.

Отчасти повторяясь, отметим, что большинство содержательных примеров базисов псевдотождеств образовано псевдотождествами, составленными из ш-псевдоопераций. Кроме того, именно си-псевдооперации являются наиболее полезными и часто встречаются в исследованиях, касающихся применения псевдоопераций к изучению псевдомногообразий (см., например, указанные выше работы [9], [12], [25]). Тем не менее, о самих си-псевдооперациях известно крайне мало. Неизвестен ответ даже на следующий естественный вопрос:

можно ли, а если можно, то как, выяснить, задают ли два данных унарных слова одну и ту же си-псевдооперацию?

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

Напомним, что унарной полугруппой называется полугруппа с дополнительной унарной операцией, рассматриваемая как универсальная алгебра типа (2,1).

Под операцией возведения в ш-степень на конечной полугруппе 5" будем подразумевать отображение 5 н-» Пусть обозначает класс всех конечных полугрупп с дополнительной унарной операцией возведения в о-'-степень, а § — многообразие унарных полугрупп, порожденное классом Напомним, что многообразие (универсальных алгебр) имеет разрешимую проблему равенства, если существует алгоритм, который по произвольному тождеству выясняет, выполнено ли оно в рассматриваемом многообразии. В противном случае говорят, что многообразие имеет неразрешимую проблему равенства. Отметим, что, как легко убедиться, полугруппа всех унарных слов над некоторым фиксированным алфавитом А, снабженная дополнительной унарной операцией С н-» (£)"' "приписывания (¿»-степени", свободна над А в многообразии всех унарных полугрупп. Это позволяет нам использовать унарные слова в качестве термов в сигнатуре унарных полугрупп. Поэтому под унарно-полугрупповым тождеством (или, короче, под у.п.-тождеством) будем подразумевать формальное равенство унарных слов. Легко проверить, что у.п.-тождество ( = £ выполняется на унарной полугруппе 5' € если и только если совпадают определенные ранее отображения (,$■ и £5. Следовательно, у.п.-тождество ( = С выполняется в классе (что равносильно "в многообразии 8"), если и только если унарные слова ( и £ определяют одну и ту же псевдооперацию. Таким образом, вышеупомянутый вопрос немедленно переформулируется в проблему равенства для свободной унарной полугруппы многообразия Кроме того, его можно трактовать как проблему нахождения у многообразия § базиса тождеств.

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

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

Закончим обсуждение первого направления следующим замечанием. На основании указанного выше сведения вопроса об а;-псевдооперациях к вопросам, касающимся многообразия далее в рамках первого направления мы исследуем именно многообразие

Теперь перейдем к задачам второго из ранее перечисленных направлений.

Полное описание строения псевдосвободных полугрупп получено лишь для относительно небольшого числа псевдомногообразий. В качестве основных примеров отметим псевдомногообразие LI всех конечных идеальных расширений прямоугольных связок посредством нильпотентных полугрупп (см., например, [15]), псевдомногообразие J всех конечных ¿/"-тривиальных полугрупп [8], а также, псевдомногообразие R. всех конечных 1Z-тривиальных полугрупп [14]. Для некоторых других псевдомногообразий удалось получить описание псевдосвободных полугрупп по модулю максимальных подгрупп, охарактеризовав последние, как подходящие псевдосвободные группы (т. е. псевдосвободные полугруппы подходящих групповых псевдомногообразий). А именно, описание получено в виде некоторой конструкции, составной частью которой являются псевдосвободные группы. Это относится, например, к псевдомногообразию CS всех конечных вполне простых полугрупп [10] и к псевдомногообразию DRG всех конечных полугрупп, в которых регулярные ©-классы являются правыми группами [14]. Кроме того, опираясь на [7, следствие 3.3, теорема 4.4] и [1, теорема 2.1] можно охарактеризовать строение псевдосвободных полугрупп объединения, пересечения и полупрямого произведения данных псевдомногообразий, указав некоторую связь таких псевдосвободных полугрупп с псевдосвободными полугруппами исходных псевдомногообразий.

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

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

• наибольшее псевдомногообразие, содержащее лишь тривиальные полурешетки;

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

• псевдомногообразие всех таких конечных полугрупп S, что все локальные подмоноиды из S (т. е. подполугруппы вида eSe, где е = е2 € S) являются группами

Кроме того, полурешетки полугрупп из LG образуют псевдомногообразие DS всех конечных полугрупп, в которых регулярные ©-классы образуют подполугруппы,

1 отсюда и англоязычный термин locally groups, приводящий к сокращению LG

изучению которого уделяется особое внимание (см., например, [15, раздел 2] и [6, раздел 8.1]).

Из очевидного равенства LG = (JmLGm в силу [15, Proposition 1.9] вытекает, что полугруппа iiJLG является проективным пределом полугрупп firJLGm относительно проективной системы, включающей все так называемые канонические гомоморфизмы участвующих псевдосвободных полугрупп. По этой причине мы направим свое исследование именно на псевдосвободные полугруппы псевдомногообразий LGm (ср. с подходом из разделов 10.6, 10.7, 10.9 в [6]).

Отметим, что псевдомногообразие LGi — это в точности псевдомногообразие CS всех конечных вполне простых полугрупп. Описание полугрупп fi„CS получено в [10] и довольно близко к описанию свободных алгебр хорошо известного клиффордова многообразия CS всех вполне простых полугрупп (независимо получено Клиффордом [17], Расиным [4] и Джонсом [23]). Поэтому ниже мы предполагаем, что т > 2. Кроме того в работе рассматривается более общий случай псевдомногообразия LHm всех полугрупп из LGTO с максимальными подгруппами из произвольного группового псевдомногообразия Н.

Основным результатом второй главы является описание псевдосвободных полугрупп iiraLIH[TO. Легко показать, что полугруппа 0„LIHITO является идеальным расширением некоторой вполне