Алгебра, и логика, 39, N 2 (2000), 134-144
УДК 512.54.05
Е Щ Е Р А З О В О П Р О С Е ХИГМАНА*)
А. С. М О Р О З О В Юрию Леонидовичу Ершову ко дню 60-летия
К сожалению, недавно стало ясно, что предыдущая работа автора [1], в которой сообщается о решении вопроса Хигмана, содержит неиспра вимую ошибку (см. добавление). Напомним вопрос Хигмана. Легко убедиться в том, что если конеч но-порожденная группа представима рекурсивными перестановками, то ее проблема равенства слов коперечислима. Г. Хигман интересовался истин ностью обратного утверждения: верно ли, что каждая
конечно-порож
денная группа с коперечислимой проблемой равенства представима ре курсивными
перестановками?
В настоящей работе мы решаем этот вопрос, а именно: строим двупорожденную группу с коперечислимой проблемой равенства, не вложимую в группу всех рекурсивных перестановок. В неверном примере из [1] было 4 порождающих. Вопрос о существо вании подобной группы с двумя порождающими оставался открытым и несколько раз ставился автором, например, в [2]. Таким образом, в данной работе также решается вопрос о минимальном возможном числе порожда ющих. Этот результат был получен автором во время работы в универси тете г. Хайдельберга (Германия) в качестве научного стипендиата фон** Работа выполнена при финансовой поддержке фонда Александра фон Гумбольд та.
©
Сибирский фонд алгебры и логики, 2000
Еще раз о вопросе Хягмана
135
да Александра фон Гумбольдта. Автор выражает глубокую благодар ность проф. К. Амбош-Спису за поддержку и гостеприимство, а так же благодарит А. Ниса за моральную поддержку и ценные замечания, О.В.Богопольского и анонимного рецензента за устранение ряда неточ ностей в изложении. Предполагаем, что для любого конечного или бесконечного набора порождающих со, c i , . . . зафиксирована такая нумерация групповых тер мов от этих порождающих (т. е. всевозможных произведений этих поро ждающих и обратных к ним), что с помощью некоторых алгоритмических процедур можно переходить от номеров к словам и наоборот. В силу это го, выражения типа "перечислимое" или "коперечислимое семейство слов", "П^-предикаты на словах" и им подобные имеют вполне ясный смысл. Бу дем говорить, что группа С с заданным (может быть неявно) счетным или конечным множеством порождающих со,Ci,... является П-группой, если ее проблема равенства слов над со, c i , . . . коперечислима.*) В дальнейшем используем сокращения р. п. (для рекурсивно пере числимых) и ко-р. п. (для коперечислимых семейств). Т Е О Р Е М А . Существует двупорожденная U-группа, не вложимая в группу всех рекурсивных перестановок. ДОКАЗАТЕЛЬСТВО. Очертим общую структуру доказательства. Вначале дадим некоторую общую характеризацию П-групп. При этом вы яснится, что класс П-групп состоит в точности из групп, порожденных вычислимыми семействами автоморфизмов негативных нумераций (опре деление нумерации см. ниже). Затем построим вычислимое семейство ав томорфизмов (zi)i
hi не продолжается до вложения групп. Далее используем стан дартную конструкцию с HNN-расширениями для вложения группы, поро жденной автоморфизмами (^t) t<w , в двупорожденную группу. Последняя часть доказательства заключается в том, чтобы убедиться, что полученная группа является П-группой. *)Термин П-группа предложен А.Нисом.
А. С. Морозов
136
Напомним некоторые понятия из теории нумераций, следуя [3]. Ну мерацией называется произвольное отображение "на" и : и -> М. Взаимно однозначное отображение (р : М —)• М называется автоморфизмом
нуме
рации и, если найдутся рекурсивные функции / и д такие, что ""1i/ = r/gr. Пусть / будет либо множеством всех натуральных чисел, ли бо его начальным отрезком. Индексированное семейство функций ( Л ) ^ / назовем вычислимым, если значение функции /,(ж) равномерно вычисля ется по данному индексу г £ / и аргументу х, или, что эквивалентно, семейство {(x,y,i)
| г € J & /;(я) = у} является р.п. Семейство авто
морфизмов (ро, (pi,.., нумерации и назовем вычислимым, если существуют вычислимые семейства /о, Л , . . . и <7о> <7ь • • • рекурсивных функций такие, что для всех i < и выполняются равенства щи = i//t- и ^ : V = г/#«. Нуме рация I/ называется негативной, если ее нумерационная эквивалентность Tju = {(ж, у) | */ж = ь>г/} является ко-р. п. Приступим к изложению первой части доказательства. В следующей лемме П-группы охарактеризованы в терминах автоморфизмов негатив ных нумераций. Л Е М М А 1. 1. Пусть G = gr (#сь <7ъ • • •) является П-группой. Тогда существует негативная нумерация и и ее вычислимое семейство авто морфизмов фо,ф\,...
такие, что отображение gi ь-> ф{ определяет изо
морфное вложение. 2. Пусть v — негативная нумерация и фо,ф\,... мейство ее автоморфизмов. Тогда G = gr (фо,ф\,..)
— вычислимое се является
П-груп-
пой. ДОКАЗАТЕЛЬСТВО. 1. Пусть и(п) — элемент группы G, представ ленный групповым словом с номером п. Если w — групповой терм, будем обозначать через [w] элемент группы, представленный этим термом. Для каждого i ?...Ф1* = 1& Vn ( е f?„),
Еще раз о вопросе Хигмаяа
137
откуда и следует лемма. Наш пример группы базируется на следующем несложном наблюде нии. Л Е М М А 2, Пусть (zi)i<w
~ вычислимое семейство
рекурсивных
перестановок и порядок o(zi) каждой перестановки Z{ является
простым
числом. Тогда функция г У-Ь O(ZJ) рекурсивна. ДОКАЗАТЕЛЬСТВО тривиально. Группа, существование которой доказывается в следующей лемме, играет важную роль в дальнейшем доказательстве теоремы. Л Е М М А 3, Существуют негативная нумерация и и вычислимое семейство (• o(tfi) не рекурсивна. СЛЕДСТВИЕ* В этом случае С = gr (y>0, <Ри • • •) будет П-группой по лемме 1. По лемме 2, она не вкладывается в группу всех рекурсивных перестановок так, чтобы последовательность образов для <^о? <Ри • • • была вычислимой. ДОКАЗАТЕЛЬСТВО леммы. Обозначим через с любое рекурсивное 1—1 отображение из и X и на са, и пусть (-)о и (-)i будут декодирующими функциями, т. е. для всех ж, у 6 и выполняются равенства (с(ж,у))о = я, (с(ж, у))х = у и с((ж)о, (#)i) = х. Пусть Ri = {х | (х)о = г} для всех г < и. Построим нумерацию и бесконечное семейство ее автоморфизмов по шагам. Пусть каждая функция /,- будет тождественной вне JRt, и далее будем определять ft только внутри Я,, постоянно расширяя эту часть так, чтобы в итоге получить всюду определенные функции (и даже перестанов ки) /;. Зафиксируем некоторое р. п. нерекурсивное множество А и некото рое его перечисление. Часть множества А, перечисленная к шагу £, будет обозначаться Аг. Начнем построение с функций /,-, нигде не определенных на Я,. Ш а г t. Предположим, что i^A*.
В этом случае уже построенная
часть функции fi на Д, образует конечную цепочку (возможно, пустую): ао —* ел —> a ajb,
138
А. С. Морозов
все элементы которой различны. Выбирая новые элементы из Я;, расши рим эту цепочку на один элемент с каждого из концов. Предположим теперь, что на шаге t впервые выяснилось, что г £ А*. В этом случае добавляем новые элементы в цепочку для /,- так, чтобы получить цикл простой длины большей 2 и полагаем /,- тождественной на остальных элементах множества i?,; таким образом, /,- уже полностью определена, и больше ничего с ней не делаем на последующих шагах. Определим отношение эквивалентности rj путем перечисления его до полнения. Неформально, пока г£А*, /» определяет 2-цикл на R%fr), т.е. каждое а, вовлеченное в построение, будет ^-эквивалентно ff{o)-
Если
в дальнейшем окажется, что г € А, то все элементы в Я, становятся не ^-эквивалентными. Формально -*(хт!у) т± х ф у & ((ж) 0 ф (у)о V ((х)о = (у)о & ((х)о € А V
^{ф£Ч*) = уу fffilw = *))))Принимая во внимание, что отображение г , а : н /,(ж) рекурсивно, получа ем, что т] является ко-р.п. отношением. Как видно из построения, (/i) t < w представляет собой вычислимое се мейство перестановок, определяющее вычислимое семейство автоморфиз мов {i{v(x)) = v(fi(x))
такое, что каждый
порядок o((pi) является простым числом, и o((pi) ф 2 выполняется тогда и только тогда, когда г £ А. Следовательно, отображение г *->• o((fi) не может быть рекурсивным. Лемма доказана. Итак, мы построили группу С = gr (<,po, <£ъ • • •) i порожденную вычис лимым семейством автоморфизмов (ро> <£>i,... некоторой негативной нуме рации v и такую, что не существует вложения в группу всех рекурсив ных перестановок натуральных чисел, относительно которого образы эле ментов <А)>¥>ъ ••• образуют вычислимую последовательность. Она будет П-группой по лемме 1. Заметим, что С устроена весьма просто. Она изоморфна ]Г) Z 9 n , где qn равно 2, если п не принадлежит А, и наименьшему простому числу, большему либо равному 2t и не равному 2, если п попадает в А на шаге t.
Еще раз о вопросе Хигмана
139
Другое представление С = gr (c 0 ,ci,...) этой группы, в котором с 0 = 1, ci = (p0l c2 = Vi, . . . также будет П-группой с теми же самыми свойствами. Зафиксируем элементы CQ,CI,. .. В дальнейшем используется обычная конструкция для вложения любой счетной группы в двупорожденную группу. Мы следуем изложению этой конструкции в [4]. А имен но, сначала рассмотрим свободное произведение С * Fa,b с группой Fa?&, свободно порожденной новыми буквами а и Ь. Потом выделим подгруппы gr (Ь~паЬп | n e w ) ,
Я
=
S
— gr (6,^0* a~lbal,
gr (c„ • a~~nban | и е w),
свободно порожденные указанными элементами. После этого мы рассмо трим HNN-расширение G
=
(c*F f l > 6 , t | Г 1 -b~nabn-t
= c n .
Как замечено в доказательстве теоремы 3.1 в [4] (впрочем, это видно непо средственно), данная группа порождается элементами t и а. Более того, <рп =
Сп+1
= r16-n-1aftn+1t - (a-n-1ftan+1)-1,
т.е. если бы мы вложили G в группу всех рекурсивных перестановок, <рп образовали бы вычислимое семейство перестановок. Поэтому G не представима рекурсивными перестановками. Оставшаяся часть доказательства посвящена объяснению того, что G = gr (£, а) является П-группой. Л Е М М А 4. Множество слов от порождающих а и Ь, представля ющих элементы группы Н = gr (b~nabn | n € u>), рекурсивно. Л Е М М А б. Пусть С == gr (со, с 1 ? ...) и D = gr (d0, d i , . . . ) являются П-группами. Тогда С * D = gr (c0, c i , . . . , do,di,...)
также П-группа.
ДОКАЗАТЕЛЬСТВО. Достаточно показать, как по данному т £ w можно равномерно перечислять все групповые слова вида wo^o- - w m i ; m , где wo? •••> wm являются групповыми словами в алфавите { C Q , C I , . . . } , а
140
А. С. Морозов
Щ, - • •> Vm — групповыми словами в алфавите {do?di,...}, представляю щими нетривиальные элементы. По теореме о канонической форме из [4], имеем UQV0 . . . UmVm = 1
<=>
(u0 = 1 к VQ . . . W m U m = 1)
V(t*> = 1 & («ot4i)vi.. .umvm
= 1)
V(vm = 1 & w 0 i;o.. .um = 1). Теперь делаем то же самое с равенствами vo...umVrn • •• umvm
= 1, (^o^iW . . .
= 1, . . . , мо^о-'-^т = 1, и т.д. В конце концов, приходим к
булевой комбинации равенств вида и = 1, которые являются П?-предика тами. Заметим, что так полученная булева комбинация содержит лишь & и V. Значит, вынося кванторы влево, получаем П^-форму для утверждения ^о^о... umvm = 1. Его отрицание дает нам Е^-форму для UQVQ . . . umvm ф Ф 1, что в свою очередь дает в наше распоряжение метод перечисления всех таких слов, не равных 1. Лемма доказана. Л Е М М А 6. Пусть С = gr(co,ci,...) является Tl-группой. Тогда множество всех слов из С * Fa>b, представляющих элементы подгруппы H = gr{b"nabn
\п£и),
является ко-р. п. ДОКАЗАТЕЛЬСТВО. Рассмотрим гомоморфизм ф : С * FQlb ~> Faib такой, что ф(а) = а, ф(Ь) = b и ф(с$ — 1 для всех г < а;, существующий по определению свободного произведения. Заметим, что ф тождествен на Faf>. Если произвольное групповое слово w представляет элемент из Я в C*Fafa то элемент ф(ю) представим групповым словом w, которое получается из w опусканием всех вхождений cf1. Поскольку ф тождествен на Я С F0>5, имеем w = ф{и)) 6 Я . Рассматривая " как синтаксическую операцию, получаем: w€H&w€H$zw
— w.
По лемме 4, отношение w £ Я рекурсивно. В силу леммы 5, w = w являет ся П1-отношением. Следовательно, w £ Я также является П^-отношением.
Еще раз о вопросе Хигмана
141
Лемма доказана. Л Е М М А 7. Пусть С = gr(c 0 ,ci
) является П-группой. Тогда
в группе С * Fa,b множество всех слов, представляющих элементы под группы S = gr (c n • а~"пЬап | п € w) является ко-р. п. ДОКАЗАТЕЛЬСТВО. Определим гомоморфизм ф : С * F a , 6 ->• ^ а ,ь так, чтобы V( a ) = a, VK&) = Ь и V>(c«) = 1 для всех i < и. Пусть В = = gr (a~nban | n 6 OJ). Для каждого группового слова ш Е В от о и Ь, определим слово й) следующим образом. Поскольку w E В, оно может быть представлено в эквивалентном виде (a~ , 0 6a , 0 ) W o ... (a~*kbatk)mk. w = (с10 • a-iobaio)mo... Если w£B,
Полагаем
(ан • сГЧа 1 '*)" 1 *.
пусть й) = 1. По лемме 4 отображение w »-»• w является вычис
лимым. Проверим эквивалентность w е S <& ф(ю) е В & Щт) = «?,
(1)
из которой и следует лемма. Предположим w € 5 . Тогда для подходящего слова
выполняется равенство w = ti;'. Отсюда ^(w) = ^(u/) = (a"4a f *°) Wo . . . (a~ikbaik)mk
€ JB.
Далее,
Предположим теперь, что справедлива правая часть (1). Поскольку ^(w) 6 В, ф(ги) равняется подходящему групповому слову вида V = (a"iobaio)mo
...(a-ikbaik)mk.
Тогда w = t/>(™) = w7 = (cl0 • o" io 6a f ' 0 ) mo . . . (cife • a",*ba**)w* € 5.
142
А. С. Морозов
Лемма доказана. Л Е М М А 8, Пусть С = gr (co,ci,...) является U-группой. Тогда ее HNN-расширение G = (С * Ffljb, t \ t~lb~nabnt ляется
= c n a~ n ba n ) также яв
U-группой,
ДОКАЗАТЕЛЬСТВО. Нам понадобится Л Е М М А Б р а й т о н а (см. [4]). Пусть G — группа, A
и ф: А-^
—> G — вложение. Рассмотрим HNN-расширение Gi = gr (G, t 1 1 " 1 ^ = ф(а), a e A) . ,Е?сли терлс euda aot€laite7 . ..an-itenan,
Si G {-1,1} равен 1, n > 0 u все
a t не содержат вхождений буквы t, то этот терм содержит подтерм либо вида t~lait} где a t 6 А, либо вида to,-*""1, где а{ £ ф(А). Таким образом, если такое слово равно 1, то оно может быть реду цировано, т.е. некоторая его часть может быть заменена по одному из двух следующих правил: t~lat -> ф(а), tat~l —> ф"г(а). В нашем случае вложение ф : Н —> 5 задано как ф(Ь~паЬп) =
спа~пЬап.
Определим две вычислимые функции на групповых словах над ал фавитом {со, c i , . . . } U {а, 6}. Первая из них обозначается Ф(и) и выдает, ф(и) если и Е Я , и произвольный элемент в противном случае. Вторая функция Ф аналогичным образом "ответственна" за фг1. Для определения Ф заметим, что если и лежит в Я , то по доказа тельству леммы 6, результат вычеркивания из него всех вхождений cf1 тоже лежит в Я , и полученное при этом выражение равно исходному. Поэтому Ф(и) определяется так. Сначала мы вычеркиваем из и все вхо ждения cf1 и используем лемму 4, чтобы установить, принадлежит ли Н результат и'. Если и' $ Н, выдаем 1 в качестве результата, в про тивном случае записываем и1 в виде (fe~ lo ab* 0 ) m °... (b~tkab%k)mk и выдаем (c*0a-I'°bat'0)rao . . . (c1-fca-f'*bal'*)m*. Определим Ф. Заметим, что если и 6 5, то по доказательству лем мы 7, результат вычеркивания из него всех вхождений cf1 попадает в В = gr (a~~nban | п £ и). Ввиду отсутствия нетривиальных соотношений между а и 6, получится выражение вида (a~tobato)m°
• . . . • (a~'*6a'*) mfc ,
143
Еще раз о вопросе Хигмана откуда и = (ct 0 a~ lo ba lo ) Wo - . . . • (cika~%kbaik)mk %0
и Ф(^) можно положить
t0 m
равным (b~ ab ) ° • . . . • (б"** aft**)™*. Суммируя сказанное, применение Ф к г* можно определить как вычеркивание всех вхождений cfl с последую щей перестановкой между собой букв а и 6. Пусть w = oot^ai**1 ...ajfe^ajfe+i, где Si € {-1,1}, <*• не содержит вхождений t^ 1 . По лемме Брайтона мы имеем: aot€°ait€l . ..akt€kak+i
= 1<$
[е0 = - 1 & ei = 1 к аг £ Я & a 0 $ ( a i ) a 2 ^ 2 . . . a ^ a f c + i = 1] V[e0 = 1 & £i = - 1 & ai 6 S & a 0 * ( a i ) a 2 ^ 2 . . .аЛ*е*а*+1 = 1] V[6i = - 1 &
...]V...
Продолжая процесс внутри этой формулы, мы приходим к не содержа щей отрицаний булевой комбинации П^-утверждений вида и 6 Я , и G 5 и t* = 1, где w — групповое слово в алфавите {со, с\%.. .}U{a, Ь}. Затем то, что получится, приводим к П^-форме. Таким образом, имеем П^-форму для утверждения w = 1. Заметим, что это делается равномерно по начально му слову w. Следовательно, w ф 1 эквивалентно некоторому Е^-условию, выписываемому равномерно по w. Это доказывает коперечислимость про блемы равенства в G и заканчивает доказательство леммы, а вместе с ней и теоремы. Д о б а в л е н и е . В работе [1] мы рассмотрели перестановки ао = (0,1), 9о = П (2*,2г + 1), д\ = П (2* + 1,2г + 2) и показали: *
i
если h — перестановка, доя которой группа gr (ft,ao, So» Pi) вложима в группу всех рекурсивных перестановок, то h обязана быть рекурсивной. Далее утверждается, что строится нерекурсивная перестановка h на и такая, что проблема равенства в gr (А,оо> 0
в
А. С. Морозов
144
ЛИТЕРАТУРА 1. А. С. Морозов, Об одном вопросе Хигмана, Алгебра и логика, 29, N 1 (1990), 29-34. 2. А. S. Morozov, Groups of computable automorphisms (chapter 8), In: Handbook of recursive mathematics, Elsevier Science B. V., 1998, 311—345. 3. Ю.Л.Ершов, Теория нумераций, М., Наука, 1977. 4. Р. Линдон, П. Шупп, Комбинаторная теория групп, М., Мир, 1980.
Адрес автора: МОРОЗОВ Андрей Сергеевич, РОССИЯ, 630090, г. Новосибирск, пр. Ак. Коптюга, 4, Институт математики СО РАН. e-mail: [email protected]
Поступило 3 марта 1999 г. Окончательный вариант 21 февраля 2000 г.
