Изменения

Другими словами, моноид {{---}} это [[Полугруппа|полугруппа]], в которую добавлен нейтральный элемент. Например, множество натуральных чисел <tex> \mathbb{N} </tex> с операцией сложения не является моноидом, а с операцией умножения является.

'''Свободным моноидомГомоморфизмом моноидов''' (англ. ''free monoidhomomorphism'') <tex> M </tex> над множеством и <tex> S N</tex> называется отображение <tex>\varphi \colon M \rightarrow N</tex>(совместимое с операциями из <tex> M </tex>обозначается как и <tex> M_S )N </tex> называется моноид над множеством такое, что <tex> S^* \forall m, m' \in M \colon \varphi(m\cdot m') = \varphi(m) \cdot \varphi(n)</tex> {{---}} набором всевозможных элементов, полученных конечным числом применений ассоциативной операции и операции сокращения нейтрального элемента к элементам множества а также <tex>S\varphi(\varepsilon_M) = \varepsilon_N</tex>.

* тривиальный пример: множество {{Определение|definition='''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> над множеством <tex> S = \{\varnothing\} </tex> и операция <tex> \cup (</tex>обозначается как <tex> M_S )</tex>. Тогда называется моноид над множеством <tex> S^* = \</tex> {{\varnothing\---}} набором всевозможных последовательностей (или списков) конечной длины (в том числе и нулевой), образованных из элементов множества <tex> S </tex>{{---}} с ассоциативной операцией [[Основные определения: алфавит, чтослово, очевидноязык, является моноидом с операцией конкатенация, свободный моноид слов; операции над языками#defconcat|конкатенации]] этих последовательностей.}} * тривиальный пример: множество <tex> S = \varnothing </tex>. Тогда <tex>S^* = \{\cupvarnothing\} </tex>.* <tex> S = \{0, 1\} </tex>, операция {{---}} сложение. Тогда <tex>S^* = \mathbb{N[], [1], [1, 1], ... \}</tex>, так . Такой моноид с введённой на нём операцией сложения как любое натуральное число является либо нулемобъединением списков, либо суммой конечного числа единиц* контрпример: TODO[[Изоморфизм групп | изоморфен]] моноиду натуральных чисел.

Дадим теперь В более формальное определениеобщем смысле, некоторый моноид (или полугруппа) определяется как '''свободный''', если они изоморфен свободному моноиду (полугруппе) над каким-то множеством.

'''Свободным моноидомМоноидом с порождающими отношениями''' (англ. ''equational presentation of monoid'' над множеством <tex> S </tex> ) называется моноид <tex> M </tex> вместе с отображением <tex> i\colon S \rightarrow M </tex> при условии, что для любого на котором введены дополнительные правила, отождествляющие некоторые элементы моноида <tex> N </tex> и для любых отображений <tex> f \colon S \rightarrow N </tex> существует уникальный [[Гомоморфизм групп | гомоморфизм]] моноидов <tex> \overline{f} \colon M_S \rightarrow N </tex> такой, что <tex> \overline{f} \circ i = f </tex>.

Это наглядно показано следующей картинкойПримером такого моноида является множество <tex> G </tex> всевозможных строк над алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> ba </tex> в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это.

[[Файл:FreeMonoidDefinition2{{Теорема |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> ba </tex> на <tex> ab </tex> можно рассматривать, как уменьшения числа инверсий в последовательности, а их точно конечное число, так как все последовательности имеют конечную длину.jpg|200px]]