Monoid

related topics
{math, number, function}

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for instance, they can be regarded as categories with a single object. Thus, they capture the idea of function composition within a set. Monoids are also commonly used in computer science, both in its foundational aspects and in practical programming. The transition monoid and syntactic monoid are used in describing finite state machines, 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.

Contents

Definition

A monoid is a set, S, together with a binary operation “•” (pronounced "dot" or "times") that satisfies the following three axioms:

And in mathematical notation we can write these as

  • Closure: a \cdot b \in S \  \forall a,b \in S,
  • Associativity: (a \cdot b) \cdot c = a \cdot (b \cdot c) \forall a,b,c \in S and
  • Identity element: \exists e \in S such that e \cdot a = a \cdot e = a \, \forall a \in S.

Full article ▸

related documents
Exponential function
Interpolation
Operator
Semidirect product
Set (mathematics)
Riemannian manifold
Metric space
Communication complexity
Dirac delta function
Category theory
Taylor's theorem
Extended Euclidean algorithm
Template (programming)
P = NP problem
Hausdorff dimension
Vigenère cipher
Cholesky decomposition
Square root
Integer
Icon (programming language)
Kernel (matrix)
Imaginary unit
Multiplication
Finite set
Tail recursion
Control flow
Cantor's diagonal argument
Equivalence relation
Exponentiation by squaring
Busy beaver