Monoid

In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. One simple example is the natural numbers with addition, where 0 acts as the identity element because adding 0 does not change any number.

Monoids are special types of semigroups that include this identity element. These kinds of algebraic structures appear in many areas of mathematics. For instance, the functions that map a set to itself form a monoid when we combine them through function composition.

In computer programming, monoids are important for handling things like strings made from a set of characters. Concepts such as transition monoids and syntactic monoids help describe finite-state machines. In theoretical computer science, studying monoids is key to 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 can help us understand ordering in algebra.

Examples

Monoids are special kinds of mathematical sets with rules for combining elements. For example, the natural numbers (like 0, 1, 2, and so on) form a monoid when we add them together, with 0 being the identity element 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 acting on other sets, similar to how groups can act on sets. This is called a monoid act. It involves a set and an operation that follows the rules of the monoid, ensuring that applying the identity element does nothing, and combining operations works smoothly. These ideas are important in areas like studying transitions in systems and automata. A monoid with such an act is known as an operator monoid.

Monoid homomorphisms

A homomorphism between two monoids is a special kind of function that keeps the monoid operation working correctly. It must ensure that when you apply the operation to two elements before or after using the function, the result is the same. Also, it 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 in this way, because it might not correctly handle the identity elements. For example, a function between certain sets of numbers can keep the multiplication working, but it does not map the identity correctly. A bijective homomorphism that also preserves identities is called a monoid isomorphism, meaning the two monoids are essentially the same in structure.

Main article: semigroup homomorphism

Further information: bijective, isomorphism

Equational presentation

Main article: Presentation of a monoid

Monoids can be described using a special way of writing their rules, similar to how groups are described. This is done by choosing some basic pieces called generators and then writing down relationships between these pieces. By using these relationships, we can build and understand the monoid in a clear way. For example, certain sets of rules can describe specific monoids, like the bicyclic monoid or the plactic monoid.

Relation to category theory

Monoids are closely related to a branch of mathematics called category theory. You can think of a monoid as a special kind of category that has only one object. In this view, the elements of the monoid act like mappings from that single object to itself.

Category theory expands the idea of monoids to include categories with many objects. Monoids themselves form a category too, where the mappings between monoids are special functions called homomorphisms. This connection helps mathematicians study monoids using the tools of category theory.

Monoids in computer science

In computer science, many types of data can use a monoid structure. This helps in processing a list of items to get a single result. For example, adding numbers in a list to find the total can be seen as using a monoid operation.

The way monoids work also allows computers to process data faster by using many processors at once. This is useful for big tasks that need a lot of calculations.

MapReduce

MapReduce is a way that computers process 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 turns it into pieces that fit into a monoid. Then, the "Reduce" step combines these pieces until only one piece remains.

For example, imagine you have a collection of items where each item has a label, like the words in 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 the same time, making it faster.

Complete monoids

A complete monoid is a special kind of mathematical structure. It is a commutative monoid, which means it has a way to combine elements that works the same no matter what order you use, and it also 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.