Научная библиотека

§ 6. Свободная группа

1. Свободная полугруппа.

Пусть задано конечное множества элементов называемых буквами. Это множество называется алфавитом. Последовательности , букв алфавита называются словами. Присоединение к данному слову справа второго слова называется умножением слов. Ясно, что это действие ассоциативно, так что по отношению к нему слова составляют полугруппу. Естественно ввести в рассмотрение пустое слово. Оно играет роль единицы в полугруппе слов. Так построенная полугруппа называется свободной полугруппой, порожденной данным алфавитом.

2. Свободная группа.

Свободная полугруппа, конечно, не является группой, так как произведение непустых слов непусто, так что у непустого слова не может существовать обратного.

Для построения на этом пути группы применим следующую конструкцию. К алфавиту присоединим второй алфавит . Строим слова в объединении этих алфавитов и вводим для слов в алфавите Т отношение эквивалентности следующим образом. Вставкой в слово в алфавите Т мы назовем присоединение между двумя буквами (или в начале слова, или в его конце) слова или . Сокращением слова назовем исключение из слова его части вида или . Два слова назовем эквивалентными, если от одного из них можно перейти ко второму посредством конечного числа вставок и сокращений. Ясно, что если два слова эквивалентны третьему, то они эквивалентны между собой, так что все слова разбиваются на непересекающиеся классы эквивалентных слов. Столь же ясно, что если слово эквивалентно слову и слово эквивалентно слову , то слово эквивалентно слову . Это позволяет ввести естественным образом умножение классов слов, считая произведением классов тот класс, который содержит произведение каких-либо слов из этих классов. Класс, содержащий пустое слово, является единицей при этом, умножении. Ассоциативность умножения, очевидно, следует из ассоциативности умножения слов в свободной полугруппе. Классы, содержащие и взаимно обратны, ибо слова превращаются в пустое слово после сокращения. Наконец для класса, содержащего любое слово, существует обратный: если класс содержит слово при , то обратным будет класс, содержащий слово (здесь под понимается ).

Итак, множество классов эквивалентных слов образует группу. Она называется конечно порожденной свободной группой. Классы, содержащие буквы алфавита S, являются ее образующими.

Когда речь идет об обширных классах объектов, всегда приятнее иметь дело с какими-либо стандартными представителями из этих классов.

Здесь роль таких представителей играют несократимые слова. Слово в алфавите Т называется несократимым, если в нем не стоят рядом буквы и .

Теорема I. В любом классе эквивалентных слов существует одно и только одно несократимое слово.

Доказательство. То, что для любого слова найдется несократимое, ему эквивалентное, очевидно: в исходном слове нужно шаг за шагом, в каком-либо порядке, сокращать соседние «двойники» . При каждом сокращении длина слова, т. е. число составляющих слово букв, уменьшается на две единицы, так что процесс сокращения должен закончиться на несократимом слове после конечного числа сокращений.

Остается доказать, что различные несократимые слова не могут быть эквивалентны. Мы докажем это от противного. Пусть даны несократимые слова А и В, и допустим, что они эквивалентны, т. е. что существует конечная последовательность слов , таких, что каждое последующее слово получается из предыдущего вставкой или сокращением. Так как А и В несократимы, переход к может быть только вставкой, переход от — только сокращением. Полной высотой перехода от А к В назовем сумму длин всех промежуточных слов.

Пусть — слово наибольшей длины среди слов крайнее, ибо длина больше длины и длина больше длины Поэтому у слова - имеется как сосед слева так и сосед справа Переход от к -должен быть вставкой, переход от — сокращением. Здесь может представиться несколько случаев:

1. При переходе от к - вставили ЬВ и при переходе от , к вставленную пару сократили. В этом случае так что мы можем исключить из перехода слово , и «склеить»

2. При переходе от к , вставили и справа от этой вставки находился элемент b, а при переходе от к в тройке соседних букв сократили . В этом случае опять То же самое будет, если вставить направо от и в тройке сократить .

3. При переходе от к , вставляется и при переходе от ; к сокращается и эта пара не имеет общих элементов со вставленной Тогда переход от можно сделать по-другому. Буквы с и с не были вставлены при переходе от и следовательно, уже присутствовало в Можно было сначала сократить получив слово а затем вставить ЬВ. Длина промежуточного слова на 4 меньше длины слова так что полная высота перехода от к В уменьшилась на 4.

Во всех случаях полная высота перехода может быть уменьшена. Это невозможно, ибо среди переходов от к В должен существовать переход с наименьшей полной высотой.

Следовательно, эквивалентные несократимые слова равны, что и требовалось доказать.

3. Конечно порожденные группы как гомоморфные образы свободной группы.

Теорема 2. Любая конечно порожденная группа с образующими есть гомоморфный образ свободной группы с образующими.

Доказательство. Пусть — система образующих группы G. Рассмотрим свободную группу сначала как полугруппу слов в алфавите Каждому слову сопоставим элемент группы G. Ясно, что произведению слов соответствует произведение элементов группы G. Покажем, что эквивалентным словам соответствуют одинаковые элементы. Действительно, вставке в слово соответствует появление сомножителя равного единице, и сокращению пары соответствует исключение из произведения Тем самым, построенное отображение есть гомоморфизм свободной группы на группу

