АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1981 г.

Для этого докажем следующую лемму. ЛЕША 2. Полугруппа 110 имеет не более трех образующих. ДОКАЗАТЕЛЬСТВО. Покажем, что предположение о наличии четырех или более образующих приводит к противоречию. Итак, пусть полугруппа П0 имеет следующее задание: П0 = < Л , С , d } , i e J , гд е D - некоторое множество символов. Из этого рассмотрим подполугруппы /7 = < d " 1 / 7 = < и ' п С п у п3=<*■”)*•*■>, п = < * ~ У п >г = < с d у полугруппы П0 , где гп - длина большого определяющего слова в полугруппе /7С , а П ~ <XfY> означает полугруппу, поровдшшую элементами X и Y . В подполугруппе П1 каждое слово из этой подполугруппы равняется конечному произведению порождающих элементов и о,иного из четырех видов: П а * ' т £ ^ /П- С V L ( ? ( а ^ < ^ ) л г т / 7 ( J * ' n a .A‘ /~ ) S s m (1) Из предположения, что полугруппа П0 не содержит ни одной свободной подполугруппы ранга 2 , следует, что в под­ полугруппе имеется равные слова вида ( I ) (но не тождест­ венно равные), каждое ив которых содержит хотя бы одно опре­ деляющее слово. Из определения класса Кя ясно, что не может быть определяющих слов вида или , так как каждое из этих слов можно разбить на два нормальных. Например, а Л-О?1=(£■ а . • Отсюда следует, что в п о л у ­ группе П0 , й также в любой из подполугрупп / 7 ^ - / 7 не может быть определяющих слов, у которых L ( It/; = 7 . Из то го , что каждое слово в полугруппе Пя будет одним из слов вида ( I ) , ясно, что определяющие слова, для кот рых L ( W ) = 2 могут Сыть подсловами только следующих видов: I ) б л шш £' ' а " 1 ( в полугруппе П1 ) , а определя­ ющих слов большей слоговой длина быть не может. Применяя подобные рассуждения к определяющим словам - 126 -