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

• Жильцов, Илья Юрьевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Жильцов, Илья Юрьевич

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Псевдооперации и псевдосвободные полугруппы»

ВВЕДЕНИЕ

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 является идеальным расширением некоторой вполне простой полугруппы С посредством свободной нильпотентной полугруппы ступени то (т. е. свободной полугруппы многообразия, определяемого тождеством Х\Х2 • ■ ■ хт = 0). Тем не менее, даже структура максимальных подгрупп из С до последнего времени оставалась неизвестной. Из полученного в диссертации описания следует, что эти подгруппы изоморфны псевдосвободным полугруппам ранга пт(п — 1) + 1 псевдомногообразия Н всех конечных групп. С другой стороны, псевдомногообразие LHTO содержит подпсев-домногообразие С8(Н) = LHi всех вполне простых полугрупп с максимальными подгруппами из Н. Поэтому было бы естественно ожидать, что полугруппа С изоморфна некоторой псевдосвободной полугруппе псевдомногообразия CS(H). Однако из полученного описания следует, что в общем случае это не верно. Доказательства основаны на свойствах так называемых специальных архимедовых полугрупп, которые введены автором в [35]

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

Первая тема связана с упомянутой в начале введения известной теоремой Эйленберга, которая устанавливает взаимно однозначное соответствие между псевдомногообразиями полугрупп и так называемыми потоками рациональных языков. При этом сопоставляемый псевдомногообразию V поток языков состоит из всевозможных булевых алгебр £(Л, V) всех V-распознаваемых языков над конечным алфавитом А. Поэтому важным приложением основных ре-

зультатов второго направления является полученная в работе характеризация ЬНт-распознаваемых языков, а также, описание булевой алгебры всех ЬИт-распознаваемых языков над фиксированным конечным алфавитом.

Переходя ко второй теме заметим, что любая конечная однопорожденная полугруппа является архимедовой. Отсюда вытекает, что псевдосвободная полугруппа ранга 1 произвольного псевдомногообразия изоморфна псевдосвободной полугруппе ранга 1 подпсевдомногообразия всех архимедовых полугрупп исходного псевдомногообразия. По этой причине в рамках изучения псевдосвободных полугрупп псевдомногообразий архимедовых полугрупп естественно исследовать псевдосвободные полугруппы ранга 1 произвольного псевдомногообразия. Именно этому и посвящена вторая часть приложения. В частности, исследовано действие унарных псевдоопераций на конечных полугруппах, строение ядра отображения, сужающего действие псевдоопераций с псевдомногообразия всех полугрупп 3 на произвольное псевдомногообразие V и строение полугрупп Г2ХУ. Отметим, что ранее наиболее полная информация об унарных псевдооперациях содержалась в работе Алмейды и Азеведо [13] (см. также [6, раздел 4 параграфа 3.7]) и касалась только псевдоопераций псевдомногообразия К сожалению, описание самих псевдоопераций и всей однопорожденной псевдосвободной полугруппы было сделано в крайне неудобных терминах, что делало невозможным обобщение полученного результата на произвольные псевдомногообразия.

3° Перейдем теперь к точным формулировкам результатов диссертации. Высотой у.п.-тождества назовем максимальную из высот унарных слов, составляющих это у.п.-тождество. Множество / у.п.-тождеств высоты <к назовем базисом высоты к многообразия унарных полугрупп V, если произвольное у.п.-тождество высоты < к выполняется в V тогда и только тогда, когда оно является следствием из I. Отметим, что, как легко видеть, если для каждого положительного целого к множество /д является базисом высоты к многообразия V, то объединение I — //г является обычным базисом многообразия V. Через £1 обозначим множество, состоящее из у.п.-тождеств

(;ХП)Ш = Хш, П> 2,.

СО СО • СО

- «АУ

х(ух)ш = (ху)шх,

множество, состоящее из у.п.-тождеств

(хп)ш = хш, п> 2,

(.хш)" =

(,хшх)ш = хш,

хш(хшу)ш = С*ШУГ,

