Проблема конечного базиса для полугрупп преобразований

• Автор: Гольдберг, Игорь Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Екатеринбург
• Количество страниц: 66 с.

0.1 Постановка проблемы конечного базиса

0.2 Полугруппы преобразований

0.3 Дополнительные замечания о проблеме конечного базиса

0.4 Проблема конечного базиса для различных серий полугрупп

преобразований

0.5 Содержание диссертации

0.6 Апробация результатов

0.7 Список обозначений

1 Тождества полугрупп треугольных матриц над конечными полями

1.1 Некоторые свойства полугруппы Тп {К)

1.2 Вспомогательные результаты о существенно бесконечно базируемых полугруппах

1.3 Доказательство теоремы 1
1.4 Обсуждение результатов главы
2 Тождества полугрупп треугольных булевых матриц
2.1 Вспомогательные результаты о полугруппах ТВп и ЫТВп
2.2 Доказательство теоремы 2
2.3 Доказательство теоремы 2
2.4 Обсуждение результатов главы
3 Тождества полугрупп базисного каркаса и полугрупп £"
3.1 Определения и вспомогательные результаты
3.2 Описания тождеств
3.3 Доказательство теоремы 3
3.4 Обсуждение результатов главы
Список литературы

0.1 Постановка проблемы конечного базиса
Пусть Е — счетный алфавит, через Е+ и Е* мы обозначим соответственно свободную полугруппу и свободный моноид над Е. Тождеством над алфавитом Е называется пара слов и, V 6 Е+, которая обозначается посредством формального равенства и = V. Полугруппа 5 удовлетворяет тождеству и = V, если для любого гомоморфизма <р : Е+ —>■ 5' выполняется шр = щ. Если I — некоторое множество тождеств, то говорят, что тождество и — V следует из I, если любая полугруппа 5, удовлетворяющая всем тождествам из I, удовлетворяет также тождеству и = V. Полугруппа 5 называется конечно базируемой, если все тождества этой полугруппы следуют из некоторого конечного набора ее тождеств (базиса тождеств полугруппы 5); в противном случае 5 называется бесконечно базируемой. Пусть М — некоторый класс конечных полугрупп. Проблема конечного базиса для класса М состоит в том, чтобы определить, какие полугруппы из М являются конечно базируемыми и какие — бесконечно базируемыми.
Решение проблемы конечного базиса известно для класса всех конечных групп. А именно, в [26] доказано, что любая конечная группа является конечно базируемой. Для конечных полугрупп это условие может не выполняться. Первый пример бесконечно базируемой полугруппы был приведен в [28]. Им стал 6-элементный моноид Брандта В , который может быть представлен в виде полугруппы 2 х 2-матриц
/О 0 (I (А (I 0 /0 1 {0 0 [0 0
1о 0)’ 1)’ Д о)’ 0у’ Д 0)’ ^0 )
относительно обычного матричного умножения. Естественно возникает задача классификации конечных полугрупп с точки зрения конечной базируемо-сти их тождеств. За последние 40 лет в этом направлении проделана большая работа, результаты которой по состоянию на 1985 г. и 2000 г. систематизированы в обзорных статьях [9, глава II] и [39] соответственно. Представляется, однако, что эти исследования еще далеки от полного завершения. В частности, для ряда конкретных конечных полугрупп, важных для теории и приложений, все еще неизвестно, конечен ли их базис тождеств.
“Идеальным” решением проблемы конечного базиса для класса всех конечных полугрупп может стать появление метода, который бы позволил различить конечно базируемые и бесконечно базируемые полугруппы. Поясним эту мысль более подробно. Поскольку любая конечная полугруппа может быть описана конструктивно (например, таблицей умножения), то имеет смысл ставить вопрос о существовании алгоритма, который по некоторому

