Введение

Алгебраическая структура, состоящая из множества с ассоциативной бинарной операцией.

В математике полугруппа — это алгебраическая структура, состоящая из множества вместе с ассоциативной внутренней бинарной операцией, определенной на нем. Бинарная операция полугруппы чаще всего обозначается мультипликативно (это лишь обозначение, не обязательно элементарное арифметическое умножение): x ⋅ y или просто xy обозначает результат применения операции полугруппы к упорядоченной паре (x, y). Ассоциативность формально выражается тем, что (x ⋅ y) ⋅ z = x ⋅ (y ⋅ z) для всех x, y и z в полугруппе. Полугруппы можно рассматривать как частный случай магм, где операция ассоциативна, или как обобщение групп, не требующее существования нейтрального элемента или обратных элементов. Как и в случае групп или магм, операция полугруппы не обязана быть коммутативной, поэтому x ⋅ y не обязательно равно y ⋅ x; хорошо известный пример операции, которая ассоциативна, но не коммутативна, — умножение матриц. Если операция полугруппы коммутативна, то полугруппа называется коммутативной полугруппой или (реже, чем в аналогичном случае групп) абелевой полугруппой. Моноид — это алгебраическая структура, занимающая промежуточное положение между полугруппами и группами, и является полугруппой, обладающей нейтральным элементом, таким образом, удовлетворяющей всем аксиомам группы, кроме одной: наличие обратных элементов не требуется для моноида. Природным примером служат строки с конкатенацией в качестве бинарной операции и пустая строка в качестве нейтрального элемента. Ограничение на непустые строки дает пример полугруппы, которая не является моноидом. Положительные целые числа с операцией сложения образуют коммутативную полугруппу, которая не является моноидом, в то время как неотрицательные целые числа образуют моноид. Полугруппу без нейтрального элемента можно легко превратить в моноид, просто добавив нейтральный элемент. Следовательно, моноиды изучаются в теории полугрупп, а не в теории групп. Полугруппы не следует путать с квазигруппами, которые являются обобщением групп в другом направлении; операция в квазигруппе не обязана быть ассоциативной, но квазигруппы сохраняют от групп понятие деления. Деление в полугруппах (или моноидах) в общем случае невозможно. Формальное изучение полугрупп началось в начале XX века. Ранние результаты включают теорему Кэли для полугрупп, представляющую любую полугруппу как полугруппу преобразований, в которой произвольные функции заменяют роль биекций в теории групп. Глубокий результат в классификации конечных полугрупп — теория Крона — Родеса, аналогичная разложению Иордана — Гёльдера для конечных групп. Некоторые другие методы изучения полугрупп, такие как отношения Грина, не имеют аналогов в теории групп. Теория конечных полугрупп имеет особое значение в теоретической информатике с 1950-х годов благодаря естественной связи между конечными полугруппами и конечными автоматами через синтаксический моноид. В теории вероятностей полугруппы связаны с марковскими процессами. В других областях прикладной математики полугруппы являются фундаментальными моделями для линейных стационарных систем. В уравнениях в частных производных полугруппа связана с любым уравнением, пространственная эволюция которого не зависит от времени. Существует множество специальных классов полугрупп, полугрупп с дополнительными свойствами, которые возникают в конкретных приложениях. Некоторые из этих классов даже ближе к группам, обладая некоторыми, но не всеми свойствами группы. К ним относятся: регулярные полугруппы, ортодоксальные полугруппы, полугруппы с инволюцией, обратные полугруппы и отменяющие полугруппы. Существуют также интересные классы полугрупп, которые не содержат никаких групп, кроме тривиальной группы; примерами последнего вида являются ленты и их коммутативный подкласс — полурешетки, которые также являются упорядоченными алгебраическими структурами.

Примеры полугрупп

