Представление групп — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Свободная группа)
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 4 участников)
Строка 1: Строка 1:
{{В разработке}}
+
== Свободная группа ==
 +
Рассмотрим конечный алфавит <tex> \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} </tex>. <br>
 +
Рассмотрим множество строк над алфавитом <tex> \Sigma \cup \Sigma^{-1} ; \; S = s_1 s_2 \dots s_k , \; s_i \in \Sigma \cup \Sigma^{-1} </tex>. <br>
  
== Свободная группа ==
+
{{Определение
Рассмотрим конечный алфавит <math> \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} </math>. <br>
+
|definition=
Рассмотрим множество строк над алфавитом <math> \Sigma \cup \Sigma^{-1} ; \; S = S_1 S_2 \dots S_k , \; символ a \in \Sigma \cup \Sigma^{-1} </math>. <br>
+
<tex>S</tex> и <tex>S'</tex> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <tex>aa^{-1}</tex> и <tex>a^{-1}a</tex>.
 +
}}
 +
 
 +
Таким образом, <tex> \Sigma \cup \Sigma^{-1} </tex> с операцией конкатенации будет [[группа|группой]] (обратным элементом будет обращение строки с заменой всех символов на «обратные» им).
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<math>S</math> и <math>S'</math> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <math>aa^{-1}</math> и <math>a^{-1}a</math>.
+
<tex> \Sigma \cup \Sigma^{-1} </tex> называется '''свободной группой, порожденной алфавитом <tex>\Sigma</tex>'''.
 +
}}
 +
 
 +
 
 +
Рассмотрим строку. Проредуцируем её (будем последовательно удалять <tex>aa^{-1}</tex> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?''
 +
 
 +
{{Теорема
 +
|id=th5
 +
|about=О редуцированной строке
 +
|statement=
 +
У одной строки существует лишь одна редуцированная строка.
 +
|proof=
 +
Пусть существуют 2 проредуцированные строки <tex>\omega_1</tex> и <tex>\omega_2</tex>, заданные одной строкой. Тогда существуют цепочки вставок и удалений <br>
 +
<tex>\omega_1 \rightarrow S_1 \rightarrow S_2 \dots \rightarrow S_k \rightarrow \omega_2 </tex>, где <tex>\rightarrow</tex> − операция вставки или удаления <tex>aa^{-1}</tex>. (Существование цепочки обеспечено тем, что эти строки образованы одним элементом). <br>
 +
 
 +
Среди цепочек рассмотрим такую, у которой минимально <tex>\sum |S_i|</tex> и пусть <tex>S_i</tex> − строка наибольшей длины. <br>
 +
Рассмотрим <tex> S_{i - 1} \rightarrow S_i \rightarrow S_{i + 1} </tex>, причем мы знаем, что переходы от <tex>i</tex> к <tex>i - 1</tex> и <tex>i + 1</tex> обеспечены за счет удаления (из-за того, что длина <tex>S_i</tex> максимальна). Эти переходы могут быть обеспечены за счет:
 +
# Двух непересекающихся пар. Тогда пусть <tex> 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 </tex>, где <tex>L_1, L_2, L_3</tex> − некие строки. <br>Таким образом, у нас есть часть цепочки <tex>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 </tex>.  Заменим эту часть цепочки на <tex>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 </tex>. Заметим, что крайние значения части цепочки от этого не изменятся, но <tex>\sum |S_i|</tex> уменьшится, а это противоречит нашему предположению о минимальности суммы.
 +
# Пар, пересекающихся по двум позициям. Тогда <tex>S_{i-1} = S_{i+1}</tex>, и можно избавиться от <tex>S_{i}</tex> и <tex>S_{i + 1}</tex>, и от этого сумма длин слов также уменьшится.
 +
# Пар, пересекающихся по одной позиции. Имеем <tex>L_1 a L_2 \rightarrow L_1 a a^{-1} a L_2 \rightarrow L_1 a L_2</tex>, и в этом случае мы также можем избавиться от <tex>S_{i}</tex> и <tex>S_{i + 1}</tex>, что также уменьшит итоговую сумму длин строк.
 +
Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему.
 
}}
 
}}
  
Таким образом, <math> \Sigma \cup \Sigma^{-1} </math> с операцией конкатенации будет группой (обратным элементом будет обращение строки с заменой всех символов на «обратные» им).
+
== Задание группы определяющими соотношениями ==
 +
Пусть также имеем алфавит <tex>\Sigma = \{ a_1, \dots a_n \} </tex> и набор пар строк <tex>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</tex>. Разрешается где угодно менять <tex>\omega_i</tex> на <tex>S_i</tex> и наоборот.  
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<math> \Sigma \cup \Sigma^{-1} </math> называется '''свободной группой, порожденной алфавитом <math>\Sigma</math>'''.
+
Выражения <tex>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</tex> называются '''определяющими соотношениями'''.
 
}}
 
}}
  
 +
{{Утверждение
 +
|about=без доказательства
 +
|statement=
 +
Задача проверки эквивалентности строк при заданных определяющих соотношениях алгоритмически неразрешима.
 +
}}
 +
 +
