Моноид

Алгебраические структуры
Группа -как Группа Полугруппа / Моноид Стеллаж и quandle Квазигруппа и петля Абелева группа Магма Группа Ли Теория групп
Кольцо -как Звенеть Rng Полукруглый Рядом с кольцом Коммутативное кольцо Интегральный домен Поле Дивизионное кольцо Теория колец
Lattice -как Решетка Полурешетка Дополненная решетка Общий заказ Алгебра Гейтинга Булева алгебра Карта решеток Теория решетки
Модуль- подобный Модуль Группа с операторами Векторное пространство Линейная алгебра
Алгебра- подобный Алгебра Ассоциативный Неассоциативный Составная алгебра Алгебра Ли Оценено Биалгебра
v т е

Алгебраические структуры между магмами и группами . Например, моноиды - это полугруппы с идентичностью.

В абстрактной алгебре , разделе математики , моноид - это набор, снабженный ассоциативной бинарной операцией и элементом идентичности .

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

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

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

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

См. Полугруппу для истории предмета и некоторых других общих свойств моноидов.

Определение [ править ]

Набор S оснащен бинарной операцией $S \times S \to S$ , который мы будем обозначать • является моноид , если она удовлетворяет следующим двум аксиомам:

Ассоциативность: Для всех a , b и c в S выполняется равенство $(a • b) • c = a • (b • c)$ .
Элемент идентичности: Там существует элемент е в S такое , что для любого элемента а в S уравнения $е • с =$ и $•$ $е$ $=$ $в$ трюме.

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

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

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

Моноидные структуры [ править ]

Субмоноиды [ править ]

Подмоноид моноида $(М, •)$ является подмножеством N из M , замкнутая относительно операций моноидных и содержит единичный элемент е из М . ^[2]^[3] Символично, Н является подмоноид M , если $N \subseteq М$ , $х • у \in N$ всякий раз , когда $х, у \in N$ , и $е \in N$ . В этом случае Nявляется моноидом под бинарной операцией , унаследованной от М .

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

Генераторы [ править ]

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

Коммутативный моноид [ править ]

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

Частично коммутативный моноид [ править ]

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

Примеры [ править ]

Из 16 возможных двоичных булевых операторов каждый из четырех, имеющих двустороннюю идентичность, также коммутативен и ассоциативен и, таким образом, делает набор {False, True} коммутативным моноидом. Согласно стандартным определениям, AND и XNOR имеют идентификатор True, а XOR и OR имеют идентификатор False. Моноиды из AND и OR также являются идемпотентными, в то время как моноиды из XOR и XNOR - нет.
Множество натуральных чисел представляет собой коммутативный моноид при сложении (единичный элемент 0 ) или умножении (единичный элемент 1 ). Подмоноид $N$ при сложении называется числовым моноидом . ${\ Displaystyle \ mathbb {N} = \ {0,1,2, \ ldots \}}$
Множество натуральных чисел представляет собой коммутативный моноид относительно умножения (единичный элемент 1). ${\ Displaystyle \ mathbb {N} \ setminus \ {0 \}}$
Для множества $A$ множество подмножеств $A$ является коммутативным моноидом относительно пересечения (единичным элементом является сам $A$ ).
Для множества $A$ множество подмножеств $A$ является коммутативным моноидом относительно объединения (единичный элемент - это пустое множество ).
Обобщая предыдущий пример, любая ограниченная полурешетка является идемпотентным коммутативным моноидом.
- В частности, любую ограниченную решетку можно снабдить структурой как встречного, так и соединительного моноида. Элементами идентичности являются соответственно верх и низ решетки. Будучи решетками, алгебры Гейтинга и булевы алгебры наделены этими структурами моноидов.
Каждое одноэлементное множество ${x},$ замкнутое относительно бинарной операции •, образует тривиальный (одноэлементный) моноид, который также является тривиальной группой .
Каждая группа является моноидом, а каждая абелева группа - коммутативным моноидом.
Любая полугруппа S может быть превращена в моноиде просто присоединяя элемент е не в S и определения е • s = s = s • е для всех s ∈ S . Это преобразование любой полугруппы в моноид осуществляется свободным функтором между категорией полугрупп и категорией моноидов. ^[5]
- Таким образом, идемпотентный моноид (иногда называют находкой-первой ) может быть образован присоединением единичного элемента е к влево нулевой полугруппе над множеством S . Напротив моноид (иногда называемый находкой-последняя ) формируются из правой нулевой полугруппы над S .
  - Присоедините единицу $e$ к полугруппе левых нулей с двумя элементами ${lt, gt}$ . Затем полученный идемпотентный моноид ${lt, e, gt}$ моделирует лексикографический порядок последовательности с учетом порядков ее элементов, где e представляет равенство.
