Введение

Алгебраическая структура с ассоциативной операцией и единичным элементом, моноидные объекты в теории категорий.

В абстрактной алгебре, ветви математики, моноид — это множество, снабжённое ассоциативной бинарной операцией и единичным элементом. Например, неотрицательные целые числа с операцией сложения образуют моноид, единичным элементом которого является 0. Моноиды — это полугруппы с единичным элементом. Такие алгебраические структуры встречаются в различных областях математики. Функции из множества в себя образуют моноид относительно композиции функций. В более общем смысле, в теории категорий, морфизмы объекта в самого себя образуют моноид, и, наоборот, моноид можно рассматривать как категорию с единственным объектом. В информатике и программировании множество строк, построенных из заданного набора символов, является свободным моноидом. Переходные моноиды и синтаксические моноиды используются при описании конечных автоматов. Моноиды следов и моноиды истории служат основой для исчислений процессов и параллельных вычислений. В теоретической информатике изучение моноидов фундаментально для теории автоматов (теория Крона — Роудса) и теории формальных языков (проблема высоты звезды). См. статью «Полугруппа» для истории предмета и некоторых других общих свойств моноидов.

Субмоноиды

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

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

Генераторы

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

Коммутативный моноид

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

Частично коммутативный моноид

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

Свойства

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

Продукты и мощности

Для каждого неотрицательного целого числа n можно определить произведение любой последовательности (a₁, …, aₙ) из n элементов моноида рекурсивно: пусть p₀ = e и pₘ = pₘ₋₁ • aₘ для 1 ≤ m ≤ n.

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

Обратные элементы

Элемент x называется обратимым, если существует элемент y, такой что 1 = x • y = e и 1 = y • x = e. Элемент y называется обратным к x. Обратные элементы, если они существуют, уникальны: если y и z – обратные к x, то по ассоциативности 1 = y = ey = (zx)y = z(xy) = ze = z. Если x обратим, скажем, с обратным y, то можно определить отрицательные степени x, полагая x^(−n) = y^(n) для каждого n ≥ 1; это обеспечивает справедливость уравнения 1 = x^(m+n) = x^(m) • x^(n) для всех m, n ∈ 'Z'. Множество всех обратимых элементов в моноиде вместе с операцией • образует группу.

Группа Grothendieck

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

Коммутативный моноид с свойством сократимости всегда можно вложить в группу с помощью построения группы Гротендика. Именно так аддитивная группа целых чисел (группа с операцией +) строится из аддитивного моноида натуральных чисел (коммутативный моноид с операцией + и свойством сократимости). Однако некоммутативный сократимый моноид не обязательно можно вложить в группу. Если моноид обладает свойством сократимости и является конечным, то он, по сути, является группой. Правые и левые сократимые элементы моноида, каждый по отдельности, образуют подмоноид (то есть замкнуты относительно операции и, очевидно, включают единичный элемент). Это означает, что сократимые элементы любого коммутативного моноида можно расширить до группы. Для выполнения построения Гротендика не требуется свойство сократимости в моноиде – достаточно коммутативности. Однако, если коммутативный моноид не обладает свойством сократимости, гомоморфизм моноида в его группу Гротендика не является инъективным. Более точно, если 1 = a • b = a • c, то b и c имеют один и тот же образ в группе Гротендика, даже если b ≠ c. В частности, если моноид имеет поглощающий элемент, то его группа Гротендика является тривиальной группой.

Типы моноидов

Инверсный моноид — это моноид, в котором для каждого элемента a из M существует единственный элемент a^(−1) из M, такой что 1=a = a • a^(−1) • a и 1=a^(−1) = a^(−1) • a • a^(−1). Если инверсный моноид является сократимым, то он является группой. В противоположном направлении, моноид без элементов, дающих в сумме ноль, — это моноид, записанный аддитивно, в котором из равенства 1=a + b = 0 следует, что 1=a = 0 и 1=b = 0: эквивалентно, что ни один элемент, отличный от нуля, не имеет аддитивного обратного.

Отношение к теории категорий

Моноиды можно рассматривать как особый класс категорий. Действительно, аксиомы, предъявляемые к моноидной операции, в точности соответствуют аксиомам композиции морфизмов, когда она ограничена множеством всех морфизмов, у которых источник и область значений – один и тот же объект. Иначе говоря, моноид, по сути, является тем же самым, что и категория с единственным объектом. Более точно, для заданного моноида (M, •) можно построить малую категорию, содержащую только один объект, а морфизмами которой будут элементы M. Композиция морфизмов определяется моноидной операцией •. Соответственно, гомоморфизмы моноидов – это просто функторы между категориями с одним объектом. Таким образом, эта конструкция устанавливает эквивалентность между категорией (малых) моноидов Mon и полной подкатегорией категории (малых) категорий Cat. Аналогично, категория групп эквивалентна другой полной подкатегории Cat. В этом смысле категорию теории можно рассматривать как обобщение понятия моноида. Многие определения и теоремы о моноидах можно обобщить на малые категории, содержащие более одного объекта. Например, факторкатегория категории с одним объектом – это просто фактормоноид. Моноиды, как и другие алгебраические структуры, сами образуют категорию Mon, объекты которой – моноиды, а морфизмы – гомоморфизмы моноидов. Также существует понятие моноидного объекта, которое представляет собой абстрактное определение моноида в категории. Моноидный объект в множествах (Set) – это просто моноид.

Карта

Применение моноидов в информатике – это так называемая модель программирования MapReduce (см. Кодирование Map Reduce как моноид с левым свёртыванием). MapReduce в вычислительной технике состоит из двух или трёх операций. Для заданного набора данных операция "Map" (отображение) заключается в сопоставлении произвольных данных элементам конкретного моноида. Операция "Reduce" (свёртывание) заключается в последовательном применении операции моноида к этим элементам, чтобы в итоге получить единственный элемент. Например, если у нас есть мультимножество, в программе оно представляется как отображение элементов на их счётчики. Элементы в этом случае называются ключами. Количество различных ключей может быть слишком велико, и в этом случае мультимножество разбивается на части. Для корректного завершения свёртывания этап "перемешивания" (shuffling) перегруппирует данные между узлами. Если этот этап не требуется, то весь процесс Map/Reduce состоит только из операций отображения и свёртывания; обе операции могут выполняться параллельно, первая – благодаря своей поэлементной природе, вторая – благодаря ассоциативности моноида.