Моноид

В абстрактной алгебре , разделе математики , моноид — это множество, снабженное ассоциативной бинарной операцией и единичным элементом . Например, неотрицательные целые числа со сложением образуют моноид, единичный элемент которого равен 0 .

Моноиды — это полугруппы с единицей. Такие алгебраические структуры встречаются в нескольких разделах математики.

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

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

В теоретической информатике изучение моноидов имеет основополагающее значение для теории автоматов ( теория Крона–Роудса ) и теории формального языка ( проблема высоты звезды ).

Историю предмета и некоторые другие общие свойства моноидов см. в разделе полугруппа .

Множество S, снабженное бинарной операцией S × S → S , которую мы будем обозначать • , является моноидом , если оно удовлетворяет следующим двум аксиомам:

Ассоциативность

Для всех a , b и c из S справедливо уравнение ( a • b ) • c = a • ( b • c ) .

Элемент идентичности

Существует элемент e в S , такой что для каждого элемента a в S справедливы равенства e • a = a и a • e = a .

Другими словами, моноид — это полугруппа с элементом тождества . Его также можно рассматривать как магму с ассоциативностью и тождеством. Элемент тождества моноида уникален. ^[a] По этой причине тождество рассматривается как константа , т.е. 0- арная (или нульарная) операция. Поэтому моноид характеризуется спецификацией тройки ( S , • , e ) .

В зависимости от контекста символ для бинарной операции может быть опущен, так что операция будет обозначена сопоставлением ; например, аксиомы моноида могут быть записаны как ( ab ) c = a ( bc ) и ea = ae = a . Эта запись не подразумевает, что умножаются числа.

Моноид, в котором каждый элемент имеет обратный, называется группой .

Подмоноид моноида ( M , •) — это подмножество N из M , замкнутое относительно операции моноида и содержащее единичный элемент e из M . ^{[1] [b]} Символически N является подмоноидом M , если e ∈ N ⊆ M , и x • y ∈ N всякий раз, когда x , y ∈ N . В этом случае N является моноидом относительно бинарной операции, унаследованной от M .

С другой стороны, если N является подмножеством моноида, который замкнут относительно операции моноида, и является моноидом для этой унаследованной операции, то N не всегда является подмоноидом, поскольку элементы идентичности могут различаться. Например, синглтон-множество {0} замкнуто относительно умножения и не является подмоноидом (мультипликативного) моноида неотрицательных целых чисел .

Говорят, что подмножество S из M порождает M, если наименьший подмоноид M , содержащий S , есть M. Если существует конечное множество, порождающее M , то M называется конечно порожденным моноидом .

Моноид, операция которого коммутативна, называется коммутативным моноидом (или, реже, абелевым моноидом ). Коммутативные моноиды часто записываются аддитивно. Любой коммутативный моноид наделяется своим алгебраическим предупорядочением ≤ , определяемым соотношением x ≤ y , если существует z такой, что x + z = y . ^[2] Порядковая единица коммутативного моноида M — это элемент u из M такой, что для любого элемента x из M существует v в множестве, порожденном u , такой, что x ≤ v . Это часто используется в случае, если M является положительным конусом частично упорядоченной абелевой группы G , и в этом случае мы говорим, что u является порядковой единицей G .

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

• Из 16 возможных бинарных булевых операторов четыре имеют двустороннюю идентичность, которая также является коммутативной и ассоциативной. Каждый из этих четырех делает множество {False, True} коммутативным моноидом. Согласно стандартным определениям, AND и XNOR имеют идентичность True , а XOR и OR имеют идентичность False . Моноиды из AND и OR также идемпотентны , а из XOR и XNOR — нет.
• Множество натуральных чисел N = {0, 1, 2, ...} является коммутативным моноидом относительно сложения (элемент единицы 0 ) или умножения (элемент единицы 1 ). Подмоноид N относительно сложения называется числовым моноидом .
• Множество положительных целых чисел N ∖ {0} является коммутативным моноидом относительно умножения (единичный элемент 1 ).
• Для данного множества A множество подмножеств A является коммутативным моноидом относительно пересечения (единичным элементом является само A ).
• Для данного множества A множество подмножеств A является коммутативным моноидом относительно объединения (элементом тождества является пустое множество ).
• Обобщая предыдущий пример, каждая ограниченная полурешетка является идемпотентным коммутативным моноидом.
  • В частности, любая ограниченная решетка может быть снабжена как структурой моноида meet - так и структурой моноида join . Элементами тождества являются вершина и основание решетки соответственно. Будучи решетками, алгебры Гейтинга и булевы алгебры снабжены этими структурами моноида.
