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

следствию 1 слово сес. e>t определяющее. Пусть 5 - простое слово, тогда СеС,* лучаем I,. вх = !> , Но тогда .? *+а - определяющее слово , что ггтю- ткворечит неприводимости в с е х степеней слова С . Аналогично С 2 s p, где Применяя лемму 1 2 , по­ прищем к противоречию, если предположить, что С * А приводимо. Пусть теперь влС^А^ - опреде.дяющее слово, вл Ф / , А<Ф у , Как и Раньше, можно док а за ть, что слова вг , Ai - двусторошие. Поэтому Л, ^ б7Л и С % е л - определяющие слова, что опять при­ водит к. противоречию. Л еж а 15 доказана. • ЛЕММА 1 6 . Пусть X - произвольный нетривиальный элемент специального моноида Черча-Россера. А) X - элемент конечного порядка тогда и только тогда, когда его неприводимая форма имеет вид X = В (И х , где t > 0 , А В - i j и если существует определяющее слово (Ui s при S » -б . Ъ) х - элемент бесконечного порядка тогда и только тог­ д а , когда его неприводимая форма имеет вид X = В С' А , где А В -Ф , i i / , слово в С*А неприводимо при любом tn > О . ДОКАЗАТЕЛЬСТВО. В одну сторону доказательство обоих у т­ верждений очевидно. Пусть теперь А нетривиальный элемент, X - его неприводимая форма. Слово X можно представить в виде В СА , где /1в = / . Выберем из в се х таких представлений т о , в котором fCI минимальна. Будем счи тать, что С / иначе лемма очевидна. А) Предположим, что существуют целые числа ( > к ^ . о ) для которых X —X . Тогда В С А содержит вхождение определяю­ щего сл о в а . По лемме 15 существует т > 1 .) при котором б1*1 со­ держит некоторое определяющее слово В . Если /£ |< /с I , то содержится в С 1 и С г где £ = Но тогда X = В £гС Я, А , /^А ВЯ г = и мы пришли к противоречию с минимальностью /б/ . Поэтому 1Я I > / с / . Тогда Я ^ ( ® Е ) РТ>, . где Г£>Е - некоторая циклическая перестановка слова С , р > о, Из р авен ства К^(СО е ) г Ъ е 2 > 2 2 > Е ( Ф £ ) Г 2> и т о го , что слово ( 2 >Е)Г 7) непусто, по лрмме 1 получаем £ £ ) з Следовательно, Е 2 ¿с откуда и вытекает первое у т в е р ­ ждение леммы. П ) Пусть X - элемент бесконечного порядка, но В С "'А содержит определяющее слово при некотором / п > о , Рассуждая, как в А ), придем к противоречию с бесконечностью порядка X 127