Пустая полугруппа: пустое множество образует полугруппу с пустой функцией в качестве бинарной операции. Полугруппа с одним элементом: существует по существу только одна (в частности, только одна с точностью до изоморфизма) – одноэлементное множество {a} с операцией a · a = a.
Полугруппа с двумя элементами: существует пять существенно различных полугрупп. Моноид "flip flop": полугруппа с тремя элементами, представляющая три операции над переключателем – установить, сбросить и ничего не делать. Множество положительных целых чисел с операцией сложения. (С включением 0 это становится моноидом.) Множество целых чисел с операцией взятия минимума или максимума. (С включением положительной или отрицательной бесконечности это становится моноидом.) Квадратные неотрицательные матрицы заданного размера с операцией матричного умножения. Любой идеал кольца с операцией умножения кольца. Множество всех конечных строк над фиксированным алфавитом Σ с операцией конкатенации строк – так называемая "свободная полугруппа над Σ". С включением пустой строки эта полугруппа становится свободным моноидом над Σ. Распределение вероятностей F вместе со всеми свёртками F, с операцией свёртки. Это называется полугруппой свёртки. Полугруппы и моноиды преобразований. Множество непрерывных функций из топологического пространства в себя с операцией композиции функций образует моноид, в котором тождественная функция является нейтральным элементом. В более общем смысле, эндоморфизмы любого объекта категории образуют моноид относительно композиции. Произведение граней расположения гиперплоскостей.

Идентичность и ноль

Левое нейтральное элемент полугруппы S (или, в более общем случае, магмы) — это элемент e, такой что для всех x из S выполняется 1 = e ⋅ x = x. Аналогично, правое нейтральное элемент — это элемент f, такой что для всех x из S выполняется 1 = x ⋅ f = x. Левые и правые нейтральные элементы вместе называются односторонними нейтральными элементами. Полугруппа может иметь один или несколько левых нейтральных элементов, но не иметь правого нейтрального элемента, и наоборот. Двусторонний нейтральный элемент (или просто нейтральный элемент) — это элемент, который является одновременно и левым, и правым нейтральным элементом. Полугруппы, имеющие двусторонний нейтральный элемент, называются моноидами. Полугруппа может иметь не более одного двустороннего нейтрального элемента. Если полугруппа имеет двусторонний нейтральный элемент, то этот двусторонний нейтральный элемент является единственным односторонним нейтральным элементом в полугруппе. Если полугруппа имеет как левый, так и правый нейтральные элементы, то она имеет двусторонний нейтральный элемент (который, следовательно, является единственным односторонним нейтральным элементом). Полугруппу S без нейтрального элемента можно вложить в моноид, образованный добавлением элемента e ∉ S к S и определением 1 = e ⋅ s = s ⋅ e = s для всех s. Обозначение S¹ обозначает моноид, полученный из S добавлением нейтрального элемента, если это необходимо (1 = S¹ = S для моноида). Аналогично, каждая магма имеет не более одного поглощающего элемента, который в теории полугрупп называется нулем. По аналогии с вышеуказанной конструкцией, для каждой полугруппы S можно определить S⁰, полугруппу с 0, которая вкладывает S.

Коэффициенты и деления

Следующие понятия вводят идею о том, что полугруппа содержится в другой. Полугруппа T является фактор-полугруппой полугруппы S, если существует сюръективный морфизм полугрупп из S в T. Например, (Z/2Z, +) является фактор-полугруппой (Z/4Z, +), используя морфизм, состоящий в вычислении остатка от деления на 2 целого числа. Полугруппа T делит полугруппу S, обозначается T ≼ S, если T является фактор-полугруппой подполугруппы S. В частности, подполугруппы S делят T, однако не обязательно существует фактор-полугруппа S. Оба этих отношения транзитивны.

Структура полугрупп

