Пример 1.

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

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

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

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

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

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

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

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

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

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

1. Группы.

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

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

Определение 2. Множество А с определенной на нем алгебраической операцией (например, умножением) называется группой, если выполнены следующие условия:

1) для любых трех элементов a, b, c Î A выполняется свойство ассоциативности:

2) в множестве А существует такой элемент е, что для любого элемента а из этого множества выполняется равенство:

3) для любого элемента а существует элемент а^-1 из этого же множества такой, что

Замечание. Различные множества могут образовывать группу относительно какой-либо операции и не являться группой относительно другой операции.

Число элементов в множестве-носителе называется порядком группы. Группа, в которой операция коммутативна, называется коммутативной или абелевой. Группа, в которой все элементы являются степенями одного элемента, называется циклической. Для абелевых групп часто применяется аддитивная форма записи: операция обозначается, как сложение, а единица обозначается, как 0.