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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Тройка <tex>\langle G,\cdot, \varepsilon \rangle</tex> называется [[моноид|моноидом]], если она удовлетворяет следующим аксиомам:
+
Кортеж <tex>\langle G,\cdot: G \times G \to G, \varepsilon \in G \rangle</tex> называется [[моноид|моноидом]], если он удовлетворяет следующим аксиомам:
* Операция <tex> \cdot \colon G \times G \rightarrow G </tex> ''ассоциативна''.
+
* Бинарная операция <tex>\cdot</tex> — определена везде и [[Ассоциативная операция | ''ассоциативна'']].
* Существует нейтральный элемент <tex> \varepsilon \in G </tex> относительно бинарной операции такой, что
+
* <tex>\varepsilon</tex> называется нейтральным элементом относительно <tex>\cdot</tex>, то есть для него выполняется:
: <tex> \forall x\in G : \varepsilon\cdot x=x \cdot \varepsilon = x</tex>. Иногда его обозначают <tex> \varepsilon_G </tex>.
+
: <tex> \forall x\in G : \varepsilon\cdot x=x \cdot \varepsilon = x</tex>. Иногда его обозначают <tex> \varepsilon_G </tex>, или <tex>e_G </tex>.
 
}}
 
}}
  
Другими словами, моноид {{---}} это [[Полугруппа|полугруппа]], в которую добавлен нейтральный элемент. Например, множество натуральных чисел с операцией сложения не является моноидом, а с операцией умножения является.
+
Другими словами, моноид {{---}} это [[Полугруппа|полугруппа]], в которую добавлен нейтральный элемент.
 +
 
 +
== Примеры ==
 +
 
 +
* множество натуральных чисел <tex> \mathbb{N} </tex> с операцией сложения является моноидом <tex>\langle \mathbb{N}, +, 0 \rangle</tex>
 +
* множество положительных целых <tex> \mathbb{Z}_+ </tex> с операцией умножения является моноидом <tex>\langle\mathbb{Z}_+, \cdot, 1 \rangle</tex>
 +
* множество натуральных числел с операцией умножения является моноидом <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex> (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, как того и требует аксиома нейтрального элемента), но тройка <tex>\langle \mathbb{N}, \cdot, 0 \rangle</tex> моноидом уже не является.
 +
 
 +
== Свойства ==
  
 
{{Утверждение
 
{{Утверждение
Строка 15: Строка 23:
 
Действительно, пусть <tex>\varepsilon_1</tex> и <tex>\varepsilon_2</tex> {{---}} два нейтральных элемента. Тогда имеем: <tex>\varepsilon_1 = \varepsilon_1\cdot \varepsilon_2 = \varepsilon_2</tex>.
 
Действительно, пусть <tex>\varepsilon_1</tex> и <tex>\varepsilon_2</tex> {{---}} два нейтральных элемента. Тогда имеем: <tex>\varepsilon_1 = \varepsilon_1\cdot \varepsilon_2 = \varepsilon_2</tex>.
 
}}
 
}}
 +
 +
== Гомоморфизм моноидов ==
 +
{{Определение
 +
|id = defmonhom
 +
|definition=
 +
'''Гомоморфизмом моноидов''' (англ. ''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>\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>
 +
}}
 +
 +
== Свободный моноид над множеством ==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> над множеством <tex> S </tex> <tex>(</tex>обозначается как <tex> M_S )</tex> называется моноид над множеством <tex> S^* </tex> {{---}} набором всевозможных элементов, полученных конечным числом применений ассоциативной операции к элементам исходного множества.
+
'''Свободным моноидом''' (англ. ''free monoid'') <tex> M </tex> '''над множеством''' <tex> S </tex> <tex>(</tex>обозначается как <tex> M_S )</tex> называется моноид над множеством <tex> S^* </tex> {{---}} набором всевозможных последовательностей (или списков) конечной длины (в том числе и нулевой), образованных из элементов множества <tex> S </tex> {{---}} с ассоциативной операцией [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#defconcat|конкатенации]] <tex>\texttt{++}</tex> этих последовательностей.
 
}}
 
}}
 +
=== Примеры свободного моноида над множеством ===
 +
 +
* тривиальный пример: множество <tex> S = \varnothing </tex>. Тогда <tex> S^* = \{\varnothing\} </tex>.
 +
* <tex> S = \{1\} </tex>. Тогда <tex>S^*  = \{[], [1], [1, 1], ... \} </tex>.
  
Тривиальный пример образуют множество <tex> S = \{\varnothing\} </tex> и операция <tex> \cup </tex>. Тогда <tex> S^* \equiv \{\varnothing\} </tex>.
+
== Свободный моноид ==
 +
 
 +
{{Определение
 +
|definition=
 +
Моноид <tex>M</tex> называется '''свободным''', если он [[Изоморфизм групп | изоморфен]] некоторому свободному моноиду над каким-то множеством.
 +
}}
 +
