Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
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. Associativity is formally expressed as that for all, and in the semigroup.
Semigroups may be considered a special case of magmas, where the operation is associative, or as a generalization of groups, without requiring the existence of an identity element or inverses. As in the case of groups or magmas, the semigroup operation need not be commutative, so is not necessarily equal to ; a well-known example of an operation that is associative but non-commutative is matrix multiplication. If the semigroup operation is commutative, then the semigroup is called a commutative semigroup or it may be called an abelian semigroup.
A monoid is an algebraic structure intermediate between semigroups and groups, and is a semigroup having an identity element, thus obeying all but one of the axioms of a group: existence of inverses is not required of a monoid. A natural example is strings with concatenation as the binary operation, and the empty string as the identity element. Restricting to non-empty strings gives an example of a semigroup that is not a monoid. Positive integers with addition form a commutative semigroup that is not a monoid, whereas the non-negative integers do form a monoid. A semigroup without an identity element can be easily turned into a monoid by just adding an identity element. Consequently, monoids are studied in the theory of semigroups rather than in group theory. Semigroups should not be confused with quasigroups, which are generalization of groups in a different direction; the operation in a quasigroup need not be associative but quasigroups preserve from groups the notion of division. Division in semigroups is not possible in general.
The formal study of semigroups began in the early 20th century. Early results include a Cayley theorem for semigroups realizing any semigroup as a transformation semigroup, in which arbitrary functions replace the role of bijections in group theory. A deep result in the classification of finite semigroups is Krohn–Rhodes theory, analogous to the Jordan–Hölder decomposition for finite groups. Some other techniques for studying semigroups, like Green's relations, do not resemble anything in group theory.
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 via the syntactic monoid. In probability theory, semigroups are associated with Markov processes. In other areas of 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.
There are numerous special classes of semigroups, semigroups with additional properties, which appear in particular applications. Some of these classes are even closer to groups by exhibiting some additional but not all properties of a group. Of these we mention: regular semigroups, orthodox semigroups, semigroups with involution, inverse semigroups and cancellative semigroups. There are also interesting classes of semigroups that do not contain any groups except the trivial group; examples of the latter kind are bands and their commutative subclass – semilattices, which are also ordered algebraic structures.

Definition

A semigroup is a set together with a binary operation that satisfies the associative property:
More succinctly, a semigroup is an associative magma.

Examples of semigroups

Empty semigroup: the empty set forms a semigroup with the empty function as the binary operation.
Semigroup with one element: there is essentially only one, the singleton with operation.
Semigroup with two elements: there are five that are essentially different.
A null semigroup on any nonempty set with a chosen zero, or a left/right zero semigroup on any set.
The "flip-flop" monoid: a semigroup with three elements representing the three operations on a switch – set, reset, and do nothing. This monoid plays a central role in Krohn-Rhodes theory.
The set of positive integers with addition.
The set of integers with minimum or maximum.
Square nonnegative matrices of a given size with matrix multiplication.
Any ideal of a ring with the multiplication of the ring.
The set of all finite strings over a fixed alphabet with concatenation of strings as the semigroup operation—called the free semigroup over. With the empty string included, this semigroup becomes the free monoid over.
A probability distribution together with all convolution powers of, with convolution as the operation. This is called a convolution semigroup.
Transformation semigroups and monoids.
The set of continuous functions from a topological space to itself with composition of functions forms a monoid with the identity function acting as the identity. More generally, the endomorphisms of any object of a category form a monoid under composition.
The product of faces of an arrangement of hyperplanes.
Basic concepts

Identity and zero

A left identity of a semigroup is an element such that for all in,. Similarly, a right identity is an element such that for all in,. Left and right identities are both called one-sided identities. A semigroup may have one or more left identities but no right identity, and vice versa.
A two-sided identity is an element that is both a left and right identity. Semigroups with a two-sided identity are called monoids. A semigroup may have at most one two-sided identity. If a semigroup has a two-sided identity, then the two-sided identity is the only one-sided identity in the semigroup. If a semigroup has both a left identity and a right identity, then it has a two-sided identity.
A semigroup without identity may be embedded in a monoid formed by adjoining an element to and defining for all. The notation denotes a monoid obtained from by adjoining an identity if necessary.
Similarly, every magma has at most one absorbing element, which in semigroup theory is called a zero. Analogous to the above construction, for every semigroup, one can define, a semigroup with 0 that embeds.

Subsemigroups and ideals

The semigroup operation induces an operation on the collection of its subsets: given subsets and of a semigroup, their product, written commonly as, is the set. In terms of this operation, a subset is called

a subsemigroup if is a subset of,
a right ideal if is a subset of, and
a left ideal if is a subset of.

If is both a left ideal and a right ideal then it is called an ideal.
If is a semigroup, then the intersection of any collection of subsemigroups of is also a subsemigroup of.
So the subsemigroups of form a complete lattice.
An example of a semigroup with no minimal ideal is the set of positive integers under addition. The minimal ideal of a commutative semigroup, when it exists, is a group.
Green's relations, a set of five equivalence relations that characterise the elements in terms of the principal ideals they generate, are important tools for analysing the ideals of a semigroup and related notions of structure.
The subset with the property that every element commutes with any other element of the semigroup is called the center of the semigroup. The center of a semigroup is actually a subsemigroup.

Homomorphisms and congruences

A semigroup homomorphism is a function that preserves semigroup structure. A function between two semigroups is a homomorphism if the equation
holds for all elements, in, i.e. the result is the same when performing the semigroup operation after or before applying the map.
A semigroup homomorphism between monoids preserves identity if it is a monoid homomorphism. But there are semigroup homomorphisms that are not monoid homomorphisms, e.g. the canonical embedding of a semigroup without identity into. Conditions characterizing monoid homomorphisms are discussed further. Let be a semigroup homomorphism. The image of is also a semigroup. If is a monoid with an identity element, then is the identity element in the image of. If is also a monoid with an identity element and belongs to the image of, then, i.e. is a monoid homomorphism. Particularly, if is surjective, then it is a monoid homomorphism.
Two semigroups and are said to be isomorphic if there exists a bijective semigroup homomorphism. Isomorphic semigroups have the same structure.
A semigroup congruence is an equivalence relation that is compatible with the semigroup operation. That is, a subset that is an equivalence relation and and implies for every in. Like any equivalence relation, a semigroup congruence induces congruence classes
and the semigroup operation induces a binary operation on the congruence classes:
Because is a congruence, the set of all congruence classes of forms a semigroup with, called the quotient semigroup or factor semigroup, and denoted. The mapping is a semigroup homomorphism, called the quotient map, canonical surjection or projection; if is a monoid then quotient semigroup is a monoid with identity. Conversely, the kernel of any semigroup homomorphism is a semigroup congruence. These results are nothing more than a particularization of the first isomorphism theorem in universal algebra. Congruence classes and factor monoids are the objects of study in string rewriting systems.
A nuclear congruence on is one that is the kernel of an endomorphism of.
A semigroup satisfies the maximal condition on congruences if any family of congruences on, ordered by inclusion, has a maximal element. By Zorn's lemma, this is equivalent to saying that the ascending chain condition holds: there is no infinite strictly ascending chain of congruences on.
Every ideal of a semigroup induces a factor semigroup, the Rees factor semigroup, via the congruence defined by if either, or both and are in.