Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that a semigroup need not have an identity element. It also (originally) generalized a group (a monoid with all inverses) to a type where every element did not have to have an inverse, thus the name semigroup.

The binary operation of a semigroup is most often denoted multiplicatively:, or simply, denotes the result of applying the semigroup operation to the ordered pair . The operation is required to be associative so that for all x, y and z, but need not be commutative so that does not have to equal (contrast to the standard multiplication operator on real numbers, where xy = yx).

By definition, a semigroup is an associative magma. A semigroup with an identity element is called a monoid. A group is then a monoid in which every element has an inverse element. Semigroups must not be confused with quasigroups which are sets with a not necessarily associative binary operation such that division is always possible.

The formal study of semigroups began in the early 20th century. Semigroups are important in many areas of mathematics because they are the abstract algebraic underpinning of "memoryless" systems: time-dependent systems that start from scratch at each iteration. In applied mathematics, semigroups are fundamental models for linear time-invariant systems. In partial differential equations, a semigroup is associated to any equation whose spatial evolution is independent of time. The theory of finite semigroups has been of particular importance in theoretical computer science since the 1950s because of the natural link between finite semigroups and finite automata. In probability theory, semigroups are associated with Markov processes (Feller 1971).