Monoid

In abstract algebra, a monoid is an algebraic structure consisting of a set with a clamp- free notierbaren ( associative ) link and a neutral element. An example are the natural numbers with addition and number 0 as a neutral element.

• 5.1 Examples

Definition

A monoid is a triple consisting of a set, an inner two -digit shortcut

And an element having the following excellent properties with respect to the specified link:

1 associativity of the link:

2 is a neutral element:

A monoid is therefore a semigroup with neutral element.

Remarks on notation

The associativity ( part 1 of the definition) justifies the omission of brackets: For the binary operator of the first term is ambiguous. However, because the result is invariant to the order specified by bracketing evaluation order, you can do without the brackets here.

In a monoid, the identity element is uniquely determined. If it is evident from the context, which is the neutral element, a monoid is often shortened written as a pair.

Frequently for the shortcut icon is used, then one speaks of a multiplicatively written monoid. The neutral element is then called unit element and is symbolized by. As is usual also in the ordinary multiplication, the Malpunkt can be omitted in many situations.

A monoid can also be additively note by the icon used for the shortcut. The neutral element is then called zero element and is symbolized by.

Examples and counter-examples

Each group is a monoid, but a monoid, in contrast to the group not necessarily inverse elements.

Submonoid

A subset of a monoid that contains the neutral element and in respect of linking is complete (ie, for all is well ) is called submonoid of.

Monoid homomorphism

A monoid homomorphism is defined as a mapping between two monoids, in which:

• ,
• .

This is therefore a figure that is in the shortcuts and friendly and the neutral element of the neutral element of maps. A monoid homomorphism in the sense of abstract algebra, a homomorphism between monoids.

The image of a monoid homomorphism is a submonoid of Zielmonoids.

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 every element of can be represented as a finite product unique items from. is then called base ( producers ) of the monoid.

Is any amount, then the set of all finite sequences in the concatenation of letter sequences as multiplicative operation and the empty row as the neutral element monoid. This monoid is called by generated free monoid. If the set is finite, then one speaks mostly of the alphabet and words or words over this alphabet; one obtains the Wortmonoid already mentioned.

The free monoid over a set plays a role (for example, formal language, regular expression, automata theory ) in many areas of theoretical computer science. See also the article about the Kleene case for a related term.

The free monoid over satisfies the following universal property: If a monoid and an arbitrary function, then there exists a unique monoid homomorphism with for all. Such homomorphisms are used in theoretical computer science to define formal languages ​​( as subsets of ).

Has a monoid is a subset such that every element of unique up to the order of the factors can be represented as a product of elements, then it is called free commutative with the producer. Such a monoid is necessary commutative. A free monoid with an at least two-element generator is not commutative.

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

Examples

• The monoid is both free and free commutative with the producer.
• For a set is the set of all functions of all the non-negative numbers that have a value equal to 0 only at a finite number of points, with componentwise addition a commutative monoid. It is free commutative with the elementary functions as a generator ( this is a Kronecker delta ).
• The Nullmonoid is both free and free commutative with the empty set as a producer.
• The monoid is free commutative over the set of prime numbers, but it is not a free monoid.
• The Kleene shell is the monoid freely generated by the alphabet with respect to the concatenation.