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

д~ С*О)... У( о ... X Q ) .. х(к)с~'= и(1)...U(i<) ■ где y f i J - x / j U x , u ( i , ) = u ( / t) = u , и = и л х и ^ U (t)-U „ (V J t(O u n (tJ, нужно ВЗЯТЬ СЛОВО у '=cx(rt...xtiMg+tl. kW c '- u M ..u t< Ju frA . u ft- t) u A( v x f o c ' которое будет удовлетворять условиям: (д’) П^Н, L (g ')<L (д). Остается убедиться в том, что < Действительно, присоединение к подгруппе И слова р или равносильно присоединению cu n ( t ) . Леша доказана. ЛЕ.Ш 10. Пусть Ж - произвольнее подмножество множест­ в а простых слов Р , И - конечно порожденная подгруппа сво­ бодной группы F , р е Р , . Тогда, если /г >К (Н ) , то д . ДОКАЗАТЕЛЬСТВО. Действительно, если душ $<=F сущест­ вует простое число / г (Ж такое, что f i * K ( W , то на основании лешы 8 существует Ж /? такое, что д п е н Так как (Зг./U -A , то д*Н . ТЕОРЕМ 2. Пусть Ж - подмножество множества простых чисел Р . Для того чтобы существовал алгоритм, позволяющий для любой конечно порожденной подгруппы Н свободной группы F построить её Ж. - изолятор, необходимо и достаточно, чтобы множество Ж било рекурсивным. ДОКАЗАТЕЛЬСТВО. Пусть Ж - рекурсивное множество и На - конечно порожденная подгруппа свободной группы F . Поста­ вим е соответствие Н0 её характеристику Х(Н0) и число К(н/0) Строим в свободной группе F слова, длина которых не превос­ ходит и выбираем среда них те, которые не принадлежат Н0 . Обозначим полученное множество слов через 1 > ф О Д .{ Е . Среди простых чисел fi< k (W B) выбираем те, которые не принад­ лежат Л , что можно сделать эффективно, поскольку проблема вхождения в рекурсивное тож ество разрешит [б] . Образуем из этих чисел множество Л 0 Присоединим к подгруппе Н0 все слова $с(0)*То , для которых существует № ° > * П о , такое, что (О))fy(o)*Н0 Получим подгруппу Hf , которая порождается нпльсековскйп множеством W, . Строим для Hf характеристику ^ ( w f ) и вы- числяем К(И,) , повторяем описание”' процесс для подгруппы К(Н,). Через конечное число тагов на основании леммы 4 п 5 мы ;юс.'роим подгруппу Н ц , которая является % изолятором I?