==Пример==
 +
Пусть группа <tex>G</tex> задана соотношениями <tex>G=\{a</tex>, <tex>b|aba=b</tex>, <tex>bab=a\}</tex>. Докажем что:
 +
 +
#<tex>a^2=b^2</tex>
 +
#<tex>a^4=b^4=e</tex>
 +
#<tex>|G|=8</tex>
 +
 +
'''Доказательство:'''
 +
 +
1) <tex>aba=b \Rightarrow a(bab)=bb</tex> подставляем из второго условия группы и получаем: <tex> aa=bb \Rightarrow a^2=b^2</tex>
 +
 +
2) <tex>aba=b \Rightarrow ba=a^{-1}b</tex>, <tex>bab=a \Rightarrow ab=b^{-1}a</tex>, перемножаем, получаем:<tex>abba=e</tex>, но из доказанного ранее <tex>a^2=b^2 \Rightarrow a^4=e</tex> и <tex>b^4=e</tex>
 +
 +
3)Рассмотрим все последовательности из <tex>3</tex> элементов: их <tex>8</tex>. Заметим, что есть последовательности из трех одинаковых элементов: <tex>(ааа</tex>, <tex>bbb)</tex>, из <tex>2</tex> подряд идущих одинаковых и одного отличного<tex>(aab</tex>, <tex>bba</tex>, <tex>baa</tex>, <tex>abb)</tex> и <tex>aba</tex>, <tex>bab</tex>. Но <tex>b^2=a^2</tex>, поэтому <tex>aab=baa=b^3</tex>, <tex>bba=abb=a^3</tex>, а <tex>aba=b</tex>, <tex>bab=a</tex>, поэтому все тройки равны либо третьей либо первой степени <tex>a</tex> или <tex>b</tex>. Из таблицы умножения(приведена далее) видно, что произведения приведенной далее видно, что произведение последовательности длинное три(те <tex>a^3</tex>,<tex>b^3</tex>, <tex>a</tex>, <tex>b</tex>) не выходит за ее пределы. Те последовательность большей длинны по правилам умножения, задания <tex>G</tex> и доказанных равенств будет сокращаться до последовательности длины <tex><=2</tex> или <tex>a^3</tex> или <tex>b^3 \Rightarrow |G|=8</tex>
  
Рассмотрим строку. Проредуцируем её (будем последовательно удалять <math>aa^{-1}</math> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?''
+
запишем таблицу умножения для <tex>G</tex>:
  
 +
{| border="2" cellpadding="8" align="center"
 +
!style="background:#efefef;"| *
 +
!style="background:#efefef;"| <big>e</big>
 +
!style="background:#efefef;"| <big>a</big>
 +
!style="background:#efefef;"| <big>b</big>
 +
!style="background:#efefef;"| <big>ab</big>
 +
!style="background:#efefef;"| <big>ba</big>
 +
!style="background:#efefef;"| <big>aa</big>
 +
!style="background:#efefef;"| <big>aaa</big>
 +
!style="background:#efefef;"| <big>bbb</big>
 +
|-
 +
!style="background:#efefef;"| <big>e</big>
 +
| <big>e</big> || <big>a</big> || <big>b</big> || <big>ab</big> || <big>ba</big> || <big>aa</big> || <big>aaa</big> || <big>bbb</big>   
 +
|-
 +
!style="background:#efefef;"| <big>a
 +
| <big>a</big> || <big>aa</big> || <big>ab</big> || <big>bbb</big> || <big>b</big> || <big>aaa</big> || <big>e</big> || <big>ba</big>
 +
|-
 +
!style="background:#efefef;"| <big>b
 +
| <big>b</big> || <big>ba</big> || <big>aa</big> || <big>a</big> || <big>ab</big> || <big>bbb</big> || <big>ab</big> || <big>e</big>
 +
|-
 +
!style="background:#efefef;"| <big>ab
 +
| <big>ab</big> || <big>b</big> || <big>aaa</big> || <big>aa</big> || <big>e</big> || <big>ba</big> || <big>bbb</big> || <big>a</big>
 +
|-
 +
!style="background:#efefef;"| <big>ba</big>
 +
| <big>ba</big> || <big>bbb</big> || <big>a</big> || <big>e</big> || <big>bb</big> || <big>ab</big> || <big>b</big> || <big>aaa</big>
 +
|-
 +
!style="background:#efefef;"| <big>aa</big>
 +
| <big>aa</big> || <big>aaa</big> || <big>bbb</big> || <big>ba</big> ||  <big>ab</big> || <big>e</big> || <big>a</big> || <big>b</big>
 +
|-
 +
!style="background:#efefef;"| <big>aaa</big>
 +
| <big>aaa</big> || <big>e</big> || <big>ba</big> || <big>b</big> || <big>bbb</big> || <big>a</big> || <big>aa</big> || <big>ab</big>
 +
|-
 +
!style="background:#efefef;"| <big>bbb</big>
 +
| <big>bbb</big> || <big>ab</big> || <big>e</big> || <big>aaa</big> || <big>a</big> || <big>b</big> || <big>ba</big> || <big>bb</big>
 +
|}
 
[[Категория:Теория групп]]
 
[[Категория:Теория групп]]

Текущая версия на 19:38, 4 сентября 2022

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

Рассмотрим конечный алфавит [math] \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} [/math].
Рассмотрим множество строк над алфавитом [math] \Sigma \cup \Sigma^{-1} ; \; S = s_1 s_2 \dots s_k , \; s_i \in \Sigma \cup \Sigma^{-1} [/math].


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


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


