# User Contributed Dictionary

### Noun

- A set which is closed under an associative binary operation, and which contains an element which is an identity for the operation.

#### See also

#### Translations

- Swedish: monoid
- Croatian: monoid

## Croatian

### Noun

hr-noun m# Extensive Definition

In abstract
algebra, a branch of mathematics, a monoid is an
algebraic
structure with a single, associative binary
operation and an identity
element. Monoids occur in a number of branches of mathematics.
In geometry, a monoid
captures the idea of function
composition; indeed, this notion is abstracted in category
theory, where the monoid is a category
with one object.
Monoids are also commonly used to lay a firm algebraic foundation
for computer
science; in this case, the transition
monoid and syntactic
monoid are used in describing a finite
state machine, whereas trace
monoids and history
monoids provide a foundation for process
calculi and concurrent
computing. Some of the more important results in the study of
monoids are the Krohn-Rhodes
theorem and the star
height problem. The history of monoids, as well as a discussion
of additional general properties, are found in the article on
semigroups.

## Definition

A monoid is a set M with binary
operation * : M × M → M, obeying the
following axioms:

- Associativity: for all a, b, c in M, (a*b)*c = a*(b*c)
- Identity element: there exists an element e in M, such that for all a in M, a*e = e*a = a.

- Closure: for all a, b in M, a*b is in M

Alternatively, a monoid is a semigroup with an identity
element.

A monoid satisfies all the axioms of a group
with the exception of having inverses.
A monoid with inverses is a group.

By abuse of
notation we sometimes refer to M itself as a monoid, implying
the presence of identity and operation. A monoid can be denoted by
the tuple (M, *) if the operation needs to be made explicit.

### Generators and submonoids

A submonoid of a monoid M is a subset N of M containing the unit element, and such that, if x,y∈N then x*y∈N. It is then clear that N is itself a monoid, under the binary operation induced by that of M. Equivalently, a submonoid is a subset N such that N=N*, where the superscript * is the Kleene star. For any subset N of M, the monoid N* is the smallest monoid that contains N.A subset N is said to be a generator of M if and
only if M=N*. If N is finite, then M is said to be finitely
generated.

### Commutative monoid

A monoid whose operation is commutative is called a commutative monoid (or, less commonly, an abelian monoid). Commutative monoids are often written additively. Any commutative monoid is endowed with its algebraic preordering ≤, defined by x ≤ y if and only if there exists z such that x + z = y. An order-unit of a commutative monoid M is an element u of M such that for any element x of M, there exists a positive integer n such that x ≤ nu. This is often used in case M is the positive cone of a partially ordered abelian group G, in which case we say that u is an order-unit of G. There is an algebraic construction that will take any commutative monoid, and turn it into a full-fledged abelian group; this construction is known as the Grothendieck group.### Partially commutative monoid

A monoid for which the operation is commutative for some, but not all elements is a trace monoid; trace monoids commonly occur in the theory of concurrent computation.### Acts, transition systems

An operator monoid is a monoid M which acts upon a set X. That is, there is an operation • : M × X → X which is compatible with the monoid operation.- For all x in X: e • x = x.
- For all a, b in M and x in X: a • (b • x) = (a * b) • x.

Operator monoids are also known as acts (since
they resemble a group
action), transition
systems, semiautomata or transformation
semigroups.

## Examples

- Every singleton set gives rise to a one-element (trivial) monoid. For fixed x this monoid is unique, since the monoid axioms require that x*x = x in this case.
- Every group is a monoid and every abelian group a commutative monoid.
- Every bounded semilattice is an idempotent commutative monoid.
- Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining e*e = e and e*s = s = s*e for all s ∈ S.
- The natural numbers, N, form a commutative monoid under addition (identity element zero), or multiplication (identity element one). A submonoid of N under addition is called a numerical monoid.
- The elements of any unital ring, with
addition or multiplication as the operation.
- The integers, rational numbers, real numbers or complex numbers, with addition or multiplication as operation.
- The set of all n by n matrices over a given ring, with matrix addition or matrix multiplication as the operation.