Если некоторое слово из свободной группы входит в ядро, то соответствующий элемент группы G равен 1, т. е. элементам ядра гомоморфизма свободной группы в G соответствуют соотношения между образующими группы

4. Задание группы образующими и соотношениями.

Теорема 3. Пусть дан алфавит и слова в этом алфавите

Здесь обозначают буквы алфавита. Тогда существует группа образующими в которой выполнены соотношения

где если если . Среди групп, для образующих которых выполнены указанные соотношения, существует группа G, в которой все соотношения между образующими являются следствиями данных соотношений, и эта группа обладает свойством универсальности — любая группа, в которой выполнены предписанные соотношения, является гомоморфным образом группы

Прежде чем доказывать теорему, необходимо выяснить, что понимается под следствиями из данных соотношений.

Мы считаем, что если есть соотношение, то соотношение является его следствием.

Если — два соотношения, то соотношение является их следствием, и, наконец, если есть соотношение, то при любом соотношение тоже считается следствием.

Доказательство. Рассмотрим свободную группу с образующими ней наименьшую нормальную подгруппу, содержащую Напомним, что эта подгруппа состоит из элементов обратных к ним элементов, сопряженных с ними и произведений всех таких элементов. Гомоморфный образ G свободной группы с так построенным ядром будет иметь предписанные соотношения. Другие соотношения будут определяться всеми элементами ядра гомоморфизма, и в силу устройства этого ядра, будут следствиями предписанных соотношений в описанном выше смысле.

Если в группе, кроме предписанных соотношений и их следствий, выполняются еще какие-либо соотношения, то ядро гомоморфизма будет содержать указанную нормальную подгруппу, и, в силу свойства универсальности факторгруппы, группа будет гомоморфным образом группы

Доказанная теорема дает возможность задавать группы при помощи задания образующих и соотношений между ними. Эти соотношения называются определяющими соотношениями. Группы, имеющие конечное число образующих и конечное число определяющих соотношений, называются конечно определенными. Именно такие группы часто возникают в приложениях теории групп к геометрии и топологии. Иногда определяющие соотношения таковы, что элементам группы удается дать некоторую каноническую запись, и умножение элементов в канонической записи не представляет труда. Рассмотрим примеры этого рода.

Пример 1. Группа задана двумя образующими а и b, связанными соотношениями . Очевидным следствием из этих соотношений является . Последние два соотношения можно записать в форме . Эти соотношения позволяют переносить образующий а через b или справа налево, заменяя b на на b. Это позволяет записать любой элемент группы в форме при Рассматривая элементы этого вида формально, с правилами умножения, вытекающими из правила переноса а справа налево и условий нетрудно проверить, что символы действительно образуют группу. Она конечна, ее порядок равен 6. Легко видеть, что она изоморфна симметрической группе подстановок трех элементов. Изоморфизм дается соответствием .

Пример 2. Группа задана двумя образующими и соотношениями . Здесь образующий с свободен, т. е. порождает бесконечную циклическую группу. Очевидным следствием из этих соотношений является аста при любом целом m, т. е. преобразование сопряжения посредством а вызывает в подгруппе, порожденной образующим с, единственный нетривиальный автоморфизм.

Из соотношения аста следует правило переноса образующего а справа налево, именно, . Это правило позволяет записать любой элемент группы в виде при и любом целом m. Легко проследить, что символы акст при умножении с правилами, обусловленными соотношениями и действительно образуют группу. Эта группа нам еще встретится в следующем параграфе.

Однако при задании группы образующими и определяющими соотношениями имеет место одна принципиальная неприятность. Если даны два элемента группы, записанные через образующие, как узнать, равны они или нет? Вопрос легко решается, если соотношения таковы, что существует каноническая форма записи. Однако такой характер соотношений является скорее исключением, чем правилом. Проблема распознавания равенства элементов группы, заданной образующими и определяющими соотношениями, называется проблемой тождества в теории групп. Для свободной группы она решается благодаря канонической записи элементов в виде несократимых слов. Проблема получила положительное решение для групп с одним соотношением. Однако в 1952 г. П. С. Новиков доказал, что не существует алгорифма, позволяющего решать проблему тождества в общей постановке. Более того, им построена такая система определяющих соотношений между образующими, что не существует алгорифма для решения проблемы тождества в группе, заданной этими образующими и соотношениями. При этом доказательство потребовало точного определения того, что такое алгорифм, и привлечения средств современной математической логики.

Разумеется, несуществование общего алгорифма для любых элементов не значит, что задача не может быть решена индивидуальным приемом для заданной пары элементов. Из того, что алгорифмически неразрешима массовая проблема, не следует неразрешимость индивидуальных проблем.

По своей принципиальной значимости результат П. С. Новикова находится в одном ряду с классическими «отрицательными» результатами в математике, такими, как недоказуемость постулата Евклида о параллельных (следующая, например, из непротиворечивости геометрии Лобачевского) и неразрешимость в радикалах общих алгебраических уравнений пятой степени и выше.