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

i ) CL-g*- 2 ) a S a - £ л х =Л2# г.. 4 ) aSo--Sa. ь )£ а ~ - £ к * - / , <?,... ,6) ql $ c i = q A 7) a$CL=fa_ 8) a*£a_=a£ 9) aA= -/a. § 2. Доказательство основной теоремы Предварительно докажем несколько лемм. ЛЕММА. I . Для классов полугрупп А г и К& справедли­ во отношение AY с /б • 2 г 2 ДОКАЗАТЕЛЬСТВО. Пусть существует хотя бы одна полугруп­ па /7е A х такая, что П е Кг . Тогда в полугруппе П найдется хотя бы одно определяющее слово С- такое, что его. можно разбить на два нормалышх сло­ ва X и Y . Тогда могут представиться следующие случаи. случай I . t c X > = £ c Y ) ■ В этом случае =g и /7 е XY . Получили противоречие, следовательно, случай I быть не может. СЛУЧАЙ 2, £ ( Х ) > £( Y), ■ Тогда у З > | д AY . Опять получили прот^ворецце, следовательно, случай 2 также не может быть. Анал гичцо' показывается, ' что и последний случай Ub<l < Y) невозможен. Отсюда сдедуе , что если полугруппа /7<sX | , то Н е Кг ■ Остается до к а зать , что, существует строгое включение,т.е. что красен Ах и Ка ' не совпадают. Для этого достаточно указада хотя одну подуурутщу П такую, что П&К2 и Такой пример дает класс полугрупп, 77^= < сс > } где. t% - ыдтураг;шое числэ и, П ^ 1 . Д е п о видеть, что Кг . iia полугрупп /7„ только Пг е . Ддя / г >А НИ одна П ^ е А, это и завершает доказательство леммы I . Теперь предположим, что существует хо.тя бы, одна немоно- генная полугруппа / £ е К г , которая не содержит ни одной подполугруппы, свободно порожденной двумя элементами. Изучим, какое задание имеет полугруппа П0 при этом предположении. - 125 -