Моноид — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (изменена картинка)
м
Строка 29: Строка 29:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Свободным моноидом''' над множеством <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> 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>.
 
}}
 
}}
 
Это наглядно показано следующей картинкой.
 
Это наглядно показано следующей картинкой.

Версия 14:35, 10 ноября 2013

Определение:
Тройка [math]\langle G,\cdot, \varepsilon \rangle[/math] называется моноидом, если она удовлетворяет следующим аксиомам:
  • Операция [math] \cdot \colon G \times G \rightarrow G [/math] ассоциативна.
  • Существует нейтральный элемент [math] \varepsilon \in G [/math] относительно бинарной операции такой, что
[math] \forall x\in G : \varepsilon\cdot x=x \cdot \varepsilon = x[/math]. Иногда его обозначают [math] \varepsilon_G [/math].


Другими словами, моноид — это полугруппа, в которую добавлен нейтральный элемент. Например, множество натуральных чисел с операцией сложения не является моноидом, а с операцией умножения является.

Утверждение (О единственности нейтрального элемента):
Нейтральный элемент в моноиде единственен.
[math]\triangleright[/math]
Действительно, пусть [math]\varepsilon_1[/math] и [math]\varepsilon_2[/math] — два нейтральных элемента. Тогда имеем: [math]\varepsilon_1 = \varepsilon_1\cdot \varepsilon_2 = \varepsilon_2[/math].
[math]\triangleleft[/math]


Определение:
Свободным моноидом (англ. free monoid) [math] M [/math] над множеством [math] S [/math] [math]([/math]обозначается как [math] M_S )[/math] называется моноид над множеством [math] S^* [/math] — набором всевозможных элементов, полученных конечным числом применений ассоциативной операции к элементам исходного множества.


Тривиальный пример образуют множество [math] S = \{\varnothing\} [/math] и операция [math] \cup [/math]. Тогда [math] S^* \equiv \{\varnothing\} [/math].

Другой пример: [math] S = \{0, 1\} [/math], операция — сложение. Тогда [math]S^* \equiv \mathbb{N} \cup \{0\} [/math].

Дадим теперь более формальное определение.


Определение:
Свободным моноидом над множеством [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].

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

FreeMonoidDefinition2.jpg


См. также

Ссылки