В математике полугруппа — алгебраическая структура , состоящая из множества и ассоциативной внутренней бинарной операции над ним.
Бинарная операция полугруппы чаще всего обозначается мультипликативно (просто обозначение, не обязательно элементарное арифметическое умножение ): x ⋅ y , или просто xy , обозначает результат применения полугрупповой операции к упорядоченной паре ( x , y ) . Ассоциативность формально выражается так: ( x ⋅ y ) ⋅ z = x ⋅ ( y ⋅ z ) для всех x , y и z в полугруппе.
Полугруппы можно рассматривать как особый случай магм , где операция ассоциативна, или как обобщение групп , не требуя существования единичного элемента или обратных. [a] Как и в случае групп или магм, полугрупповая операция не обязательно должна быть коммутативной , поэтому x ⋅ y не обязательно равно y ⋅ x ; хорошо известным примером операции, которая ассоциативна, но некоммутативна, является умножение матриц . Если полугрупповая операция коммутативна, то полугруппа называется коммутативной полугруппой или (реже, чем в аналогичном случае групп ) ее можно назвать абелевой полугруппой .
Моноид — это алгебраическая структура, промежуточная между полугруппами и группами, и является полугруппой, имеющей единичный элемент , таким образом, подчиняющейся всем, кроме одной, аксиомам группы: существование обратных не требуется для моноида. Естественным примером являются строки с конкатенацией в качестве бинарной операции и пустой строкой в качестве единичного элемента. Ограничение непустыми строками дает пример полугруппы, которая не является моноидом. Положительные целые числа со сложением образуют коммутативную полугруппу, которая не является моноидом, тогда как неотрицательные целые числа образуют моноид. Полугруппу без единичного элемента можно легко превратить в моноид, просто добавив единичный элемент. Следовательно, моноиды изучаются в теории полугрупп, а не в теории групп. Полугруппы не следует путать с квазигруппами , которые являются обобщением групп в другом направлении; операция в квазигруппе не обязательно должна быть ассоциативной, но квазигруппы сохраняют от групп понятие деления . Деление на полугруппы (или на моноиды) в общем случае невозможно.
Формальное изучение полугрупп началось в начале 20 века. Ранние результаты включают теорему Кэли для полугрупп, реализующую любую полугруппу как полугруппу преобразований , в которой произвольные функции заменяют роль биекций в теории групп. Глубоким результатом в классификации конечных полугрупп является теория Крона–Роудса , аналогичная разложению Жордана–Гёльдера для конечных групп. Некоторые другие методы изучения полугрупп, такие как отношения Грина , не похожи ни на что в теории групп.
Теория конечных полугрупп имеет особое значение в теоретической информатике с 1950-х годов из-за естественной связи между конечными полугруппами и конечными автоматами через синтаксический моноид . В теории вероятностей полугруппы связаны с марковскими процессами . [1] В других областях прикладной математики полугруппы являются фундаментальными моделями для линейных стационарных систем . В частных дифференциальных уравнениях полугруппа связана с любым уравнением, пространственная эволюция которого не зависит от времени.
Существует множество специальных классов полугрупп , полугрупп с дополнительными свойствами, которые появляются в конкретных приложениях. Некоторые из этих классов даже ближе к группам, демонстрируя некоторые дополнительные, но не все свойства группы. Из них мы упомянем: регулярные полугруппы , ортодоксальные полугруппы , полугруппы с инволюцией , инверсные полугруппы и сократимые полугруппы . Существуют также интересные классы полугрупп, которые не содержат никаких групп, кроме тривиальной группы ; примерами последнего вида являются полосы и их коммутативный подкласс – полурешетки , которые также являются упорядоченными алгебраическими структурами .
Полугруппа — это множество S вместе с бинарной операцией ⋅ (то есть функцией ⋅ : S × S → S ), которая удовлетворяет ассоциативному свойству :
Более кратко, полугруппа — это ассоциативная магма .
Левая единица полугруппы S (или, в более общем смысле, магма ) — это элемент e, такой что для всех x в S , e ⋅ x = x . Аналогично правая единица — это элемент f, такой что для всех x в S , x ⋅ f = x . Левая и правая единицы называются односторонними единицами . Полугруппа может иметь одну или несколько левых единиц, но не иметь правой единицы, и наоборот.
Двустороннее тождество (или просто тождество ) — это элемент, который является как левым, так и правым тождеством. Полугруппы с двусторонним тождеством называются моноидами . Полугруппа может иметь не более одного двустороннего тождества. Если полугруппа имеет двустороннее тождество, то двустороннее тождество является единственным односторонним тождеством в полугруппе. Если полугруппа имеет как левое тождество, так и правое тождество, то она имеет двустороннее тождество (которое, следовательно, является единственным односторонним тождеством).
Полугруппа S без единицы может быть вложена в моноид, образованный присоединением элемента e ∉ S к S и определением e ⋅ s = s ⋅ e = s для всех s ∈ S ∪ { e } . [2] [3] Обозначение S 1 обозначает моноид, полученный из S присоединением единицы, если необходимо ( S 1 = S для моноида). [3]
Аналогично, каждая магма имеет максимум один поглощающий элемент , который в теории полугрупп называется нулем . Аналогично вышеприведенной конструкции, для каждой полугруппы S можно определить S 0 , полугруппу с 0, которая вкладывает S .
Операция полугруппы индуцирует операцию над совокупностью ее подмножеств: если даны подмножества A и B полугруппы S , их произведение A · B , обычно записываемое как AB , представляет собой множество { ab | a в A и b в B }. (Это понятие определяется так же, как и для групп .) В терминах этой операции подмножество A называется
Если A является одновременно левым и правым идеалом, то он называется идеалом ( или двусторонним идеалом ).
Если S — полугруппа, то пересечение любого набора подполугрупп S также является подполугруппой S. Таким образом, подполугруппы S образуют полную решетку .
Примером полугруппы без минимального идеала является множество положительных целых чисел при сложении. Минимальный идеал коммутативной полугруппы, если он существует, является группой.
Отношения Грина — набор из пяти отношений эквивалентности , характеризующих элементы с точки зрения порождаемых ими главных идеалов , — являются важными инструментами для анализа идеалов полугруппы и связанных с ними понятий структуры.
Подмножество, обладающее свойством, что каждый элемент коммутирует с любым другим элементом полугруппы, называется центром полугруппы. [4] Центр полугруппы на самом деле является подполугруппой. [5]
Гомоморфизм полугрупп — это функция, которая сохраняет структуру полугруппы. Функция f : S → T между двумя полугруппами является гомоморфизмом, если уравнение
справедливо для всех элементов a , b в S , т.е. результат одинаков при выполнении полугрупповой операции после или до применения отображения f .
Гомоморфизм полугрупп между моноидами сохраняет тождество, если он является гомоморфизмом моноидов . Но существуют гомоморфизмы полугрупп, которые не являются гомоморфизмами моноидов, например, каноническое вложение полугруппы S без тождества в S 1 . Условия, характеризующие гомоморфизмы моноидов, обсуждаются далее. Пусть f : S 0 → S 1 — гомоморфизм полугрупп. Образ f также является полугруппой. Если S 0 — моноид с единичным элементом e 0 , то f ( e 0 ) — единичный элемент в образе f . Если S 1 — также моноид с единичным элементом e 1 и e 1 принадлежит образу f , то f ( e 0 ) = e 1 , т. е . f — гомоморфизм моноидов. В частности, если f сюръективен , то это гомоморфизм моноидов.
Две полугруппы S и T называются изоморфными, если существует биективный гомоморфизм полугрупп f : S → T. Изоморфные полугруппы имеют одинаковую структуру.
Полугрупповая конгруэнтность ~ — это отношение эквивалентности , совместимое с полугрупповой операцией. То есть подмножество ~ ⊆ S × S , которое является отношением эквивалентности, и x ~ y и u ~ v влечет xu ~ yv для любых x , y , u , v из S . Как и любое отношение эквивалентности, полугрупповая конгруэнтность ~ индуцирует классы конгруэнтности
и операция полугруппы индуцирует бинарную операцию ∘ на классах конгруэнтности:
Поскольку ~ является конгруэнцией, множество всех классов конгруэнтности ~ образует полугруппу с ∘, называемую фактор-полугруппой или фактор-полугруппой и обозначаемую S / ~ . Отображение x ↦ [ x ] ~ является гомоморфизмом полугрупп, называемым отображением фактора , канонической сюръекцией или проекцией ; если S является моноидом, то фактор-полугруппа является моноидом с тождеством [1] ~ . Наоборот, ядро любого гомоморфизма полугрупп является конгруэнтностью полугрупп. Эти результаты являются не чем иным, как частностью первой теоремы об изоморфизме в универсальной алгебре . Классы конгруэнтности и фактор-моноиды являются объектами изучения в системах переписывания строк .
Ядерная конгруэнция на S — это та , которая является ядром эндоморфизма S. [6]
Полугруппа S удовлетворяет максимальному условию на конгруэнции , если любое семейство конгруэнций на S , упорядоченное по включению, имеет максимальный элемент. По лемме Цорна это эквивалентно утверждению, что выполняется условие возрастающей цепи : не существует бесконечной строго возрастающей цепи конгруэнций на S. [ 7]
Каждый идеал I полугруппы индуцирует фактор-полугруппу, фактор-полугруппу Риса , посредством конгруэнции ρ, определяемой соотношением x ρ y , если либо x = y , либо оба x и y принадлежат I.
Следующие понятия [8] вводят идею о том, что одна полугруппа содержится в другой.
Полугруппа T является частным полугруппы S , если существует сюръективный морфизм полугрупп из S в T. Например, ( Z /2 Z , +) является частным ( Z /4 Z , +) , используя морфизм, состоящий в взятии остатка по модулю 2 от целого числа.
Полугруппа T делит полугруппу S , обозначаемую как T ≼ S , если T является фактором подполугруппы S. В частности, подполугруппы S делят T , при этом не обязательно существует фактор S.
Оба эти отношения транзитивны.
Для любого подмножества A из S существует наименьшая подполугруппа T из S , которая содержит A , и мы говорим, что A порождает T. Один элемент x из S порождает подполугруппу { x n | n ∈ Z + } . Если это конечно, то говорят, что x имеет конечный порядок , в противном случае говорят, что он имеет бесконечный порядок . Полугруппа называется периодической, если все ее элементы имеют конечный порядок. Полугруппа, порожденная одним элементом, называется моногенной (или циклической ). Если моногенная полугруппа бесконечна, то она изоморфна полугруппе положительных целых чисел с операцией сложения. Если она конечна и непуста, то она должна содержать по крайней мере один идемпотент . Отсюда следует, что каждая непустая периодическая полугруппа имеет по крайней мере один идемпотент.
Подполугруппа, которая также является группой, называется подгруппой . Существует тесная связь между подгруппами полугруппы и ее идемпотентами. Каждая подгруппа содержит ровно один идемпотент, а именно единичный элемент подгруппы. Для каждого идемпотента e полугруппы существует единственная максимальная подгруппа, содержащая e . Каждая максимальная подгруппа возникает таким образом, поэтому между идемпотентами и максимальными подгруппами существует взаимно однозначное соответствие. Здесь термин максимальная подгруппа отличается от его стандартного использования в теории групп.
Часто можно сказать больше, когда порядок конечен. Например, каждая непустая конечная полугруппа является периодической и имеет минимальный идеал и по крайней мере один идемпотент. Число конечных полугрупп заданного размера (больше 1) (очевидно) больше числа групп того же размера. Например, из шестнадцати возможных «таблиц умножения» для набора из двух элементов {a, b } восемь образуют полугруппы [b], тогда как только четыре из них являются моноидами и только две образуют группы. Подробнее о структуре конечных полугрупп см. в теории Крона–Роудса .
Существует структурная теорема для коммутативных полугрупп в терминах полурешеток . [10] Полурешетка (или, точнее, встречающаяся полурешетка) ( L , ≤) — это частично упорядоченное множество , где каждая пара элементов a , b ∈ L имеет точную нижнюю границу , обозначаемую a ∧ b . Операция ∧ превращает L в полугруппу, которая удовлетворяет дополнительному закону идемпотентности a ∧ a = a .
При гомоморфизме f : S → L из произвольной полугруппы в полурешетку каждый обратный образ S a = f −1 { a } является (возможно, пустой) полугруппой. Более того, S становится градуированным по L , в том смысле, что S a S b ⊆ S a ∧ b .
Если f — на, полурешетка L изоморфна фактору S по отношению эквивалентности ~, такому, что x ~ y тогда и только тогда, когда f ( x ) = f ( y ) . Это отношение эквивалентности является полугрупповой конгруэнцией, как определено выше.
Всякий раз, когда мы берем фактор-коммутативную полугруппу по конгруэнции, мы получаем другую коммутативную полугруппу. Структурная теорема утверждает, что для любой коммутативной полугруппы S существует наилучшая конгруэнция ~ такая, что фактор-коммутация S по этому отношению эквивалентности является полурешеткой. Обозначая эту полурешетку через L , мы получаем гомоморфизм f из S на L. Как уже упоминалось, S становится градуированной этой полурешеткой.
Более того, компоненты S a являются архимедовыми полугруппами . Архимедова полугруппа — это такая, в которой для любой пары элементов x , y существует элемент z и n > 0 такой, что x n = yz .
Архимедовость немедленно следует из упорядочения в полурешетке L , поскольку при этом упорядочении f ( x ) ≤ f ( y ) тогда и только тогда, когда x n = yz для некоторых z и n > 0 .
Группа дробей или групповое пополнение полугруппы S — это группа G = G ( S ), порожденная элементами S как генераторами и всеми уравнениями xy = z , которые верны в S как отношениями . [11] Существует очевидный гомоморфизм полугрупп j : S → G ( S ) , который отправляет каждый элемент S в соответствующий генератор. Это имеет универсальное свойство для морфизмов из S в группу: [12] для любой группы H и любого гомоморфизма полугрупп k : S → H существует единственный гомоморфизм групп f : G → H с k = fj . Мы можем рассматривать G как «наиболее общую» группу, которая содержит гомоморфный образ S .
Важным вопросом является характеристика тех полугрупп, для которых это отображение является вложением. Это не всегда так: например, возьмем S в качестве полугруппы подмножеств некоторого множества X с теоретико-множественным пересечением в качестве бинарной операции (это пример полурешетки). Поскольку A . A = A выполняется для всех элементов S , это должно быть верно и для всех генераторов G ( S ), которая, следовательно, является тривиальной группой . Очевидно, что для вложимости необходимо, чтобы S обладала свойством сокращения . Когда S коммутативна, это условие также достаточно [13] , и группа Гротендика полугруппы обеспечивает конструкцию группы дробей. Проблема для некоммутативных полугрупп может быть прослежена до первой существенной статьи о полугруппах. [14] [15] Анатолий Мальцев дал необходимые и достаточные условия вложимости в 1937 году. [16]
Теория полугрупп может быть использована для изучения некоторых проблем в области уравнений с частными производными . Грубо говоря, подход полугрупп заключается в том, чтобы рассматривать зависящее от времени уравнение с частными производными как обыкновенное дифференциальное уравнение на функциональном пространстве. Например, рассмотрим следующую начальную/краевую задачу для уравнения теплопроводности на пространственном интервале (0, 1) ⊂ R и временах t ≥ 0 :
Пусть X = L 2 ((0, 1) R ) — пространство L p квадратично-интегрируемых действительных функций с областью определения в интервале (0, 1) , а A — оператор второй производной с областью определения
где H 2 — пространство Соболева . Тогда указанную выше начально-краевую задачу можно интерпретировать как начально-краевую задачу для обыкновенного дифференциального уравнения в пространстве X :
На эвристическом уровне решение этой проблемы «должно» быть u ( t ) = exp( tA ) u 0 . Однако для строгого рассмотрения необходимо придать смысл экспоненте tA . Как функция t , exp( tA ) представляет собой полугруппу операторов из X в себя, переводящую начальное состояние u 0 в момент времени t = 0 в состояние u ( t ) = exp( tA ) u 0 в момент времени t . Оператор A называется инфинитезимальным генератором полугруппы.
Изучение полугрупп отставало от изучения других алгебраических структур с более сложными аксиомами, такими как группы или кольца . Ряд источников [17] [18] приписывают первое использование термина (на французском языке) Ж.-А. де Сегье в работе Élements de la Théorie des Groupes Abstraits (Элементы теории абстрактных групп) в 1904 году. Термин был использован на английском языке в 1908 году в работе Гарольда Хинтона « Теория групп конечного порядка» .
Антон Сушкевич получил первые нетривиальные результаты о полугруппах. Его работа 1928 года «Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit» («О конечных группах без правила однозначной обратимости») определила структуру конечных простых полугрупп и показала, что минимальный идеал (или J-класс отношений Грина ) конечной полугруппы прост. [18] С этого момента основы теории полугрупп были дополнительно заложены Дэвидом Рисом , Джеймсом Александром Грином , Евгением Сергеевичем Ляпиным , Альфредом Х. Клиффордом и Гордоном Престоном . Последние двое опубликовали двухтомную монографию по теории полугрупп в 1961 и 1967 годах соответственно. В 1970 году новое периодическое издание под названием Semigroup Forum (в настоящее время редактируется Springer Verlag ) стало одним из немногих математических журналов, полностью посвященных теории полугрупп.
Теория представлений полугрупп была разработана в 1963 году Борисом Шейном с использованием бинарных отношений на множестве A и композиции отношений для полугруппового произведения. [19] На алгебраической конференции в 1972 году Шейн сделал обзор литературы по B A , полугруппе отношений на A . [20] В 1997 году Шейн и Ральф Маккензи доказали, что каждая полугруппа изоморфна транзитивной полугруппе бинарных отношений. [21]
В последние годы исследователи в этой области стали более специализированными: появились специальные монографии, посвященные важным классам полугрупп, таким как инверсные полугруппы , а также монографии, посвященные приложениям в теории алгебраических автоматов, особенно для конечных автоматов, а также в функциональном анализе .
Если аксиому ассоциативности полугруппы отбросить, то результатом будет магма , которая представляет собой не что иное , как множество M, снабженное бинарной замкнутой операцией M × M → M.
Обобщая в другом направлении, n -арная полугруппа (также n- арная полугруппа , полиадическая полугруппа или мультиарная полугруппа ) является обобщением полугруппы на множество G с n -арной операцией вместо бинарной операции. [22] Ассоциативный закон обобщается следующим образом: тернарная ассоциативность — это ( abc ) de = a ( bcd ) e = ab ( cde ) , т. е. строка abcde с любыми тремя соседними элементами в квадратных скобках. n -арная ассоциативность — это строка длины n + ( n − 1) с любыми n соседними элементами в квадратных скобках. 2-арная полугруппа — это просто полугруппа. Дальнейшие аксиомы приводят к n -арной группе .
Третье обобщение — это полугруппоид , в котором снимается требование, чтобы бинарное отношение было тотальным. Поскольку категории обобщают моноиды таким же образом, полугруппоид ведет себя во многом как категория, но не имеет тождеств.
Бесконечные обобщения коммутативных полугрупп иногда рассматривались различными авторами. [c]