=== Примеры свободного моноида ===
  
Другой пример: <tex> S = \{0, 1\} </tex>, операция {{---}} сложение. Тогда <tex>S^* \equiv \mathbb{N} \cup \{0\} </tex>.
+
* <tex>\langle \mathbb{N}, +, 0 \rangle </tex> {{---}} пример свободного моноида, так как он изоморфен свободному моноиду над <tex>S = \{1\}</tex>:
 +
** <tex>i(0) = []</tex>
 +
** <tex>i(a + b) = i(a) ~ \texttt{++} ~ i(b)</tex>
  
Дадим теперь более формальное определение.
+
== Моноид с порождающими соотношениями ==
  
 +
Введём дополнительное определение, чтобы привести пример моноида, не являющегося свободным.
 
{{Определение
 
{{Определение
 
|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>.
+
'''Моноидом с порождающими соотношениями''' (англ. ''equational presentation of monoid'') называется моноид, на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.
 
}}
 
}}
Это наглядно показано следующей картинкой.
+
Примером такого моноида является множество <tex> G </tex> всевозможных строк над алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> ba </tex> в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это.
 +
 
 +
{{Теорема
 +
|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> a^i b^j </tex> и <tex> a^k b^t </tex> аналогична операции конкатенации строк, только после её применения строку надо привести к виду <tex> a^{i + k} b^{j + t} </tex>, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]].
 +
 
 +
Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множеством <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \to M_S </tex>. Оно сохраняет ассоциативность операций, поэтому
 +
 
 +
<tex> f(ab) = f(a) ~\texttt{++}~ f(b) </tex>
 +
 +
<tex> f(ba) = f(b) ~\texttt{++}~ f(a) </tex>
 +
 
 +
Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\texttt{++}~ f(b) = f(b) ~\texttt{++}~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у последовательности <tex> f(a) ~\texttt{++}~ f(b) </tex> есть два [[Период и бордер, их связь | бордера]] длин <tex> m </tex> и <tex> n </tex> соответственно, значит, она периодическая и имеет период равный <tex>\gcd(n, m)</tex>.
 +
 
 +
[[File:FreeMonoidConcatExample.png|300px]]
 +
 
 +
Из этого следует, что последовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину <tex>\gcd(n, m)</tex>.
 +
 
 +
<tex> f(a) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{p} </tex>
 +
 
 +
<tex> f(b) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{q} , s \in M_S </tex>
  
[[Файл:FreeMonoidDefinition.png]]
+
Пусть <tex>\mathrm{lcm}(p, q) = l</tex>, тогда
  
 +
<tex dpi> \overbrace{f(a) ~\texttt{++}~ f(a) ~\texttt{++}~ ... ~\texttt{++}~ f(a)}^{l / p} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} </tex>
 +
 +
<tex dpi> \overbrace{f(b) ~\texttt{++}~ f(b) ~\texttt{++}~ ... ~\texttt{++}~ f(b)}^{l / q} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} </tex>
 +
 +
Откуда следует, что <tex dpi = 140> a^{l / p} = b^{l / q} </tex>, то есть отображение <tex> f </tex> не является изоморфизмом. Значит, мы пришли к противоречию, предположив, что данный моноид <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex> является свободным.
 +
 +
Равенство <tex> f(ab) = f(ba) </tex> может сохранять изоморфизм, если <tex> f(a) = [] </tex>, но тогда <tex> f(a) = f(aa) </tex>, что опять же приводит нас к противоречию.
 +
}}
  
 
== См. также ==
 
== См. также ==
Строка 40: Строка 104:
 
* [[Изоморфизм групп]]  
 
* [[Изоморфизм групп]]  
  
== Ссылки ==
+
== Источники информации ==
 +
* [[wikipedia:Monoid | Wikipedia {{---}} Monoid ]]
 +
* [[wikipedia:ru:Моноид | Википедия {{---}} Моноид ]]
 
* [[wikipedia:Free_monoid | Wikipedia {{---}} Free monoid ]]
 
* [[wikipedia:Free_monoid | Wikipedia {{---}} Free monoid ]]
 
* [http://ncatlab.org/nlab/show/free+monoid nLab {{---}} Free Monoid]
 
* [http://ncatlab.org/nlab/show/free+monoid nLab {{---}} Free Monoid]
 
* [http://www.proofwiki.org/wiki/Definition:Free_Monoid Proof Wiki {{---}} Free monoid]
 
* [http://www.proofwiki.org/wiki/Definition:Free_Monoid Proof Wiki {{---}} Free monoid]
 +
* [http://habrahabr.ru/post/112394/ Habrahabr {{---}} Моноиды и их приложения: моноидальные вычисления в деревьях]
  
 
[[Категория:Теория групп]]
 
[[Категория:Теория групп]]

Текущая версия на 19:38, 4 сентября 2022

Определение:
Кортеж [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].

FreeMonoidConcatExample.png

Из этого следует, что последовательности [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]

См. также

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