Определение:
[math] \Sigma \cup \Sigma^{-1} [/math] называется свободной группой, порожденной алфавитом [math]\Sigma[/math].


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

Теорема (О редуцированной строке):
У одной строки существует лишь одна редуцированная строка.
Доказательство:
[math]\triangleright[/math]

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

Среди цепочек рассмотрим такую, у которой минимально [math]\sum |S_i|[/math] и пусть [math]S_i[/math] − строка наибольшей длины.
Рассмотрим [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] максимальна). Эти переходы могут быть обеспечены за счет:

  1. Двух непересекающихся пар. Тогда пусть [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] − некие строки.
    Таким образом, у нас есть часть цепочки [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] уменьшится, а это противоречит нашему предположению о минимальности суммы.
  2. Пар, пересекающихся по двум позициям. Тогда [math]S_{i-1} = S_{i+1}[/math], и можно избавиться от [math]S_{i}[/math] и [math]S_{i + 1}[/math], и от этого сумма длин слов также уменьшится.
  3. Пар, пересекающихся по одной позиции. Имеем [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]\triangleleft[/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] и наоборот.


Определение:
Выражения [math]S_1 \sim \omega_1, \dots, S_n \sim \omega_n[/math] называются определяющими соотношениями.


Утверждение (без доказательства):
Задача проверки эквивалентности строк при заданных определяющих соотношениях алгоритмически неразрешима.

Пример

Пусть группа [math]G[/math] задана соотношениями [math]G=\{a[/math], [math]b|aba=b[/math], [math]bab=a\}[/math]. Докажем что:

  1. [math]a^2=b^2[/math]
  2. [math]a^4=b^4=e[/math]
  3. [math]|G|=8[/math]

Доказательство:

1) [math]aba=b \Rightarrow a(bab)=bb[/math] подставляем из второго условия группы и получаем: [math] aa=bb \Rightarrow a^2=b^2[/math]

2) [math]aba=b \Rightarrow ba=a^{-1}b[/math], [math]bab=a \Rightarrow ab=b^{-1}a[/math], перемножаем, получаем:[math]abba=e[/math], но из доказанного ранее [math]a^2=b^2 \Rightarrow a^4=e[/math] и [math]b^4=e[/math]

3)Рассмотрим все последовательности из [math]3[/math] элементов: их [math]8[/math]. Заметим, что есть последовательности из трех одинаковых элементов: [math](ааа[/math], [math]bbb)[/math], из [math]2[/math] подряд идущих одинаковых и одного отличного[math](aab[/math], [math]bba[/math], [math]baa[/math], [math]abb)[/math] и [math]aba[/math], [math]bab[/math]. Но [math]b^2=a^2[/math], поэтому [math]aab=baa=b^3[/math], [math]bba=abb=a^3[/math], а [math]aba=b[/math], [math]bab=a[/math], поэтому все тройки равны либо третьей либо первой степени [math]a[/math] или [math]b[/math]. Из таблицы умножения(приведена далее) видно, что произведения приведенной далее видно, что произведение последовательности длинное три(те [math]a^3[/math],[math]b^3[/math], [math]a[/math], [math]b[/math]) не выходит за ее пределы. Те последовательность большей длинны по правилам умножения, задания [math]G[/math] и доказанных равенств будет сокращаться до последовательности длины [math]\lt =2[/math] или [math]a^3[/math] или [math]b^3 \Rightarrow |G|=8[/math]

запишем таблицу умножения для [math]G[/math]:

* e a b ab ba aa aaa bbb
e e a b ab ba aa aaa bbb
a a aa ab bbb b aaa e ba
b b ba aa a ab bbb ab e
ab ab b aaa aa e ba bbb a
ba ba bbb a e bb ab b aaa
aa aa aaa bbb ba ab e a b
aaa aaa e ba b bbb a aa ab
bbb bbb ab e aaa a b ba bb