• Каждое одноэлементное множество { x }, замкнутое относительно бинарной операции •, образует тривиальный (одноэлементный) моноид, который также является тривиальной группой .
• Каждая группа является моноидом, а каждая абелева группа — коммутативным моноидом.
• Любая полугруппа S может быть превращена в моноид простым присоединением элемента e, не входящего в S , и определением e • s = s = s • e для всех s ∈ S. Это преобразование любой полугруппы в моноид осуществляется свободным функтором между категорией полугрупп и категорией моноидов. ^[3]
  • Таким образом, идемпотентный моноид (иногда называемый find-first ) может быть образован присоединением единичного элемента e к левой нулевой полугруппе над множеством S. Противоположный моноид (иногда называемый find-last ) образуется из правой нулевой полугруппы над S.
    • Присоединим единицу e к левой нулевой полугруппе с двумя элементами {lt, gt} . Тогда полученный идемпотентный моноид {lt, e , gt} моделирует лексикографический порядок последовательности, заданной порядками ее элементов, где e представляет равенство.
• Базовый набор любого кольца , с операцией сложения или умножения. (По определению, кольцо имеет мультипликативную идентичность 1. )
  • Целые числа , рациональные числа , действительные числа или комплексные числа с операцией сложения или умножения. ^[4]
  • Множество всех матриц размера n на n над заданным кольцом, с операцией сложения или умножения матриц .
• Множество всех конечных строк над некоторым фиксированным алфавитом Σ образует моноид с конкатенацией строк в качестве операции. Пустая строка служит элементом идентичности. Этот моноид обозначается Σ ^∗ и называется свободным моноидом над Σ . Он не коммутативен, если Σ имеет по крайней мере два элемента.
• Для любого моноида M противоположный моноид M ^op имеет тот же несущий набор и элемент идентичности, что и M , и его операция определяется как x • ^op y = y • x . Любой коммутативный моноид является противоположным моноидом самого себя.
• Если даны два множества M и N, наделенные моноидной структурой (или, в общем случае, любое конечное число моноидов, M ₁ , ..., M _k ), их декартово произведение M × N с бинарной операцией и элементом тождества, определенными на соответствующих координатах, называемое прямым произведением , также является моноидом (соответственно, M ₁ × ⋅⋅⋅ × M _k ). ^[5]
• Зафиксируем моноид M. Множество всех функций из заданного множества в M также является моноидом. Элемент тождества — это постоянная функция, отображающая любое значение в тождество M ; ассоциативная операция определяется поточечно .
• Зафиксируем моноид M с операцией • и единичным элементом e и рассмотрим его множество мощности P ( M ), состоящее из всех подмножеств M. Бинарная операция для таких подмножеств может быть определена как S • T = { s • t  : s ∈ S , t ∈ T } . Это превращает P ( M ) в моноид с единичным элементом { e } . Точно так же множество мощности группы G является моноидом относительно произведения подмножеств группы .
• Пусть S — множество. Множество всех функций S → S образует моноид относительно композиции функций . Тождество — это просто тождественная функция . Его также называют полным моноидом преобразований S. Если S конечно с n элементами, то моноид функций на S конечен с n ⁿ элементами.
• Обобщая предыдущий пример, пусть C — категория , а X — объект C. Множество всех эндоморфизмов X , обозначаемое End _C ( X ) , образует моноид относительно композиции морфизмов . Подробнее о связи между теорией категорий и моноидами см. ниже .
• Множество классов гомеоморфизма компактных поверхностей со связной суммой . Его единичным элементом является класс обычной 2-сферы. Более того, если a обозначает класс тора , а b обозначает класс проективной плоскости, то каждый элемент c моноида имеет единственное выражение в виде c = na + mb , где n — положительное целое число и m = 0, 1 или 2 . Имеем 3 b = a + b .
• Пусть ⟨ f ⟩ — циклический моноид порядка n , то есть ⟨ f ⟩ = { f ⁰ , f ¹ , ..., f ^{n −1} } . Тогда f ⁿ = f ^k для некоторого 0 ≤ k < n . Каждое такое k дает отдельный моноид порядка n , и каждый циклический моноид изоморфен одному из них.
  Более того, f можно рассматривать как функцию от точек {0, 1, 2, ..., n −1}, заданную формулой

