FACTOID # 27: If you're itching to live in a trailer park, hitch up your home and head to South Carolina, where a whopping 18% of residences are mobile homes.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Monoid" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... In mathematics, associativity is a property that a binary operation can have. ... In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...

Contents

Definition

A monoid is a set M with binary operation * : M × MM, obeying the following axioms: In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ...

  • 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 In mathematics, associativity is a property that a binary operation can have. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...

  • 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. In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ...


Alternatively, a monoid is a semigroup with an identity element. In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...


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. This picture illustrates how the hours in a clock form a group. ... In mathematics, the inverse of an element x, with respect to an operation *, is an element x such that their compose gives a neutral element. ...


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. In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered sets. ... In abstract algebra, an ordered group is a group G equipped with a partial order ≤ which is translation-invariant; in other words, ≤ has the property that, for all a, b, and g in G, if a ≤ b then ag ≤ bg and ga ≤ gb. ... In abstract algebra, an ordered group is a group G equipped with a partial order ≤ which is translation-invariant; in other words, ≤ has the property that, for all a, b, and g in G, if a ≤ b then ag ≤ bg and ga ≤ gb. ...


An operator monoid is a monoid M which acts upon a set X. That is, there is an operation • : M × XX 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.

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 sS.
  • 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 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 SS 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 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 0,1,2,..,n − 1 given by In mathematics, a singleton is a set with exactly one element. ... This picture illustrates how the hours in a clock form a group. ... In mathematics, an abelian group, also called a commutative group, is a group such that for all a and b in G. In other words, the order of elements in a product doesnt matter. ... A semilattice is a mathematical concept with two definitions, one as a type of ordered set, the other as an algebraic structure. ... In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... 0 (zero) is both a number and a numerical digit used to represent that number in numerals. ... Look up one in Wiktionary, the free dictionary. ... In mathematics, an associative algebra is unital if it contains a multiplicative identity element, i. ... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... The integers are commonly denoted by the above symbol. ... In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ... The operations on matrices differ from similar operations of scalar algebra in several respects. ... This article gives an overview of the various ways to perform matrix multiplication. ... In computer programming and some branches of mathematics, strings are sequences of various simple objects. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... In abstract algebra, the free monoid on a set A is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from A, with the binary operation of concatenation. ... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, one can define a product of group subsets in a natural way. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes which preserve structure. ... In mathematics, an endomorphism is a morphism (or homomorphism) from a mathematical object to itself. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In the mathematical field of topology a homeomorphism or topological isomorphism (from the Greek words homeos = identical and morphe = shape) is a special isomorphism between topological spaces which respects topological properties. ... In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ... In mathematics, a closed manifold, or compact manifold, is a manifold that is compact as a topological space. ... In geometric topology, a connected sum of two connected -dimensional manifolds is a manifold formed by deleting a ball inside each manifold and gluing together the resulting boundary spheres. ...

begin{bmatrix} 0 & 1 & 2 & ... & n-2 & n-1  1 & 2 & 3 & ... & n-1 & kend{bmatrix}

or, equivalently

f(i) := begin{cases} i+1, & mbox{if } 0 le i < n-1  k, & mbox{if } i = n-1. end{cases}

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. In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na...


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. In mathematics, the inverse of an element x, with respect to an operation *, is an element x such that their compose gives a neutral element. ...


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. This picture illustrates how the hours in a clock form 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. In mathematics, an element a in a magma (M,*) has the left cancellation property (or is left-cancellative) if for all b and c in M, a * b = a * c always implies b = c. ... In mathematics, an element a in a magma (M,*) has the left cancellation property (or is left-cancellative) if for all b and c in M, a*b = a*c always implies b = c. ...


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. If an inverse monoid is cancellative, then it is a group.


A submonoid of a monoid M, is a subset N of M containing the unit element, and such that, if x,yN then x*yN. It is then clear that N is itself a monoid, under the binary operation induced by that of M.


Monoid homomorphisms

A homomorphism between two monoids (M,*) and (M′,•) is a function f : MM′ such that In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). ...

  • 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. Given two groups (G, *) and (H, ·), a group homomorphism from (G, *) to (H, ·) is a function h : G -> H such that for all u and v in G it holds that h(u * v) = h(u) · h(v) From this property, one can deduce that h maps the identity element... Group theory is that branch of mathematics concerned with the study of groups. ...


A bijective monoid homomorphism is called a monoid isomorphism. Two monoids are said to be isomorphic if there is an isomorphism between them. In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...


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, In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ...

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. Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ...


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. In category theory, a monoid (or monoid object) in a monoidal category C is an object M together with two morphisms called multiplication, and called unit, such that the diagrams and commute. ...


See also

In mathematics, the Grothendieck group construction in abstract algebra constructs an abelian group from a commutative monoid in the best possible way. ...

References


  Results from FactBites:
 
Monoid - Wikipedia, the free encyclopedia (1059 words)
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element.
A monoid whose operation is commutative is called a commutative monoid (or, less commonly, an abelian monoid).
The axioms required of a monoid operation are exactly those required of morphism composition when restricted to the set of all morphisms which start and end at a given object (i.e.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m