8.2. Полугруппы и моноиды

Множество П с заданной в нем бинарной ассоциативной операцией называется полугруппой. Полугруппа с единичным элементом называется моноидом (или просто полугруппой с единицей).

Примеры

1. Пусть X — произвольное множество, М(Х)—множество всех отображений X в себя. Тогда относительно операции композиции отображений М (X) — моноид, он некоммутативный. Обозначим его М(Х, О, е_х).

2. Множество квадратных матриц порядка п относительно умножения матриц — некоммутативный моноид с единичным элементом — единичной матрицей, а относительно сложения матриц — коммутативный моноид с единичным элементом — нулевой матрицей. Обозначим их соответственно (M_n(R),•,E), (M_n(R),+,0).

3. Множество целых чисел — коммутативный моноид как относительно сложения, так и умножения. Обозначим их соответственно (Z, +, 0), (Z, •, 1). Множество целых чисел, делящихся на n(n>1),— коммутативная полугруппа без единицы относительно умножения. Обозначим ее (nZ, •).

4. Пусть A = {a₁, ..., а_n}—конечное множество символов — алфавит. Конечная последовательность символов называется словом в алфавите А. На множестве П слов в алфавите А введем бинарную операцию—«приписывание», т.е. если , то . Тогда П — полугруппа. Она называется свободной полугруппой, порожденной множеством А.

5. Множество {X₁, X₂, Х₃, Х₄} относительно операции, заданной таблицей Кэли (см. табл. 8.1.),— коммутативный моноид, единичный элемент которого Х₁.

Подмножество П' полугруппы П называется подполугруппой, если аbЄП' для всех а, bЄП'. В этом случае говорят также, что подмножество П' замкнуто относительно рассматриваемой операции. Очевидно, подполугруппа П' сама является полугруппой относительно операции в П. Если М — моноид и подмножество М' не только замкнуто относительно операции, но и содержит единичный элемент, то М' называется подмоноидом М.

Например, множество чисел, кратных п, — подполугруппа в полугруппе целых чисел относительно умножения (Z, •, 1) и подмоноид в (Z, +,0). В полугруппе П слов в алфавите А подмножество слов в алфавите А΄А также подполугруппа.

Элемент а моноида М с единичным элементом е называется обратимым, если для некоторого элемента b выполняется равенство ab=ba=e. Элемент b называется обратным а и обозначается a^-1. Обратный элемент единственен. Действительно, если еще и ab'=b'a=e, то b'=eb^΄=(ba)b'=b(ab')=be=b.

Нетрудно видеть, что (а^-1)^-1=а. Кроме того, если а, b обратимы, то (аb)^-1 = b^-1a^-1, так как (ab) (b^-la^-1)=a(bb^-1)a^-1 = аеа^-1=аа^-1=е, и аналогично (b^-la^-1) (ab)=e, т. е. элемент ab тоже обратим.

Множество всех обратимых элементов моноида образует подмоноид, так как содержит единичный элемент и замкнуто относительно операции: если а и b обратимы, то b^-la^-1 — элемент, обратный ab.

Рассмотрим проблему тождества слов в полугруппах.

Пусть S={s_1, ...., s_n} — подмножество элементов полугруппы П такое, что любой элемент из П может быть представлен как произведение элементов из S. Тогда множество S называется системой образующих полугруппы П. Например, для свободной полугруппы П, порожденной алфавитом A ={a₁, ..., а_n}, само множество А является системой образующих; для полугруппы целых чисел относительно сложения (Z, +, 0) системой образующих является множество {-1, 1, 0}, а для полугруппы целых чисел относительно умножения (Z, •, 1) образующими являются все простые числа и единица.

Следует заметить, что далеко не все произведения элементов множества S будут различными элементами полугруппы П. В общем случае вопрос о равенстве таких произведений довольно сложен.

Будем рассматривать полугруппы, порожденные конечным множеством своих элементов. Они называются конечно-порожденными.

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

Каждая полугруппа П может быть задана образующими

a_1, a_2,…, a_n (8.2.1.)

(алфавит полугруппы) и определяющими соотношениями

A_i=B_i (i=1, 2,…) (8.2.2.)

где A_i и B_i — слова в алфавите (8.2.1.).

Элемент полугруппы, т.е., слово в алфавите (8.2.1), называют словом полугруппы П.

Элементарным преобразованием полугруппы П называется переход от слова вида XA_iY к слову XB_iY (или обратно), где X,Y, - произвольные слова полугруппы П, а A_i=B_i; — одно из определяющих соотношений (8.2.2).

Элементарные преобразования представляются в виде схем

X A_i Y→X B_i Y; X B_i Y→X A_i Y.

К схемам элементарных преобразований относятся также тавтологические переходы вида Х→Х. Графическое совпадение двух слов X и Y обозначают ХōY.

Соотношения (8.2.2.) определяют равенство слов в полугруппе П, которое связано с элементарными преобразованиями полугруппы П следующим образом. Два слова X и Y полугруппы П равны в П тогда и только тогда, когда можно указать последовательность элементарных преобразований полугруппы П

XōX₀→X₁→...→X_i→X_i+1→…→X_kōY,

переводящую слово X в слово У.

Для свободной полугруппы с алфавитом (8.2.1.) множество определяющих соотношений пусто; два слова равны тогда и только тогда, когда они графически совпадают.

Полугруппу (Z, +, 0) целых чисел относительно сложения можно задать образующими {—1, 1, 0} и определяющими (в аддитивной записи) соотношениями:

1+(-1)=0; (-1) + 1=0.

Проблема тождества слов в полугруппе заключается в следующем: указать алгоритм, который по любым двум словам устанавливал бы, равны они в полугруппе П или нет. Доказано, что эта проблема алгоритмически неразрешима. Простым примером полугруппы с неразрешимой проблемой тождества слов является полугруппа с образующими а, b, с, d, e и определяющими соотношениями ас=са, ad=da, bс=сb, bd=db, еса=cе, edb=de, сса=ссае.