# Monoid

In abstract algebra , a monoid is an algebraic structure consisting of a set with an associative link that can be notated without parentheses and a neutral element . An example are the natural numbers with addition and the number 0 as a neutral element. A monoid in which every element can be inverted is called a group .

## definition

A monoid is a triple consisting of a set , an inner two-digit link${\ displaystyle \ left (M, *, e \ right)}$${\ displaystyle M}$

${\ displaystyle * \ colon M \ times M \ to M, \ quad (a, b) \ mapsto a * b}$

and an excellent element with the following properties in relation to the specified linkage: ${\ displaystyle e \ in M}$

1. Associativity of the link:
${\ displaystyle \ forall a, b, c \ in M ​​\ colon (a * b) * c = a * (b * c)}$
2. ${\ displaystyle e}$is a neutral element :
${\ displaystyle \ forall a \ in M ​​\ colon e * a = a * e = a}$

A monoid is a semigroup with a neutral element. Each group is a monoid, but unlike the group, a monoid does not necessarily have inverse elements.

### Notes on the notation

The associativity (part 1 of the definition) justifies the omission of brackets: For the binary operator , the term is initially ambiguous. However, because the result is invariant with regard to the evaluation sequence determined by brackets, you can do without brackets here. ${\ displaystyle *}$ ${\ displaystyle a * b * c}$

In a monoid, the neutral element is clearly defined. If it is clear from the context which the neutral element is, a monoid is often also written in abbreviated form as a pair . However, this does not correspond to the normal form for (heterogeneous and) universal algebras , since the axiom for the neutral element then requires an existential quantifier - to be avoided . ${\ displaystyle \ left (M, * \ right)}$

The symbol is often used for the link ; one then speaks of a multiplicatively written monoid. The neutral element is then called the unity element and is symbolized by. As is common with ordinary multiplication , the painting point can be left out in many situations. ${\ displaystyle *}$${\ displaystyle \ cdot}$${\ displaystyle 1}$

A monoid can also be noted additively by using the symbol for the link . The neutral element is then called the zero element and is symbolized by. ${\ displaystyle *}$${\ displaystyle +}$${\ displaystyle 0}$

## Examples and counterexamples

 ${\ displaystyle \ left (\ mathbb {N} _ {0}, +, 0 \ right)}$ is a monoid. ${\ displaystyle (\ mathbb {N}, \ cdot, 1)}$ is a monoid. That’s a dioid . ${\ displaystyle (\ mathbb {N} _ {0}, +, 0, \ cdot, 1)}$ ${\ displaystyle (\ mathbb {N},:, 1)}$ is not a monoid because division is not closed and division is not associative. ${\ displaystyle \ mathbb {N}}$ ${\ displaystyle (\ mathbb {Z}, +, 0)}$ (the set of whole numbers with addition) is a monoid. ${\ displaystyle (\ mathbb {Z}, -, 0)}$ is not a monoid because the subtraction is not associative. ${\ displaystyle \ left (\ mathbb {R} ^ {n \ times n}, \ cdot, E \ right)}$ (the set of n × n matrices with the usual matrix multiplication and the unit matrix E ) is a non-commutative monoid. ${\ displaystyle \ left (\ mathbb {R} ^ {3}, \ times, {\ vec {0}} \ right)}$ (the three-dimensional real space with the vector product ) is not a monoid, since the associative law is violated: Let us denote with the i -th unit vector , so is , but . ${\ displaystyle e_ {i}}$${\ displaystyle (e_ {1} \ times e_ {1}) \ times e_ {2} = 0}$${\ displaystyle e_ {1} \ times (e_ {1} \ times e_ {2}) = - e_ {2}}$ ${\ displaystyle (n \ mathbb {Z}, +, 0)}$ (the set of multiples of the integer n with addition) is a monoid. ${\ displaystyle \ left (\ mathbb {Q} _ {+}, +, 0 \ right)}$ (the set of nonnegative rational numbers with addition) is a monoid. ${\ displaystyle (\ mathbb {Q} _ {+} ^ {*}, \ cdot, 1)}$ (the set of positive rational numbers with multiplication) is a monoid. So there is a half ring (even a half body ). ${\ displaystyle (\ mathbb {Q} _ {+}, +, 0, \ cdot, 1)}$ ${\ displaystyle \ left ({\ mathcal {P}} (X), \ cap, X \ right)}$ (the power set of a set X with the intersection operator) is a commutative monoid. ${\ displaystyle (\ Sigma ^ {*}, \ cdot, \ varepsilon)}$ the words above the alphabet form the so-called word monoid with the concatenation and the empty word . ${\ displaystyle \ Sigma}$${\ displaystyle \ cdot}$${\ displaystyle \ varepsilon}$

## Sub-monoid

A subset of a monoid that the neutral element containing and relative to the bond of is finished (i. E., For all is well ) is submonoid of . ${\ displaystyle U \ subseteq M}$${\ displaystyle (M, *, e)}$${\ displaystyle e}$${\ displaystyle *}$${\ displaystyle M}$${\ displaystyle u, v \ in U}$${\ displaystyle u * v \ in U}$${\ displaystyle M}$

