Изменения

Пара Кортеж <tex>\langle G,\cdot : G \times G \to G, \varepsilon \in G \rangle</tex> называется [[моноид|моноидом]], если она он удовлетворяет следующим аксиомам:* Операция Бинарная операция <tex> \cdot \colon G \times G \rightarrow G </tex> — определена везде и [[Ассоциативная операция | ''ассоциативна'']].* Существует нейтральный элемент <tex> \varepsilon </tex> называется нейтральным элементом относительно <tex>\in G cdot</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> моноидом уже не является. == Свойства ==

'''Гомоморфизмом моноидов''' (англ. ''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 mx, m' y \in M \colon \varphi(mx\cdot m'cdot_M y) = \varphi(mx) \cdot cdot_N \varphi(ny)</tex>, а также <tex>\varphi(\varepsilon_M) = \varepsilon_N</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 = \{1\} </tex>. Тогда <tex>S^* = \{[], [1], [1, 1], ... \} </tex>. Такой  == Свободный моноид с введённой на нём операцией сложения как объединением списков== {{Определение|definition=Моноид <tex>M</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> == Моноид с порождающими соотношениями ==

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

Для начала покажем, что каждый элемент такого моноида можно представить в виде <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> Пусть <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> M_S f(a) = [] </tex>, то есть существует биективное отображение но тогда <tex> f : G \to M_S (a) = f(aa) </tex>, что опять же приводит нас к противоречию. Это отображение

== Ссылки Источники информации ==