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

Материал из Викиконспекты
Перейти к: навигация, поиск
(так все-таки получше выглядит)
(и так получше)
Строка 24: Строка 24:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Гомоморфизмом моноидов''' (англ. ''monoid homomorphism'') <tex>M</tex> и <tex>N</tex> называется отображение <tex>\varphi \colon M \rightarrow N</tex> совместимое с операциями из <tex> M </tex> и <tex> N </tex> такое, что  
+
'''Гомоморфизмом моноидов''' (англ. ''monoid homomorphism'') <tex>\langle M, \cdot_M, \varepsilon_M \rangle </tex> и <tex>\langle N, \cdot_N, \varepsilon_N \rangle </tex> называется отображение <tex>\varphi \colon M \rightarrow N</tex> совместимое с операциями из <tex> M </tex> и <tex> N </tex>, то есть такое, что:
<tex> \forall m, m' \in M \colon \varphi(m\cdot m') = \varphi(m) \cdot \varphi(n)</tex>, а также <tex>\varphi(\varepsilon_M) = \varepsilon_N</tex>. 
+
 
 +
* <tex>\varphi(\varepsilon_M) = \varepsilon_N</tex>
 +
* <tex> \forall x, y \in M \colon \varphi(x\cdot_M y) = \varphi(x) \cdot_N \varphi(y)</tex>
 
}}
 
}}
  

Версия 22:50, 15 ноября 2013

Определение:
Кортеж [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]1[/math], так как [math]1 \cdot 0 = 0[/math], а не [math]1[/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] S = \varnothing [/math]. Тогда [math] S^* = \{\varnothing\} [/math].
  • [math] S = \{1\} [/math]. Тогда [math]S^* = \{[], [1], [1, 1], ... \} [/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] ba [/math] на [math] ab [/math] можно рассматривать, как уменьшения числа инверсий в последовательности, а их точно конечное число, так как все последовательности имеют конечную длину.

Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду [math] M_S [/math], то есть существует биективное отображение [math] f : G \to M_S [/math]. Оно сохраняет ассоциативность операций, поэтому

[math] f(ab) = f(a) \cdot f(b) [/math]

[math] f(ba) = f(b) \cdot f(a) [/math]

Следовательно, так как [math] ab = ba [/math] и отображение [math] f [/math] является изоморфизмом, то [math] f(ab) = f(a) \cdot f(b) = f(b) \cdot f(a) = f(ba) [/math]. Равенство этих последовательностей означает, что у строки [math] f(a) \cdot f(b) [/math] есть бордер, а значит, она периодическая.

TODO: картинка, которая объяснит все равенства

Из этого следует, что

[math] f(a) = \overbrace{s \cdot s \cdot ... \cdot s}^{p} [/math]

[math] f(b) = \overbrace{s \cdot s \cdot ... \cdot s}^{q} , s \in M_S [/math]

Пусть НОК[math](p, q) = l[/math], тогда

[math] \overbrace{f(a) \cdot f(a) \cdot ... \cdot f(a)}^{\frac{l}{p}} = \overbrace{s \cdot s \cdot ... \cdot s}^{l} [/math]

[math] \overbrace{f(b) \cdot f(b) \cdot ... \cdot f(b)}^{\frac{l}{q}} = \overbrace{s \cdot s \cdot ... \cdot s}^{l} [/math]

Откуда следует, что [math] a^{\frac{l}{p}} = b^{\frac{l}{q}} [/math], то есть отображение [math] f [/math] не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид [math] G = \Sigma^{*}_{/ab = ba} [/math] является свободным.
[math]\triangleleft[/math]

См. также

Ссылки