Моноид

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

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

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

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

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

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

Определение

Множество $S,$ снабженное бинарной операцией $S$ $\times$ $S$ $\to$ $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$ $\in$ $N$ $\subseteq$ $M$ , и $x$ $•$ $y$ $\in$ $N$ всякий раз, когда x $,$ $y$ $\in$ $N$ $.$ В этом случае $N$ является моноидом относительно бинарной операции, унаследованной от $M$ .

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

Генераторы

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

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

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

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

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

Примеры

Из 16 возможных бинарных булевых операторов четыре имеют двустороннюю идентичность, которая также коммутативна и ассоциативна. Каждый из этих четырех делает множество ${False, True}$ коммутативным моноидом. Согласно стандартным определениям, AND и XNOR имеют идентичность $True$ , а XOR и OR имеют идентичность $False$ . Моноиды из AND и OR также идемпотентны , а из XOR и XNOR — нет.
Множество натуральных чисел $N = {0, 1, 2, ...}$ является коммутативным моноидом относительно сложения (элемент единицы ) или умножения (элемент единицы 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 1, ..., M k$ ), их декартово произведение $M \times N$ с бинарной операцией и элементом тождества, определенными на соответствующих координатах, называемое прямым произведением , также является моноидом (соответственно, $M 1 \times \cdot\cdot\cdot \times M k$ ). ^[5]
Зафиксируем моноид $M.$ Множество всех функций из заданного множества в $M$ также является моноидом. Элемент тождества — это постоянная функция, отображающая любое значение в тождество $M$ ; ассоциативная операция определяется поточечно .
Зафиксируем моноид $M$ с операцией $•$ и единичным элементом $e$ и рассмотрим его множество $P (M),$ состоящее из всех подмножеств M. Бинарная операция для таких подмножеств может быть определена как $S$ $•$ $T$ $=$ ${$ $s$ $•$ $t$ $:$ $s\inS$ $,$ $t\inT$ $}$ $.$ Это превращает $P$ $($ $M$ $)$ $в$ моноид с единичным элементом ${$ $e$ $}$ $.$ Точно так же множество группы $G$ $является$ моноидом относительно произведения подмножеств группы .
Пусть $S$ — множество. Множество всех функций $S \to S$ образует моноид относительно композиции функций . Тождество — это просто тождественная функция . Его также называют полным моноидом преобразований S. Если $S$ конечно с $n элементами,$ $то$ моноид функций на $S$ конечен с $n$ $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 0, f 1, ..., f n -1}$ . Тогда $f n = f k$ для некоторого $0 \leq k < n$ . Каждое такое $k$ дает отдельный моноид порядка $n$ , и каждый циклический моноид изоморфен одному из них.
Более того, $f$ можно рассматривать как функцию от точек ${0, 1, 2, ..., n -1},$ заданную формулой

${\begin{bmatrix}0&1&2&\cdots &n-2&n-1\\1&2&3&\cdots &n-1&k\end{bmatrix}}$ или, что то же самое $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$ $1$ $, ...,$ $an$ $)$ $из$ n $элементов$ моноида: пусть $p$ $0$ $=$ $e$ и пусть $p$ $m$ $=$ $p$ $m$ $-1$ $•$ $a$ $m$ для $1 \leq$ $m$ $\leq$ $n$ . $p_{n}=\textstyle \prod _{i=1}^{n}a_{i}$

В качестве частного случая можно определить неотрицательные целые степени элемента $x$ моноида: $x 0 = 1$ и $x n = x n -1 • x$ для $n \geq 1.$ Тогда $x m + n = x m • x n$ для всех $m, n \geq 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$ для каждого $n \geq 1$ ; это делает уравнение $x m + n = x m • x n$ верным для всех $m, n \in 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 \neq c$ . В частности, если моноид имеет поглощающий элемент , то его группа Гротендика является тривиальной группой .

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

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

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

Действия и операторные моноиды

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

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

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

Моноидные гомоморфизмы

Гомоморфизм между двумя моноидами $($ M $, *)$ и $($ $N$ $, •)$ — это функция $f$ $:$ $M$ $\to$ $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] 3 \to [Z] 6 ,$ заданная формулой $[k] 3 \mapsto [3 k] 6$ , является гомоморфизмом полугрупп, поскольку $[3 k \cdot 3 l] 6 = [9 kl] 6 = [3 kl] 6$ . Однако $f ([1] 3) = [3] 6 \neq [1] 6$ , поэтому гомоморфизм моноидов является полугрупповым гомоморфизмом между моноидами, который отображает тождество первого моноида в тождество второго моноида, и последнее условие не может быть опущено.

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

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

Эквациональное представление

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

Для бинарного отношения $R \subset Σ * \times Σ *$ определяется его симметричное замыкание как $R \cup R -1$ . Это можно расширить до симметричного отношения $E \subset Σ * \times Σ * ,$ определив $x ~ E y$ тогда и только тогда, когда $x = sut$ и $y = svt$ для некоторых строк $u, v, s, t \in Σ *$ с $(u, v) \in R \cup R -1$ . Наконец, берется рефлексивное и транзитивное замыкание $E$ , которое затем является моноидной конгруэнцией.

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

\langle p,q\,\vert \;pq=1\rangle

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

