1632
правки
Изменения
Моноид
,rollbackEdits.php mass rollback
{{Определение
|definition=
: <tex> \forall x\in G : \varepsilon\cdot x=x \cdot \varepsilon = x</tex>. Иногда его обозначают <tex> \varepsilon_G </tex>, или <tex>e_G </tex>.
}}
Другими словами, моноид {{---}} это [[Полугруппа|полугруппа]], в которую добавлен нейтральный элемент. Например, == Примеры == * множество натуральных чисел <tex> \mathbb{N} </tex> с операцией сложения не является моноидом<tex>\langle \mathbb{N}, +, 0 \rangle</tex>* множество положительных целых <tex> \mathbb{Z}_+ </tex> с операцией умножения является моноидом <tex>\langle\mathbb{Z}_+, \cdot, а 1 \rangle</tex>* множество натуральных числел с операцией умножения является моноидом <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex> (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, как того и требует аксиома нейтрального элемента), но тройка <tex>\langle \mathbb{N}, \cdot, 0 \rangle</tex> моноидом уже не является. == Свойства ==
{{Утверждение
}}
== Гомоморфизм моноидов ==
{{Определение
|id = defmonhom
|definition=
'''Свободным моноидомГомоморфизмом моноидов''' (англ. ''free monoidhomomorphism'') <tex> \langle M , \cdot_M, \varepsilon_M \rangle </tex> над множеством и <tex> S \langle N, \cdot_N, \varepsilon_N \rangle </tex> называется отображение <tex>(\varphi \colon M \rightarrow N</tex>обозначается как совместимое с операциями из <tex> M_S )M </tex> называется моноид над множеством и <tex> N </tex> S^, то есть такое, что: * <tex>\varphi(\varepsilon_M) = \varepsilon_N</tex> {{---}} набором всевозможных элементов, полученных конечным числом применений ассоциативной операции и операции сокращения нейтрального элемента к элементам множества * <tex>S\forall x, y \in M \colon \varphi(x\cdot_M y) = \varphi(x) \cdot_N \varphi(y)</tex>.
}}
{{Определение
|definition=
}}
Введём дополнительное определение, чтобы привести пример моноида, не являющегося свободным.
{{Определение
|definition=
'''Моноидом с порождающими соотношениями''' (англ. ''equational presentation of monoid'') называется моноид, на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.
}}
Примером такого моноида является множество <tex> G </tex> всевозможных строк над алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> ba </tex> в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это.
{{Теорема
|statement= Моноид <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex> не является свободным
|proof=
Для начала покажем, что каждый элемент такого моноида можно представить в виде <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> a^i b^j </tex> и <tex> a^k b^t </tex> аналогична операции конкатенации строк, только после её применения строку надо привести к виду <tex> a^{i + k} b^{j + t} </tex>, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]].
Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множеством <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \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) ~\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>.
[[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) ~\texttt{++}~ 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 = \Sigma^{*}_{/ab = ba} </tex> является свободным.
Равенство <tex> f(ab) = f(ba) </tex> может сохранять изоморфизм, если <tex> f(a) = [] </tex>, но тогда <tex> f(a) = f(aa) </tex>, что опять же приводит нас к противоречию.
}}
== См. также ==
* [[Изоморфизм групп]]
== Ссылки Источники информации ==* [[wikipedia:Monoid | Wikipedia {{---}} Monoid ]]* [[wikipedia:ru:Моноид | Википедия {{---}} Моноид ]]
* [[wikipedia:Free_monoid | Wikipedia {{---}} Free monoid ]]
* [http://ncatlab.org/nlab/show/free+monoid nLab {{---}} Free Monoid]
* [http://www.proofwiki.org/wiki/Definition:Free_Monoid Proof Wiki {{---}} Free monoid]
* [http://habrahabr.ru/post/112394/ Habrahabr {{---}} Моноиды и их приложения: моноидальные вычисления в деревьях]
[[Категория:Теория групп]]