Полугруппа

Множество М с заданной на нем бинарной ассоциативной операцией f₂ называется полугруппой <М, f₂>. Пусть S полугруппа на алгебраической структуре с f₂ ≡ *. Подмножество S' S называется подполугруппой, если а*b S' для всех а,b S', тогда подмножество S' замкнуто относительно операции *. Для полугруппы для любых a, b, c принадлежащих М выполняется для бинарной операции условие

a * (b * c) = (a * b) * c

Пример 1. Множество непустых слов A⁺ в алфавите A образует полугруппу относительно бинарной операции конкатенации.

Пример 2. Любое множество функций, замкнутое относительно суперпозиции, образует полугруппу.

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

Пример 1. <N, +> является циклической полугруппой, поскольку {1} является системой образующих, т.е каждое натуральное число можно представить, как последовательность знаков 1. Различные слова в алфавите {1} это различные элементы носителя, то есть эта полугруппа свободна.

Теорема (Маркова-Поста). Существует полугруппа, в которой проблема распознования равенства слов алгоритмически неразрешима.

Моноид

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

Моноид – это полугруппа с единицей.

Теорема. Единица моноида единственна.

Доказательство. Пусть . Тогда

Теорема. Всякий моноид над М изоморфен некоторому моноиду преобразований над М.

Доказательство. Пусть М = <М, *> - моноид над М = {e,a,b,c, ….}. Построим. Тогда