В теории групп обратная полугруппа (иногда называемая инверсионной полугруппой [1] ) S — это полугруппа , в которой каждый элемент x в S имеет единственный обратный y в S в том смысле, что x = xyx и y = yxy , т. е. регулярная полугруппа , в которой каждый элемент имеет единственный обратный. Обратные полугруппы появляются в различных контекстах; например, их можно использовать при изучении частичных симметрий . [2]
(В этой статье будет принято соглашение о записи функции справа от ее аргумента, например, x f, а не f ( x ), и составлении функций слева направо — соглашение, часто соблюдаемое в теории полугрупп.)
Инверсные полугруппы были введены независимо Виктором Владимировичем Вагнером [3] в Советском Союзе в 1952 году [4] и Гордоном Престоном в Соединенном Королевстве в 1954 году [5]. Оба автора пришли к инверсным полугруппам через изучение частичных биекций множества : частичное преобразование α множества X является функцией из A в B , где A и B являются подмножествами X. Пусть α и β являются частичными преобразованиями множества X ; α и β могут быть составлены (слева направо) на наибольшей области , на которой «имеет смысл» их составление:
где α −1 обозначает прообраз под α . Частичные преобразования уже изучались в контексте псевдогрупп . [6] Однако именно Вагнер был первым, кто заметил, что композиция частичных преобразований является частным случаем композиции бинарных отношений . [7] Он также признал, что областью композиции двух частичных преобразований может быть пустое множество , поэтому он ввел пустое преобразование , чтобы учесть это. С добавлением этого пустого преобразования композиция частичных преобразований множества становится всюду определенной ассоциативной бинарной операцией . При этой композиции совокупность всех частичных однозначных преобразований множества X образует обратную полугруппу, называемую симметричной обратной полугруппой (или моноидом) на X , с обратным — функциональным обратным, определенным от образа к области (эквивалентно, обратное отношение ). [8] Это «архетипическая» обратная полугруппа, таким же образом, как симметричная группа является архетипической группой . Например, подобно тому, как каждая группа может быть вложена в симметричную группу , каждая обратная полугруппа может быть вложена в симметричную обратную полугруппу (см. § Гомоморфизмы и представления обратных полугрупп ниже).
Обратный элемент x инверсной полугруппы S обычно записывается как x −1 . Обратные элементы в инверсной полугруппе обладают многими из тех же свойств, что и обратные элементы в группе , например, ( ab ) −1 = b −1 a −1 . В инверсном моноиде xx −1 и x −1 x не обязательно равны единице, но они оба идемпотентны . [9] Инверсный моноид S , в котором xx −1 = 1 = x −1 x , для всех x из S ( унипотентный инверсный моноид), является, конечно, группой .
Существует ряд эквивалентных характеристик инверсной полугруппы S : [10]
Идемпотент в -классе s есть s −1 s , в то время как идемпотент в -классе s есть ss −1 . Поэтому существует простая характеристика соотношений Грина в инверсной полугруппе: [11]
Если не указано иное, E(S) будет обозначать полурешетку идемпотентов инверсной полугруппы S.
Пример таблицы умножения. Она ассоциативна и каждый элемент имеет свою собственную обратную согласно aba = a , bab = b . Она не имеет тождества и не коммутативна.
Инверсная полугруппа S обладает естественным отношением частичного порядка ≤ (иногда обозначаемым как ω), которое определяется следующим образом: [12]
для некоторого идемпотента e в S. Эквивалентно,
для некоторого (в общем случае, другого) идемпотента f в S. Фактически, e можно взять равным aa −1 , а f — равным a −1 a . [13]
Естественный частичный порядок совместим как с умножением, так и с инверсией, то есть [14]
и
В группе этот частичный порядок просто сводится к равенству, поскольку тождество является единственным идемпотентом . В симметричной обратной полугруппе частичный порядок сводится к ограничению отображений, т. е. α ≤ β тогда и только тогда, когда область α содержится в области β и xα = xβ для всех x в области α . [15]
Естественный частичный порядок на инверсной полугруппе взаимодействует с отношениями Грина следующим образом: если s ≤ t и s t , то s = t . Аналогично, если s t . [16]
На E ( S ) естественный частичный порядок становится:
Итак, поскольку идемпотенты образуют полурешетку относительно операции произведения, произведения на E ( S ) дают наименьшие верхние границы относительно ≤.
Если E ( S ) конечен и образует цепь (т.е. E ( S ) полностью упорядочен по ≤), то S является объединением групп . [17] Если E ( S ) является бесконечной цепью , то можно получить аналогичный результат при дополнительных гипотезах относительно S и E ( S ) . [18]
Гомоморфизм (или морфизм ) инверсных полугрупп определяется точно так же, как и для любой другой полугруппы: для инверсных полугрупп S и T функция θ из S в T является морфизмом , если ( sθ ) ( tθ ) = ( st ) θ , для всех s , t из S . Определение морфизма инверсных полугрупп можно было бы расширить, включив условие ( sθ ) −1 = s −1 θ , однако в этом нет необходимости, поскольку это свойство следует из приведенного выше определения с помощью следующей теоремы:
Теорема. Гомоморфный образ инверсной полугруппы является инверсной полугруппой; инверсия элемента всегда отображается в инверсию образа этого элемента. [19]
Одним из самых ранних результатов, доказанных относительно инверсных полугрупп, была теорема Вагнера–Престона , которая является аналогом теоремы Кэли для групп :
Теорема Вагнера–Престона. Если S — обратная полугруппа, то функция φ из S в , заданная формулой
является точным представлением S. [ 20 ]
Таким образом, любая обратная полугруппа может быть вложена в симметричную обратную полугруппу, причем с образом, замкнутым относительно обратной операции над частичными биекциями. Обратно, любая подполугруппа симметричной обратной полугруппы, замкнутая относительно обратной операции, является обратной полугруппой. Следовательно, полугруппа S изоморфна подполугруппе симметричной обратной полугруппы, замкнутой относительно обратных операций, тогда и только тогда, когда S является обратной полугруппой.
Конгруэнтность определяется на инверсных полугруппах точно так же, как и для любой другой полугруппы: конгруэнтность ρ — это отношение эквивалентности , совместимое с умножением полугрупп, т. е.
Особый интерес представляет отношение , определяемое на инверсной полугруппе S соотношением
Можно показать, что σ является конгруэнцией и, по сути, это групповая конгруэнция , что означает, что фактор-полугруппа S / σ является группой. В множестве всех групповых конгруэнций на полугруппе S минимальный элемент (для частичного порядка, определяемого включением множеств) не обязательно должен быть наименьшим элементом. В конкретном случае, когда S является обратной полугруппой, σ является наименьшей конгруэнцией на S такой, что S / σ является группой, то есть, если τ является любой другой конгруэнцией на S с S / τ группой, то σ содержится в τ . Конгруэнция σ называется минимальной групповой конгруэнцией на S . [23] Минимальная групповая конгруэнция может быть использована для характеристики E -унитарных инверсных полугрупп (см. ниже).
Конгруэнция ρ на инверсной полугруппе S называется идемпотентно чистой , если
Одним из классов инверсных полугрупп , который интенсивно изучался на протяжении многих лет, является класс E -унитарных инверсных полугрупп: инверсная полугруппа S (с полурешеткой E идемпотентов ) является E -унитарной , если для всех e из E и всех s из S ,
Эквивалентно,
Еще одна характеристика E -унитарной инверсной полугруппы S следующая: если e принадлежит E и e ≤ s для некоторого s из S , то s принадлежит E. [26]
Теорема. Пусть S — инверсная полугруппа с полурешеткой E идемпотентов и минимальной групповой конгруэнтностью σ . Тогда следующие условия эквивалентны: [27]
где — отношение совместимости на S , определяемое формулой
Теорема покрытия Макалистера. Каждая обратная полугруппа S имеет E-унитарное покрытие; то есть существует идемпотентный разделяющий сюръективный гомоморфизм из некоторой E-унитарной полугруппы T на S. [28]
Центральным в изучении E -унитарных обратных полугрупп является следующая конструкция. [29] Пусть будет частично упорядоченным множеством с порядком ≤, и пусть будет подмножеством со свойствами, которые
Теперь пусть G — группа , действующая на (слева), такая, что
Предполагается также, что тройка обладает следующими свойствами:
Такая тройка называется тройкой Макалистера . Тройка Макалистера используется для определения следующего:
вместе с умножением
Тогда — инверсная полугруппа относительно этого умножения, с ( A , g ) −1 = ( g −1 A , g −1 ) . Одним из основных результатов в изучении E -унитарных инверсных полугрупп является P-теорема Макалистера :
P-теорема Макалистера. Пусть — тройка Макалистера. Тогда — E -унитарная обратная полугруппа. Обратно, каждая E -унитарная обратная полугруппа изоморфна одной из этого типа. [30]
Говорят, что инверсная полугруппа является F -инверсной, если каждый элемент имеет единственный максимальный элемент над собой в естественном частичном порядке, т.е. каждый σ -класс имеет максимальный элемент. Каждая F -инверсная полугруппа является E -унитарным моноидом. Теорема покрытия Макалистера была улучшена М. В. Лоусоном до:
Теорема. Каждая инверсная полугруппа имеет F -обратное покрытие. [31]
P -теорема Макалистера также использовалась для характеристики F -обратных полугрупп. Тройка Макалистера является F -обратной полугруппой тогда и только тогда, когда является главным идеалом и является полурешеткой.
Для инверсных полугрупп возможна конструкция, аналогичная свободной группе . Представление свободной инверсной полугруппы на множестве X можно получить, рассматривая свободную полугруппу с инволюцией , где инволюция — это взятие инверсии, а затем взятие фактора по сравнению Вагнера
Проблема слов для свободных обратных полугрупп гораздо сложнее, чем для свободных групп. Знаменитый результат в этой области принадлежит У. Д. Манну, который показал, что элементы свободной обратной полугруппы можно естественным образом рассматривать как деревья, известные как деревья Манна. Умножение в свободной обратной полугруппе имеет корреспондента на деревьях Манна, которые по сути состоят из перекрывающихся общих частей деревьев. (см. Lawson 1998 для получения дополнительных подробностей)
Любая свободная инверсная полугруппа является F -инверсной. [31]
Вышеуказанная композиция частичных преобразований множества порождает симметричную обратную полугруппу. Существует другой способ композиции частичных преобразований, который является более ограничительным, чем использованный выше: два частичных преобразования α и β составляются тогда и только тогда, когда образ α равен области определения β ; в противном случае композиция αβ не определена. При этой альтернативной композиции совокупность всех частичных взаимно-однозначных преобразований множества образует не обратную полугруппу, а индуктивный группоид в смысле теории категорий . Эта тесная связь между обратными полугруппами и индуктивными группоидами воплощена в теореме Эресмана–Шейна–Намбурипада , которая утверждает, что индуктивный группоид всегда можно построить из обратной полугруппы, и наоборот. [32] Точнее, инверсная полугруппа — это в точности группоид в категории частично упорядоченных множеств, который является этальным группоидом относительно своей (двойственной) топологии Александрова и частично упорядоченный набор объектов которого является полурешеткой встреч.
Как отмечено выше, инверсная полугруппа S может быть определена условиями (1) S является регулярной полугруппой и (2) идемпотенты в S коммутируют; это привело к двум различным классам обобщений инверсной полугруппы: полугруппы, в которых (1) выполняется, но (2) не выполняется, и наоборот.
Примерами регулярных обобщений инверсной полугруппы являются: [33]
Класс обобщенно -инверсных полугрупп является пересечением класса локально-инверсных полугрупп и класса ортодоксальных полугрупп. [34]
Среди нерегулярных обобщений инверсной полугруппы: [35]
Это понятие инверсии также легко обобщается на категории . Инверсная категория — это просто категория, в которой каждый морфизм f : X → Y имеет обобщенную инверсию g : Y → X такую, что fgf = f и gfg = g . Инверсная категория является самодвойственной . Категория множеств и частичных биекций — яркий пример. [36]
Обратные категории нашли различные применения в теоретической информатике . [37]
{{cite journal}}
: CS1 maint: postscript (link)