$${\displaystyle {\begin{bmatrix}0&1&2&\cdots &n-2&n-1\\1&2&3&\cdots &n-1&k\end{bmatrix}}}$$или, что то же самое$${\displaystyle f(i):={\begin{cases}i+1,&{\text{if }}0\leq i<n-1\\k,&{\text{if }}i=n-1.\end{cases}}}$$

Умножение элементов в ⟨ f ⟩ затем задается композицией функций.

Если k = 0 , то функция f является перестановкой {0, 1, 2, ..., n −1} и дает единственную циклическую группу порядка n .

Аксиомы моноида подразумевают, что единичный элемент e уникален: если e и f являются единичными элементами моноида, то e = ef = f .

Для каждого неотрицательного целого числа n можно рекурсивно определить произведение любой последовательности ( a ₁ , ..., _an ) из n элементов моноида: пусть p ₀ = e и пусть p _m = p _{m −1} • a _m для 1 ≤ m ≤ n .${\displaystyle p_{n}=\textstyle \prod _{i=1}^{n}a_{i}}$

В качестве частного случая можно определить неотрицательные целые степени элемента x моноида: x ⁰ = 1 и x ⁿ = x ^{n −1} • x для n ≥ 1. Тогда x ^{m + n} = x ^m • x ⁿ для всех m , n ≥ 0 .

Элемент x называется обратимым , если существует элемент y такой, что x • y = e и y • x = e . Элемент y называется обратным к x . Обратные элементы, если они существуют, уникальны: если y и z являются обратными к x , то по ассоциативности y = ey = ( zx ) y = z ( xy ) = ze = z . ^[6]

Если x обратим, скажем, с обратным y , то можно определить отрицательные степени x, установив x ^{− n} = y ⁿ для каждого n ≥ 1 ; это делает уравнение x ^{m + n} = x ^m • x ⁿ верным для всех m , n ∈ Z .

Множество всех обратимых элементов моноида вместе с операцией • образует группу .

Не каждый моноид находится внутри группы. Например, вполне возможно иметь моноид, в котором существуют два элемента a и b, такие, что a • b = a выполняется, даже если b не является единичным элементом. Такой моноид не может быть вложен в группу, потому что в группе умножение обеих сторон на обратный элемент a дало бы b = e , что неверно.

Моноид ( M , •) обладает свойством сокращения (или является сокращаемым), если для всех a , b и c из M равенство a • b = a • c влечет b = c , а равенство b • a = c • a влечет b = c .

Коммутативный моноид со свойством сокращения всегда может быть вложен в группу с помощью групповой конструкции Гротендика . Таким образом, аддитивная группа целых чисел (группа с операцией + ) строится из аддитивного моноида натуральных чисел (коммутативный моноид с операцией + и свойством сокращения). Однако некоммутативный сократимый моноид не обязан быть вложенным в группу.

Если моноид обладает свойством сокращения и является конечным , то он фактически является группой. ^[c]

Правые и левые сократительные элементы моноида, в свою очередь, образуют подмоноид (т.е. замкнуты относительно операции и, очевидно, включают единицу). Это означает, что сократительные элементы любого коммутативного моноида могут быть расширены до группы.

Свойство сокращения в моноиде не является необходимым для выполнения конструкции Гротендика — достаточно коммутативности. Однако, если коммутативный моноид не обладает свойством сокращения, гомоморфизм моноида в его группу Гротендика не является инъективным. Точнее, если a • b = a • c , то b и c имеют один и тот же образ в группе Гротендика, даже если b ≠ c . В частности, если моноид имеет поглощающий элемент , то его группа Гротендика является тривиальной группой .