- The set of all finite strings over some fixed alphabet Σ forms a monoid with string concatenation as the operation. The empty string serves as the identity element. This monoid is denoted Σ* and is called the free monoid over Σ.
- Fix a monoid M, and consider its power set P(M) consisting of all subsets of M. A binary operation for such subsets can be defined by S * T = . This turns P(M) into a monoid with identity element . In the same way the power set of a group G is a monoid under the product of group subsets.
- Let S be a set. The set of all functions S → S forms a monoid under function composition. The identity is just the identity function. If S is finite with n elements, the monoid of functions on S is finite with nn elements.
- Generalizing the previous example, let C be a category and X an object in C. The set of all endomorphisms of X, denoted EndC(X), forms a monoid under composition of morphisms. For more on the relationship between category theory and monoids see below.
- The set of homeomorphism classes of compact surfaces with the connected sum. Its unit element is the class of the ordinary 2-sphere. Furthermore, if a denotes the class of the torus, and b denotes the class of the projective plane, then every element c of the monoid has a unique expression the form c=na+mb where n is the integer ≥ 0 and m=0,1, or 2. We have 3b=a+b.
- Let be a cyclic monoid of order n, that is, = \. Then f^n = f^k for some 0 \le k \le n. In fact, each such k gives a distinct monoid of order n, and every cyclic monoid is isomorphic to one of these.

Moreover, f can be considered as a function on
the points given by

- \begin

or, equivalently

- f(i) := \begin i+1, & \mbox 0 \le i

Multiplication of elements in is then given by
function composition.

Note also that when k = 0 then the function f is
a permutation of \ and gives the unique cyclic group
of order n.

## Properties

In a monoid, one can define positive integer
powers of an element x : x1=x, and xn=x*...*x (n times) for n>1
. The rule of powers xn+p=xn * xp is obvious.

Directly from the definition, one can show that
the identity element e is unique. Then, for any x , one can set
x0=e and the rule of powers is still true with nonnegative
exponents.

It is possible to define invertible
elements: an element x is called invertible if there exists an
element y such x*y = e and y*x = e. The element y is called the
inverse of x . Associativity guarantees that inverses, if they
exist, are unique.

If y is the inverse of x , one can define
negative powers of x by setting x−1=y and
x−n=y*...*y (n times) for n>1 . And the rule of
exponents is still verified for all n,p rational integers. This is
why the inverse of x is usually written x−1. The set of
all invertible elements in a monoid M, together with the operation
*, forms a group.
In that sense, every monoid contains a group (if only the trivial
one consisting of the identity alone).

However, not every monoid sits inside a group.
For instance, it is perfectly possible to have a monoid in which
two elements a and b exist such that a*b = a holds even though b is
not the identity element. Such a monoid cannot be embedded in a
group, because in the group we could multiply both sides with the
inverse of a and would get that b = e, which isn't true. A monoid
(M,*) has the cancellation
property (or is cancellative) if for all a,
b and c in M, a*b = a*c always implies b = c and b*a = c*a always
implies b = c. A commutative monoid with the cancellation property
can always be embedded in a group. That's how the additive
group of the integers (a group with operation +) is constructed
from the additive monoid of natural numbers (a commutative monoid
with operation + and cancellation property). However, a
non-commutative cancellative monoid need not be embeddable in a
group.

If a monoid has the cancellation property and is
finite, then it is in fact a group.

The right- and left-cancellative elements of a
monoid each in turn form a submonoid (i.e. obviously include the
identity and not so obviously are closed under the operation). This
means that the cancellative elements of any commutative monoid can
be extended to a group.

An inverse monoid, is a monoid where for every a
in M, there exists a unique a-1 in M such that a=a*a-1*a and
a-1=a-1*a*a-1. If an inverse monoid is cancellative, then it is a
group.

## Monoid homomorphisms

A homomorphism between two
monoids (M,*) and (M′,•) is a function f : M
→ M′ such that

- f(x*y) = f(x)•f(y) for all x, y in M
- f(e) = e′

Not every magma
(groupoid) homomorphism is a monoid homomorphism since it may
not preserve the identity. Contrast this with the case of group
homomorphisms: the axioms of group theory
ensure that every magma
(groupoid) homomorphism between groups preserves the identity.
For monoids this isn't always true and it is necessary to state it
as a separate requirement.

