Изменения

[[Полугруппа]] Кортеж <tex>\langle G,\cdot: G \times G \to G, \varepsilon \in G \rangle</tex> называется [[моноид|моноидом]], если в множестве он удовлетворяет следующим аксиомам:* Бинарная операция <tex>\cdot</tex>G— определена везде и [[Ассоциативная операция | ''ассоциативна'']].* <tex>\varepsilon</tex> называется нейтральным элементом относительно <tex>\cdot</tex> существует элемент, нейтральный относительно операции полугруппыто есть для него выполняется::<tex>\exists e\in G : \forall x\in G : e\varepsilon\cdot x=x \cdot e\varepsilon =x</tex>. Иногда его обозначают <tex> \varepsilon_G </tex>, или <tex> e_G </tex>.

Действительно, путь пусть <tex>e_1\varepsilon_1</tex> и <tex>e_2\varepsilon_2</tex> {{---}} два нейтральных элемента. Тогда имеем: <tex>e_1 \varepsilon_1 = e_1\varepsilon_1\cdot e_2 \varepsilon_2 = \varepsilon_2</tex>.}} == Гомоморфизм моноидов =={{Определение|id = defmonhom|definition='''Гомоморфизмом моноидов''' (англ. ''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 x, y \in M \colon \varphi(x\cdot_M y) = \varphi(x) \cdot_N \varphi(y)</tex>}} = e_2= Свободный моноид над множеством == {{Определение|definition='''Свободным моноидом''' (англ. ''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 = \varnothing </tex>. Тогда <tex> S^* = \mathbb{R\varnothing\}</tex> c операцией умножения или сложения (нейтральными элементами являются 1 и 0 соответственно).* Множество [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|строк]] из <tex> S = \Sigma^* {1\} </tex> с операцией конкатенацией и нейтральным элементом {{---}} пустой строкой (обозначаемой . Тогда <tex>S^* = \varepsilon{[], [1], [1, 1], ... \} </tex>). == Свободный моноид == 

'''Гомоморфизмом моноидов''' (англ. ''monoid homomorphism'') Моноид <tex>M</tex> и <tex>N</tex> называется отображение <tex>\varphi \colon M \rightarrow N</tex> совместимое с операциями из <tex> M </tex> и <tex> N </tex> такое, что <tex> \forall m, m' \in M \colon \varphi(m\cdot m') = \varphi(m) \cdot \varphi(n)</tex>'свободным''', а также <tex>\varphi(e_M) = e_N</tex>если он [[Изоморфизм групп | изоморфен]] некоторому свободному моноиду над каким-то множеством.

'''Свободным моноидомМоноидом с порождающими соотношениями''' (англ. ''free equational presentation of monoid'') называется моноид, на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.}}Примером такого моноида является множество <tex> G </tex> всевозможных строк над множеством алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> S ba </tex> называется в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это. {{Теорема |statement= Моноид <texdpi = 130> M G = \Sigma^{*}_{/ab = ba} </tex> вместе с отображением не является свободным|proof=Для начала покажем, что каждый элемент такого моноида можно представить в виде <tex> a^i b^j, i\colon S geqslant 0, j \rightarrow M geqslant 0 </tex> при условии. Докажем это конструктивно. Возьмём произвольную строку и будем в ней заменять все подстроки вида <tex> ba </tex> на подстроки <tex> ab </tex>. Если таких подстрок нет, то наша строка имеет вид <tex> a^i b^j </tex>, а если есть, то строка за конечное число шагов приведётся к указанному виду. '''Замечание''': конкатенация двух последовательностей <tex> a^i b^j </tex> и <tex> a^k b^t </tex> аналогична операции конкатенации строк, только после её применения строку надо привести к виду <tex> a^{i + k} b^{j + t} </tex>, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]]. Предположим, что данный моноид свободный. Это значит, что для любого моноида он изоморфен какому-то свободному моноиду над множеством <tex> N M_S </tex> и для любых отображений , то есть существует биективное отображение <tex> f \colon S G \rightarrow N to M_S </tex> существует единственный гомоморфизм моноидов . Оно сохраняет ассоциативность операций, поэтому  <tex> f(ab) = f(a) ~\texttt{++}~ f(b) </tex> <tex> f(ba) = f(b) ~\texttt{++}~ f(a) </tex> Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\overlinetexttt{++}~ f(b) = f(b) ~\texttt{++} ~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у последовательности <tex> f(a) ~\colon Mtexttt{++}~ f(Sb) </tex> есть два [[Период и бордер, их связь | бордера]] длин <tex> m </tex> и <tex> n </tex> соответственно, значит, она периодическая и имеет период равный <tex>\rightarrow N gcd(n, m)</tex> такой. [[File:FreeMonoidConcatExample.png|300px]] Из этого следует, что последовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину <tex>\gcd(n, m)</tex>. <tex> f(a) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{p} </tex> <tex> f(b) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{q} , s \in M_S </tex> Пусть <tex>\mathrm{lcm}(p, q) = l</tex>, тогда <tex dpi> \overbrace{f(a) ~\texttt{++}~ f(a) ~\texttt{++}~ ... ~\texttt{++}~ f(a)}^{l / p} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} </tex>  <tex dpi> \overbrace{f(b) ~\overlinetexttt{++}~ f(b) ~\texttt{++}~ ... ~\texttt{++}~ f(b)}^{l / q} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} </tex>  Откуда следует, что <tex dpi = 140> a^{l / p} = b^{l / q} </tex>, то есть отображение <tex> f </tex> не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид <tex dpi = 130> G = \circ i Sigma^{*}_{/ab = ba} </tex> является свободным. Равенство <tex> f(ab) = f(ba) </tex> может сохранять изоморфизм, если <tex> f(a) = [] </tex>, но тогда <tex> f(a) = f (aa) </tex>, что опять же приводит нас к противоречию.

Если <tex> S <== См. также ==* [[Группа]]* [[Изоморфизм групп]]  == Источники информации ==* [[wikipedia:Monoid | Wikipedia {{---}} Monoid ]]* [[wikipedia:ru:Моноид | Википедия {{---}} Моноид ]]* [[wikipedia:Free_monoid | Wikipedia {{---}} Free monoid ]]* [http://ncatlab.org/nlab/show/tex> является подмножеством <tex> M <free+monoid nLab {{---}} Free Monoid]* [http:/tex>, то отображение <tex> i </tex> называют '''естественным вложением''' (англwww.proofwiki. ''natural injection''), и пишут <tex> i \colon S \hookrightarrow M <org/wiki/Definition:Free_Monoid Proof Wiki {{---}} Free monoid]* [http://tex>habrahabr.ru/post/112394/ Habrahabr {{---}} Моноиды и их приложения: моноидальные вычисления в деревьях] [[Категория: АлгебраТеория групп]]