Моноид

Определение:

Полугруппа [math]\langle G,\cdot\rangle[/math] называется моноидом, если в множестве [math]G[/math] существует элемент, нейтральный относительно операции полугруппы: [math]\exists e\in G : \forall x\in G : e\cdot x=x \cdot e=x[/math]. Иногда его обозначают [math] e_G [/math].

Утверждение (О единственности нейтрального элемента):

Нейтральный элемент в моноиде единственен.

[math]\triangleright[/math]

Действительно, путь [math]e_1[/math] и [math]e_2[/math] — два нейтральных элемента. Тогда имеем: [math]e_1 = e_1\cdot e_2 = e_2[/math].

[math]\triangleleft[/math]

Примеры

• Множество действительных чисел [math]\mathbb{R}[/math] c операцией умножения или сложения (нейтральными элементами являются 1 и 0 соответственно).
• Множество строк из [math] \Sigma^* [/math] с операцией конкатенацией и нейтральным элементом — пустой строкой (обозначаемой [math]\varepsilon[/math]).

Определение:

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

Определение:

Свободным моноидом (англ. free monoid) над множеством [math] S [/math] называется моноид [math] M [/math] вместе с отображением [math] i\colon S \rightarrow M [/math] при условии, что для любого моноида [math] N [/math] и для любых отображений [math] f \colon S \rightarrow N [/math] существует единственный гомоморфизм моноидов [math] \overline{f} \colon M(S) \rightarrow N [/math] такой, что [math] \overline{f} \circ i = f [/math].

Это наглядно показано следующей картинкой. TODO: картинка

Если [math] S [/math] является подмножеством [math] M [/math], то отображение [math] i [/math] называют естественным вложением (англ. natural injection), и пишут [math] i \colon S \hookrightarrow M [/math].

Ссылки

• Proof Wiki — Free monoid