Моноид

Моноид — полугруппа с нейтральным элементом. То есть моноидом называется множество [math]\displaystyle{ M }[/math], на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует такой элемент [math]\displaystyle{ e }[/math], что [math]\displaystyle{ ex=x=xe }[/math] для любого [math]\displaystyle{ x\in M }[/math]. Элемент [math]\displaystyle{ e }[/math] называется единицей и часто обозначается [math]\displaystyle{ 1 }[/math]. В любом моноиде имеется ровно один нейтральный элемент.

Моноид это формализация понятия "множество с операцией". Таким образом моноид это упорядочная пара [math]\displaystyle{ M=(|M|, \mu) }[/math], где [math]\displaystyle{ |M| }[/math] - основное множество моноида, а [math]\displaystyle{ \mu: |M| \times |M| \to |M| }[/math] - это операция, замкнутая на множестве [math]\displaystyle{ M }[/math].

Моноиды возникают в различных областях математики; например, моноиды можно рассматривать как категории из одного объекта. Таким образом, моноиды обобщают свойства композиции функций. Также моноиды используются в информатике и в теории формальных языков.

Примеры

Всякая группа является моноидом.
Множество всех отображений произвольного множества [math]\displaystyle{ S }[/math] в себя является моноидом относительно операции последовательного выполнения (композиции) отображений. Единицей служит тождественное отображение.
Множество эндоморфизмов любой универсальной алгебры [math]\displaystyle{ A }[/math] является моноидом относительно операции суперпозиции, единица — тождественный эндоморфизм.
Любую полугруппу S можно превратить в моноид, просто присоединив элемент e и определив e*s = s = s*e для всех s ∈ S.
Неотрицательные числа (Натуральные числа и ноль) образуют коммутативный моноид (моноид с коммутативной операцией) как по умножению, так и по сложению.
Множество всех конечных строк с элементами из алфавита Σ образует моноид, обычно обозначаемый Σ^∗. Операция определяется как конкатенация строк.
Зафиксируем моноид M. Тогда множество всех функций из фиксированного множества в M образует моноид; единица которого — функция, отображающая всё множество в единицу M, операция определяется поточечно.
Список с операцией конкатенации и пустым списком как нейтральным элементом.
Словарь. Нейтральный элемент — пустой словарь. Операция — объединение словарей по ключу, при равенстве ключа для значений должна быть определена операция слияния (замечание: если операция слияния значений некоммутативна, то слияние словарей тоже будет некоммутативно). Например, можно определить операцию слияния как
- числа складывать
- строки конкатенировать
- списки конкатенировать
- для вложенных словарей проводить операцию рекурсивно

Например, словари

 {"a" => 2, "b" => "cd", "c" => [1, 2], "d" => {"e" => 1}, "f" => 1}
 {"a" => 3, "b" => "e", "c" => [3], "d" => {"e" => 2}, "g" => 1}

могут быть объединены в

 {"a" => 5, "b" => "cde", "c" => [1, 2, 3], "d" => {"e" => 3}, "f" => 1, "g" => 1}

Подмоноид

Подмоноидом моноида [math]\displaystyle{ M }[/math], называется подмножество [math]\displaystyle{ H }[/math] множества [math]\displaystyle{ M }[/math], содержащее нейтральный элемент [math]\displaystyle{ e }[/math] и выполняющее условие, что если [math]\displaystyle{ x, y \in H }[/math], то [math]\displaystyle{ xy\in H }[/math] ([math]\displaystyle{ xy }[/math] или [math]\displaystyle{ x\cdot y }[/math] - бинарная операция умножения). Последнее условие означает, что множество [math]\displaystyle{ H }[/math] замкнуто под бинарной операцией или под законом композиции. Подмоноид [math]\displaystyle{ H }[/math] сам является моноидом, закон композиции которого вытекает из закона композиции моноида [math]\displaystyle{ M }[/math].

Свойства

Всякий моноид можно представить как моноид всех эндоморфизмов некоторой универсальной алгебры.^{[источник не указан 4564 дня]}

