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

3. ТЕОРЕМА 3. Пусть - специальное множество слов группы G-* и пусть ( { щ } с ^ ) = д р CM0i S ) . Существу­ ет алгоритм, позволяющий для любого слова w e G * установить, принадлежит оно подгруппе gp(Jll0, S ) или нет. ДОКАЗАТИТЫЛВО. Будем вести доказательство методом мате­ матической индукции по длине слова и г . 01,. Пусть u r - t . По определению L(w )=*0 . Если ts y p C /U e ^ ) , то t - u f ил ...и к , Но L (u ,...u k)> L (U i) , отсюда следует, чтг t=U , , то есть t должно содержаться среди элементов множества AU<> Пусть иг~В> , где B^G- , и допустим, что В eyp(MoS). Тогда на основании леммы 8 среди подгрупп ря­ да ( 6 ) , порождающих основание S др (JUo,S) , должна содер­ жаться подгруппа Ц 'и A , , A t - б & , такая, что и Щ . я J j ■ <*,. Предположим, что для любого слова и / группы G-* слоговой д а н и меньше П- .можно через конечное число шагов установить, принадлежит это слово подгруппе др (М0) S) щ л нет. Пусть 1 ( и гЩ а := О, ± ' ; |3 -• О, ± f ; и wi.gp (JUr)>^ \ тогда Щ-=иг ,.и а , , где u r ..U rf - слово в подгруппе g o (M o ,S ) поэтому 1 ( и й)±1(и>) Выпишем из упорядоченного ряда (6) подгруппы ( ^ 4 / , правое крыло трансформ которых оканчивается на £ 16 , получим ряд: (■'££«’,) ^ ^j g ’, Присоединим к множеству подгрупп (19) нетраиоформы из JioWU 'o , оканчивающиеся на Полученное множество обо­ значим A r f . Разбиваем его на подмножества. Объединяем в одно подмножество в с п подгруппы ряда (19) и нетрансформы из А / й , тлеющие общее закрытое конечное подолово (Ад t Р . к т т ш т , f , Затем каждое из подмножеств ’"'.вбиваем, на под­ множества с общим конечным закрытым подсловом гд.щ подучаем подмножества: - 36 -