Базовый набор любого кольца с операцией сложения или умножения. (По определению кольцо имеет мультипликативную единицу 1.)
- Эти целые числа , рациональные числа , действительные числа или комплексные числа , с добавлением или умножением в эксплуатацию. ^[6]
- Набор всех матриц размера $n$ на $n$ в данном кольце с операцией сложения или умножения матриц .
Множество всех конечных строк над некоторым фиксированным алфавитом $Σ$ образует моноид с конкатенацией строк в качестве операции. Пустая строка служит в качестве единичного элемента. Этот моноид обозначается $Σ *$ и называется свободным моноидом над $Σ$ .
При любом моноид $М$ , то напротив моноид $М оп$ имеет тот же набор носитель и единичный элемент , как $М$ , и его работа определяется $Купить • оп у = у • х$ . Любой коммутативный моноид - это моноид, противоположный самому себе.
Для двух множеств $M$ и $N,$ наделенных структурой моноидов (или, вообще говоря, любого конечного числа моноидов, $M 1, ..., M k)$ , их декартово произведение $M \times N$ также является моноидом (соответственно $M 1 \times \dots \times M л$ ). Ассоциативная операция и элемент идентичности определяются попарно. ^[7]
Фикс моноид $M$ . Множество всех функций из данного набора в $M$ также является моноидом. Элемент идентичности - это постоянная функция, отображающая любое значение в идентичность $M$ ; ассоциативная операция определяется поточечно .
Исправление моноидных $М$ с операцией $•$ и единичный элементом $е$ , и рассмотрят его набор мощности $P (M)$ , состоящая из всех подмножеств из $М$ . Бинарную операцию для таких подмножеств можно определить как $S • T = {s • t : s \in S, t \in T}$ . Это превращает $P (M)$ в моноид с единицей ${e}$ . Точно так же набор мощности группы $G$ является моноидом относительно произведения подмножеств группы .
Пусть $S$ - множество. Множество всех функций $S \to S$ образует моноид относительно композиции функций . Идентичность - это просто функция идентичности . Он также называется полным преобразованием Моноид из $S$ . Если $S$ конечно с $n$ элементами, моноид функций на $S$ конечен с $n n$ элементами.
Обобщая предыдущий пример, пусть $С$ быть категория и $Х$ объект $C$ . Множество всех эндоморфизмов из $X$ , обозначается $конец С (Х)$ , образует моноид по составу морфизмов . Подробнее о взаимосвязи между теорией категорий и моноидами см. Ниже.
Множество гомеоморфизма классов на компактные поверхности с связной суммой . Единичный элемент - это класс обычной 2-сферы. Кроме того, если $a$ обозначает класс тора , а b обозначает класс проективной плоскости, то каждый элемент c моноида имеет уникальное выражение вида $c = na + mb,$ где $n$ - натуральное число и $m = 0, 1$ или $2$ . Имеем $3 b = a + b$ .
Пусть - циклический моноид порядка $n$ , т. Е .. Тогда для некоторых . Фактически, каждый такой $k$ дает отдельный моноид порядка $n$ , и каждый циклический моноид изоморфен одному из них. Более того, $f$ можно рассматривать как функцию в точках, заданных формулой ${\ displaystyle \ langle f \ rangle}$ ${\ displaystyle \ langle f \ rangle = \ left \ {f ^ {0}, f ^ {1}, \ dots, f ^ {n-1} \ right \}}$ ${\ Displaystyle е ^ {п} = е ^ {к}}$ ${\ Displaystyle 0 \ Leq к <п}$
$\{0,1,2,\dots ,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}}

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

\langle f\rangle

Когда тогда функция

f

является перестановкой и дает единственную циклическую группу порядка

n

.

k=0

\{0,1,2,\dots ,n-1\},

Свойства [ править ]