Для любого подмножества A множества S существует наименьшая подполугруппа T множества S, содержащая A, и мы говорим, что A порождает T. Один элемент x множества S порождает подполугруппу, состоящую из степеней x. Если эта подполугруппа конечна, то x называется элементом конечного порядка, иначе – бесконечного порядка. Полугруппа называется периодической, если все ее элементы имеют конечный порядок. Полугруппа, порожденная одним элементом, называется моногенной (или циклической). Если моногенная полугруппа бесконечна, то она изоморфна полугруппе положительных целых чисел с операцией сложения. Если она конечна и непуста, то она должна содержать по крайней мере один идемпотент. Следовательно, каждая непустая периодическая полугруппа имеет по крайней мере один идемпотент. Подполугруппа, которая также является группой, называется подгруппой. Существует тесная связь между подгруппами полугруппы и ее идемпотентами. Каждая подгруппа содержит ровно один идемпотент, а именно – нейтральный элемент подгруппы. Для каждого идемпотента e полугруппы существует единственная максимальная подгруппа, содержащая e. Каждая максимальная подгруппа возникает таким образом, поэтому существует взаимно однозначное соответствие между идемпотентами и максимальными подгруппами. Здесь термин "максимальная подгруппа" отличается от его стандартного использования в теории групп. Часто можно сказать больше, когда порядок конечен. Например, каждая непустая конечная полугруппа является периодической и имеет минимальный идеал и по крайней мере один идемпотент. Количество конечных полугрупп заданного размера (большего 1) (очевидно) больше, чем количество групп того же размера. Например, из шестнадцати возможных "таблиц умножения" для множества из двух элементов {a, b} восемь образуют полугруппы, в то время как только четыре из них являются моноидами и только две – группами. Более подробно о структуре конечных полугрупп см. теорию Крона — Роудса.

Специальные классы полугрупп

Моноид — это полугруппа с элементом нейтрали. Группа — это моноид, в котором каждый элемент имеет обратный элемент. Подполугруппа — это подмножество полугруппы, замкнутое относительно операции полугруппы. Отменяющая полугруппа — это полугруппа, обладающая свойством отмены: если a · b = a · c, то b = c, и аналогично, если b · a = c · a, то b = c. Каждая группа является отменяющей полугруппой, и каждая конечная отменяющая полугруппа является группой. Полоса — это полугруппа, операция которой идемпотентна. Полурешётка — это полугруппа, операция которой идемпотентна и коммутативна. 0 простых полугрупп. Полугруппы преобразований: любая конечная полугруппа S может быть представлена преобразованиями множества Q (состояний), содержащего не более состояний. Каждый элемент x из S отображает Q в себя: x: Q → Q, а последовательность xy определяется как q(xy) = (qx)y для каждого q из Q. Последовательное применение является ассоциативной операцией, здесь эквивалентной композиции функций. Это представление является базовым для любого автомата или машины с конечным числом состояний (FSM). Бициклическая полугруппа фактически является моноидом, который можно описать как свободную полугруппу на двух образующих p и q, с соотношением pq = 1. Полугруппы C0. Регулярные полугруппы. Каждый элемент x имеет хотя бы один обратный элемент y, удовлетворяющий условиям xyx = x и yxy = y; элементы x и y иногда называют "взаимно обратными". Обратные полугруппы — это регулярные полугруппы, в которых каждый элемент имеет ровно один обратный элемент. Кроме того, регулярная полугруппа является обратной тогда и только тогда, когда любые два идемпотента коммутируют. Аффинная полугруппа: полугруппа, изоморфная конечно порожденной подполугруппе Zd. Эти полугруппы находят применение в коммутативной алгебре.

Теорема структуры для коммутативных полугрупп

Существует теорема о структуре коммутативных полугрупп, выраженная через полурешетки. Полурешетка (или, точнее, полурешетка пересечения) (L, ≤) – частично упорядоченное множество, в котором для каждой пары элементов a, b ∈ L существует наибольшая нижняя граница, обозначаемая a ∧ b. Операция ∧ делает L полугруппой, удовлетворяющей дополнительному закону идемпотентности 1 = a ∧ a = a. Если задан гомоморфизм f : S → L из произвольной полугруппы в полурешетку, то каждый прообраз является (возможно, пустым) полугруппой. Более того, полугруппа S становится градуированной по L, в том смысле, что SaSb ⊆ Sa∧b. Если f является сюръективным, то полурешетка L изоморфна фактор-полугруппе S по отношению эквивалентности ~ такому, что x ~ y тогда и только тогда, когда 1 = f(x) = f(y). Это отношение эквивалентности является полугрупповой конгруэнтностью, как определено выше. Каждый раз, когда мы берем фактор-полугруппу коммутативной полугруппы по конгруэнтности, мы получаем другую коммутативную полугруппу. Теорема о структуре утверждает, что для любой коммутативной полугруппы S существует наибольшая конгруэнтность ~ такая, что фактор-полугруппа S по этому отношению эквивалентности является полурешеткой. Обозначая эту полурешетку L, мы получаем гомоморфизм f из S на L. Как уже упоминалось, S становится градуированной этой полурешеткой. Кроме того, компоненты Sa являются всеми архимедовыми полугруппами. Архимедовой полугруппой называется такая, в которой для любой пары элементов x, y существует элемент z и n > 0 такие, что 1 = xⁿ = yz. Архимедово свойство следует непосредственно из упорядочения в полурешетке L, поскольку при этом упорядочении f(x) ≤ f(y) тогда и только тогда, когда 1 = xⁿ = yz для некоторых z и n > 0.

