Текущая версия |
Ваш текст |
Строка 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> | + | Рассмотрим конечный алфавит <math> \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} </math>. <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 \cup \Sigma^{-1} ; \; S = S_1 S_2 \dots S_k , \; символ a \in \Sigma \cup \Sigma^{-1} </math>. <br> |
| | | |
| {{Определение | | {{Определение |
| |definition= | | |definition= |
− | <tex>S</tex> и <tex>S'</tex> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <tex>aa^{-1}</tex> и <tex>a^{-1}a</tex>. | + | <math>S</math> и <math>S'</math> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <math>aa^{-1}</math> и <math>a^{-1}a</math>. |
| }} | | }} |
| | | |
− | Таким образом, <tex> \Sigma \cup \Sigma^{-1} </tex> с операцией конкатенации будет [[группа|группой]] (обратным элементом будет обращение строки с заменой всех символов на «обратные» им). | + | Таким образом, <math> \Sigma \cup \Sigma^{-1} </math> с операцией конкатенации будет группой (обратным элементом будет обращение строки с заменой всех символов на «обратные» им). |
| | | |
| {{Определение | | {{Определение |
| |definition= | | |definition= |
− | <tex> \Sigma \cup \Sigma^{-1} </tex> называется '''свободной группой, порожденной алфавитом <tex>\Sigma</tex>'''. | + | <math> \Sigma \cup \Sigma^{-1} </math> называется '''свободной группой, порожденной алфавитом <math>\Sigma</math>'''. |
| }} | | }} |
| | | |
| | | |
− | Рассмотрим строку. Проредуцируем её (будем последовательно удалять <tex>aa^{-1}</tex> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?'' | + | Рассмотрим строку. Проредуцируем её (будем последовательно удалять <math>aa^{-1}</math> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?'' |
| | | |
| {{Теорема | | {{Теорема |
− | |id=th5
| |
− | |about=О редуцированной строке
| |
| |statement= | | |statement= |
− | У одной строки существует лишь одна редуцированная строка. | + | У одной строки существует лишь одна редуцированная строка |
| |proof= | | |proof= |
− | Пусть существуют 2 проредуцированные строки <tex>\omega_1</tex> и <tex>\omega_2</tex>, заданные одной строкой. Тогда существуют цепочки вставок и удалений <br> | + | Пусть существуют 2 проредуцированные строки <math>\omega_1</math> и <math>\omega_2</math>, заданные одной строкой. Тогда существуют цепочки вставок и удалений <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> | + | <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> |
| | | |
− | Среди цепочек рассмотрим такую, у которой минимально <tex>\sum |S_i|</tex> и пусть <tex>S_i</tex> − строка наибольшей длины. <br> | + | Среди цепочек рассмотрим такую, у которой минимально <math>\sum |S_i|</math> и пусть <math>S_i</math> − строка наибольшей длины. <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> максимальна). Эти переходы могут быть обеспечены за счет: | + | Рассмотрим <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> максимальна). Эти переходы могут быть обеспечены за счет: |
− | # Двух непересекающихся пар. Тогда пусть <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> уменьшится, а это противоречит нашему предположению о минимальности суммы. | + | # Двух непересекающихся пар. Тогда пусть <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> уменьшится, а это противоречит нашему предположению о минимальности суммы. |
− | # Пар, пересекающихся по двум позициям. Тогда <tex>S_{i-1} = S_{i+1}</tex>, и можно избавиться от <tex>S_{i}</tex> и <tex>S_{i + 1}</tex>, и от этого сумма длин слов также уменьшится. | + | # Пар, пересекающихся по двум позициям. Тогда <math>S_{i-1} = S_{i+1}</math>, и можно избавиться от <math>S_{i}</math> и <math>S_{i + 1}</math>, и от этого сумма длин слов также уменьшится. |
− | # Пар, пересекающихся по одной позиции. Имеем <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>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>, что также уменьшит итоговую сумму длин строк. |
| Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему. | | Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему. |
| }} | | }} |
| | | |
| == Задание группы определяющими соотношениями == | | == Задание группы определяющими соотношениями == |
− | Пусть также имеем алфавит <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> и наоборот. | + | Пусть также имеем алфавит <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= | | |definition= |
− | Выражения <tex>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</tex> называются '''определяющими соотношениями'''. | + | Выражения <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math> называются '''определяющими соотношениями'''. |
| }} | | }} |
| | | |
Строка 49: |
Строка 49: |
| }} | | }} |
| | | |
− | ==Пример==
| |
− | Пусть группа <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>
| |
− |
| |
− | запишем таблицу умножения для <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>
| |
− | |}
| |
| [[Категория:Теория групп]] | | [[Категория:Теория групп]] |