\langle a,b\,\vert \;aba=baa,bba=bab\rangle

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

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

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

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

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

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

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

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

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

Моноиды в информатике

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

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

\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] $\Sigma _{I}$

\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

\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$ вместе с частичным порядком $\leq$ таким, что $a \geq 0$ для каждого $a \in M$ , и $a \leq b$ влечет $a + c \leq b + c$ для всех $a, b, c \in M$ .

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

a+\sup S=\sup(a+S)

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

Если $(M, \leq)$ — непрерывный моноид, то для любого множества индексов $I$ и набора элементов $(a i) i \in I$ можно определить

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

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

Смотрите также

Примечания

^ Если и $e 1 ,$ и $e 2$ удовлетворяют приведенным выше уравнениям, то $e 1 = e 1 • e 2 = e 2$ .
^ Некоторые авторы опускают требование, чтобы подмоноид обязательно содержал единичный элемент из своего определения, требуя только, чтобы он имел единичный элемент, который может отличаться от элемента $M.$
^ Доказательство: Зафиксируем элемент $x$ в моноиде. Поскольку моноид конечен, $x n = x m$ для некоторого $m > n > 0.$ Но тогда, сокращая, мы получаем, что $x m - n = e$ , где $e$ — единица. Следовательно, $x • x m - n -1 = e$ , так что $x$ имеет обратный элемент.
^ $f (x) * f (e M) = f (x * e M) = f (x)$ для каждого $x$ из $M$ , когда $f$ является гомоморфизмом полугруппы, а $e M$ является единицей его моноида области $M$ .

Цитаты

^ Якобсон 2009
^ Гондрана и Мину 2008, стр. 13
^ Родс и Стейнберг 2009, стр. 22
^ Якобсон 2009, стр. 29, примеры 1, 2, 4 и 5
^ Якобсон 2009, стр. 35
^ Якобсон 2009, стр. 31, §1.2
^ Верунг 1996
^ abc Awodey 2006, стр. 10
^ Дросте и Куич 2009, стр. 7–10.
^ Хебиш 1992
^ Куич 1990
^ ab Kuich 2011.

Ссылки

Аводей, Стив (2006). Теория категорий . Oxford Logic Guides. Том 49. Oxford University Press . ISBN 0-19-856861-4. Збл 1100.18001.
Droste, M.; Kuich, W (2009), "Полукольца и формальные степенные ряды", Handbook of Weighted Automata , стр. 3–28, CiteSeerX 10.1.1.304.6152 , doi :10.1007/978-3-642-01492-5_1
Gondran, Michel; Minoux, Michel (2008). Графы, диоиды и полукольца: новые модели и алгоритмы . Серия Operations Research/Computer Science Interfaces. Том 41. Дордрехт: Springer-Verlag . ISBN 978-0-387-75450-5. Збл 1201.16038.
Хебиш, Удо (1992). «Eine алгебраическая теория unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe». Bayreuther Mathematische Schriften (на немецком языке). 40 : 21–152. Збл 0747.08005.
Хауи, Джон М. (1995), Основы теории полугрупп , Монографии Лондонского математического общества. Новая серия, т. 12, Оксфорд: Clarendon Press, ISBN 0-19-851194-9, Збл 0835.20077
Якобсон, Натан (1951), Лекции по абстрактной алгебре , т. I, D. Van Nostrand Company, ISBN 0-387-90122-1
Якобсон, Натан (2009), Основы алгебры , т. 1 (2-е изд.), Довер, ISBN 978-0-486-47189-1
Килп, Мати; Кнауэр, Ульрих; Михалев, Александр В. (2000), Моноиды, акты и категории. С приложениями к сплетениям и графам. Справочник для студентов и исследователей , de Gruyter Expositions in Mathematics, т. 29, Берлин: Walter de Gruyter, ISBN 3-11-015248-7, ЗБЛ 0945.20036
Kuich, Werner (1990). "ω-непрерывные полукольца, алгебраические системы и автоматы с магазинной памятью". В Paterson, Michael S. (ред.). Автоматы, языки и программирование: 17-й международный коллоквиум, Уорикский университет, Англия, 16–20 июля 1990 г., Труды . Конспект лекций по информатике. Том 443. Springer-Verlag . С. 103–110. ISBN 3-540-52826-1.
Kuich, Werner (2011). «Алгебраические системы и автоматы с магазинной памятью». В Kuich, Werner (ред.). Алгебраические основы в информатике. Эссе, посвященные Симеону Бозапалидису по случаю его выхода на пенсию . Конспект лекций по информатике. Том 7020. Берлин: Springer-Verlag . С. 228–256. ISBN 978-3-642-24896-2. Збл 1251.68135.
Лотер, М. , ред. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, т. 17 (2-е изд.), Cambridge University Press , doi : 10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR 1475463, Zbl 0874.20040
Родс, Джон; Стейнберг, Бенджамин (2009), Q-теория конечных полугрупп: новый подход , Springer Monographs in Mathematics, т. 71, Springer, ISBN 9780387097817
Верунг, Фридрих (1996). «Тензорные произведения структур с интерполяцией». Pacific Journal of Mathematics . 176 (1): 267–285. doi : 10.2140/pjm.1996.176.267 . S2CID 56410568. Zbl 0865.06010.

Внешние ссылки

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