## Monoid homomorphism

A monoid homomorphism is defined as a mapping between two monoids , for which holds: ${\ displaystyle f \ colon A \ to B}$${\ displaystyle \ left (A, * _ {A}, e_ {A} \ right)}$${\ displaystyle \ left (B, * _ {B}, e_ {B} \ right)}$

• ${\ displaystyle \ forall x, y \ in A \ colon f (x * _ {A} y) = f (x) * _ {B} f (y)}$,
• ${\ displaystyle f \ left (e_ {A} \ right) = e_ {B}}$.

This is a mapping that is compatible with the links in and and maps the neutral element of to the neutral element of . In terms of abstract algebra, a monoid homomorphism is a homomorphism between monoids. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

The image of a monoid homomorphism is a sub -monoid of the target monoids . ${\ displaystyle f \ left (A \ right)}$${\ displaystyle f \ colon A \ to B}$${\ displaystyle B}$

If the monoid homomorphism is bijective , then it is called a monoid isomorphism and the monoids and isomorphic. ${\ displaystyle f \ colon A \ to B}$ ${\ displaystyle A}$${\ displaystyle B}$

## Free monoid

A monoid is called free if there is a subset such that each element can be represented uniquely as a finite product of elements . is then called the base (producer) of the monoid. ${\ displaystyle (M, *, e)}$${\ displaystyle A \ subset M}$${\ displaystyle M}$${\ displaystyle A}$${\ displaystyle A}$

Is any amount, then the amount forms of all finite sequences in the concatenation writing the sequences as multiplicative combination and the empty sequence as a neutral element , the monoid . This monoid is called the free monoid generated by . If the set is finite, then one usually speaks of the alphabet and of words or words above this alphabet; one obtains the already mentioned word monoid. ${\ displaystyle A}$${\ displaystyle A ^ {*}}$${\ displaystyle A}$${\ displaystyle \ cdot}$${\ displaystyle \ varepsilon}$${\ displaystyle (A ^ {*}, \ cdot, \ varepsilon)}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$

The free monoid over a set plays a role in many areas of theoretical computer science (for example formal language , regular expression , automata theory ). See also the article on the Kleenesche shell for a related term. ${\ displaystyle A ^ {*}}$${\ displaystyle A}$

The free monoid over fulfills the following universal property : If a monoid and any function, then there is exactly one monoid homomorphism with for all . Such homomorphisms are used in theoretical computer science to define formal languages ​​(as subsets of ). ${\ displaystyle A ^ {*}}$${\ displaystyle A}$${\ displaystyle M}$${\ displaystyle f \ colon A \ to M}$ ${\ displaystyle T \ colon A ^ {*} \ to M}$${\ displaystyle T (a) = f \ left (a \ right)}$${\ displaystyle a \ in A}$${\ displaystyle A ^ {*}}$

If a monoid has a subset , so that each element can be represented as a product of elements from unambiguously down to the order of the factors , then one calls freely commutative with the producer . Such a monoid is necessarily commutative. in this case is the set of multisets which contain the elements of . A free monoid with at least a two-element generator is not commutative. ${\ displaystyle (M, *, e)}$${\ displaystyle A}$${\ displaystyle M}$${\ displaystyle A}$${\ displaystyle M}$ ${\ displaystyle A}$${\ displaystyle M}$${\ displaystyle A}$

The free monoid, like the free group, is an example of a free object in category theory .

### Examples

• The monoid is both free and freely commutative with the producer .${\ displaystyle (\ mathbb {N} _ {0}, +, 0)}$${\ displaystyle \ {1 \}}$
• For a set , the set of all mappings from into the nonnegative integers, which only have a value unequal to 0 in finitely many places, is a commutative monoid with the addition of components. It is freely commutative with the elementary functions as generators (there is a Kronecker delta ).${\ displaystyle A}$${\ displaystyle \ operatorname {Abb_ {fin}} (A, \ mathbb {N} _ {0})}$${\ displaystyle A}$${\ displaystyle \ chi _ {a} (x) = \ delta _ {a, x}}$${\ displaystyle \ delta _ {a, x}}$
• The null monoid is free as well as free commutative with the empty set as producer.${\ displaystyle (\ {0 \}, +, 0)}$
• The monoid is freely commutative over the set of prime numbers , but it is not a free monoid.${\ displaystyle (\ mathbb {N}, \ cdot, 1)}$
• The Kleen's envelope is the monoid freely generated by the alphabet with regard to concatenation .${\ displaystyle \ Sigma ^ {*}}$ ${\ displaystyle \ Sigma}$

## literature

• Dirk Hachenberger: Mathematics for Computer Scientists. 2nd Edition. Pearson Studium, Munich 2008, ISBN 978-3-8273-7320-5 , section 6.1.