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

Пусть уе<у,/>Г)С7. Индукцией по длине слова v покажем, что v яв- ляется словом в образующих х0,х ....... ху, ..... Если /(v) = 1, то утверждение оче­ видно. Пусть для всех слов v, длины которых не превосходят некоторого т > 1, утверждение верно. Покажем, что оно справедливо и для слова v длины т +1. Так как v e G , то по лемме Британа [4] оно содержит некоторое подслово V следующего вида v' = r'v '(x 0,x....... Xj,...)t либо v '= rv’(xn,x,, ..., х,,...)/-1, где v"e(p(G) (12) Пусть v' = r ‘v'(x0,x,, .... Xj,...)t, тогда v' = v'(x.......xy+l,...) и так как в результате Г-редукций [4] длина слова v уменьшилась, то к нему можно при­ менить индуктивное предположение. Пусть v' = tv \x 0,x .......^ Если v" = v”(x{i ...» *^...),> то v'.= v*(x0,x,, Xj,...) и так как в резуль­ тате /-редукций длина уменьшилась, то опять применимо индуктивное предпо- ложение. Если v'(x0,x ,...... х},...) =y*°q,ya'q 2 ...уа,Яа, где q,=q,(x„ .... ху,...), то, так как qt е (р(G) а у <t <p(G) следует, что v' г <p(G) вопреки условию (11). Следовательно, < y,t > f|G =<х0, х ,,... xJ t...>. Индукцией по j покажем теперь, что ............. ... - свободные обра­ зующие группы < у, t > DG. Докажем, что Lj =<х0,х,, ... Xj,...> является свободной группой ранга /+ 1 . Так как х, = <p(x0)e<p(G), то <х0,х, >=<х0 > *< х , > - свободная груп­ па. Пусть теперь утверждение справедливо для всех j <j ', покажем, что оно останется верным и при j = j ’. Так как <-х„ ... ху > = Г ‘ <х0, ... ху_, >t = Г 1£уч/ = 1(х,,... х; ). По ин­ дуктивному предположению Lj_{ - свободная группа, следовательно Ц х ,,... Xj ) - также свободная группа. Так как для любого j Ц х {, ... ху) с cp(G), 24