Из аксиом моноида следует, что единичный элемент $e$ уникален: если $e$ и $f$ - единичные элементы моноида, то $e = ef = f$ .

Продукты и возможности [ править ]

Для каждого неотрицательного целого числа $n$ можно определить произведение любой последовательности из $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}$ $(a_{1},\ldots ,a_{n})$

В качестве частного случая можно определить целые неотрицательные степени элемента $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$ .^[8]

Если $x$ обратим, скажем, с обратным $y$ , то можно определить отрицательные степени $x$ , положив $x - n = y n$ для каждого $n \geq 1$ ; это делает уравнение $х т + п = х м • х п$ выполняться для всех $т, п \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$ . Коммутативный моноид со свойством сокращения всегда может быть вложен в группу с помощью конструкции Гротендика. Таким образом аддитивная группа целых чисел (группа с операцией +) строится из аддитивного моноида натуральных чисел (коммутативный моноид с операцией + и свойством сокращения). Однако некоммутативный сократительный моноид не обязательно должен быть вложен в группу.

Если моноид обладает свойством сокращения и конечен , то это фактически группа. Доказательство. Зафиксируйте элемент x в моноиде. Поскольку моноид конечен, $x n = x m$ для некоторого $m > n > 0$ . Но тогда путем сокращения мы получаем, что $x m - n = e,$ где e - это тождество. Следовательно, $x • x m - n - 1 = e$ , поэтому x имеет обратный.

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

Оказывается, требование свойства сокращения в моноиде не требуется для выполнения конструкции Гротендика - достаточно коммутативности. Однако, если исходный моноид имеет поглощающий элемент, то его группа Гротендика является тривиальной группой. Следовательно, гомоморфизм, вообще говоря, не инъективен.

Типы моноидов [ править ]

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

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

Акты и моноиды операторов [ править ]

Пусть 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 -акты. Моноид с актом также известен как операторный моноид . Важные примеры включают переходные системы из semiautomata . Преобразование полугруппа может быть превращена в операторе моноид присоединения тождественного преобразования.

Гомоморфизмы моноидов [ править ]

Пример гомоморфизма моноида

x \mapsto 2 x

из

(N, +, 0)

в

(N, \times, 1)

. Это инъективно, но не сюръективно.

Гомоморфизм между двумя моноидами $(М, *)$ и $(N, •)$ является функцией $F : M \to N$ такое , что

$f (x * y) = f (x) • f (y)$ для всех x , y в M
$f (e M) = e N$ ,

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

Не каждый гомоморфизм полугрупп между моноидами является гомоморфизмом моноидов, так как он не может отображать идентичность в идентичность целевого моноида, даже если идентичность является идентичностью образа гомоморфизма. ^[10] Например, рассмотрим множество классов вычетов по модулю, снабженное умножением. В частности, классом является тождество. Функция, заданная в, является гомоморфизмом полугрупп, как в . Однако, таким образом, гомоморфизм моноидов - это гомоморфизм полугрупп между моноидами, который отображает идентичность первого моноида в идентичность второго моноида, и последнее условие не может быть опущено. $M_{n}$ $n$ $1$ $f\colon M_{3}\to M_{6}$ $f(k)=3k$ $3k\cdot 3l=9kl=3kl$ $M_{6}$ $f(1)=3\neq 1$

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

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

Формульное представление [ править ]

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

Для бинарного отношения $R \subset Σ * \times Σ *$ его симметричное замыкание определяется как $R \cup R -1$ . Это может быть расширено до симметричного отношения $E \subset Σ * \times Σ *$ , определяя $x \sim 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},\cdots ,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}$

Отношение к теории категорий [ править ]

Групповые структуры
	Целостность ^α	Ассоциативность	Личность	Обратимость	Коммутативность