Обратный моноид — это моноид, в котором для каждого a из M существует единственный a ⁻¹ из M , такой что a = a • a ⁻¹ • a и a ⁻¹ = a ⁻¹ • a • a ⁻¹ . Если обратный моноид является сокращаемым, то он является группой.

В противоположном направлении моноид без нулевой суммы — это аддитивно записанный моноид, в котором a + b = 0 подразумевает, что a = 0 и b = 0 : ^[7] эквивалентно, что никакой элемент, кроме нуля, не имеет аддитивного обратного.

Пусть M — моноид с бинарной операцией, обозначенной • , и единичным элементом, обозначенным e . Тогда (левый) M -акт (или левый акт над M ) — это множество X вместе с операцией ⋅ : M × X → X , которая совместима со структурой моноида следующим образом:

• для всех x в X : e ⋅ x = x ;
• для всех a , b из M и x из X : a ⋅ ( b ⋅ x ) = ( a • b ) ⋅ x .

Это аналог в теории моноидов (левого) группового действия . Правые M -акты определяются аналогичным образом. Моноид с актом также известен как операторный моноид . Важные примеры включают системы переходов полуавтоматов . Полугруппу преобразований можно превратить в операторный моноид , присоединив тождественное преобразование.

Гомоморфизм между двумя моноидами ( M , ∗) и ( N , •) — это функция f  : M → N такая, что

• f ( x ∗ y ) = f ( x ) • f ( y ) для всех x , y в M
• f ( е _М ) = е _N ,

где e _M и e _N — тождества на M и N соответственно. Моноидные гомоморфизмы иногда просто называют моноидными морфизмами .

Не каждый гомоморфизм полугрупп между моноидами является гомоморфизмом моноидов, поскольку он может не отображать тождество в тождество целевого моноида, даже если тождество является тождеством образа гомоморфизма. ^[d] Например, рассмотрим [ Z ] _n , множество классов вычетов по модулю n , снабженное умножением. В частности, [1] _n является элементом тождества. Функция f  : [ Z ] ₃ → [ Z ] _{6 ,} заданная формулой [ k ] ₃ ↦ [3 k ] ₆ , является гомоморфизмом полугрупп, поскольку [3 k ⋅ 3 l ] ₆ = [9 kl ] ₆ = [3 kl ] ₆ . Однако f ([1] ₃ ) = [3] ₆ ≠ [1] ₆ , поэтому гомоморфизм моноидов является полугрупповым гомоморфизмом между моноидами, который отображает тождество первого моноида в тождество второго моноида, и последнее условие не может быть опущено.

Напротив, гомоморфизм полугрупп между группами всегда является гомоморфизмом групп , поскольку он обязательно сохраняет тождество (потому что в целевой группе гомоморфизма тождественный элемент является единственным элементом x, таким что x ⋅ x = x ).

Биективный гомоморфизм моноидов называется изоморфизмом моноидов . Два моноида называются изоморфными, если между ними существует изоморфизм моноидов .

Моноидам можно задать представление , во многом таким же образом, как группы можно задать с помощью представления группы . Это делается путем указания набора генераторов Σ и набора отношений на свободном моноиде Σ ^∗ . Это делается путем расширения (конечных) бинарных отношений на Σ ^∗ до конгруэнтностей моноида, а затем построения фактормоноида, как указано выше.

Для бинарного отношения R ⊂ Σ ^∗ × Σ ^∗ определяется его симметричное замыкание как R ∪ R ⁻¹ . Это можно расширить до симметричного отношения E ⊂ Σ ^∗ × Σ ^{∗ ,} определив x ~ _E y тогда и только тогда, когда x = sut и y = svt для некоторых строк u , v , s , t ∈ Σ ^∗ с ( u , v ) ∈ R ∪ R ⁻¹ . Наконец, берется рефлексивное и транзитивное замыкание E , которое затем является моноидной конгруэнцией.

В типичной ситуации отношение R просто задается как набор уравнений, так что R = { u ₁ = v ₁ , ..., u _n = v _n } . Так, например,

${\displaystyle \langle p,q\,\vert \;pq=1\rangle }$

является эквациональным представлением для бициклического моноида , и

${\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }$

