Functional Programming

Moniod Part2

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 implied by the notion of a binary operation.
Alternatively, a monoid is a semigroup with an identity element; it can also be understood as a category with closure.
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.

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). A submonoid of N under addition is called a numerical monoid. 
• The elements of any unital ring, with addition or multiplication as the operation. 
o The integers, rational numbers, real numbers or complex numbers, with addition or multiplication as operation. 
o 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 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 < f > be a cyclic monoid of order n, that is, < f > = {f0,f1,..,fn − 1}. Then fn = fk for some . In fact, each such k gives a distinct monoid of order n, and every cyclic monoid is isomorphic to one of these.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s