Просмотр исходного текста страницы Представление групп

{{В разработке}}

== Свободная группа ==
Рассмотрим конечный алфавит <math> \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} </math>. <br>
Рассмотрим множество строк над алфавитом <math> \Sigma \cup \Sigma^{-1} ; \; S = S_1 S_2 \dots S_k , \; символ a \in \Sigma \cup \Sigma^{-1} </math>. <br>

{{Определение
|definition=
<math>S</math> и <math>S'</math> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <math>aa^{-1}</math> и <math>a^{-1}a</math>.
}}

Таким образом, <math> \Sigma \cup \Sigma^{-1} </math> с операцией конкатенации будет группой (обратным элементом будет обращение строки с заменой всех символов на «обратные» им).

{{Определение
|definition=
<math> \Sigma \cup \Sigma^{-1} </math> называется '''свободной группой, порожденной алфавитом <math>\Sigma</math>'''.
}}


Рассмотрим строку. Проредуцируем её (будем последовательно удалять <math>aa^{-1}</math> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?''

{{Теорема
|statement=
У одной строки существует лишь одна редуцированная строка
|proof=
Пусть существуют 2 проредуцированные строки <math>\omega_1</math> и <math>\omega_2</math>, заданные одной строкой. Тогда существуют цепочки вставок и удалений <br>
<math>\omega_1 \rightarrow S_1 \rightarrow S_2 \dots \rightarrow S_k \rightarrow \omega_2 </math>, где <math>\rightarrow</math> − операция вставки или удаления <math>aa^{-1}</math>. (Существование цепочки обеспечено тем, что эти строки образованы одним элементом). <br>

Среди цепочек рассмотрим такую, у которой минимально <math>\sum |S_i|</math> и пусть <math>S_i</math> − строка наибольшей длины. <br>
Рассмотрим <math> S_{i - 1} \rightarrow S_i \rightarrow S_{i + 1} </math>, причем мы знаем, что переходы от <math>i</math> к <math>i - 1</math> и <math>i + 1</math> обеспечены за счет удаления (из-за того, что длина <math>S_i</math> максимальна). Эти переходы могут быть обеспечены за счет:
# Двух непересекающихся пар. Тогда пусть <math> S_{i - 1} = L_1 L_2 b b^{-1} L_3, \quad S_i = L_1 a a^{-1} L_2 b b^{-1} L_3, \quad S_{i + 1} = L_1 a a^{-1} L_2 L_3 </math>, где <math>L_1, L_2, L_3</math> − некие строки. <br>Таким образом, у нас есть часть цепочки <math>L_1 L_2 b b^{-1} L_3 \rightarrow L_1 a a^{-1} L_2 b b^{-1} L_3 \rightarrow L_1 a a^{-1} L_2 L_3 </math>.  Заменим эту часть цепочки на <math>L_1 L_2 b b^{-1} L_3 \rightarrow L_1 L_2 L_3 \rightarrow L_1 a a^{-1} L_2 L_3 </math>. Заметим, что крайние значения части цепочки от этого не изменятся, но <math>\sum |S_i|</math> уменьшится, а это противоречит нашему предположению о минимальности суммы.
# Пар, пересекающихся по двум позициям. Тогда <math>S_{i-1} = S_{i+1}</math>, и можно избавиться от <math>S_{i}</math> и <math>S_{i + 1}</math>, и от этого сумма длин слов также уменьшится.
# Пар, пересекающихся по одной позиции. Имеем <math>L_1 a L_2 \rightarrow L_1 a a^{-1} a L_2 \rightarrow L_1 a L_2</math>, и в этом случае мы также можем избавиться от <math>S_{i}</math> и <math>S_{i + 1}</math>, что также уменьшит итоговую сумму длин строк.
Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему.
}}

== Задание группы определяющими соотношениями ==
Пусть также имеем алфавит <math>\Sigma = \{ a_1, \dots a_n \} </math> и набор пар строк <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math>. Разрешается где угодно менять <math>\omega_i</math> на <math>S_i</math> и наоборот. 

{{Определение
|definition=
Выражения <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math> называются '''определяющими соотношениями'''.
}}

{{Утверждение
|about=без доказательства
|statement=
Задача проверки эквивалентности строк при заданных определяющих соотношениях алгоритмически неразрешима.
}}

[[Категория:Теория групп]]