Monoid

In abstract algebra, a monoid is a group of things with a special way to combine them. This way of combining must follow a rule called associative and there must be a special item called an identity element. The identity element doesn't change anything when it is combined with other items.

One simple example is the natural numbers with addition. Here, 0 is the identity element because adding 0 to any number leaves that number unchanged.

Monoids are a type of semigroups that always have this identity element. These kinds of algebraic structures show up in many parts of mathematics. For example, the rules for joining functions together can form a monoid.

In computer programming, monoids help us work with strings made from characters. Ideas such as transition monoids and syntactic monoids help explain finite-state machines. In theoretical computer science, learning about monoids is important for understanding automata theory and formal language theory.

Definition

A monoid is a special kind of math structure. It has a group of items, called a set, and a way to combine any two items together, called a binary operation. This combining must follow two important rules.

First, when you combine three items, it doesn’t matter which pair you combine first. This is called associativity.

Second, there must be a special item that doesn’t change anything when you combine it with another item. This is called an identity element.

In simple terms, a monoid is like a semigroup but with an extra identity element.

Monoid structures

A submonoid is a smaller group inside a monoid that follows the same rules. It must include the identity element and stay closed under the monoid's operation.

A commutative monoid is a monoid where the operation works the same forward and backward, like adding numbers. These monoids help us understand ordering in algebra.

Examples

Monoids are special math sets with rules for combining things. For example, the natural numbers (like 0, 1, 2, and so on) form a monoid when we add them, with 0 being the identity because adding 0 doesn’t change the number.

Other examples include:

• The set {False, True} with the AND operation, where True is the identity.
• The set of natural numbers under multiplication, where 1 is the identity.
• The set of all subsets of a set under union, where the empty set is the identity.

Acts and operator monoids

In algebra, a monoid has a special way of working with other sets, much like how groups can work with sets. This is called a monoid act. It uses a set and an operation that follows the monoid's rules. This means using the identity element does not change anything, and combining operations works well together. These ideas help us understand things like changes in systems and automata. A monoid with such an act is called an operator monoid.

Monoid homomorphisms

A homomorphism between two monoids is a special kind of function. It makes sure that the monoid operation still works correctly. This means that applying the operation before or after using the function gives the same result. It also must map the identity element of the first monoid to the identity element of the second monoid.

Not every function that works for semigroups will work for monoids, because it might not handle the identity elements properly.

Main article: semigroup homomorphism

Further information: bijective, isomorphism

Equational presentation

Main article: Presentation of a monoid

Monoids can be described using a special set of rules. This is similar to how groups are described. We pick some basic pieces called generators. Then we write down the relationships between these pieces. These relationships help us understand the monoid better. Some rules can describe special monoids, like the bicyclic monoid or the plactic monoid.

Relation to category theory

Monoids are connected to a part of mathematics called category theory. A monoid is like a special kind of category with just one object. In this idea, the parts of the monoid work like paths from that one object back to itself.

Category theory grows the idea of monoids to include categories with many objects. Monoids also form their own category, where the paths between monoids are special functions called homomorphisms. This link helps mathematicians learn about monoids using the methods of category theory.

Monoids in computer science

In computer science, data can often be organized in a special way called a monoid. This helps computers work with lists of items to find one result. For example, adding up numbers in a list to get the total is an example of using a monoid.

Monoids also help computers work faster by letting them use many processors together. This is helpful for big jobs that need a lot of calculations.

MapReduce

MapReduce is a way that computers handle large amounts of data, and it uses the idea of monoids. In MapReduce, there are usually two or three steps. First, the "Map" step takes data and breaks it into smaller parts that fit into a monoid. Then, the "Reduce" step combines these parts until only one piece is left.

For example, imagine you have a list of words from a book. The Map step might count how many times each word appears. The Reduce step then adds up these counts. This process can be done by many computers at once, which makes it faster.

Complete monoids

A complete monoid is a special kind of mathematical structure. It is a commutative monoid, meaning it has a way to combine elements that works the same no matter the order used, and it has an identity element.

This structure also includes a special operation for adding up many elements at once. This operation follows certain rules, making the structure useful in advanced areas of mathematics.