Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Зачастую мы будем упрощать теоретико-множественные обозначения и, например, вместо
G=({a, b); {а2, b\ (ab)2})
писать
G= (a, b; а2, b\ (ab)*).
Часто бывает приятнее в записи представления для группы записывать соотношения в форме равенств, а не слов; в этом случае предыдущее представление принимает вид
G=(a, b; а2=\, b* = \, a~1ba=b-1).
Можно, наконец, в записи представления опускать порождающие, если все они встречаются в записи определяющих соотношений; при этом соглашении получаем
G= (а2, b\ (ab)2).
Магнус, Каррас и Солитэр определяют представление как тройку (X, R, q>), где X и R означают то же, что и выше, а ф — гомоморфизм из F на Gc ядром N. Такое определение строже, но это та строгость, которая нам не понадобится.
Представление (X; R) называется конечно порожденным, если множество X конечно, и конечно определенным, если конечно R; при этом и группа G= (X; R) называется конечно порожденной и
1. Введение
127
конечно определенной соответственно. Представление (X; R) называется конечным, если и X, и R конечны; в этом случае группа G=(X; R) называется конечно представленной 1). Конечное представление конечной группы получается из ее таблицы умножения: в качестве порождающих следует взять все элементы gt группы G, в качестве определяющих соотношений — все равенства вида gig) = =gk, которые справедливы в G. Таким образом, представление группы можно мыслить себе как сокращенную запись таблицы умножения. Многие важные бесконечные группы допускают конечное представление. С другой стороны, Б. Нейман [1937] показал, что существует несчетно много неизоморфных групп, порожденных двумя элементами; отсюда следует, что существует много конечно порожденных групп, не обладающих конечным представлением.
Понятно, что группа определяется своим представлением с точностью до изоморфизма. С другой стороны, мы увидим, что даже наличие конечного представления еще не очень большая информация о группе G. Если X или R не являются конечными, то часто их описывают с помощью параметров. Такие представления естественным образом возникают для групп матриц над данным кольцом или полем; см., например, Цассенхауз [1969], Бер и Меннике [1968], Битам [1971], Суон [1971]2).
В важном частном случае множество X индексировано некоторым множеством /, состоящим из всех натуральных чисел либо являющимся конечным подмножеством множества натуральных чисел. В этом случае нетрудно определить простой код (или гёделев-скую нумерацию) /, устанавливающий взаимно однозначное соответствие между F и множеством натуральных чисел. В математической логике имеется точное определение рекурсивного или рекурсивно перечислимого множества U натуральных чисел; интуитивно можно представлять себе рекурсивное множество U как множество, для которого существует алгоритм, позволяющий определять, принадлежит данное натуральное число этому множеству или нет; для рекурсивно перечислимого множества U существует алгоритм, позволяющий в некотором порядке перенумеровать все элементы данного множества. Будем употреблять эту терминологию и в случае группы F, говоря, что подмножество R группы F рекурсивно или рекурсивно перечислимо, когда этим свойством обладает множество f(R); это определение не зависит от выбранного кода.
Скажем, что представление (X; R) рекурсивно, если X индексировано указанным выше множеством / и при этом R рекурсивно Перечислимо. Такая терминология может показаться довольно странной, но позднее мы увидим, что если группа обладает представ-
Обычно определяют только два класса: конечно порожденные группы, когда множество X конечно, и конечно определенные, когда Ли/? конечные.-— Прим. ред.
2> А также Н. С. Романовский [1971 *] и Г. А. Носков [1975*].- Прим. ред,
т-;а*ч ни тттллшг —»»і h» дата ш.- «MMtiMMNBrfcti*- r rtmi ir -v-,
128 Гл. //. Порождающие и соотношения
лением, в котором R рекурсивно перечислимо, то она обладает и представлением, в котором R рекурсивно. Замечательная теорема Г. Хигмана [1961] утверждает, что конечно порожденная группа G имеет рекурсивное представление тогда и только тогда, когда она может быть вложена в конечно представленную группу. Из приведенного выше результата Неймана и соображений мощности следует, что имеется много групп, не допускающих рекурсивного представления.
Проблема равенства слов — первая из трех фундаментальных алгоритмических проблем, поставленных Дэном в 1912 году. Вопрос состоит в следующем: пусть дано представление G= (X; R); существует ли алгоритм, выясняющий по любым двум элементам W1 и W2 группы F, представляют эти элементы один элемент группы G или нет? Эквивалентно, есть ли алгоритм, решающий, лежит W= =w1w21 в N или нет? Если такой алгоритм существует, т. е. если N рекурсивно, то говорят, что проблема равенства слов для представления (X; R) группы G разрешима. Фундаментальный результат П. С. Новикова [1955] (см. также Бун [1959]) состоит в построении группы G с неразрешимой проблемой равенства слов. (См. также Бриттон [1963], Г. Хигман [1961], Ротман [1973] и раздел IV.7 данной книги.)