В бинарной операции умножения элементов моноида можно вставить скобки в любом месте и это не изменит значение выражения:

[math]\displaystyle{ \prod_{\mu=1}^m x_{\mu} \cdot \prod_{m+1}^{m+n} x_{\nu} = \prod_{\nu=1}^{m+n} x_{\nu} }[/math].

В теории групп условились, что пустое произведение равно нейтральному элементу:

[math]\displaystyle{ \prod_{\nu=1}^{0} x_{\nu} = e }[/math].

Для любого элемента моноида можно определить нулевую степень как [math]\displaystyle{ a^0=e, \forall a }[/math] Так как моноид является частным случаем полугруппы, то для его элементов определена натуральная степень. Свойства степени [math]\displaystyle{ a^{m+n}=a^m a^n, (a^m)^n=a^{mn} }[/math] остаются справедливыми для [math]\displaystyle{ \mathbb N\cup\{0\} }[/math].

Можно ввести определение обратимого элемента моноида: x является обратимым, если существует такой элемент y, что xy = yx = e. Если y и z — два элемента с таким свойством, то по ассоциативности y = (zx)y = z(xy) = z, следовательно, обратный элемент определён однозначно^[1] (обычно его обозначают x⁻¹). Множество всех обратимых элементов моноида образует группу (возможно, тривиальную).

С другой стороны, не каждый моноид можно вложить в группу. Например, вполне возможно что в моноиде существуют элементы a и b, такие что ab = a и при этом b не является нейтральным элементом. Если бы этот моноид являлся подмножеством некоторой группы, мы могли бы домножить обе части равенства на a⁻¹ слева и получили бы противоречие. Говорят, что моноид M обладает свойством сокращения, если, для любых его элементов, [math]\displaystyle{ ab=ac\Rightarrow b=c }[/math] и [math]\displaystyle{ ba=ca\Rightarrow b=c }[/math]. Коммутативный моноид со свойством сокращения можно вложить в группу, используя конструкцию группы Гротендика. Это обобщает способ, по которому аддитивную группу целых чисел можно восстановить по аддитивной группе натуральных чисел.

Конечный моноид со свойством сокращения всегда является группой. Действительно, пусть x — произвольный элемент такого моноида. Из принципа Дирихле следует, что xⁿ = x^m для некоторых m > n > 0. Но тогда из свойства сокращения следует, что x^m−n = e, где e — единица. Следовательно, x * x^m−n−1 = x^m−n−1 * x = e, так что x обратим.

Гомоморфизм из моноида M в моноид N — это функция [math]\displaystyle{ f\colon M \to N }[/math], такая что [math]\displaystyle{ f(xy)=f(x)\cdot f(y) }[/math] (для любых x и y из M) и [math]\displaystyle{ f(e)=e }[/math].

Связь с теорией категорий

Аксиомы моноида совпадают с теми аксиомами, которые накладываются на композицию морфизмов одного объекта в категории, то есть моноиды можно рассматривать как категории из одного объекта.

Аналогично, гомоморфизмы моноидов — это в точности функторы между соответствующими категориями.^[2] Эта конструкция задаёт эквивалентность между категорией (малых) моноидов Mon и полной подкатегорией в Cat.

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

См. также

Примечания

↑ Jacobson, I.5. p. 22
↑ Awodey, Steve (2006). Category Theory. Oxford Logic Guides 49. Oxford University Press. p. 10. ISBN 0-19-856861-4. Zbl 1100.18001.

Литература

Jacobson, Nathan (2009), Basic algebra 1 (2nd ed.), Dover — ISBN 978-0-486-47189-1.

Ссылки

Hazewinkel, Michiel, ed. (2001), Monoid, Encyclopedia of Mathematics, Springer — ISBN 978-1-55608-010-4

[1] Jacobson, I.5. p. 22

[2] Awodey, Steve (2006). Category Theory. Oxford Logic Guides 49. Oxford University Press. p. 10. ISBN 0-19-856861-4. Zbl 1100.18001.

[1]

[2]