(ух Т^ =

(хшухшГ = (хшу)шхш,

х((у1хт---{учху)ш = ({ху1у---{хучуух, д> 1. Основными результатами главы 1 являются

Теорема А. (теорема 1.1) Множество Ех является базисом высоты 1 многообразия я

Теорема В. (теорема 6.29) Множество Ег является базисом высоты 2 многообразия §. я

Теорема С. (теорема 6.32) Существует алгоритм, определяющий выполняется ли данное у.п.-тождество высоты <2 в многообразии §. я

Отметим, что с формальной точки зрения теорема С является следствием теоремы В. Действительно, поскольку множество Е2 счетно, множество у.п.-тождеств высоты <2, выполняющихся в §, рекурсивно перечислимо. С другой стороны, множество таблиц Кэли неизоморфных конечных полугрупп также рекурсивно перечислимо. Поэтому, перечисляя те и другие, мы либо встретим исследуемое у.п.-тождество, либо найдем конечную полугруппу, на которой оно не выполняется. Однако такой алгоритм крайне трудоемок с точки зрения его реализации. Поэтому представляется полезным найденный в данной работе существенно более простой алгоритм. А именно, построена такая переписывающая система 712 (параграф 4), что 7^-2 полна и вычислима над множеством унарных слов высоты <2 (следствие 6.28) и верна

Теорема Ю. (теорема 6.30) У.п.-тождество ( = £ высоты <2 выполняется в многообразии §, если и только если унарные слова ( я ( имеют одинаковые

приведенные формы, я

Отметим, что вытекающий отсюда алгоритм гораздо менее трудоемок, чем описанный ранее. Более того, для нечрезмерно длинного унарного слова вычисление его ^-приведенной формы можно реализовать "вручную" за разумное время. Поэтому такой алгоритм имеет не только теоретическую, но и практическую ценность.

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

Для целого положительного к определим к-образ унарного слова ( как слово, получаемое из ( посредством замены ( )ш —( )к для всех вхождений ш в Длиной |(| унарного слова ( назовем длину 1-образа т. е. длину слова, получающегося из ( при удалении всех символов ( )ш.

Теорема Е. (теорема 6.31) Пусть (о я £ о — некоторые 1Z2-приведенные формы произвольных унарных слов ( высоты <2 соответственно. У.п.-тождество ( = £ выполняется в многообразии S. если и только если полугрупповое тождество ^(k) ^ £(k) ВЬШолняется в бернсайдовом многообразии var[a:fc = х2к] для всех [для какого либо] k > 8тах(|(0|, |£о|)-

Условие к > 8тах(|(о|, |£о|) по смыслу означает, что к — "достаточно большое" число. В связи с этим выбор именно константы 8 представляется не очень принципиальным и объясняется следующей причиной: это наименьшая константа, которая хорошо легла в канву доказательства.

Для фиксированного множества А с выделенным элементом у в разделе 7.1 определяется так называемая специальная архимедова полугруппа Sm(G,a), где структурными параметрами являются число m, > 1, группа G и произвольное отображение а множества А^ = (А \ {y})y.Am (J {у}х{ут} в G. Основными результатами главы 2 являются

Теорема F. (теорема 7.1) Пусть Н — псевдомногообразие групп, m, > 1, А —конечное множество с выделенным элементом у и А^ = (А\{?/})хАт (J {?/}х{?/т}. Тогда, псевдосвободная полугруппа i]|yi|LlHIm изоморфна топологической полугруппе 8т(П|Л(т)|Н, f3), где /3 — биекция множества на каноническое порождающее множество псевдосвободной группы Г2Л(т)Н.

Теорема G. (предложение 7.2) Максимальные подгруппы псевдосвободной полугруппы finLHm ранга п псевдомногообразия LHm изоморфны псевдосвободной полугруппе ранга nm(n — 1) + 1 группового псевдомногообразия Н.

Теорема Н. (предложение 7.3) Если п > 2, m > 2 и групповое псевдомногообразие Н нетривиально, то ядро псевдосвободной полугруппы 0„]ЫШт не изоморфно ни какой псевдосвободной полугруппе псевдомногообразия CS(H).

Поскольку приложение к главе 2 занимает небольшой объем, приведем лишь самый главный результат по каждой из затрагиваемых в нем тем.

Множество всех подмножеств множества В обозначим через В{В), множество всех V-распознаваемых языков над В — через С(В, V). Будем рассматривать множества

B{A<m),C{A^m\ Н), и С(А, LHm) как булевы алгебры (с обычными операциями объединения, пересечения и дополнения), а множество С{А^т\ Ш)АтхАт всех отображений из Ат х Ат в С(А^т\ ИГ) — как степень булевой алгебры £(А(т),Н). В параграфе 8.1

для слов u, v £ Ат и языка К над алфавитом А^

определяется язык L(u,K,v).

Теорема I. (теорема 8.4) Пусть А — конечное множество, m > 1 и Н — псевдомногообразие групп. Тогда следующее отображение является изоморфизмом булевых алгебр.

Г : В{А<т) х С(А^т\ Ш)АтхАт £(Л,Шт),

(М, ф) М и и«

tv£Am L(u, ф[и, и), и).

и

Как обычно, N обозначает множество всех натуральных чисел, а р^ обозначает к-ое простое число. Дискретная группа Ъ/пЪ вычетов по модулю п обозначается через а ее элементы — через 0,1,... . Напомним, что аддитивная топо-

логическая группа Ъ,р целых р-адических чисел есть подгруппа топологической группы ПгеКгЖр1)' состоящая из таких последовательностей й = (о^, ...), что для каждого канонический гомоморфизм из Z(pг+1) в 2{р1) переводит ¿(»+1) в Топологическая группа Ъ определяется как прямое произведение топологических групп Пг'еК .

Сопоставим элементу ( = ((1, (2, Сз, • • •) € Ъ функцию Щ : N —> N и {0}, задаваемую следующим образом. Если п = р^р^ • • • р^ € ГЧ, то значение Щ(п) определяется из двух условий:

. Щ{п) € {0,1,..., п — 1},

• Н((п) = ({^(тос! * =

Каждому элементу ( € Ъ сопоставим псевдооперацию и{С,). определяемую следующим условием: для всех € §и 5 £ 5

КСИ*) = (^<тс(|си)-

Теорема 3. (теорема 8.7) Отображение V : Z —> Г^В \ Г2х§> является изоморфизмом топологических групп.

Основные результаты работы докладывались на Международной конференции "Полугруппы и их приложения, включая полугрупповые кольца" (С.Петербург, 1995), Международной конференции по алгебре (С.-Петербург, 1997), а также на семинаре Московского государственого университета и семинаре "Алгебраические системы" Уральского государственого университета. Они опубликованы в работах [30]—[36].

Работа выполнена под руководством доцента Игоря Олеговича Корякова, которому автор выражает глубокую благодарность за постоянное внимание и всестороннюю поддержку.

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

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

целые числа (обычно натуральные): i, к, I, га, п, д,г;

буквы некоторого алфавита: х,у;

слова: и, г>, ио, г, а, Ь;

унарные слова: а, /9;

отображения:

псевдооперации: 7г,<т.

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

Всюду далее через А обозначается некоторое конечное множество, называемое алфавитом, элементы которого называют буквами. Словом, над алфавитом А называется конечная (возможно, пустая) последовательность букв. Множество всех непустых слов [всех слов] над А обозначается через А+ [соотв. А*]. Обычно это множество рассматривается вместе с операцией конкатенации, т. е. присоединения одного слова в конец другого. Хорошо известно, что множество А+ [множество А*], снабженное такой операцией, является свободной полугруппой [свободным моноидом] на множестве А.

Говорят, что слово V является подсловом слова т (содержится в и), входит в и'), если существуют такие слова Ю1,ги2, что ю = Ю1УШ2. Слова ъи 1 и го2 могут определяться неоднозначно. В этом случае мы говорим о разных вхождениях подслова V в слово IV. Желая указать конкретное вхождение, мы будем писать ю = Юг ■ V ■ и>2 или будем изображать его диаграммой, подобной следующей:

V и> 2

= ' V У ^ .

Слово V называют префиксом [суффиксом] слова ш, если существует такое слово и, что ю = уи [г£> = ии]. Длиной |и;| слова из называют число вхождений букв в это слово. Говорят, что слово IV является и-периодическим, если ю является подсловом некоторой степени слова и. Слово ю называют I-периодическим, если оно и-периодично для некоторого слова и длины I. Непустое слово называют примитивным, если оно не является степенью другого слова. Два слова и и V называют сопряженными, если найдутся такие слова что и = к^г^ и

V = "№2^1. При одновременном рассмотрении двух подслов и и и одного и того же слова ш всегда будем иметь ввиду некоторые конкретные вхождения гх> = и>г • V • ю2 = и?з • и ■ го4, и будем говорить, что подслово V содержится в подслове и (входит в и), если ¡-гх>11 > |г«з| и ¡гог! >

V

«, =-, ' ;- -

и 13

Объединением подслов и и V слова ю называют минимальное подслово слова IV, в которое входят как и, так и V. Два подслова некоторого слова называются пересекающимися, если они содержат общее непустое подслово. Пересечением пересекающихся подслов ми V слова ю называют максимальное подслово слова г«, которое входит как в и, так и в V, а пересечением непересекающихся подслов — пустое слово:

и и

и.

V

г -}-

объединение пересечение

Понятия объединения и пересечения обычным образом распространяются на конечные семейства подслов. Если слово w представимо в виде w = vu, то через ■иш-1 будем обозначать слово v, в противном случае выражение wuне определено. Двойственным образом определяется выражение

Всюду далее мы будем использовать без ссылок следующие хорошо известные факты из комбинаторной теории слов (см., например, [3] или [24]).

• Слово, сопряженное к примитивному, само примитивно.

• Каждое слово являтся степенью в точности одного примитивного слова.

• Если слово w /-периодично, то оно u-периодично для любого своего подслова длины I. Кроме этого, все подслова из w длины I попарно сопряжены.

• Если слово v примитивно, то любая его степень содержит вхождения слова v лишь вида vn ■ v ■ vm.

• Если слово v примитивно и W\VW2 — некоторое и-периодическое слово, то

является суффиксом, а w2 является префиксом некоторой степени слова v (прямо следует из предыдущего утверждения).

Кроме того, отдельно сформулируем известную лемму Файна-Уилфа ([19], а также [24, Proposition 1.3.5]) и одно ее простое следствие.

Лемма 0.1. Если u,v — примитивные слова и слово w длины + — Я0Д(|и|, |г>|) одновременно и- и и-периодично, то слова и и v сопряжены. ■

Следствие 0.2. Пусть для примитивных слов и и v некоторое слово w содержит и-периодическое подслово w\ и v-периодическое подслово Тогда если и W2 имеют пересечение длины >|и| + то слова и и v сопряжены, |tt| = |v| и объединение подслов w1 и vj2 является как и-, так и v-периодическим словом.

Доказательство. Применяя к пересечению слов w\ и лемму 0.1, получаем, что слова wit) сопряжены и, в частности, имеют общую длину |и| = |г>|, которую мы обозначим через I. Поскольку подслова w% и w2 являются ^-периодическими и имеют пересечение длины >£, их объединение, очевидно, также ^-периодично. Осталось лишь заметить, что любое /-периодическое слово, содержащее подслова миг; является как и-, так и и-периодическим. ■

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

Строковой переписывающей системой над алфавитом А называется подмножество 'Я. в /1" х А". Пары из Л называют переписывающими правилами. С переписывающей системой 71 связывают следующие отношения —> и —По определению, и-^гу означает, что найдется такая пара (г/', и') € % и такие слова что и — гихм'гог и V — гих^'^г- В этом случае говорят, что слово V получено из и применением переписывающего правила (и', и'). Через обозначают рефлексивно-транзитивное замыкание отношения —► . Говорят, что слово V приведено относительно 7Z (^-приведено), если нет такого слова ю, что Говорят также, что слово V является приведенной формой слова и относительно 7?. (Л-приведеппой формой), если и-^—^'о и слово V приведено относительно 71.

Нам понадобится модифицировать хорошо известные понятия нетеровой и конфлюэнтной переписывающей систем следующим образом. Скажем, что подмножество Т С А* замкнуто относительно переписывающей системы 71, если из те

и £ Т и и—>у следует и € Т. Назовем переписывающую систему 71 нетеровой на

подмножестве Т С Л*, если Г замкнуто относительно Я и не существует такой

те

бесконечной последовательности слов г>х,г>2,... из Т, что —для всех г > 1. В этом случае любое слово из Т, очевидно, обладает приведенной относительно 71 формой. Назовем переписывающую систему 7?- конфлюэнтной на подмножестве Т С А*, если Т замкнуто относительно 7?. и для любых слов г;, г>г, г^ £ Г из

те* те* , ^ т и* , и* ,

V—и г>—следует существование такого слова V £ 1 , что их—»и и г>2—■

Нетрудно проверить, что в этом случае любое слово имеет не более одной приведенной формы относительно 71.

Переписывающая система 7?. называется вычислимой на подмножестве Т С А*, если существует алгоритм, который для любого слова и £ Т либо находит какое-нибудь слово V, такое, что либо определяет, что таких слов V нет.

Переписывающая система называется полной на подмножестве Т С А*, если она нетерова на Т и конфлюэнтна на Т. Ясно, что относительно такой системы любое слово ь £ Т имеет однозначно определенную приведенную форму. Легко убедиться, что два слова из подмножества Т С А* имеют одну и ту же приведенную форму относительно полной на Т переписывающей системы 71 в том и только

том случае, когда эти слова лежат в одном классе симметричного замыкания от-

те *

ношения —т. е. в одном классе полугрупповой конгруэнции, порожденной на А* парами из 7?, (см., например, [3]).

Отсюда вытекает, что для нахождения алгоритма, который решает, лежат ли два слова из некоторого подмножества Г С А* в одном классе некоторой полугрупповой конгруэнции р на А*, достаточно найти вычислимую и полную над Т переписывающую систему 71, которая порождает конгруэнцию р. Действительно, если такая переписывающая система найдена, то, чтобы узнать, лежат ли два слова в одном классе конгруэнции р, достаточно применять, пока это будет возможно, к каждому из них какие-нибудь подходящие переписывающие правила из

а затем сравнить полученные ^-приведенные слова.

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

Теорема 0.3. ([21], теорема А) Для т > 3 и п > 1 проблема равенства слов в бернсайдовом многообразии уаг[жт = жт+?г] разрешима, я

Обозначим через В (А, га, п) полугруппу, свободную на множестве А в беры-сайдовом многообразии уаг[жт = хш+п]. Следующее утверждение явно выведено при доказательстве теоремы 4.2 в работе [20].

Теорема 0.4. Если т > 3 и п > 1, то каждый элемент в бернсайдовой полугруппе В(А, т, п) имеет лишь конечное число левых (правых) делителей, я

Кроме самой теоремы 0.3, нам понадобится доказывающий ее алгоритм из работы В.С.Губы [20]. Мы приведем лишь его вариант, адаптированный для частного случая, когда константы тип равны. А именно, фиксируем к>3 и приступим к описанию алгоритма, который позволяет по полугрупповому тождеству выяснить, выполнено ли оно в бернсайдовом многообразии уаг[жА' = х2к]. Для удобства, будем именовать описываемый алгоритм по фамилии автора первоначального варианта: "алгоритм В.С.Губы". Прежде, чем сформулировать алгоритм, определим, следуя [20], по индукции несколько понятий, зависящих от натурального параметра г> 1, называемого рангом. Особо отметим, что вводимые понятия:

период ранга г,

длинное г-периодическое слово, сократимое г-периодическое слово,

непосредственное продолжение слова влево [вправо] в ранге г, продолжение слова влево [вправо] в ранге г

определяются совместной индукцией по г.

1. Периодом, ранга г> 1 назовем слово и, обладающее следующими свойствами:

(а) и — примитивное слово;

(б) |и| = г;

(в) слово и3 не содержит сократимых ¿-периодических подслов при £<г.

2. Слово и> назовем длинным г-периодическим словом, если существуют период и ранга г и такие слова г/, г/', что

(а) у'уоу" есть и-периодическое слово;

(б) ь'гш [и)'о"} — продолжение слова ю влево [вправо] в ранге г — 1, если г > 1, и само слово го, если г = 1.

(в) \v'wv"\ > \ик\]

(г) \w\ > \ик-2\,

(В отличие от оригинала, пункт (г) изменен согласно [20, лемма 2.2].)

3. Слово w назовем сократимым г-периодическим словом, если существует такой период и ранга г, что

(а) w есть и - периоди ческ ое слово;

(б) w = w'w", где |u/| = \uk\, a w" есть длинное г-периодическое слово.

4. Слово v'v называется непосредственным продолжением слова v влево в ранге г, если для некоторых слов w,w' выполняются условия:

(а) v = ww';

(б) w — длинное г-периодическое слово-

(в) v'w — r-периодическое слово.

Аналогично определяется непосредственное продолжение слова v вправо в ранге г. (Отметим, что непосредственным продолжением влево [вправо] в ранге г обладают лишь те слова, которые имеют префикс [суффикс], являющийся длинным r-периодическим словом.)

5. Слово v'v называется продолжением слова v влево в ранге г, если существуют такие слова v^, ..., что

(а) vr+1 = v;

(б) v\ = v'v;

(в) для всех j от 1 до г либо Vj = Vj+1, либо Vj есть непосредственное продолжение влево слова Vj+j в ранге j.

Аналогично определяется продолжение слова v вправо в ранге г.

Замечание 0.5. Как легко видеть, любое слово является своим собственным

продолжением влево (вправо) в любом ранге.

Замечание 0.6. Из пунктов 3(6) и 2(г) определений следует, что сократимое г-периодическое слово имеет длину > (2к — 2)г.

Замечание О.Т. Считая, что слова v' и v" из определения длинного г-периоди-ческого слова пусты, в силу замечания 0.5 получаем, что если и — период ранга г и w — u-периодическое слово длины >kr, то слово w является длинным г-периодическим словом.

Отметим лишь одно из указанных в [20] свойств длинных и сократимых г-периодических слов, слегка его модифицировав.

Лемма 0.8. ([20, лемма 2.1]) Если и — период ранга г, v — « -периода ческое слово, v содержит некоторое подслово w, и w есть длинное [сократимое] г-периодическое слово, то слово v — также длинное [сократимое] г-периодическое слово, ш

Пусть v — произвольное слово. Индукцией по г>0 определим понятие г-приведенной формы слова v (относительно алгоритма В.С.Губы). При г — 0 это будет само слово v. Пусть r> 1. Рассмотрим (г — 1)-приведенную форму слова v. Выделим в ней все максимальные сократимые r-периодические подслова и рассмотрим их список (возможно, пустой). Отметим в каждом г-периодическом слове из этого списка его префикс максимальной длины, кратной rk, так, чтобы оставшаяся неотмеченной часть была длинным г-периодическим словом. Как показано в [20], отмеченные слова попарно не пересекаются и не граничат друг с другом. Результат удаления из (г — 1)-приведенной формы слова v подслов, отмеченных в ходе описанного выше процесса, называется г-приведенной формой слова v. Приведенной формой слова v называется его ^-приведенная форма. Из доказательства теоремы 4.1 работы [20] вытекает

Лемма 0.9. Полугрупповое тождество = v2 выполняется в бернсайдовом многообразии у&г[хк = х2к] тогда и только тогда, когда приведенные формы слов г>1

и v-2 совпадают.ш

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

Закончим раздел одним простым, но полезным следствием леммы 0.8. Лемма 0.10. Если и — период ранга г и ww" — такие слова, что

(а) слово w'w" u-периодично,

(б) слово w' непусто и имеет длину, кратную \ик\,

(в) слово w" не является сократимым г-периодическим,

(г) слово w" — длинное г-периодическое,

то слово w'w" является сократимым г-периодическим словом. Кроме того, согласно алгоритму В. С.Губы в слове w'w" отмечается именно префикс w'.

Доказательство. В силу условия (б) слово w' содержит префикс w длины \ик\. Отсюда в силу условия (а) слово го = (го w')w" является и-периодическим,

а значит, по лемме 0.8 слово w, так же как и слово w", является длинным г-периодическим словом. Следовательно, слово w'w" = w • w по определению является сократимым г- периоди ческим.

Для доказательства второго утверждения леммы достаточно показать, что после удаления из слова w" префикса длины \ик\ оно перестает быть длинным r-периодическим. Это очевидно, ибо в противном случае оно оказалось бы сократимым ?'-периодическим, что противоречит условию (г). ■

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

Для подмножества Т полугруппы S через (Г) обозначается подполугруппа в 5', порожденная подмножеством Т. Для элемента s конечной полугруппы S через 5w=î<;(s) обозначается единственный идемпотент из (s), а через Gs — максимальная подгруппа в (s) (которая совпадает с (.ss^)). Как обычно, ядром полугруппы называем ее наименьший идеал. Под операцией возведения в и-степень на конечной полугруппе S будем подразумевать отображение s н-> sw,sÇ.S. Унарной полугруппой называется полугруппа с дополнительной унарной операцией, рассматриваемая как универсальная алгебра типа (2,1). Под операцией возведения в to-степень на конечной полугруппе S будем подразумевать отображение s .ч s S. Пусть обозначает класс всех конечных полугрупп с дополнительной унарной операцией возведения в о;-степень, a S — многообразие унарных полугрупп, порожденное классом Б>ш.

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

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

6(С1Г6(С2Г6---(С.Г6,

где t > 1, каждое Q является унарным словом над А высоты h, и каждое является унарным словом над А высоты < h. Скажем, что унарное слово £ является унарным подсловом унарного слова если существуют такие унарные слова Съ (г> что ( = Ci£C2. Подсловом унарного слова назовем унарное подслово, являющееся словом. Понятия вхождения, префикса, суффикса, объединения и пересечения унарных подслое определяются аналогично соответствующим понятиям для слов. Для натурального к определим к-образ унарного слова ( как слово, получаемое из С посредством замены ( )ш > ( )к для всех вхождений ш в (. Длиной унарного слова ( назовем длину 1-образа i^1). Под uj-степенью с основанием £ будем подразумевать унарное слово а под из-подстепенью — унарное подслово, являющееся си-степенью. Переписывающей системой на множестве всех унарных слов над алфавитом А назовем строковую переписывающую систему над алфавитом, состоящим из всех букв алфавита А и всех (^-степеней над А.

Полугруппа всех унарных слов над некоторым фиксированным алфавитом А, снабженная дополнительной унарной операцией ( i—> (()ш "приписывания си-степени", свободна над А в многообразии всех унарных полугрупп. Поэтому под унарно-полугрупповым тождеством (или, короче, под у.п.-тождеством) будем подразумевать формальное равенство унарных слов. Высотой у.п.-тождества назовем максимальную из высот унарных слов, составляющих это у.п.-тождество. Множество у.п.-тождеств I высоты <h назовем базисом высоты h многообразия унарных полугрупп V, если произвольное у.п.-тождество высоты <h выполняется в V тогда и только тогда, когда оно является следствием из I.

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

Пусть V — псевдомногообразие конечных полугрупп и п — натуральное число. Семейство тт — {7Г5 | S'gV} называется n-арной псевдооперацией на V, если:

(i) 7г5 — всюду определенное отображение из Sn в S]

(ii) для любого гомоморфизма tp : S Т полугрупп из V и любых элементов 5i,..., sn(E.S выполняется равенство

TT(<P(si), ■ ■ ■ ,<p(sn)) = ^(^(si, • • • , 5«))-

На множестве f2nV всех n-арных псевдоопераций на V задают операцию умножения, сопоставляя каждым 7r,/?Gf2nV элемент ттр^П^У, определяемый следующим условием: для любой полугруппы 5GV и любых si,..., sn£S

(irp)s(-Si, ...,sn) = 7Cs(si,..., sn)ps(si,..., sn).

Данная операция ассоциативна. Полученную полугруппу QnV наделяют инициальной топологией относительно семейства всех гомоморфизмов в полугруппы из V (как в дискретные полугруппы), т.е. наименьшей топологией, при которой все указанные гомоморфизмы непрерывны. После введении такой топологии полугруппа П„¥ становится топологической полугруппой. Она называется псевдосвободной полугруппой ранга п псевдомногообразия V. Отметим, что псевдосвободная полугруппа группового многообразия является группой.

Для 1 < i < п обозначим через хг такую псевдооперацию из finV, что для каждой полугруппы S"GV отображение (xi)s-Sn —> S является проекцией на г-ю компоненту декартова произведения Sn. Подполугруппу, порожденную множеством А = {xi,..., хп}, обозначают finV.

Предложение 0.11. (Рейтерман [29, Lemma 3.6, Proposition 3.7]) Множество OnV всюду плотно в компактном топологическом пространстве i)nV.

Как следствие, указанное выше множество А порождает 0„¥ как топологическую полугруппу. Будем называть это множество каноническим порождающим множеством псевдосвободной полугруппы 0ИУ.

Псевдосвободные полугруппы обладают еще одним важным свойством.

Предложение 0.12. (Алмейда [7]) Топологическая полугруппа ОиУ есть V-свободная топологическая полугруппа над {х-х,..., хп}, т.е. для любой полугруппы ,Ь'СЕ¥ и элементов .51,..., з,,.(Е5' существует единственный непрерывный гомоморфизм (р: ППУ —> Б такой, что = Si, 1 < г < п.

В частности, полугруппа О^У свободна на множестве А в многообразии, порожденном псевдомногообразием V.

Следуя [15], укажем второй способ прийти к понятию псевдосвободной полугруппы. Пусть А — произвольное конечное множество. Назовем А-порожденной полугруппой такое отображение ¡л-.А-^в в конечную полугруппу 5", что подмножество /лА является порождающим.

Морфизмом .4-порожденных полугрупп /л-.А^-Я и р:А—*Т назовем такой гомоморфизм (рЙ1/: Б—^Т, что оц — V. Упорядочим Л-порожденные полугруппы, положив ¡х < и в том и только том случае, когда существует указанный морфизм. (Как обычно, при таких рассмотрениях мы отождествляем все изоморфные копии одной и той же полугруппы)

Напомним, что семейство полугрупп Si, г'б/, индексированное направленным множеством /, образует вместе с семейством гомоморфизмов

-+ г,

проективную систему, если для любых г,;, г<] < к выполнены равенства

= И С=

Проективным пределом этой проективной системы называют следующую подполугруппу прямого произведения Пае / '5'г :

1ш1(5<)<6/ = {(®«)«'€/ € Ц 5,- : Уг > з, = я,}.

¿6/

При этом проективный предел наделяется топологией, индуцированной тихоновской топологией произведения.

Как отмечено в [15], Л-порожденные полугруппы произвольного псевдомногообразия V конечных полугрупп образуют вместе с совокупностью своих мор-физмов проективную систему. Предел этой проективной системы называют А-порожденной псевдосвободной полугруппой псевдомногообразия V и обозначают Я4у. В [7] показано, что если множество А является тг-элементным, то топологические полугруппы О,аV и О^У изоморфны. Поэтому мы будем их отождествлять. В дальнейшем из контекста будет ясно, какое из определений используется в данный момент.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Жильцов, Илья Юрьевич

выводим a(xym-11ymY1a(xym-1,ym-1 x) = 1,

Hy^™)"1«^™,?/™) = 1, 138 pxym-l tym-lx — Pym:ym = где 1 обозначает единичный элемент группы С. Таким образом, ввиду (51) и (52), получаем е/е = {уГП1Ру™,угпРХут-1,ут-1хРу™,ут1Ут) = (ут тРу™ ,ут^Ут) — е1 а значит, на основании леммы 7.18, полугруппа С8ТО(С, а) не может быть псевдосвободной в С8(Н). ■

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

Отметим, что существует другой подход к описанию полугрупп П„1Ь(ут. Как показано в [28], псевдомногообразие 1ЬСт совпадает с полупрямым произведением псевдомногообразия © всех конечных групп и псевдомногообразия Ю>то, определяемого тождеством уххх2 ■ • • хт = Х\Х2 ■ ■ ■ хт. Поэтому для описания полугруппы можно применить результат Алмейды и Азеведо [11] (ср. [6, теорема 10.6.12]), касающийся полупрямых произведений произвольного псевдомногообразия и псевдомногообразия Рто. При этом используются вспомогательные полугруппы, обозначаемые /), а искомое описание дается в виде гомоморфного образа полугруппы в подходящую полугруппу вида ЛД.(5',/). Автору кажется, что полученное им описание более предпочтительно в силу следующих причин. Во-первых, оно дает модель рассматриваемой полугруппы, а значит, является более прозрачным. Во-вторых, оно сразу приводит к ответу на вопрос о максимальных подгруппах, тогда как описание Алмейды и Азеведо не предоставляет такой возможности. (Из него можно извлечь лишь тот факт, что упоминаемые подгруппы являются гомоморфными образами некоторой псевдосвободной группы ранга пт+л.) Кроме того, описание автора может быть легко обобщено и для ряда других псевдомногообразий архимедовых полугрупп, например, для псевдомногообразия всех архимедовых полугрупп данного индекса; в то же время неясно, как можно приспособить подход из [11] хотя бы для только что названного случая. И, наконец, именно "точность" полученного описания дала автору возможность описать булеву алгебру формальных языков, распознаваемых псевдомногообразием 1ЬОт (раздел 8.1). Заканчивая обсуждать подход Алмейды и Азеведо, отметим, что конструкция специальной архимедовой полугруппы в самых общих чертах напоминает конструкцию полугрупп М/;(5, /), но, тем не менее, они не могут быть сведены друг к другу.

Как замечено во введении, псевдосвободная полугруппа ГУЬС является проективным пределом полугрупп относительно проективной системы, включающей все так называемые канонические гомоморфизмы участвующих псевдосвободных полугрупп. Поэтому, опираясь на полученное описание для полугрупп нетрудно получить описание полугруппы ГУЬ© в виде конструкции, аналогичной специальным архимедовым полугруппам. Однако такое описание оказывается настолько вычурным и сложным с технической точки зрения, что его полезность для исследования псевдомногообразия ЕС кажется сомнительной. Автору представляется, что такое описание является более туманным и менее пригодным, чем представление полугруппы ПДХг в виде проективного предела относительно прозрачно описанных полугрупп П„1Ь

И, наконец, отметим, что первоначально результаты параграфа были получены в [35] для некоторых эпигрупповых многообразий. Эпигруппой называется полугруппа, в которой некоторая степень каждого элемента лежит в подходящей подгруппе. (Основная информация, касающаяся эпигрупп, содержится в работе [5].) Обычно эпигруппу рассматривают как полугруппу, наделенную некоторой естественным образом определяемой дополнительной унарной операцией псевдообращения. Как оказалось, задача описания псевдосвободных полугрупп псевдомногообразия тесно связана с задачей описания свободных алгебр некоторых эпигрупповых многообразий. Одним из проявлений этой связи является упомянутое во введении родство соответствующих результатов для псевдомногообразия СЗ и клиффордова многообразия (38 (клиффордовы многообразия являются частным случаем эпигрупповых многообразий). В исследованиях автора эта связь выражается в том, что соответствующие доказательства отличаются лишь некоторыми нюансами применения одних и тех же общих технических лемм, касающихся специальных архимедовых полугрупп (эпигрупп).

Список литературы диссертационного исследования кандидат физико-математических наук Жильцов, Илья Юрьевич, 1999 год

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

[1] Алмейда Ж., Вейль П. Свободные проконечные полугруппы над полупрямыми произведениями// Известия ВУЗов. Математика. — 1995. — №1. — с.3-31.

[2] Бурбаки Н. Общая топология. Основные структуры: Пер. с фр. — М.: Наука, 1968. — 272 с.

[3] Лаллеман Ж. Полугруппы и комбинаторные приложения: Пер. с англ. — М.: Мир, 1985. — 440 с.

[4] Расин В.В. Свободные вполне простые полугруппы// Исследования по современной алгебре (Мат. зап. Уральского ун-та. — Вып. 11. — №3.) — 1979. — с.140-151.

[5] Шеврин Л.Н. К теории эпигрупп. I, II// Математический сборник. — 1994.

— №8. — С.129-160; №9. — с.153-176.

[6] Almeida J. Finite Semigroups and Universal Algebra. — Singapore: World Scientific, 1994. — xvii+511 p.

[7] Almeida J. The algebra of implicit operations// Algebra Universalis. — 1989. — №26. — p.16-32.

[8] Almeida J. Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon// Journal of Pure and Applied Algebra. — 1990. — №69. — p.205-218.

[9] Almeida J. Power exponents of aperiodic pseudovarieties// preprint.

[10] Almeida J. On finite simple semigroups// Proc. Edinburgh Math. Soc. — 1991.

— №34. — p.205-215.

[11] Almeida J., Azevedo A. On regular implicit operations// Portugalias Mathematica

— 1993. — №50. — p.35-61.

[12] Almeida J., Azevedo A. The join of the pseudovarieties ofH-trivial and C-trivial monoids// J. Pure and Applied Algebra. — 1989. — №60. — p.129-137.

[13] Almeida J., Azevedo A. Implicit operations on certain classes of semigroups// Semigroups and their Applications, edited by S.Goberstein and P.Higgins, D.Reidel. — 1987. — p.1-11.

[14] Almeida J., Weil P. Free profinite R-trivial monoids// Technical Report LITP 93-55, Paris.

[15] Almeida J., Weil P., Relatively free profinite monoids: an introduction and examples/ / Semigroups, Formal Languages and Groups, edited by J.B.Fountain and V.A.R.Gould, Dordrecht:Kluwer Academic Publ., 1995. — p.73-117.

[16 [17 [18 [19 [20

[22 [23 [24 [25 [26

Banaschewski B. The Birkhoff Theorem for varieties of finite algebras// Algebra Universalis. — 1983. — №17. — p.360-368.

Clifford A. H. The free completely regular semigroup on a set// J. of Algebra — 1979. — №59. — p.434-451.

Eilenberg S. Automata, Languages and Machines, vol. B// New York: Academic Press, 1974. — xiii+387 p.

Fine N. J., Wilf M. S. Uniqueness theorem for periodic functions// Proc. Amer. Math. Soc. — 1965. — vol. 16. — p.109-114.

Guba V. S. The word problem for the relatively free semigroup satisfying Tm = Tm+n with m > 4 or m = 3, n = 1// Int. J. Algebra and Comput. — 1993. — vol. 3. — №2. — p.125-140.

Guba V. S. The word problem for the relatively free semigroup satisfying Tm = Tm+n with m > 3// Int. J. Algebra and Comput. — 1993. — vol. 3. — №3. — p.335-347.

Higgins P. M. An algebraic proof that pseudovariety are defined by pseudoidenti-tiesf / Algebra Universalis. — 1990. — №27. — p.597-599.

Jones P. Universal aspects of completely simple semigroups// Semigroups, N.Y.: Academic Press. — 1980. — p.27-46.

Lothaire M. Combinatorics on Words// Volume 17 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1983 — xix+238 p.

Margolis S., Sapir M., Weil P. Irreducibility of certain pseudovarieties// Communications and Algebra. — 1998. — vol. 3. — №26. — p.779-792.

McCammond J. The solution of the word problem for the relatively free semigroups satisfying Ta = Ta+b with a > 6// Int. J. Algebra and Comput. — 1991. — vol. 1. — №1. — p.1-32.

Petrich M. Introduction to Semigroups. — Columbus, Ohio: Charles E. Merrill, 1973. — vii+198 p.

Pin J. E. Variétés de langages et variétés de semigroupes, Ph. D. thesis — U. Paris 7, 1981.

Reiterman J. The Birkhoff Theorem for finite algebras// Algebra Universalis. — 1982. —№14. — p.1-10.

* * *

[30] Жильцов И.Ю. Унарные псевдооперации на псевдомногообразиях полугрупп/ / Известия ВУЗов. Математика. — 1995. — №1. — с.45-52.

[31] Жильцов И.Ю. Тождества на конечных полугруппах с унарной операцией сопоставления идемпотентной степени// Урал, ун-т, Екатеринбург, 1999, деп. в ВИНИТИ М41-В99 от 20.01.99 — 114 с.

[32] Zhil'tsov I. Yu. On continuous embeddings of free profinite semigroups/ / Int. Conf. "Semigroups and their applications, including semigroup rings", Abstracts, St Peterburg. — 1995. — p.86.

[33] Zhil'tsov I. Yu. On equality of to-terms on finite semigroups/ / Int. Conf. on Algebra, Abstracts, St Peterburg. — 1997. — p.149-150.

[34] Zhil'tsov I. Yu. The languages recognizable by locally groups// Int. Conf. on Algebra, Abstracts, St Peterburg. — 1997. — p.148-149.

[35] Zhil'tsov I. Yu. The free Archimedean epigroups of finite degree// Semigroup Forum. — 1998. — vol. 57. — №3. — p.378-396.

[36] Zhil'tsov I. Yu. On to-identities of finite semigroups/ / Algebreiic Engineering, edited by C.L. Nehaniv and M. Ito, (Proc. Kyoto Workshop on Computer Systems and Formal Languages and First Int. Conf. on Semigroups and Algebraic Engineering.) Singapore: World Scientific Press. — 1999. —

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

Ьа1>расширение, 124 ¿-образ, 19 2-слово, 34

и-периодическое, 35

запрещенное унарное подслово, 53 зацепление поде лов, 25

пара со-подстепеней /-согласованная, 76 дружественная, 50, 88 квазидружественная, 67 квазиродственная, 67 родственная, 50, 88 согласованная, 76 период ранга г, 16 подслово, 13 Z-cлoвa, 35

большое ¿/-периодическое, 102 продолжение слова в ранге г, 17 непосредственное, 17

разрушение, 76 ранг, 16

семья, 89 слово, 13 Вр, 93 Г(С), 88 Г(С), 76

/,92

/р; 92

аг, 89 Ъг, 89 Ср, 89 ¿р, 89 4,93 с-р ч 93 щ, 88

/-периодическое, 13

гг-периодическое, 13 длинное г-периодическое, 16 примитивное, 13 сократимое г-периодическое, 17

тройка оьподстепеней /-согласованная, 76 согласованная, 76

унарная полугруппа, 19 унарное слово, 19 С, 54 с, 54

вполне примитивное, 45 нормальное (высоты <1), 29 нормальное (высоты <2), 53 примитивное, 34 унарные слова

конгруэнтные, 34

факторизация Z-cлoвa, 35 форма слова

г-приведенная, 18 ^-приведенная, 15 приведенная (относительно алгоритма В. С. Губы), 18 приведенная относительно переписывающей системы, 15 форма унарного слова г-разрушенная, 77 (высоты <1) нормальная, 29 (высоты <2) нормальная, 53 разрушенная, 77

число З'р! 92 3Р, 92 гр, 89 Зр, 89

ядро, 19