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

Л еш а 1 6 доказана. Из н е е , в частности , следует, что в конечно определенном специальном моноиде Черча-Россера существует такое конечное множество Р элементов, что любой элемент конечного порядка сопряжен с некоторым элементом из Р . ЛШМА 1 ? . Если при некотором ^ > о справедливо равенство (46 ; а с 1 = р 1а то Ц С 1 - Р с @ при ^ ^ О . ДОКАЗАТЕЛЬСТВО. Можно считать, что <2 , С , Г непусты. Применим к (4 6 ) лемму 8 : с ‘ 3 Г Д , Г Ч Т при некоторых Р г . Тогда (С. С ) ( = £ Т Е 1 С 1 - циклическая перестановка слова с . Из последних равенств получается, чтр Г г СХС, . Для некоторого простого слова и С * * * « ’ «*• Равенство (4 6 ] примет вид « ( и , и х ) М * ( * , * , / * ■ РассуждаЯ* КаК В доказательстве леммы 1 2 , приходим к заключению о том, что и О г и * т . е . # * #г йгТ'Отсюда и следует утверждение леммы. ЛЕМА 1 8 . Пусть X , У - элементы бесконечного порядка специального моноида Черча-Россера. Если X У при , то существует элемент В 'и числа Р >^>0 такие, что > У = 2 * . ДОКАЗАТЕЛЬСТВО. По лемме 16_запишем для неприводимых форм элементов X и К : Х * В С * А , У г Е Р * £ > , г д е р) £ > о ) слова С и Г - простые, слова В С А и £ Г неприводимы при любом ш > о . Тогда ЬС*РА -а Е Г * * 0 • №) Докажем, что АСА = £ Т ® • Возможны следующие случаи :' 1 . /#/»/£/ , ¡АI > /¡01 и хотя бы одно из неравенств строгое. 2 . 181>1Е1, 1А1£1®1 . Остальные возможности симметричны этим двум. В первом случае из равенства А в * / мы легко получаем противоречие с непри­ водимостью слов Г * * . Остается второй случай , в котором из (47] получаем: В = И з равенств / * ~ . / = э й ' легко следует ® /- $ / • А поскольку , В - неприводимые слова , то 2 > 'г « ' Поэтому 6 = Е а , Ю * в А , где введено обозначение 0 е ® '. После сокращения (4 7 ] слева на £ и справа н а /4 имеем ? (48] По лемме 8 слова £ * и Р** являются цшшгческши псрестшюв- у- е/. — /и г ) £ 2 6 У • ками друг друга, поэтому г — г • л 128