Теорема о свободе

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ  ВПО

 Тульский  государственный педагогический  университет им. Л.Н. Толстого 
 
 
 

Курсовая  работа

на тему:

«Теорема о свободе» 
 

Выполнил:

студент 4 курса факультета

математики, физики и

информатики группы А

Захаренко А.В. 

Проверил:

д. ф.-м. наук, профессор 

Безверхний В. Н. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Тула 

2009 

Содержание 

 

 

1. Определение свободной группы

 

      Пусть нам дано множество элементов  S={s₁, … , s_n}, причем не предполагается, что число n конечно или даже счетно. Но когда это будет нам нужно, мы будем считать множество индексов i элементов s_i вполне упорядоченным. Введем символы – новый символ.

     Слово – это пустая (обозначается 1) или конечная последовательность a₁a₂…a_t, где каждый символ a_i есть один из символов 1,

     Слово называется редуцированным, если оно, либо пустое, либо в его записи a₁a₂…a_t нет ни одной пары рядом стоящих символов a_i,     a_i+1 (i=1, …, t-1) вида где .

     Два слова f₁ и f₂ будем называть соседними, если они имеют вид .

     Два слова  f  и g эквивалентны (обозначается ), если существует такая последовательность слов f₁=f, f₂, …, f_m=g, что слова f_i, f_i+1 – соседние при i=1, …, m-1. Ясно, что отношение рефлексивно, симметрично и транзитивно. Все слова, эквивалентные слову f, образуют класс эквивалентных слов, который мы обозначим через [f].

     Лемма 1.1. Любой класс содержит одно и только одно редуцированное слово.

     Доказательство. Если слово f=a₁…a_t содержит подслово    ,  то соседнее с ним слово a₁…a_i-1a_i+2…a_t состоит из меньшего числа символов. После не более чем t/2 шагов сокращения мы придем к редуцированному слову, эквивалентному слову f. Этим показано, что класс [f] содержит, по меньшей мере, одно редуцированное слово.

     Далее, исходя из слова f=a₁a₂…a_t, мы определяем следующую систему преобразований, которую назовем W-процессом:

W₀=1 – пустое слово,

W₁=a₁,

W_i+1=W_ia_i+1, если W_i не редуцированное слово вида,

W_i+1=X, если W_i – редуцированное слово вида.

Тогда, по индукции, легко видеть, что слова  W₀, W_1, …, W_t являются редуцированными и что W_t=f, если слово f редуцировано. Пусть теперь

f₁= a₁…a_ra_r+1…a_t ,

,

и пусть  обозначают слова W-процесса, примененного к f₁, а – соответствующие слова для слова f₂. Покажем, что      . Имеют места равенства , … , так как до r-го шага W-процессы совпадают. Дальше же возможны два случая.

