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

затор каждой конечно порожденной подгруппы конечно порожден, то по теореме I этим свойством обладает и группа & . Переходя в £> , мы должны добавить элементы из Теорема доказана. ТЕОРЕМА 3 . Ne>i^ 6 i ’, e l 4 > )= ^ 1 , 5 ^ - ? ДОКАЗАТЕЛЬСТВО. Пусть г £ N ь а ( г б ^ , 6ХЧ>) и пусть А - < .д > - < 6 1 ч ,<5гч> . С помощью преобразований вида: 1) вычеркивание X из слова Н = н^Х = • гДе 2 ) вычеркивание Д * и ь Ъ - 2 .дДк (. Ъ - A , 3 ) сокращение двух соседних взаимно-обратных букв и им .обрат­ ных выберем Ъ самым коротким положительным словом в А 2 А . Для доказательства теоремы достаточно рассмотреть ра­ венства : ( I ) б хч г - * У , V ' e < 6 14 , 6 lM> . ( 2 ) I . Пусть хотя бы одно из слов V . У *1 содержит отрица- тельные степени. Например, слово V . Заметим, что 6 д 'ч= « х бдг б ’ бд € г д '4 6 { * - 6 д б хг б / б ^ б д А 4 . (3 ) Используя ( 3 ) , выделим в слове V А в отрицательной степени. На стыках 6 Хб лг 6 х бд 1 6 х и б^ выделим А в поло­ жительной степени и Полученные степени соберем. Имеем V ^У/дл'-'угде с/. ? ч Уд е G-+ и не содержит Л . Так как слева равенства Ш ст о и т положительное слово, то сло­ во , стоящее справа данного равенства может быть преобразовано в положительное. Этого мы добьемся, если на стыке 2 и V ' ' будут выделяться А -с л о в а . Возможны следующие случаи, а) Пусть У имело вид 6 A' 4 б ^ 4 <l 1 6 ^ J> X • Тогда б * г = t б Г 4 б i4Ji х = н « , 6д1 б х* б х'бд * . где > >i . _ V 2 > еСЛИ ( t * i ) « l i X O ) (б >=1 , Ыд>0) ^ 3 , если х = д , ыд Будем выделять Д -сл о ва следующим образом: б/ 2. = 6 , 6 ^ 6 * б дЧ г Ъл~А= бЛ л ^ г^ А б д б *«Л о*? = 2.г б г б ^ б г Ъ д ' ,А+4 б .б ^ б , . у д ц+1= Далее выделение А -сл о ва может произойти, если положить г .^ - 3 у б гбд (при -t = 3 ) или г ъ = г ч б ! . В обоих случаях имеем -g _ 2 * б д Ч и ДЛИНУ 2 можно укоротить с помощью