Полугрупоидный	Ненужный	Обязательный	Ненужный	Ненужный	Ненужный
Малая категория	Ненужный	Обязательный	Обязательный	Ненужный	Ненужный
Группоид	Ненужный	Обязательный	Обязательный	Обязательный	Ненужный
Магма	Обязательный	Ненужный	Ненужный	Ненужный	Ненужный
Квазигруппа	Обязательный	Ненужный	Ненужный	Обязательный	Ненужный
Единая Магма	Обязательный	Ненужный	Обязательный	Ненужный	Ненужный
Петля	Обязательный	Ненужный	Обязательный	Обязательный	Ненужный
Полугруппа	Обязательный	Обязательный	Ненужный	Ненужный	Ненужный
Обратная полугруппа	Обязательный	Обязательный	Ненужный	Обязательный	Ненужный
Моноид	Обязательный	Обязательный	Обязательный	Ненужный	Ненужный
Коммутативный моноид	Обязательный	Обязательный	Обязательный	Ненужный	Обязательный
Группа	Обязательный	Обязательный	Обязательный	Обязательный	Ненужный
Абелева группа	Обязательный	Обязательный	Обязательный	Обязательный	Обязательный
^ α Замыкание, которое используется во многих источниках, является аксиомой, эквивалентной тотальности, хотя и определяется по-другому.

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

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

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

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

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

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

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

Моноиды в информатике [ править ]

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

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

\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 [ править ]

Применение моноидов в информатике - это так называемая модель программирования MapReduce (см. Кодирование Map-Reduce как моноида с левым складыванием ). В вычислениях MapReduce состоит из двух или трех операций. Для данного набора данных «Карта» состоит из сопоставления произвольных данных с элементами определенного моноида. "Reduce" состоит из сворачивания этих элементов, так что в итоге мы получаем только один элемент.

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

Полные моноиды [ править ]

Полная моноид является коммутативным моноид оснащен инфинитарной операцией суммы для любого индекса установлен $я$ так , что: ^[12]^[13]^[14]^[15] $\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'

Непрерывный моноид является упорядоченным коммутативным моноидом , в котором каждое направленном множество имеет минимум верхней границы совместим с операцией моноидной:

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

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

\sum _{I}a_{i}=\sup \sum _{E}a_{i}

где супремум справа пробегает все конечные подмножества $E$ в $I,$ а каждая сумма справа является конечной суммой в моноиде. ^[15]

См. Также [ править ]

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

Заметки [ править ]

^ Если и e _1, и e ₂ удовлетворяют указанным выше уравнениям, то e ₁ = e ₁ • e ₂ = e ₂ .
^ Якобсон 2009 .
^ Некоторые авторы опускают требование подмоноид должен содержать единичный элемент из его определения, требуя толькочто есть в единичный элементе, который может быть отличным от такового М .
^ Гондран, Мишель; Мину, Мишель (2008). Графы, диоиды и полукольца: новые модели и алгоритмы . Серия интерфейсов «Исследование операций / Информатика». 41 . Дордрехт: Springer-Verlag . п. 13. ISBN 978-0-387-75450-5. Zbl 1201.16038 .
^ Родос, Джон; Стейнберг, Бенджамин (2009), q-теория конечных полугрупп: новый подход , Монографии Спрингера по математике, 71 , Springer, с. 22, ISBN 9780387097817.
^ Якобсон 2009 , стр. 29, примеры 1, 2, 4 и 5.
^ Якобсон 2009 , стр. 35.
^ Якобсон, I.5. п. 22
^ Wehrung, Фридрих (1996). «Тензорные произведения структур с интерполяцией» . Тихоокеанский математический журнал . 176 (1): 267–285. Zbl 0865.06010 .
^ $Е (х) * е (е М) = е (х * е М) = е (х)$ для каждого $х$ в $М$ , когда $F$ является полугруппой гомоморфизма и $й М$ являются идентичностью своей области моноида $M$ .
^ a b c Awodey, Стив (2006). Теория категорий . Oxford Logic Guides. 49 . Издательство Оксфордского университета . п. 10. ISBN 0-19-856861-4. Zbl 1100,18001 .
^ Droste, М., & Kuich, W. (2009). Полукольца и формальные степенные ряды. Справочник по взвешенным автоматам , 3–28. DOI : 10.1007 / 978-3-642-01492-5_1 , стр. 7–10
^ Hebisch, Удо (1992). "Eine algebraische Theorie undendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe". Bayreuther Mathematische Schriften (на немецком языке). 40 : 21–152. Zbl 0747.08005 .
^ Куич, Вернер (1990). «ω-непрерывные полукольца, алгебраические системы и автоматы проталкивания». В Патерсоне, Майкл С. (ред.). Автоматы, языки и программирование: 17-й международный коллоквиум, Уорикский университет, Англия, 16-20 июля 1990 г., Труды . Конспект лекций по информатике. 443 . Springer-Verlag . С. 103–110 . ISBN 3-540-52826-1.
^ a b Куич, Вернер (2011). «Алгебраические системы и выталкивающие автоматы». В Kuich, Вернер (ред.). Алгебраические основы информатики. Очерки, посвященные Симеону Бозапалидису по случаю его выхода на пенсию . Конспект лекций по информатике. 7020 . Берлин: Springer-Verlag . С. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135 .