1. Слово редуцированно и имеет вид . так как слово редуцированно, то слово X не может быть вида Y. Тогда для слова f₂ имеем , .
2. Слово редуцировано, но не имеет вида . Тогда  , .

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

     Мы  можем теперь определить произведение классов эквивалентных слов, относительно которого они будут образовывать группу. Мы назовем ее свободной  группой F, порожденной множеством S.

     Теорема 1.1. Для произвольной пары классов слов [f₁], [f₂] над множеством S определим произведение следующим образом: [f₁] [f₂]= [f₁ f₂]. Это произведение вполне определено, и относительно него классы эквивалентных слов над множеством S образуют группу – свободную группу F, порожденную множеством S.

     Доказательство. Если , , то . Действительно, сперва можно показать, что , заменяя последовательно соседними словами, ведущими от к . Аналогично доказывается, что , откуда следует, что , т. е. ]=[. Поэтому произведение [ зависит только от перемножаемых классов, но не от их представителей. При таком умножении класс, содержащий пустое слово, представляет собой единичный элемент, так как [1][f]=[f][1]=[f]. Кроме того, если f=a₁…a_t и , то [f][h]=[fh]=[1] и [h][f]=[hf]=[1]. Поэтому класс есть обратный класс для класса [a₁…a_t]. Далее мы обнаруживаем, что ([f₁] [f₂]) [f₃]= [f₁ f₂ f₃]= [f₁] ([f₂] [f₃]), т. е. ассоциативный закон выполняется. Таким образом, классы слов образуют группу, называемую свободной группой F, порожденной множеством S. Чтобы отметить последнее обстоятельство, эту свободную группу часто обозначают через F_S.

     Удобно  писать f₁=f₂, если слова f₁ и f₂ эквивалентны и, следовательно, представляют один и тот же элемент группы F. мы будем писать для обозначения равенства слов f₁ и f₂. Удобно в качестве представителя класса выбирать редуцированное слово. Если слово f=a₁…a_t редуцированное, то мы говорим, что оно редуцировано к этому виду.

     В произвольной группе G множество элементов X: x₁, …, x_n порождает подгруппу H, состоящую из всех конечных произведений b₁b₂…b_t, где каждый элемент b_j вида 1. Нетрудно проверить, что эти конечные произведения действительно образуют подгруппу. Вообще говоря, элемент подгруппы H может быть записан в виде указанного конечного произведения многими способами. Кроме того, очевидно, что все элементы группы G порождают группу G. Следовательно, произвольную группу G можно рассматривать как группу, порожденную некоторым множеством элементов X, при этом пишут G={X}. Следующая теорема показывает, почему свободные группы интересны не только сами по себе, но и как орудие исследования произвольных групп.

     Теорема 1.2. Пусть группа G порождается множеством элементов X: x₁, …, x_n, а F – свободная группа с образующими S:s₁, ..., s_n. Тогда существует гомоморфизм , определяемый отображениями для всех i.

     Доказательство. Пусть f=a₁…a_t – любое слово над множеством S. Рассмотрим элемент , где , если . Тогда отображение переводит каждое слово над множеством S в некоторый элемент группы G. Ясно, что соседние, а поэтому и эквивалентные слова над S отображаются в один и тот же элемент группы G. Следовательно отображение есть фактически отображение элементов свободной группы F на элементы группы G. При этом из того, что и следует, что . Значит, отображения определяют гомоморфизм свободной группы F на группу G.

     Следствие 1.1. Произвольная группа G с заданным множеством образующих Х изоморфна фактор-группе свободной группы F с таким же количеством образующих элементов.

     Дадим другое определение свободной группы.

     Определение 1.1. Свободная группа F, порожденная множеством элементов S, – это группа со следующими свойствами:

1. Группа F порождается множеством элементов S.
2. Если G – произвольная группа, порожденная множеством элементов Х, и если дано взаимно однозначное соответствие между множествами S и Х, , то существует гомоморфизм группы F на группу G, , продолжающий отображение S на множество Х.
 

2. Подгруппы свободных групп. Метод Шрейера 
   

     Природа подгрупп всегда играет фундаментальную  роль при изучении групп. Нильсен и Шрейер доказали, что подгруппы свободных групп сами свободны. Нильсен оперировал непосредственно элементами подгруппы, а Шрейер – смежными классами по подгруппе.

     Множество G элементов свободной группы F называется шрейеровской системой, если для любого элемента имеет место

1. – редуцированное слово,
2. слово также принадлежит G.

Множество G – двусторонняя шрейеровская система, если наряду с 1) и 2) имеет место следующее свойство:

3. Слово также принадлежит G.

     Заметим, что шрейеровская система всегда имеет единичный элемент.

     Пусть F – свободная группа, порожденная множеством S, U – ее подгруппа. Рассмотрим левое разложение группы F по подгруппе U:

.   (2.1)

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

     Лемма 2.1. (Обобщенная лемма Шрейера.) Если U – подгруппа свободной группы F, то в качестве системы представителей левых смежных классов по подгруппе U можно выбрать некоторую шрейеровскую систему. Если U – инвариантная подгруппа группы F, то может быть выбрана система представителей, образующая двустороннюю шрейеровскую систему.

     Доказательство. Пусть множество образующих S: группы F и обратных к ним элементов некоторым образом вполне упорядочено. Если число n конечно, это может быть сделано, например, так:    . Но здесь вовсе не предполагается, что множество S конечно или даже счетно; предполагается лишь, что множество может быть вполне упорядочено.

     Полное  упорядочение множества  может быть продолжено в лексикографическое упорядочение. А именно для двух элементов f и g группы F мы следующим образом определим отношение f<g, если редуцированные представления

     f=a₁…a_t ,

     g=b₁…b_u ,

<