Полугруппы.

Определение. Полугруппой называется алгебра вида с одной ассоциативной бинарной операцией .

Как правило, в качестве такой операции используется умножение. Поэтому результат её применения к двум различным элементам записывают в виде или , а результат неоднократного применения к одному элементу записывают в виде и так далее. Такая запись называется мультипликативной. Полугруппу часто обозначают записью .

Замечание. Не следует понимать сказанное выше в том смысле, что полугруппа всегда включает в себя именно арифметическую операцию умножения. Термин “умножение” здесь является достаточно условным. Символ “ ” применяется именно для того, чтобы указать на это. Под символом“ ” может пониматься и произведение матриц или векторов, и композиция каких-либо преобразований, и даже сложение.

В общем случае, (как, например, произведение матриц), то есть данная операция некоммутативна. Если же умножение коммутативно, то полугруппа называется коммутативной или абелевой полугруппой.

Если множество-носитель полугруппы содержит такой элемент , что для любого выполняется , то этот элемент называется единицей (нейтральным элементом), а такая полугруппа называется моноидом. Легко показать, что если полугруппа содержит единицу, то она единственна. Действительно, допустим, существуют две единицы и . Тогда и , следовательно .

Пример 1.

а) Алгебра , где множество чётных чисел является абелевой полугруппой. Однако, очевидно, она не имеет единицы.

б) Алгебра , где множество квадратных матриц одинаковой размерности образует некоммутативную полугруппу. Причём эта полугруппа является моноидом, а роль единицы в ней выполняет единичная матрица .

в) Алгебра является коммутативной полугруппой с единицей.

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

Например, в полугруппе порождающим множеством служит бесконечное множество простых чисел.

Определение. Полугруппа, которая имеет только одну образующую, называется циклической.

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

Пусть полугруппа имеет конечное число образующих . Если в записи опустить обозначение операции (как это обычно делается для умножения), то все элементы полугруппы можно рассматривать как слова в алфавите . Причём некоторые различные слова могут оказаться равными, как элементы (равные элементы записаны различными словами). В коммутативной полугруппе для двух любых элементов выполняется равенство , позволяющее устанавливать равенство элементов, в том числе, записанных различными словами. Подобные равенства называются определяющими соотношениями.

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

Доказано, что каждую полугруппу можно получить из некоторой свободной полугруппы введением некоторых определяющих соотношений. Элементы заданной так полугруппы – это слова в алфавите образующих, причём некоторые слова равны (то есть задают один элемент) в силу определяющих соотношений. Они позволяют из любого слова получить любые эквивалентные ему слова. Отношение равенства слов есть отношение эквивалентности. Кстати, намного сложнее выяснить для двух данных слов, можно ли получить одно из другого с помощью определяющих соотношений. Исследование этой проблемы оказало значительное влияние на теорию алгоритмов.