эффективному описанию полугруппы 5 определял бы, является она конечно базируемой или нет. Такая формулировка проблемы конечного базиса была предложена А. Тарским в начале 60-х годов в более общем случае, а именно, для класса всех конечных алгебр [37]. Вопрос о существовании такого алгоритма для конечных полугрупп открыт до сих пор. Отметим, что для класса всех конечных группоидов проблема Тарского была решена Р. Мак-Кензи в работе [24], где было показано, что такого алгоритма не существует.
Известен алгоритм, определяющий, является ли конечная инверсная полугруппа 5 конечно базируемой. Алгоритм основан на том, что для конечной базируемости полугруппы 5 необходимо и достаточно, чтобы моноид Брандта В не принадлежал многообразию уаг5. Необходимость этого условия была доказана М. В. Волковым в [1], а достаточность является следствием результатов М. В. Сапира [6].
0.2 Полугруппы преобразований
Полугруппы преобразований являются классическим объектом общей теории полугрупп и изучение их абстрактных свойств занимает важное место в современной алгебре. Этой тематике посвящено огромное число публикаций, в том числе и обобщающего характера. Текущее состояние теории полугрупп преобразований отражено в недавнем обзоре Р. Салливана [36].
В литературе, как правило, рассматриваются серии полугрупп преобразований, индексируемые одним или несколькими естественными параметрами. Например, при исследовании полугрупп преобразований некоторого конечного множества таким параметром может служить количество элементов этого множества; при исследовании линейных преобразований линейного пространства над конечным полем параметрами могут выступать размерность пространства и само конечное поле, и т.п.
Приведем несколько примеров важных серий полугрупп преобразований. Пусть п — натуральное число. Будем пользоваться следующими обозначениями:
• % ~ полугруппа всех преобразований п-элементиого множества,
• МТп — полугруппа всех многозначных преобразований п-элементного множества,
• ТТп ~~ полугруппа всех частичных преобразований п-элементного множества,
• Вп — полугруппа всех частичных многозначных преобразований п-элементного множества,

г0.(аір) = (іо + 1 )-(аір). Тогда, пользуясь определением преобразования аїр, мы можем заключить, что їа-(аір) = («о + 1)-(а<р) — *о + 1- Из этого следует, что а = сц0 и а Є с('ш,0), что противоречит тому, что слово н является уникально разбросанным подсловом слова ги. Следовательно, преобразование аїр является инъективным и поэтому содержится в полугруппе 5,
По построению І.(илр) = т + 1, следовательно Ц-ш'ір) = т + 1. Легко проверить, что данное условие может быть выполнено только в том случае, если V является разбросанным подсловом ги1 и для первого вхождения ввів' справедливы включения с(Ч) С с(гд), где г = 0,1,... ,то. Из этих условий следует и тот факт, что слово V является уникально разбросанным подсловом слова ги1. Обратные включения получаются из симметричных рассуждений.
Теперь предположим, что тождество го = уо' содержится в множестве С„. Покажем, что для любого гомоморфизма ір : Е* —» 5 и любого натурального числа к0 = 1 п+1 выполняется ка.(икр) — ко.(и>'ір). Построим разбросанное подслово V = а ■ ■ ■ ат слова и), удовлетворяющее следующим свойствам:
ги = гиааі'Шд, причем к.(и>аір) = к, к.^иіоафір) =кфк ги'0 = іщадЧ, причем кгфщф) = к, Аі.((іща2)<р) = Ад ф к[
ш'т_2 = шт_іат-шт, причем Ат_1.(тот_1^) ^ &т_ь кт~І ~ А'т 7^ кт„і,
к.(икр) - кт.
Очевидно, что длина построенного слова и не превосходит п, а представление
ги = іиоаііи^ ■ ■ ■ и)т-іати)т
есть первое вхождение слова V в ш. Покажем, что V является уникально разбросанным подсловом слова и). Действительно, если предположить, что для некоторого і = 1,т справедливо условие а, Є с(гд), то по построению и>і имеем кіфи>іір) = кі. Поскольку а* є с(гд), то и Д-(аг<д) = Д. Но, в соответствии с выбором а,, выполняется условие кі-.(аіір) = Д, что противоречит инъективности а,(р. Следовательно, слово г» является уникально разбросанным подсловом слова гл.
Тогда слово и является также уникально разбросанным подсловом слова и)1. При этом первое вхождение слова и в ги'
ги' = и)'0али){а2 ■ ■ ■
удовлетворяет условиям с(ги0) — с(иф), с(ид) = с(гиі),... ,с(гит) — с('ш'т). Очевидно, что
к0.(ю0ір) = к0.(уі'0ір) = к0, к0.((ш0аіЮі)ір) = А0-((Чаіш'і)Ч = ки
/с0.((шоа1'ш2 ■ ■•'Шт-іатщт)4 = А0.((Ч«іЧ • ■ ■ 'т~іат'ШІт)ір) = кт.