Приветствую Вас, уважаемые Читатели! Продолжаем тему одного из последних материалов, в котором речь шла об одной из простейших алгебраических структур - полугруппе. В этой статье я напомню лишь определение, а все желающие могут перед прочтением получить более подробную информацию по ссылке:
К сожалению, Дзен так и не внедрил (хотя долго обещает) рубрикатор статей, который был бы незаменимой поддержкой для такого рода связанных по смыслу материалов. Ну что же, будем надеяться и ждать.
Итак, по определению полугруппа это:
- пара из множества произвольного вида (числа, матрицы, словари и т.д.) и бинарной операции (например, сложение, сцепление, перемножение и т.д.), обладающая свойством замкнутости (результат применения операции не выходит "за границы" множества и ассоциативности (возможности произвольного распределения скобок).
Ранее я говорил, что мы добавим еще одно требование (можно сказать, аксиому), которая нам позволит из полугруппы получить более сложного представителя алгебраического зоопарка - моноид.
И таким требованием будет существование в полугруппе единичного элемента.
Что же такое единичный элемент? На самом деле понятие "единицы" нужно понимать абсолютно абстрактно - это такое элемент (входящий в исходное множество!), который при применении к нему операции не меняет исходный аргумент:
пусть А - элемент множества Х. е - единичный элемент, если:
Аe = еА = А
Тут стоит сделать отступление: формально может существовать правый единичный элемент (такой, что Аe=А , но еА - не равно А) и левый (такой, что eА=А , но Ае - не равно А).
В курсе алгебры доказывается, что если в каком-то алгебраической структуре (например, полугруппе) существует правый и левый единичный элемент, то они совпадают.
И самым важным следствием является тот факт, что если единичный элемент существует, то он единственный.
Давайте на практике
В прошлой статье в качестве самого простого и интуитивно понятного примера полугруппы приводилась пара из множества натуральных чисел и определенной на нём операции сложения:
Есть ли в этой полугруппе единичный элемент? Очевидно, что сложение с любым натуральным число изменяет результат, т.е. не существует такого натурального числа е, такого что x + е = е+х= х.
- Но мы легко найдем выход: добавим к нашему множеству натуральных чисел "0". Именно "0" обладает свойством, которое мы требуем от "единицы" в алгебраическом понимании.
Тут еще одна ремарка: единичный элемент (его еще называют нейтральным) в алгебраических структурах с умножением принято называть единицей, в структурах со сложением - нулем. Вот такая игра слов.
Вот так мы и получаем моноид - полугруппу с единичным элементом!
Аналогичные моноиды можно "вырастить" и из других примеров полугрупп, которые мы рассматривали в прошлом материале.
Для примера со словарем всевозможных сочетаний маленьких букв русского алфавита единичным элементом является " " - пустой список, для полугруппы матриц с определенным на неё умножением - единичная матрица:
Для полугруппы матриц с определенным на ней сложением единичным элементом будет матрица, полностью состоящая из нулевых элементов.
Применение моноидов на практике обычно связывают моделью распределенных вычислений MapReduce, разработанной корпорацией Google и предназначенной для параллельных вычислений на огромных объемах данных. Кроме того, концепция моноида широко используется как в объектно-ориентированном, так и в функциональном программировании. Однако, это уже вопрос к программистам...
Нам же, как апологетам чистой математики, для восхищения достаточно малого - существования, строгости и изящности. Спасибо за внимание!
В следующей статье поговорим о менее тривиальных примеров моноидов. Подписывайтесь, будет много интересного!