A bijective monoid homomorphism
is called a monoid isomorphism. Two monoids are
said to be isomorphic if there is an isomorphism between
them.

## Monoid congruence and the quotient monoid

A monoid congruence is an equivalence relation that is compatible with the monoid product. That is, it is a subset- \sim\;\subseteq M\times M

such that it is reflexive, symmetric and
transitive (just as every equivalence relation must be), and also
has the property that if x\sim y\, and u\sim v\, for every x,y,u
and v in M, then one has that x*u\sim y*v\,.

A monoid congruence induces congruence
classes

- [m] = \

and the monoid operation * induces a binary
operation \circ on the congruence classes:

- [u]\circ [v] = [u*v]

which is a monoid homomorphism. It is also
clearly associative, and so the set of all congruence classes are a
monoid as well. This monoid is called the quotient monoid, and may
be written as

- M/\sim\; = \.

Several additional notations are common. Give a
subset L\subseteq M, one writes

- [L] = \

for the set of congruence classes induced by L.
In this notation, clearly [M]=M/\sim. In general, however, [L] is
not a monoid. Going in the opposite direction, if X\subseteq [M] is
a subset of the quotient monoid, one writes

- \bigcup X = \.

This is, of course, just the set-theoretic
union of the members of X. In general, \bigcup X is not a
monoid.

Clearly, one has L\subseteq \bigcup[L] and
\left[\bigcup X\right]=X.

## Equational presentation

Monoids may be given a presentation, much in the same way that groups can be specified by means of a group presentation. One does this by specifying a set of generators \Sigma, and a set of relations on the free monoid \Sigma^*. One does this by extending (finite) binary relations on \Sigma^* to monoid congruences, and then constructing the quotient monoid, as above.Given a binary relation R\subseteq
\Sigma^*\times\Sigma^*, one defines its symmetric closure as R\cup
R^. This can be extended to a symmetric relation E\subseteq
\Sigma^*\times\Sigma^* by defining x\sim_E y\, if and only if x=sut
and y=svt for some strings s,t\in \Sigma^* and (u,v)\in R\cup R^.
Finally, one takes the reflexive and transitive closure of E, which
is then a monoid congruence.

In the typical situation, the relation R is
simply given as a set of equations, so that R=\. Thus, for example,

- \langle p,q\,\vert\; pq=1\rangle

- \langle a,b \,\vert\; aba=baa, bba=bab\rangle

## Relation to category theory

Monoids can be viewed as a special class of categories. Indeed, the axioms required of a monoid operation are exactly those required of morphism composition when restricted to the set of all morphisms whose source and target is a given object. That is,- A monoid is, essentially, the same thing as a category with a single object.

Likewise, monoid homomorphisms are just functors between single object
categories. In this sense, category theory can be thought of as an
extension of the concept of a monoid. Many definitions and theorems
about monoids can be generalised to small categories with more than
one object.

Monoids, just like other algebraic structures,
also form their own category, Mon, whose objects are monoids and
whose morphisms are monoid homomorphisms.

There is also a notion of monoid
object which is an abstract definition of what is a monoid in a
category.

## See also

## References

- John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford ISBN 0-19-851194-9

monoid in Catalan: Monoide

monoid in Czech: Monoid

monoid in German: Monoid

monoid in Estonian: Monoid

monoid in Spanish: Monoide

monoid in French: Monoïde

monoid in Croatian: Monoid

monoid in Italian: Monoide

monoid in Hebrew: מונואיד (מבנה אלגברי)

monoid in Hungarian: Monoid

monoid in Dutch: Monoïde

monoid in Japanese: モノイド

monoid in Occitan (post 1500): Monoïde

monoid in Polish: Monoid

monoid in Portuguese: Monóide

monoid in Romanian: Monoid

monoid in Russian: Моноид

monoid in Slovenian: Monoid

monoid in Serbian: Моноид

monoid in Finnish: Monoidi

monoid in Swedish: Monoid (matematik)

monoid in Turkish: Birlik

monoid in Ukrainian: Моноїд

monoid in Chinese: 幺半群