Information & explanations, latest texts & monographs on
Monoid (including recent related patents.)
Monoid
A monoid is a magma, i.e. a pair (M,*), where M is a set and * is a binary operation on M, obeying the following rules:
closure: for all a, b in M, a*b is in M (this is implied by the notion of binary operation, and does not need to be required separately)
identity: there exists an element e in M, such that for all a in M, a*e = e*a = a.
associativity: * is an associative operation; that is, for all a, b, c in M, (a*b)*c = a*(b*c)
In other words, a monoid is a semigroup with an identity element.
Some examples of monoids:
- The natural numbers with addition as the operation (identity element zero), or with multiplication as operation (identity element one).
- The elements of any unitary ring, with addition or multiplication as the operation.
- Any group.
- The set of all finite strings (including the empty string) over some fixed alphabet Σ, with string concatenation as the operation. The empty string serves as the identity element. This monoid is often denoted Σ* and is called the "free monoid over Σ" by mathematicians.
- Pick an object of a category and consider the set of all morphisms from this object to itself, with composition as the operation. Some examples from well-known categories include:
- 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}.
Directly from the definition, one can show that the identity element e is unique. Then 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.
It turns out that the set of all invertible elements, 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 exist two elements a and b and 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=aa-1a and a-1=a-1aa-1.
Monoids can be viewed as a special class of categories.
The axioms required of a monoid operation are exactly those required of a
category operation when restricted to the set of all morphisms which start and end at a given object. Hence, a monoid is essentially the same thing as a category with a single object. Many definitions and theorems about monoids can be generalised to small categories with more than one object.
Topics in mathematics related to structure
Abstract algebra | Number theory | Algebraic geometry | Group theory | Monoids | Analysis | Topology | Linear algebra | Graph theory | Universal algebra | Category theory
This article is adapted from from Wikipedia All Wikipedia article text is available under the terms of the GNU Free Documentation License
Finitely generated commutative monoids by J. C. Rosales
Monoids and Semigroups With Applications: Proceedings of the Berkeley Workshop in Monoids, Berkeley, 31 July - 5 August 1989 by John Rhodes
Monoids, Acts and Categories with Applications to Wreath Products and Graphs (Expositions in Mathematics, Vol. 29) by Mati Kilp
Separable Algebroids (Memoirs of the American Mathematical Society, 333) by Barry Mitchell
On linear representations of affine groups by Manfred Bernd Wischnewsky
Fixed points of some operators defined on free monoids by Wit Forys
Algèbres de Lie libres et monoïdes libres : bases des algèbres de Lie libres et factorisations des monoïdes libres by Gérard Viennot
Galois-Theorie in monoidalen Kategorien by Thomas S. Ligon
Linear Algebraic Monoids by Mohan S. Putcha
Refinement Monoids by Dobbertin
Recent Monoid related patents
From USPTO:
6587844: System and methods for optimizing networks of weighted unweighted directed graphs
6493449: Method and apparatus for cryptographically secure algebraic key establishment protocols based on monoids
6385725: System and method for providing commitment security among users in a computer network
6277416: Pesticides comprising benzophenanthridine alkaloids
6088689: Multiple-agent hybrid control architecture for intelligent real-time control of distributed nonlinear processes
5963447: Multiple-agent hybrid control architecture for intelligent real-time control of distributed nonlinear processes
5915259: Document schema transformation by patterns and contextual conditions
5812072: Data conversion technique
5596682: Method and apparatus of automated theorem proving for information processing
|