Ссылки [ править ]

Хауи, Джон М. (1995), Основы теории полугрупп , Монографии Лондонского математического общества. Новая серия, 12 , Оксфорд: Clarendon Press, ISBN 0-19-851194-9, Zbl 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 по математике, 29 , Берлин: Walter de Gruyter, ISBN 3-11-015248-7, Zbl 0945,20036
Lothaire, M. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, 17 , Perrin, D .; Reutenauer, C .; Berstel, J .; Пин, JE; Pirillo, G .; Foata, D .; Сакарович, Дж .; Саймон, I .; Шютценбергер, депутат; Choffrut, C .; Cori, R .; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , doi : 10.1017 / CBO9780511566097 , ISBN 0-521-59924-5, MR 1475463 , Zbl 0874.20040

Внешние ссылки [ править ]

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

[1] Если и e _1, и e ₂ удовлетворяют указанным выше уравнениям, то e ₁ = e ₁ • e ₂ = e ₂ .

[FOOTNOTEJacobson2009-2] Якобсон 2009 .

[3] Некоторые авторы опускают требование подмоноид должен содержать единичный элемент из его определения, требуя толькочто есть в единичный элементе, который может быть отличным от такового М .

[4] Гондран, Мишель; Мину, Мишель (2008). Графы, диоиды и полукольца: новые модели и алгоритмы . Серия интерфейсов «Исследование операций / Информатика». 41 . Дордрехт: Springer-Verlag . п. 13. ISBN 978-0-387-75450-5. Zbl 1201.16038 .

[5] Родос, Джон; Стейнберг, Бенджамин (2009), q-теория конечных полугрупп: новый подход , Монографии Спрингера по математике, 71 , Springer, с. 22, ISBN 9780387097817.

[FOOTNOTEJacobson200929,_examples_1,_2,_4_&_5-6] Якобсон 2009 , стр. 29, примеры 1, 2, 4 и 5.

[FOOTNOTEJacobson200935-7] Якобсон 2009 , стр. 35.

[8] Якобсон, I.5. п. 22

[9] Wehrung, Фридрих (1996). «Тензорные произведения структур с интерполяцией» . Тихоокеанский математический журнал . 176 (1): 267–285. Zbl 0865.06010 .

[10] $Е (х) * е (е М) = е (х * е М) = е (х)$ для каждого $х$ в $М$ , когда $F$ является полугруппой гомоморфизма и $й М$ являются идентичностью своей области моноида $M$ .

[Awo10-11] Awodey, Стив (2006). Теория категорий . Oxford Logic Guides. 49 . Издательство Оксфордского университета . п. 10. ISBN 0-19-856861-4. Zbl 1100,18001 .

[droste-12] Droste, М., & Kuich, W. (2009). Полукольца и формальные степенные ряды. Справочник по взвешенным автоматам , 3–28. DOI : 10.1007 / 978-3-642-01492-5_1 , стр. 7–10

[13] Hebisch, Удо (1992). "Eine algebraische Theorie undendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe". Bayreuther Mathematische Schriften (на немецком языке). 40 : 21–152. Zbl 0747.08005 .

[14] Куич, Вернер (1990). «ω-непрерывные полукольца, алгебраические системы и автоматы проталкивания». В Патерсоне, Майкл С. (ред.). Автоматы, языки и программирование: 17-й международный коллоквиум, Уорикский университет, Англия, 16-20 июля 1990 г., Труды . Конспект лекций по информатике. 443 . Springer-Verlag . С. 103–110 . ISBN 3-540-52826-1.

[Kuich11-15] Куич, Вернер (2011). «Алгебраические системы и выталкивающие автоматы». В Kuich, Вернер (ред.). Алгебраические основы информатики. Очерки, посвященные Симеону Бозапалидису по случаю его выхода на пенсию . Конспект лекций по информатике. 7020 . Берлин: Springer-Verlag . С. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135 .