Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
В 1972 г. Макинтайр доказал другую замечательную теорему, а именно обращение теоремы Неймана. Точнее говоря, если конечно порожденная группа G вложима во все алгебраически замкнутые группы, то в ней разрешима проблема равенства слов. Объединяя эти две теоремы, мы получаем следующую алгебраическую характеризацию свойства иметь разрешимую проблему равенства: в конечно порожденной группе G проблема равенства слов разрешима в том и только в том случае, когда G вложима в каждую алгебраически замкнутую группу. Замечательная черта этой характе-ризации состоит в том, что она характеризует понятие из области эффективности — обладать разрешимой проблемой равенства слов^ в терминах совершенно дикого класса, ни одна из групп которого не обладает эффективным представлением!
Перейдем к доказательству теоремы Макинтайра.
Теорема 8.5. Если конечно порожденная группа G вложима во все алгебраически замкнутые группы, то в ней разрешима проблема равенства слов.
? По данной конечно порожденной группе
H = <hi, hn; rf, г2, ...у
с неразрешимой проблемой равенства слов мы должны построить алгебраически замкнутую группу Л, в которую Я нельзя вложить.
Пусть хи х2, . ¦ ¦— перечисление счетного множества порождающих символов. (Они окажутся порождающими группы Л.) Пусть Vi, V2, ¦ ¦ ¦— счетное множество переменных. Пусть также S0, Si, ...— перечисление всех конечных множеств уравнений и соотношений типа «не равно», включающих в себя элементы х я v. Рассмотрим, наконец, перечисление ть т2, ... всех n-ок слов над xf
И МНОЖеСТВО Zx, . . ., Zn из П переменных, отличных от Х( и Vi.
312 Гл. IV. Свободные произведения и HNN-расширения я ••
•--¦---44
Конечное множество уравнений и соотношений Wi(Xj, 0,) = 1, i=l.....т,
Yl(Xj, Vj)^ 1, Z= 1, .... я,
совместно, если существует группа G и элементы о/, Ьа из G, так\ что
UM«/. Z>,)=1, 1=1, .... m, Yifcp bj)^ l> / = 1.....п>
в G.
Группа Л будет построена в несколько этапов. Общая страі гия, используемая для этого построения, весьма проста. На эт пах с нечетными номерами, 2z+1, если система St уравнений соотношений типа «не равно» совместима с тем, что мы уже пос роили, постараемся обеспечить ей решение. На этапе с четными номерами, 2z, постараемся обеспечить, чтобы подгруппа, порожденная элементами і'-й я-ки тг, была неизоморфна группе Н.
На каждом шаге k мы будем иметь конечное множество Xh уже использованных порождающих символов и конечное множество 2„ уже обработанных систем уравнений и соотношений. Пусть ХО=0=2О. Допустим, что Xft_j и 2A_j уже определены. Построим Xh и 2ft следующим образом.
Предположим сначала, что k нечетно, ?=2/-f 1. Тогда Xj1 состоит из Xk_i и всех порождающих символов xj, встречающихся в записи системы S1.
Рассмотрим систему Sj, скажем
Wn(Xj, Vy)=U «=1. •••> т> ui (*/» Vj)=? 1, Z= 1.....d.
Предположим, что система 2ft_j и S1 совместна.
ДОПУСТИМ, ЧТО Переменные, Встречающиеся В S1- — ЭТО Vj1, . . ., Vf^
Выберем порождающие символы Xk1, ..., Xkq, не встречающиес в X'k- (Это, конечно, возможно, так как множество X* конечно. Пусть Хк—это X'k и Xk1, .... Xk4- Пусть также 2А —это 2A_j
Wh(xj, xk/)= 1, Zi= 1, ..., т,
ui(Xj, хк.)ф\, Z = 1, .... d.
Понятно, что система 2ft совместна.
Если 2ft_1l)s/ несовместна, то положим Хк = Х'к иі4 = 24_і.
Допустим теперь, что k = 2i. Используем остроумное рассуждение Макинтайра. Пусть %{= <Zi, Z„> есть Z-я я-ка из списка всех слов от порождающих символов Xj. Предположим, что Хк состоит из Хк-і и всех порождающих, встречающихс в компонентах я-ки xf.
5. Алгебраически вамкнутые группы
313
Определим теперь четыре множества слов от переменных Z1, ..•. z„. Пусть
A+ = {w (z1.....z„); w (Zi1, ..., Zin) == 1 в H)
и
а- = {и (z1-, 2Л); «(/i1, ZiJtMb Я}.
Заметим, что, поскольку проблема равенства в Я неразрешима, хотя бы одно из множеств A+ и A- не является рекурсивно перечислимым.
Пусть Ак— группа с порождающим множеством Хк, определяющие соотношения которой суть равенства w = 1 в 2ft_j. Пусть
D+ = {w(zit гп); w(tu .... U=Ib Ак\.
Поскольку Ак конечно определена, D+ рекурсивно перечислимо.
Для каждого слова и(Z1, Zn) определим Аку„ как группу, получающуюся из Ак добавлением определяющего соотношения u(ti7 tn). Поскольку каждая ЛАі„ конечно представлена, множество слов от порождающих Хк, равных 1 в Ак, а, рекурсивно перечислимо. Используя диагональную нумерацию, видим, что множество
D- = {и (Z1, г„); в sA_j имеется соотношение wт== 1, такое, что кі=1 в Akt а\
рекурсивно перечислимо. (Кратко: слово и лежит в D-, если добавление соотношения u(tlt tn) противоречит некоторому соотношению вида тФ 1 в 2ft_f.)
Поскольку D+ и D- оба рекурсивно перечислимы, а одно из A+, A- не является таковым, то либо D+t=A + , либо D-t=A-. Рассмотрим четыре возможности. Допустим, что A+-D+Ф0. Выберем WgA+-D+. Тогда v(tlt г„)тМ в Ак. Образуем добавлением соотношения v(tlt їп)Ф 1 к 2а_г-. (Понятно, что 2fe совместна.)
Если D+-A+ т== 0, то выберем v(ED+-A+. Тогда v(tit ... ..., tn) =а 1 в Ак. Образуем 2ft добавлением уравнения v(tlt .... /„)= 1 к Sft_f. Если D+=A+ и A- — D~ Ф 0, выберем v € A--D-. Образуем 2 к добавлением уравнения v (г,, ... /„) = 1 к 2A_j. Поскольку U^D-, все соотношения типа «не равно» из S6-1 выполняются в Ак<и и 2йсовместна. Если D+=A+ и D~—А~ф0, то выберем v€,D~—а-. Поскольку u?D~, v (z11 1п)ф1 в Ак. Образуем 24 добавлением соотношения u (z1, . .., і„)т==1 к s4-1.
