Бициклическая полугруппа

В математике бициклическая полугруппа — алгебраический объект, важный для теории структуры полугрупп . Хотя на самом деле это моноид , его обычно называют просто полугруппой. Вероятно, его легче всего понять как синтаксический моноид, описывающий язык Дика , состоящий из сбалансированных пар круглых скобок. Таким образом, он находит общие применения в комбинаторике , например, при описании бинарных деревьев и ассоциативных алгебр .

История [ править ]

Первое опубликованное описание этого объекта было дано Евгением Ляпиным в 1953 году. Альфред Х. Клиффорд и Гордон Престон утверждают, что один из них, работая с Дэвидом Рисом , открыл его независимо (без публикации) в какой-то момент до 1943 года.

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

Существует как минимум три стандартных способа построения бициклической полугруппы и различные обозначения для ее обозначения. Ляпин назвал его П ; Клиффорд и Престон использовали ${\mathcal {C}}$ ; и в самых последних статьях, как правило, используется B . В этой статье будет использован современный стиль.

Из свободной полугруппы [ править ]

Бициклическая полугруппа — это фактор свободного моноида по двум образующим p и q по конгруэнции, порожденной соотношением p q = 1 . Таким образом, каждый элемент полугруппы представляет собой строку из этих двух букв при условии, что подпоследовательность « p q » не встречается. Полугрупповая операция — это объединение строк, что явно ассоциативно . Тогда можно показать, что все элементы B на самом деле имеют вид q ^а п ^б, для некоторых натуральных чисел a и b . Операция композиции упрощается до

( q ^а п ^б) ( q ^с п ^д) = q ^{а + с −min { б , с }} п ^{d + b −min{ b , c }}.

Из упорядоченных пар [ править ]

Способ ограничения этих показателей предполагает, что « структуру p и q » можно отбросить, оставив только операции над частью « a и b ». Итак, B — полугруппа пар натуральных чисел (включая ноль) с операцией ^[1]

( а , б ) ( c , d ) знак равно ( а + c - min { б , c }, d + b - min { b , c }).

Этого достаточно, чтобы определить B так, чтобы это был тот же объект, что и в исходной конструкции. Точно так же, как p и q первоначально породили B с пустой строкой в качестве тождества моноида, эта новая конструкция B имеет генераторы (1, 0) и (0, 1) с тождеством (0, 0) .

Из функций [ править ]

Можно показать, что любая полугруппа S, порожденная элементами e , a и b, удовлетворяющая приведенным ниже утверждениям, изоморфна бициклической полугруппе.

а е = е а = а
б е = е б = б
а б = е
б а ≠ е

Не совсем очевидно, что это так — возможно, самая трудная задача — понять, что S должно быть бесконечным. Чтобы убедиться в этом, предположим, что ( скажем) не имеет бесконечного порядка, поэтому ^{к + ч} = а ^час для некоторых h и k . Тогда ^к = е и

б = е б = а ^к б = а ^{к -1} е = а ^{к -1},

так

б а = а ^к = и ,

что недопустимо – поэтому существует бесконечно много различных степеней . Полное доказательство приведено в книге Клиффорда и Престона.

Обратите внимание, что оба определения, данные выше, удовлетворяют этим свойствам. Третий способ получения B использует две правильно выбранные функции, чтобы получить бициклическую полугруппу как моноид преобразований натуральных чисел. Пусть α , β и ι — элементы полугруппы преобразований натуральных чисел, где

я ( п ) знак равно п
α ( п ) знак равно п + 1
β ( n ) = 0, если n = 0, и n − 1 в противном случае.

Эти три функции обладают необходимыми свойствами, поэтому полугруппа, которую они порождают, — B. это ^[2]

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

