Изменения
→Примеры: добавлено, что натуральные числа с нейтральным нулём -- не моноид
* множество натуральных чисел <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>1\langle \mathbb{N}, \cdot, 0 \rangle</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>
* [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 {{---}} Моноиды и их приложения: моноидальные вычисления в деревьях]
[[Категория:Теория групп]]
