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

CtJ =A , @ tj 5 K y,, , и из симметризованности Mn сл едует, что Л у V/y #v - ^ - определяющее соотношение или д , Д у /В,у s F . Таким образом, F становится новым Y ,j , К,%( - новым , YCj„ - новым £у/+, . Легко видеть, что все утверждения леммы выполняются. 2 .4 . £ пересекается с Y tj, Yij+< , Y i j -ц . Если хотя бы один из кусков t -ijr , , &IJ-H п у ст, то Yl / t t - кусок и определяющее слово t’<yt< явл яется произведением не более, чем двух ку ск ов. Значит, бу у, у д , £ ,y T i? A и, по ин­ дуктивному предположению, Д у Поэтому £ не мо­ жет захватывать целиком ни Ку , ни Ку >2 , иначе определяющие слова бу К/у ^ )y->i ^ ijn разлагались бы в произведение не более, чем двух ку ск ов. Значит, Е = -Ку*., • Теперь с помощью условия надо д о к а за ть, что Элементарное преобразование , в результате которого образовалось олово Yij+i , входящее в £ , имеет вид - « , б , у +, К у у ,Я у > , ^ 2 для некоторых слов ^ s . Допустим, что это элементарное преобразование имеет номер м . Рассмотрим последовательность елементарных преобразований от (т *х\ -г о преобразования до К -г о . Эта последовательность не затраги вает VY/+/ , имеет длину не более К и п е р е в о д е К г в Y 1 Yq YLj ¥i Иу+, Уi для некоторых Yf , К , По ин­ дуктивному предположению, примененному к словам и Viy« Yt , получаем ' П л г ^ 5 * о ' т / 1 : . . - . г / л ; , V и выполняются остальные утверждения лешш 1 . Поскольку не затрагивается элементарными преобразованиями, то оно должно быть пустым. Тогда выполняется или а ) 2 для некото­ рого ? , или б ) Хи 35 ^/// ^ • Пс индуктивному предположе­ ние, Хи B ff - определяющее слово, R'f - ку сок. Если бы был справедлив случай а ) , то Хи было бы куском, что невозможно. Следовательно, -? . Аналогично доказы вается, что ^ ^ = Y0 n W для некоторого W . По предположению индукции, либо Х н В " ~ К * - определяющее соотношение, либо X,' &'( г Y ,' 25,/ . Таким образом, возможны два случая: 71