является пластическим моноидом степени 2 (он имеет бесконечный порядок). Элементы этого пластического моноида могут быть записаны как для целых чисел i , j , k , поскольку соотношения показывают, что ba коммутирует как с a , так и с b .${\displaystyle a^{i}b^{j}(ba)^{k}}$

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

Моноид, по сути, то же самое, что и категория с одним объектом.

Точнее, если задан моноид ( M , •) , можно построить малую категорию с единственным объектом, морфизмы которой являются элементами M. Композиция морфизмов задается моноидной операцией  • .

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

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

Моноиды, как и другие алгебраические структуры, также образуют свою собственную категорию Mon , объектами которой являются моноиды, а морфизмами — гомоморфизмы моноидов. ^[8]

Существует также понятие моноидного объекта , которое является абстрактным определением того, что является моноидом в категории. Моноидный объект в Set — это просто моноид.

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

Для последовательности значений типа M с единичным элементом ε и ассоциативной операцией  • операция свертывания определяется следующим образом:

${\displaystyle \mathrm {fold} :M^{*}\rightarrow M=\ell \mapsto {\begin{cases}\varepsilon &{\mbox{if }}\ell =\mathrm {nil} \\m\bullet \mathrm {fold} \,\ell '&{\mbox{if }}\ell =\mathrm {cons} \,m\,\ell '\end{cases}}}$

Кроме того, любая структура данных может быть «свернута» аналогичным образом, учитывая сериализацию ее элементов. Например, результат «сворачивания» бинарного дерева может отличаться в зависимости от обхода дерева в прямом и обратном порядке .

Применение моноидов в информатике — это так называемая модель программирования MapReduce (см. Encoding Map-Reduce As A Monoid With Left folding). MapReduce в вычислениях состоит из двух или трех операций. При наличии набора данных «Map» состоит из отображения произвольных данных на элементы определенного моноида. «Reduce» состоит из свертывания этих элементов, так что в итоге мы получаем только один элемент.

Например, если у нас есть мультимножество , в программе оно представлено как отображение элементов на их номера. В этом случае элементы называются ключами. Количество различных ключей может быть слишком большим, и в этом случае мультимножество сегментируется . Чтобы завершить правильное сокращение, этап «Перемешивание» перегруппировывает данные между узлами. Если нам не нужен этот шаг, весь Map/Reduce состоит из отображения и сокращения; обе операции являются параллелизуемыми, первая из-за ее поэлементной природы, вторая из-за ассоциативности моноида.

Полный моноид — это коммутативный моноид, снабженный бесконечной операцией суммирования для любого набора индексов I , такого что ^{[9] [10] [11] [12]}${\displaystyle \Sigma _{I}}$

${\displaystyle \sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\text{ for }}j\neq k}$

и

${\displaystyle \sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}m_{i}\quad {\text{ if }}\bigcup _{j\in J}I_{j}=I{\text{ and }}I_{j}\cap I_{j'}=\emptyset \quad {\text{ for }}j\neq j'}$.

Упорядоченный коммутативный моноид — это коммутативный моноид M вместе с частичным порядком ≤ таким, что a ≥ 0 для каждого a ∈ M , и a ≤ b влечет a + c ≤ b + c для всех a , b , c ∈ M .

Непрерывный моноид — это упорядоченный коммутативный моноид ( M , ≤), в котором каждое направленное подмножество имеет наименьшую верхнюю границу , и эти наименьшие верхние границы совместимы с операцией моноида:

${\displaystyle a+\sup S=\sup(a+S)}$

для каждого a ∈ M и направленного подмножества S множества M.

Если ( M , ≤) — непрерывный моноид, то для любого множества индексов I и набора элементов ( a _i ) _{i ∈ I} можно определить

${\displaystyle \sum _{I}a_{i}=\sup _{{\text{finite }}E\subset I}\;\sum _{E}a_{i},}$

и M вместе с этой бесконечной операцией суммы является полным моноидом. ^[12]

• Декартов моноид
• отношения Грина
• Монада (функциональное программирование)
• Полукольцо и алгебра Клини
• Проблема высоты звезды
• Ведический квадрат
• Фробениоид

• «Моноид», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. "Моноид". MathWorld .
• Моноид в PlanetMath .