Monoid

From Wikipedia, the free encyclopedia

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element.

Contents 1 Definition 2 Examples 3 Properties 4 Monoid homomorphisms 5 Relation to category theory 6 External links

[edit] 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.

One often sees the additional axiom

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

though, strictly speaking, this axiom is not necessary as it is implied by the notion of a binary operation.

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 the same thing as a group.

A monoid whose operation is commutative is called a commutative monoid (or, less commonly, an abelian monoid). 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.

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.

[edit] Examples

• Every singleton set {x} 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).
• 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 = {s * t : s in S and t in T}. This turns P(M) into a monoid with identity element {e}. 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 nⁿ elements.
• Generalizing the previous example, let C be a category and X an object in C. The set of all endomorphisms of X, denoted End_C(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 < f > be a cyclic monoid of order n, that is, < f > = {f⁰,f¹,..,f^{n − 1}}. Then fⁿ = f^k for some . 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 0,1,2,..,n − 1 given by

or, equivalently

Multiplication of elements in < f > is then given by function composition.

Note also that when k = 0 then the function f is a permutation of {0,1,2,..,n − 1} and gives the unique cyclic group of order n.

[edit] Properties

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

Directly from the definition, one can show that the identity element e is unique. Then, for any x , one can set x⁰=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⁻¹=y and x⁻ⁿ=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⁻¹. 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.

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 integers (a group with operation +) are constructed from the 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.

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.

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.

[edit] 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′

where e and e′ are the identities on M and M′ respectively.

Not every magma 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 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.

[edit] 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.

More precisely, given a monoid (M,*), one can construct a small category with only one object and whose morphisms are the elements of M. The composition of morphisms is given by the monoid operation *.

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.

[edit] External links

• Eric W. Weisstein, Monoid at MathWorld.
• Monoid at PlanetMath.