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
and an excellent element with the following properties in relation to the specified linkage:
-
Associativity of the link:
-
is a neutral element :
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.
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 .
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.
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.
Examples and counterexamples
is a monoid. | |
is a monoid. That’s a dioid . | |
is not a monoid because division is not closed and division is not associative. | |
(the set of whole numbers with addition) is a monoid. | |
is not a monoid because the subtraction is not associative. | |
(the set of n × n matrices with the usual matrix multiplication and the unit matrix E ) is a non-commutative monoid. | |
(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 . | |
(the set of multiples of the integer n with addition) is a monoid. | |
(the set of nonnegative rational numbers with addition) is a monoid. | |
(the set of positive rational numbers with multiplication) is a monoid. So there is a half ring (even a half body ). | |
(the power set of a set X with the intersection operator) is a commutative monoid. | |
the words above the alphabet form the so-called word monoid with the concatenation and the empty word . |
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 .
Monoid homomorphism
A monoid homomorphism is defined as a mapping between two monoids , for which holds:
- ,
- .
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.
The image of a monoid homomorphism is a sub -monoid of the target monoids .
If the monoid homomorphism is bijective , then it is called a monoid isomorphism and the monoids and isomorphic.
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.
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.
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.
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 ).
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.
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 .
- 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 ).
- The null monoid is free as well as free commutative with the empty set as producer.
- The monoid is freely commutative over the set of prime numbers , but it is not a free monoid.
- The Kleen's envelope is the monoid freely generated by the alphabet with regard to concatenation .
literature
- Dirk Hachenberger: Mathematics for Computer Scientists. 2nd Edition. Pearson Studium, Munich 2008, ISBN 978-3-8273-7320-5 , section 6.1.