Моноид

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

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

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

Примеры

• множество натуральных чисел [math] \mathbb{N} [/math] с операцией сложения является моноидом [math]\langle \mathbb{N}, +, 0 \rangle[/math]
• множество положительных целых [math] \mathbb{Z}_+ [/math] с операцией умножения является моноидом [math]\langle\mathbb{Z}_+, \cdot, 1 \rangle[/math]
• множество натуральных числел с операцией умножения является моноидом [math]\langle \mathbb{N}, \cdot, 1 \rangle[/math] с нейтральным элементом [math]1[/math] (наличие нуля не мешает этой структуре быть моноидом: [math]1 \cdot 0 = 0[/math], как того и требует аксиома нейтрального элемента), но тройка [math]\langle \mathbb{N}, \cdot, 0 \rangle[/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]

Гомоморфизм моноидов

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

Гомоморфизмом моноидов (англ. monoid homomorphism) [math]\langle M, \cdot_M, \varepsilon_M \rangle [/math] и [math]\langle N, \cdot_N, \varepsilon_N \rangle [/math] называется отображение [math]\varphi \colon M \rightarrow N[/math] совместимое с операциями из [math] M [/math] и [math] N [/math], то есть такое, что: [math]\varphi(\varepsilon_M) = \varepsilon_N[/math] [math] \forall x, y \in M \colon \varphi(x\cdot_M y) = \varphi(x) \cdot_N \varphi(y)[/math]

Свободный моноид над множеством

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

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

Примеры свободного моноида над множеством

• тривиальный пример: множество [math] S = \varnothing [/math]. Тогда [math] S^* = \{\varnothing\} [/math].
• [math] S = \{1\} [/math]. Тогда [math]S^* = \{[], [1], [1, 1], ... \} [/math].

Свободный моноид

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

Моноид [math]M[/math] называется свободным, если он изоморфен некоторому свободному моноиду над каким-то множеством.

Примеры свободного моноида

• [math]\langle \mathbb{N}, +, 0 \rangle [/math] — пример свободного моноида, так как он изоморфен свободному моноиду над [math]S = \{1\}[/math]:
  • [math]i(0) = [][/math]
  • [math]i(a + b) = i(a) ~ \texttt{++} ~ i(b)[/math]

Моноид с порождающими соотношениями

Введём дополнительное определение, чтобы привести пример моноида, не являющегося свободным.

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

Моноидом с порождающими соотношениями (англ. equational presentation of monoid) называется моноид, на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.

Примером такого моноида является множество [math] G [/math] всевозможных строк над алфавитом [math] \Sigma = \{a, b\} [/math], [math] G = \Sigma^{*}_{/ab = ba} [/math], что обозначает равенство строк [math] ab [/math] и [math] ba [/math] в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это.

Теорема:

Моноид [math] G = \Sigma^{*}_{/ab = ba} [/math] не является свободным

Доказательство:

[math]\triangleright[/math]

Для начала покажем, что каждый элемент такого моноида можно представить в виде [math] a^i b^j, i \geqslant 0, j \geqslant 0 [/math]. Докажем это конструктивно. Возьмём произвольную строку и будем в ней заменять все подстроки вида [math] ba [/math] на подстроки [math] ab [/math]. Если таких подстрок нет, то наша строка имеет вид [math] a^i b^j [/math], а если есть, то строка за конечное число шагов приведётся к указанному виду. Замечание: конкатенация двух последовательностей [math] a^i b^j [/math] и [math] a^k b^t [/math] аналогична операции конкатенации строк, только после её применения строку надо привести к виду [math] a^{i + k} b^{j + t} [/math], поэтому результат операции равен не конкретной строке, а целому классу эквивалентности. Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множеством [math] M_S [/math], то есть существует биективное отображение [math] f \colon G \to M_S [/math]. Оно сохраняет ассоциативность операций, поэтому [math] f(ab) = f(a) ~\texttt{++}~ f(b) [/math] [math] f(ba) = f(b) ~\texttt{++}~ f(a) [/math] Следовательно, так как [math] ab = ba [/math] и отображение [math] f [/math] является изоморфизмом, то [math] f(ab) = f(a) ~\texttt{++}~ f(b) = f(b) ~\texttt{++}~ f(a) = f(ba) [/math]. Пусть [math] |f(a)| = m, |f(b)| = n [/math]. Равенство этих последовательностей означает, что у последовательности [math] f(a) ~\texttt{++}~ f(b) [/math] есть два бордера длин [math] m [/math] и [math] n [/math] соответственно, значит, она периодическая и имеет период равный [math]\gcd(n, m)[/math]. Из этого следует, что последовательности [math] f(a) [/math] и [math] f(b) [/math] можно представить в виде конечного объединения некоторой подпоследовательности [math] s [/math], являющейся периодом и имеющей длину [math]\gcd(n, m)[/math]. [math] f(a) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{p} [/math] [math] f(b) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{q} , s \in M_S [/math] Пусть [math]\mathrm{lcm}(p, q) = l[/math], тогда [math] \overbrace{f(a) ~\texttt{++}~ f(a) ~\texttt{++}~ ... ~\texttt{++}~ f(a)}^{l / p} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} [/math] [math] \overbrace{f(b) ~\texttt{++}~ f(b) ~\texttt{++}~ ... ~\texttt{++}~ f(b)}^{l / q} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} [/math] Откуда следует, что [math] a^{l / p} = b^{l / q} [/math], то есть отображение [math] f [/math] не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид [math] G = \Sigma^{*}_{/ab = ba} [/math] является свободным. Равенство [math] f(ab) = f(ba) [/math] может сохранять изоморфизм, если [math] f(a) = [] [/math], но тогда [math] f(a) = f(aa) [/math], что опять же приводит нас к противоречию.

[math]\triangleleft[/math]

См. также

• Группа
• Изоморфизм групп

Источники информации

• Wikipedia — Monoid
• Википедия — Моноид
• Wikipedia — Free monoid
• nLab — Free Monoid
• Proof Wiki — Free monoid
• Habrahabr — Моноиды и их приложения: моноидальные вычисления в деревьях