Изменения

* Бинарная операция <tex>\cdot</tex> — определена везде и [[Ассоциативность Ассоциативная операция | ''ассоциативна'']].

== Примеры:==

* множество натуральных числел '''не''' с операцией умножения является моноидом по умножению <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex>, так как (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, а не как того и требует аксиома нейтрального элемента), но тройка <tex>1\langle \mathbb{N}, \cdot, 0 \rangle</tex>, как того требует аксиома нейтрального элементамоноидом уже не является. == Свойства ==

'''Гомоморфизмом моноидов''' (англ. ''monoid homomorphism'') <tex>\langle M, \cdot_M, \varepsilon_M \rangle </tex> и <tex>\langle N, \cdot_N, \varepsilon_N \rangle </tex> называется отображение <tex>\varphi \colon M \rightarrow N</tex> совместимое с операциями из <tex> M </tex> и <tex> N </tex> , то есть такое, что : * <tex>\varphi(\varepsilon_M) = \varepsilon_N</tex>* <tex> \forall mx, m' y \in M \colon \varphi(mx\cdot m'cdot_M y) = \varphi(mx) \cdot cdot_N \varphi(ny)</tex>, а также <tex>\varphi(\varepsilon_M) = \varepsilon_N</tex>.

'''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> '''над множеством ''' <tex> S </tex> <tex>(</tex>обозначается как <tex> M_S )</tex> называется моноид над множеством <tex> S^* </tex> {{---}} набором всевозможных последовательностей (или списков) конечной длины (в том числе и нулевой), образованных из элементов множества <tex> S </tex> {{---}} с ассоциативной операцией [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#defconcat|конкатенации]] <tex>\texttt{++}</tex> этих последовательностей.

* <tex> S = \{1\} </tex>. Тогда <tex>S^* = \{[], [1], [1, 1], ... \} </tex>. Такой моноид с введённой на нём операцией сложения как объединением списков, [[Изоморфизм групп | изоморфен]] моноиду натуральных чисел.

В более общем смысле, некоторый == Свободный моноид (или полугруппа) определяется как == {{Определение|definition=Моноид <tex>M</tex> называется '''свободныйсвободным''', если они он [[Изоморфизм групп | изоморфен ]] некоторому свободному моноиду (полугруппе) над каким-то множеством.}}=== Примеры свободного моноида === * <tex>\langle \mathbb{N}, +, 0 \rangle </tex> {{---}} пример свободного моноида, так как он изоморфен свободному моноиду над <tex>S = \{1\}</tex>: ** <tex>i(0) = []</tex>** <tex>i(a + b) = i(a) ~ \texttt{++} ~ i(b)</tex> == Моноид с порождающими соотношениями ==

'''Моноидом с порождающими отношениямисоотношениями''' (англ. ''equational presentation of monoid'') называется моноид, на котором введены дополнительные правила(то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.

Для начала покажем, что каждый элемент такого моноида можно представить в виде <tex> a^i b^j, i \geqslant 0, j \geqslant 0 </tex>. Докажем это конструктивно. Возьмём произвольную строку и будем в ней заменять все подстроки вида <tex> ba </tex> на подстроки <tex> ab </tex>. Если таких подстрок нет, то наша строка имеет вид <tex> a^i b^j </tex>, а если есть, то строка за конечное число шагов приведётся к указанному виду, потому что операцию замены <tex> ba </tex> на <tex> ab </tex> можно рассматривать, как уменьшения числа инверсий в последовательности, а их точно конечное число, так как все последовательности имеют конечную длину.

Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду '''Замечание''': конкатенация двух последовательностей <tex> a^i b^j </tex> и <tex> M_S a^k b^t </tex>аналогична операции конкатенации строк, то есть существует биективное отображение только после её применения строку надо привести к виду <tex> f : G \to M_S a^{i + k} b^{j + t} </tex>. Оно сохраняет ассоциативность операций, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]].

Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множеством <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \to M_S </tex>. Оно сохраняет ассоциативность операций, поэтому  <tex> f(ab) = f(a) ~\cdot texttt{++}~ f(b) </tex>

<tex> f(ba) = f(b) ~\cdot texttt{++}~ f(a) </tex> Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\texttt{++}~ f(b) = f(b) ~\texttt{++}~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у последовательности <tex> f(a) ~\texttt{++}~ f(b) </tex> есть два [[Период и бордер, их связь | бордера]] длин <tex> m </tex> и <tex> n </tex> соответственно, значит, она периодическая и имеет период равный <tex>\gcd(n, m)</tex>.

Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) \cdot f(b) = f(b) \cdot f(a) = f(ba) </tex>. Равенство этих последовательностей означает, что у строки <tex> f(a) \cdot f(b) </tex> есть [[Период и бордер, их связь File:FreeMonoidConcatExample.png| бордер300px]], а значит, она периодическая.

TODO: картинкаИз этого следует, которая объяснит все равенствачто последовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину <tex>\gcd(n, m)</tex>.

<tex> f(ab) = \overbrace{s ~\cdot texttt{++}~ s ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ s}^{pq} , s \in M_S </tex>

Пусть <tex> f(b) = \overbracemathrm{s \cdot s \cdot ... \cdot slcm}^{(p, q} , s \in M_S ) = l</tex>, тогда

Пусть НОК<texdpi>\overbrace{f(a) ~\texttt{++}~ f(a) ~\texttt{++}~ ... ~\texttt{++}~ f(a)}^{l / p, q) } = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} </tex>, тогда

<tex dpi = 140> \overbrace{f(ab) ~\cdot texttt{++}~ f(ab) ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ f(ab)}^{\frac{l}{p}/ q} = \overbrace{s ~\cdot texttt{++}~ s ~\cdot texttt{++}~ ... ~\cdot texttt{++}~ s}^{l} </tex>

Откуда следует, что <tex dpi = 140> \overbracea^{f(b) \cdot f(l / p} = b) \cdot ... \cdot f(b)}^{\frac{l}{/ q}} </tex>, то есть отображение <tex> f </tex> не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид <tex dpi = 130> G = \overbraceSigma^{s \cdot s \cdot ... \cdot s*}^_{l/ab = ba} </tex> является свободным.

Откуда следует, что Равенство <tex dpi = 140> a^{\frac{l}{p}} f(ab) = b^{\frac{l}{q}} f(ba) </tex>может сохранять изоморфизм, то есть отображение если <tex> f (a) = [] </tex> не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид но тогда <tex dpi = 130> G f(a) = \Sigma^{*}_{/ab = ba} f(aa) </tex> является свободным, что опять же приводит нас к противоречию.

== Ссылки Источники информации ==