Бициклическая полугруппа обладает тем свойством, что образ любого гомоморфизма φ из B полугруппу S либо циклический , либо является изоморфной копией B. в другую Элементы φ ( a ), φ ( b ) и φ ( e ) из S всегда будут удовлетворять вышеуказанным условиям (поскольку φ является гомоморфизмом) с возможным исключением, что φ ( b ) φ ( a ) может оказаться φ ( е ). Если это не так, то φ ( B ) изоморфна B ; в противном случае это циклическая полугруппа, порожденная φ ( a ). На практике это означает, что бициклическую полугруппу можно найти во многих различных контекстах.

Идемпотентами ) B — любое натуральное число (с использованием являются все пары ( x , x B , где x упорядоченной парной характеристики ) . Поскольку они коммутируют, а B регулярна x (для каждого x существует y такой, что y x = x ) , бициклическая полугруппа является обратной полугруппой . (Это означает, что каждый элемент x из B имеет уникальный обратный y в смысле «слабой» полугруппы, что x y x = x и y x y = y .)

Каждый идеал B равны является главным: левый и правый главные ( m , n ) идеалы

( м , п ) B знак равно {( s , т ) : s ≥ м } и
B ( м , п ) знак равно {( s , т ) : т ≥ п }.

Каждый из них содержит бесконечное множество других, поэтому B не имеет минимальных левых или правых идеалов.

С точки зрения отношений Грина , B имеет только один D -класс (он бипрост ), а значит, имеет только один J -класс (он прост ). Отношения L и R определяются выражениями

( a , b ) R ( c , d ) тогда и только тогда, когда a = c ; и
( а , б ) L ( c , d ) тогда и только тогда, когда б знак равно d . ^[3]

Это означает, что два элемента H -родственны тогда и только тогда, когда они идентичны. Следовательно, единственными подгруппами группы B являются бесконечное число копий тривиальной группы, каждая из которых соответствует одному из идемпотентов.

Диаграмма «яичная коробка» для B бесконечно велика; верхний левый угол начинается:

(0, 0)	(1, 0)	(2, 0)	...
(0, 1)	(1, 1)	(2, 1)	...
(0, 2)	(1, 2)	(2, 2)	...
...	...	...	...

Каждая запись представляет одноэлементный H -класс; строки — это R -классы, а столбцы — L -классы. Идемпотенты группы B появляются по диагонали в соответствии с тем, что в регулярной полугруппе с коммутирующими идемпотентами каждый L -класс и каждый R -класс должны содержать ровно один идемпотент.

Бициклическая полугруппа является «простейшим» примером бипростой обратной полугруппы с единицей; есть много других. Там, где при определении B из упорядоченных пар использовался класс натуральных чисел (который является не только аддитивной полугруппой, но и коммутативной решеткой относительно операций min и max), вместо него могло появиться другое множество с соответствующими свойствами, и «+», Операции «-» и «max» изменены соответствующим образом.

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

Примечания [ править ]

^ Холлингс (2007) , с. 332
^ Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. п. 459. ИСБН 978-0-521-18071-9 . Артикул 1221.68183 .
^ Хоуи стр. 60

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

Алгебраическая теория полугрупп , А. Х. Клиффорд и Г. Б. Престон. Американское математическое общество, 1961 (том 1), 1967 (том 2).
Полугруппы: введение в теорию структур , Пьер Антуан Грийе. Марсель Деккер, Inc., 1995.
Каноническая форма элементов ассоциативной системы, заданная определяющими соотношениями , Ляпин Евгений Сергеевич, Ленинградский гос. Пед. Инст. Уч. Зап. 89 (1953), стр. 45–54.
Холлингс, компакт-диск (2007). «Некоторые первые волнующие шаги в теорию полугрупп». Журнал «Математика» . 80 . Математическая ассоциация Америки: 331–344. JSTOR 27643058 .

[FOOTNOTEHollings2007332-1] Холлингс (2007) , с. 332

[Lot459-2] Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. п. 459. ИСБН 978-0-521-18071-9 . Артикул 1221.68183 .

[3] Хоуи стр. 60

[1]

[2]

[3]