Алгоритмические проблемы теории групп и полугрупп. 1994 г.

В С } гд е _ В ^ / , то А — В . СЛЕДСТВИЕ 1 . Если А В - определяющее слово и хотя'бы одно из слов А или В является непустым двусторонним, то В А - тоже определяющее слово. Формулировка лемм 2 -4 похожа на [ 1 , глава 3 , лемма 1 С], хотя рассматриваемые нами слова не обязаны быть элементарными в смысле [ 1 ] . ЛРД'А с . с/ сть А В, А, В , В ^ - определяющие слова специального моноида Ч ерча-Россер а, - некоторый конец слова В , - непустое начало слова , слова А , . . . А^ и ь ч . . . В 4 чеппиводимы и выполнено равенство в * * * а < . . . а ^ а (: . Тогда л = / . ДОКАЗАТЕЛЬСТВО. 3 :метим ср азу , что все слова Ас , Вс непусты, иначе гп 1 X 0 ,дим к противоречию с неприво.цимостью ... А ^ , Вл ... В 4 ь Г А,,- ■' ------- ’ ■ Спустил', что ^ > 4 . Пусть А = В * > й (К> ТОГ7ТЯ И Я = А 0 м А л (н) ° ° ° . тогда д а = А В Ау... А«, - определяющее слово. А (Н / ПОСКОЛЬКУ А л ЯВЛЯеТСЯ непустым двусторонним словом, то мож- __ ^ » . /VI н а « * А М ( 2 ) но применить лемму 1 . Учитывая равенство подучаем, что _ К = А В А < . . . А ъ ч Рассмотрим д ва возможных случая. 1 . 1в^1 > 1 А л-4 I . Тогда из (2) сл еду ет, что Вл — £>А ^-4 для некоторого слова 0 . В этом случае слово Вл = = ^ А \-4 8^,-4 &1 приводимо, чего не может быть по условию. 2 . IВ ^1 < 1 а л-4 I . Следовательно, А ^ 1 = А в . . . . и поэтому 1 А 4 ■■ А^-1Ал — А 4 •■ -А А^' а В(Н>А, ■■. А ( з ) Из (2) сл еду ет, что А^’ а в ' >А1 ... - определяющее слово. Таким образом, Ау-< яв.ляется непустым двусторонним словом. /з леммы 1 еле.дует В \-4 - А ^ А В 1 А, . . . Ал. г_ , поэтому в (3 ) выделилось определяющее слово /К -*$•»-/. что противоречит условию леммы. Лемма 2 доказала. ЛИМА 2'. Пусть АВ, А, В,, . . А* 8Ч - рпроделвдие слова, специального моноида Черча—Россера, А ^ - некоторое наняло слова А , _ непустой конец слова й ч , слога А , . . . А - у К В\ . ■• В 4 НСПриВОДИМЫ И В?,’Полнено ] : ' (—гг;Птг 106