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

ДОКАЗАТЕЛЬСТВО. Равенство (6/ будем доказы­ вать индукцией по I , а ( 7 ,8 ) - индукцией но / . При .А '*/ (б ) выполняется; докажем, что выполняется ( 7 ) или ( 8 ) . Пусть J * Ц . Из (б ) следует, что либо Хс, я Ус, Ц , либо К ,ъ К , Ц Лемма в обоих случаях справедлива. Пусть л еш а выполняется для , / » > / . Предположим, что имеет место (У ), т .е . Х с ,- - Х(- - У с , . . . К * . , (другой случай рассматривается анало­ гично) и что для /=• яг л еш а не выполняется. Тогда 3 К > / (91 w _ Ь' * И- я I/ * = И /' У гд е Г ,я . / - и * . , > К * . , - г< *-, /'Ч«* • Рассмотрим по отдельности каждый кл асс полугрупп. 1 . П явл яется полугруппой с условиями К f a ) или К ( ь ) Я Т ( к ) . Слово Ус*., не может быть пустым, так как иначе получаем противоречие d предположением индукции. Если А с ы пусто, то имеготся_определяющие олова УС * В с * и С ; * . , У с *., У С* К С , ■ В этом случае Х с * - кусок и су­ ществует определяющее слово, равное произведению двух Кусков, чего не может быть. Значит, А , * непусто. Тогда по лемме 1 В с * . , = Л , а из этого по Той же л еш е вытекает* Что •“ У с * - , ~ Y u . . . Усы-1 ® im ~ * ■ Ид (9 ) получаем Ус, ... К * . , * Х с, . . . У с * К С , Ъ ы ; ■ Слово Н s Хс* У с * . , ® с * . , непусто, т .к . непусто Х с, из последних соотношений следует Теперь У с, •- • Х с * X i, - . - X ; ы -, Н , что невозможно по следствию 1 , Таким образом, предположив, что лемма не выполняется, мы пришли к противоречию. 2 , П явл яется полугруппой с условием К ( л ) X Т ( в ) . Если YiС , £ Л . т о лемма справедлива при пустом К * Пусть К ” < непусто. Тогда, если А С* непусто, то придем к противоречию со следствием 1 , как и в пункте 1 . Пусть Тогда Х с* вс,„ - определяющее слово и поэтому ни Х с*, , ни &СШ не может быть пустым. Значит, А сПы, = А и Х , * „ А Л Ясно, что У с*-, и Х с * ,, имеют некоторое непустое общее на­ чало S и слово Хс* S явл яется подсловом определяющего сло­ ва У с * * У с * ., ® с*.,. Из до к азател ьства леммы 1 (случаи 3 , 5 ) 76 л