Группа дробей

Группа дробей или групповое завершение полугруппы S – это группа G = G(S), порожденная элементами S как образующими и всеми уравнениями xy = z, которые выполняются в S как соотношениями. Существует очевидный гомоморфизм полугрупп j : S → G(S), который отображает каждый элемент S в соответствующий образующий. Это обладает универсальным свойством для морфизмов из S в группу: для любой группы H и любого гомоморфизма полугрупп k : S → H существует единственный гомоморфизм группы f : G → H такой, что k = fj. Можно рассматривать G как "наиболее общую" группу, содержащую гомоморфный образ S. Важным вопросом является характеризация полугрупп, для которых это отображение является вложением. Это не всегда имеет место: например, пусть S – полугруппа подмножеств некоторого множества X, где бинарной операцией является теоретико-множественное пересечение (это пример полурешетки). Поскольку A ∩ A = A для всех элементов S, это должно выполняться и для всех образующих G(S), что, следовательно, означает, что G(S) является тривиальной группой. Для вложимости необходимо, чтобы S обладала свойством сократимости. Когда S коммутативна, это условие также достаточно, и группа Гротендика полугруппы предоставляет построение группы дробей. Проблема для некоммутативных полугрупп восходит к первой значительной работе о полугруппах. Анатолий Мальцев дал необходимые и достаточные условия для вложимости в 1937 году.

История

Изучение полугрупп отставало от изучения других алгебраических структур с более сложными аксиомами, таких как группы или кольца. Ряд источников приписывают первое использование термина (на французском языке) Ж. А. де Сегье в "Элементах теории абстрактных групп" в 1904 году. Термин был использован в английском языке в 1908 году в работе Гарольда Хинтона "Теория групп конечного порядка". Антон Сушкевич получил первые нетривиальные результаты о полугруппах. Его статья 1928 года "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit" ("О конечных группах без закона однозначной обратимости") определила структуру конечных простых полугрупп и показала, что минимальный идеал (или J-класс отношений Грина) конечной полугруппы является простым. На алгебраической конференции в 1972 году Шейн представил обзор литературы по BA – полугруппе отношений на множестве A. В 1997 году Шейн и Ральф Маккензи доказали, что каждая полугруппа изоморфна транзитивной полугруппе бинарных отношений. В последние годы исследователи в этой области стали более специализироваться, и появились отдельные монографии, посвященные важным классам полугрупп, таким как обратные полугруппы, а также монографии, фокусирующиеся на приложениях в алгебраической теории автоматов, особенно для конечных автоматов, и в функциональном анализе.

Обобщения

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

Обобщая в другом направлении, n-арная полугруппа (также n-полугруппа, полиадическая полугруппа или многоарная полугруппа) является обобщением полугруппы на множество G с n-арной операцией вместо бинарной. Закон ассоциативности обобщается следующим образом: тройная ассоциативность выражается как 1 = (abc)de = a(bcd)e = ab(cde), то есть строка abcde с любыми тремя соседними элементами, заключенными в скобки. n-арная ассоциативность – это строка длиной n + (n − 1) с любыми n соседними элементами, заключенными в скобки. 2-арная полугруппа – это просто полугруппа. Дополнительные аксиомы приводят к n-арной группе. Третье обобщение – полугруппоид, в котором снимается требование полноты бинарного отношения. Поскольку категории обобщают моноиды аналогичным образом, полугруппоид ведет себя подобно категории, но не имеет единичных элементов. Бесконечномерные обобщения коммутативных полугрупп иногда рассматривались различными авторами.