Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Следующая теорема принадлежит Хигману [1961].
Теорема 7.3. Существует конечно представленная группа Я, в которую вложима любая рекурсивно представленная группа.
? Множество всех конечных представлений Gj=(Xj; R1) естественным образом счетно и рекурсивно перечислимо. Ясно, что можно выбрать такую нумерацию, при которой все X1 — последовательные непересекающиеся отрезки некоторого множества X = (Xf, х2, ...}. Понятно, что в этом случае (X; URi) — рекурсивное представление для группы G, изоморфной свободному произведению групп Gj и, следовательно, содержащей подгруппы, изоморфные любой конечно представленной группе. Поэтому по теореме Хигмана — Нейман — Неймана G может быть вложена в некоторую рекурсивно представленную 2-порожденную группу G*. Вложим затем G* в некоторую конечно представленную группу Я. Ясно, что в Я содержится экземпляр каждой конечно представленной группы. Еще раз применяя теорему Хигмана о вложении, видим, что в Я содержится экземпляр каждой рекурсивно представленной группы. ?
Обратимся теперь к одной теореме Буна и Хигмана [1974], дающей сжатую алгебраическую характеризацию конечно порожденных групп с разрешимой проблемой равенства слов.
Теорема 7.4. Проблема равенства слов в конечно порожденной группе G разрешима в том и только том случае, когда G вложима в простую подгруппу конечно представленной группы.
294 Гл. rV. Свободные произведения и HNN-расширения
? Допустим, что G может быть вложена в простую подгруппу некоторой конечно представленной группы Н. Тот факт, что проблема равенства слов в G разрешима, фактически содержится в теореме Кузнецова (теорема 3.6). Поскольку G конечно порождена и вложима в конечно представленную группу, множество слов, равных 1 в G, рекурсивно перечислимо. Поэтому достаточно показать, что множество слов, не равных единице в G, также рекур. сивно перечислимо. Пусть гр: G-+-H — вложение, такое, чтогр(С)?5, где S — простая подгруппа в Н. Выберем фиксированный элемент l==?s(ES. Для произвольного w?G пусть Hw — группа, получающаяся из H добавлением определяющего соотношения гр(до). Поскольку S проста, если гр(до)==^1 в Н, все элементы из S, в частности s, равны 1 в Hw. Таким образом, тфі в G тогда и только тогда, когда s=I в Hw. Поскольку G конечно порождена, а Ню конечно представлена, множество до, таких, что s=I в Hw, рекурсивно перечислимо.
Теперь нам нужно показать, что если G — конечно порожденная группа с разрешимой проблемой равенства, то G может быть вложена в простую подгруппу некоторой конечно представленной группы. Первый шаг состоит во вложении группы G в простую группу S с рекурсивным множеством определяющих соотношений. Конструкция группы S напоминает конструкцию группы, в которой любые два элемента одного и того же порядка сопряжены, однако нужно заботиться о разрешимости проблемы равенства, слов. 1
Поскольку в G разрешима проблема равенства слов, множеств!
{(Ui, Vi), (и2, V2), ...} I
пар элементов группы G, ни один из которых не равен 1, рекуя сивно. Пусть 1
G1 = (G-, X1, tt (і~^\)\ tJ1U{Xj1U 1Xj = ViX11U1X1, t^l>. І
Элементы U1Xi1UiXi и ViXi1UiXi как элементы свободного произвв дения циклически приведены, и их длина равна 4. Поэтому они являются элементами бесконечного порядка, более того, проблеме вхождения в циклические подгруппы, порожденные этими элемеи тами, единообразно разрешима. Таким образом, Gi есть HNrM расширение группы G*{Xi), такое, что проблема равенства ело» в Gi разрешима.
Предположим, что группа Gk определена, и введем Gk+1, исходя из Gn, как это проделано в предыдущем абзаце. Пусть
5= UG6.
в силу единообразия нашего процесса построения проблема равенства слов в 5 разрешима. Проверим простоту группы 5. Пред-
7. Теорема Хигмана о вложении
295
положим, что и и v — нетривиальные элементы из S. Подберем индекс k—1, такой, что и и v лежат в Gk_x. В этом случае существует проходная буква р, такая, что в Gk имеет место соотношение
P^UXk1UX11P = VXJ1UXk-
Разрешая это уравнение относительно v, мы видим, что v лежит в нормальном замыкании элемента и. Поскольку uav произвольные, группа S является простой.
Множество определяющих соотношений группы 5 рекурсивно. Поэтому по теореме Хигмана — Нейман — Неймана 5 может быть вложена в рекурсивно представленную 2-порожденную группу К. По теореме Хигмана о вложении К может быть вложена в конечно представленную группу Я. Цепочка вложений
G^S-+K-+H
доказывает теорему. ?
Для доказательства теоремы Хигмана о вложении нам требуется иметь точные определения понятий «рекурсивное™» и «рекурсивной перечислимости». В свое время было дано много определений: через машины Тьюринга, через формальные системы, через ^-вычислимость и т. д. Все предложенные определения оказались эквивалентными. Именно эквивалентность этих формально совершенно различных понятий привела логиков к убеждению, что точно определенное понятие рекурсивности является удовлетворительной формализацией интуитивного понятия «эффективности». Это философское кредо называется тезисом Чёрча — Тьюринга. На практике это означает, что если кто-либо доказал, что некоторая функция / не является рекурсивной, то другим не следует тратить время на нахождение процедуры (обязательно нерекурсивной) для вычисления функции /, которая в каком-либо смысле «эффективна».
