Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
L^ = Gp{до(0.....о, с. о.....о). Is, $Фі}>
L7j = Gp{w(0.....о, І3(8фі, j), t;tj},
LlLi = Gp{w(0.....о). Ms=^='\ j, I), Uh, Uh)^
^./,'=°РІш(о.....о), и^фі, j, I), Upf<l, ljPi,i}-
Для доказательства утверждения заметим сначала, что простой проверкой обнаруживается, что
(1) .....*.)= 0V-.....4-і, 4+t.....*»).
(2) pJ^iW^.....г j pi l = W(z'o...../my TRe Zi = Z1^ZZj И z's = Zs ДЛЯ
Бфі.
(При проверке формулы (2) нужно помнить, что 0 < / <}.) Назначение порождающих и p/t t теперь понятно. Если Г — элементарная формула, то из определения группы Lr и равенств (1) и (2) следует, что Lrn F э At- Однако обратное включение легко получается при помощи леммы Бриттона, так как если Некоторый элемент и из Lr содержится в F, он должен приво-
304
Гл. IV. Свободные произведения и HNN-расширения
диться к некоторому слову w из F последовательными ред циями, связанными с проходными буквами. Это, однако, обесп чивает вхождение w Q Ar, завершая тем самым доказательство леммы. ?
Основной леммы 7.8 вполне достаточно для доказательства су. ществования конечно представленной группы с неразрешимой пр< лемой равенства слов. (Заметим, что при доказательстве предыд1 щей леммы нам нужна была только лемма 7.7. Лемма 7.6 не испо зовалась.)
Теорема 7.2. Существует конечно представленная группа с неразрешимой проблемой равенства слов.
? Пусть S — рекурсивно перечислимое нерекурсивное множеств натуральных чисел. По лемме 7.8 подгруппа
B = Gp{asbc*\ sQS}
— удобная подгруппа в свободной группе K = <а, Ъ, с>. скольку подгруппа Gp {azbcz; zQZ\ свободно порождена ук занными порождающими,
z QS тогда и только тогда, когда агЪсг Q В.
Поскольку В удобна, существует вложение <р группы Kb = </С, t; t'1, Bt = By в некоторую конечно представленн группу Н. Из того, что Kb есть HNN-расширение, для прои вольного уQK получаем
уQB тогда и только тогда, когда t~xyt = y.
Следовательно,
z QS тогда и только тогда, когда у (azbcz) = у (t~xazbczt).
Поэтому решение проблемы равенства слов в H позволяет решать вопрос о принадлежности множеству S. Поскольку 5 не рекурсивно, проблема равенства слов в H должна быть неразрешимой. ?
Теперь нам предстоит завершить доказательство теоремы Хигмана о вложении. Отметим сначала, что, поскольку стандартное вложение Хигмана — Нейман — Неймана в 2-порожденную группу сохраняет рекурсивность представлений, достаточно показать, что удобными являются рекурсивно перечислимые подгруппы свободной группы L= (а, Ъ).
Нам нужно точно определить, что мы имеем в виду, когда говорим, что множество W слов от порождающих а и Ъ рекурсивно перечислимо. Для этого эффективно сопоставим каждому слову wQL некоторый гёделевский номер y(w). Тогда будем говорить, что множество W рекурсивно перечислимо, если рекурсивно пере'
7. Теорема Хигмана о вложении
305
числимо множество
у(W) = {у{W); w?W).
Придадим пустому слову гёделевский номер 0. Если w — произвольное непустое слово, не обязательно приведенное, от символов а, Ь, а~х, Ь-1, то y(w) — номер, получающийся, если рассматривать w как число в десятичной системе счисления, причем буквы a, Ь, а-1, Ь'1 — это соответственно цифры 1, 2, 3, 4. Так, у(Ьа)=2\, а у{а-^)=Ш.
С каждым словом w свяжем кодовое слово gw в свободной группе F= (а, Ь, с, d, е, h), такое, что
gw = whcywdevw.
Пусть
G = GpIg10; w—слово от a, b, а-1, Ь~1}
— подгруппа в F, порожденная всеми кодовыми словами. Заметим, что G свободно порождена выписанными порождающими.
Рассмотрим подгруппу N^L, порожденную множеством XsL. Поскольку группа
Y = Gp [h, а, Ь, сЧе1; і Zy (X)}
свободно порождена указанными порождающими, в F
N = Gp {Gn Y, h, с, d, e}nGp{a, Ь}.
Предположим, что X рекурсивно перечислимо. В этом случае множество v(X) рекурсивно перечислимо, так что по лемме 7.8 подгруппа Y удобна. Если мы установим, что и G удобна, останется только применить лемму 7.7 и доказательство теоремы будет закончено.
Для доказательства того, что G удобна, рассмотрим HNN-расширение F* группы F, полученное добавлением проходных букв tx, Х=а±г, b±l, и определяющих соотношений
txa = atx, txb = btx, ^1Ctx = C10, K1Ctx = C10, КШх = сУ(Ые"(Х).
С помощью этих соотношений легко проверить, что если W = X1.. .Xn- слово от а, b, а-1, Ь'1, то
.(*) Kn1... t-XlhutXl ..•Kn = whey (»>dev «-) = gw.
Из определяющих соотношений следует также, что если w — слово, оканчивающееся на букву X, скажем w=uX, то
(**) hgjx1 = huXhcy «*>dev ^tx1 =
= иХХ~%сУ mt^y Л)йеУ *>?le* w = gv
306 Гл. IV. Свободные произведения и УИШ-расширения
Утверждается, что в F*
G = Gp {hd, ta, ta-,, tb, h-^nF.
Из соотношения (*) очевидно, что G содержится в правой части.; Для доказательства обратного включения мы будем использовать лемму Бриттона. Пусть T — свободно приведенное слово от 1щ и tx. Если T Z.F, то существует последовательность слов T =' = Т0, T1, T1n, в которой каждое слово Tl+i получается;
из T1 редукцией относительно одной проходной буквы, a Tn Н~ содержит проходных букв. Утверждается, что в каждом T1 из. того, что 2 —- некоторое подслово между двумя последовательными вхождениями проходных букв, т.е. T1- = S,/x2/?S2, причем 2 не содержит проходных букв, следует z?G. Так как hdZG, это верно для Т. Из (*) вытекает, что если z?G, то txxztx?G.
