Semigroup

A semigroup is a set ${\displaystyle S}$ together with a binary operation "${\displaystyle \cdot }$" (that is, a function ${\displaystyle \cdot :S\times S\rightarrow S}$) that satisfies the associative property:

For all ${\displaystyle a,b,c\in S}$, the equation ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$ holds.

More succinctly, a semigroup is an associative magma.

• 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 (specifically, only one up to isomorphism), the singleton {a} with operation a · a = a.
• Semigroup with two elements: there are five which are essentially different.
• The "flip-flop" monoid: a semigroup with three elements representing the three operations on a switch - set, reset, and do nothing.
• The set of positive integers with addition. (With 0 included, this becomes a monoid.)
• The set of integers with minimum or maximum. (With positive/negative infinity included, this becomes a monoid.)
• 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 — the so-called "free semigroup over Σ". With the empty string included, this semigroup becomes the free monoid over Σ.
• A probability distribution F together with all convolution powers of F, 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.

For any subset A of S there is a smallest subsemigroup T of S which contains A, and we say that A generates T. A single element x of S generates the subsemigroup { xⁿ | n ∈ Z⁺ }. If this is finite, then x is said to be of finite order, otherwise it is of infinite order. A semigroup is said to be periodic if all of its elements are of finite order. A semigroup generated by a single element is said to be monogenic (or cyclic). If a monogenic semigroup is infinite then it is isomorphic to the semigroup of positive integers with the operation of addition. If it is finite and nonempty, then it must contain at least one idempotent. It follows that every nonempty periodic semigroup has at least one idempotent.

A subsemigroup which is also a group is called a subgroup. There is a close relationship between the subgroups of a semigroup and its idempotents. Each subgroup contains exactly one idempotent, namely the identity element of the subgroup. For each idempotent e of the semigroup there is a unique maximal subgroup containing e. Each maximal subgroup arises in this way, so there is a one-to-one correspondence between idempotents and maximal subgroups. Here the term maximal subgroup differs from its standard use in group theory.

More can often be said when the order is finite. For example, every nonempty finite semigroup is periodic, and has a minimal ideal and at least one idempotent. The number of finite semigroups of a given size (greater than 1) is (obviously) larger than the number of groups of the same size. For example, of the sixteen possible "multiplication tables" for a set of two elements {a, b}, eight form semigroups[note 2] whereas only four of these are monoids and only two form groups. For more on the structure of finite semigroups, see Krohn–Rhodes theory.

• A monoid is a semigroup with an identity element.
• A group is a monoid in which every element has an inverse element.
• A subsemigroup is a subset of a semigroup that is closed under the semigroup operation.
• A cancellative semigroup is one having the cancellation property:[9] a · b = a · c implies b = c and similarly for b · a = c · a. Every group is a cancellative semigroup, and every finite cancellative semigroup is a group.
• A band is a semigroup whose operation is idempotent.
• A semilattice is a semigroup whose operation is idempotent and commutative.
• 0-simple semigroups.
• Transformation semigroups: any finite semigroup S can be represented by transformations of a (state-) set Q of at most |S| + 1 states. Each element x of S then maps Q into itself x: Q → Q and sequence xy is defined by q(xy) = (qx)y for each q in Q. Sequencing clearly is an associative operation, here equivalent to function composition. This representation is basic for any automaton or finite-state machine (FSM).
• The bicyclic semigroup is in fact a monoid, which can be described as the free semigroup on two generators p and q, under the relation pq = 1.
• C₀-semigroups.
• Regular semigroups. Every element x has at least one inverse y satisfying xyx=x and yxy=y; the elements x and y are sometimes called "mutually inverse".
• Inverse semigroups are regular semigroups where every element has exactly one inverse. Alternatively, a regular semigroup is inverse if and only if any two idempotents commute.
• Affine semigroup: a semigroup that is isomorphic to a finitely-generated subsemigroup of Z^d. These semigroups have applications to commutative algebra.

There is a structure theorem for commutative semigroups in terms of semilattices.[10] A semilattice (or more precisely a meet-semilattice) ${\displaystyle (L,\leq )}$ is a partially ordered set where every pair of elements ${\displaystyle a,b\in L}$ has a greatest lower bound, denoted ${\displaystyle a\wedge b}$. The operation ${\displaystyle \wedge }$ makes ${\displaystyle L}$ into a semigroup satisfying the additional idempotence law ${\displaystyle a\wedge a=a}$.

Given a homomorphism ${\displaystyle f:S\to L}$ from an arbitrary semigroup to a semilattice, each inverse image ${\displaystyle S_{a}=f^{-1}\{a\}}$ is a (possibly empty) semigroup. Moreover, ${\displaystyle S}$ becomes graded by ${\displaystyle L}$, in the sense that

${\displaystyle S_{a}S_{b}\subseteq S_{a\wedge b}.}$

If ${\displaystyle f}$ is onto, the semilattice ${\displaystyle L}$ is isomorphic to the quotient of ${\displaystyle S}$ by the equivalence relation ${\displaystyle \sim }$ such that ${\displaystyle x\sim y}$ if and only if ${\displaystyle f(x)=f(y)}$. This equivalence relation is a semigroup congruence, as defined above.

Whenever we take the quotient of a commutative semigroup by a congruence, we get another commutative semigroup. The structure theorem says that for any commutative semigroup ${\displaystyle S}$, there is a finest congruence ${\displaystyle \sim }$ such that the quotient of ${\displaystyle S}$ by this equivalence relation is a semilattice. Denoting this semilattice by ${\displaystyle L}$, we get a homomorphism ${\displaystyle f}$ from ${\displaystyle S}$ onto ${\displaystyle L}$. As mentioned, ${\displaystyle S}$ becomes graded by this semilattice.

Furthermore, the components ${\displaystyle S_{a}}$ are all Archimedean semigroups. An Archimedean semigroup is one where given any pair of elements ${\displaystyle x,y}$, there exists an element ${\displaystyle z}$ and ${\displaystyle n>0}$ such that ${\displaystyle x^{n}=yz}$.

The Archimedean property follows immediately from the ordering in the semilattice ${\displaystyle L}$, since with this ordering we have ${\displaystyle f(x)\leq f(y)}$ if and only if ${\displaystyle x^{n}=yz}$ for some ${\displaystyle z}$ and ${\displaystyle n>0}$.

The group of fractions or group completion of a semigroup S is the group G = G(S) generated by the elements of S as generators and all equations xy = z which hold true in S as relations.[11] There is an obvious semigroup homomorphism j : S → G(S) which sends each element of S to the corresponding generator. This has a universal property for morphisms from S to a group:[12] given any group H and any semigroup homomorphism k : S → H, there exists a unique group homomorphism f : G → H with k=fj. We may think of G as the "most general" group that contains a homomorphic image of S.

An important question is to characterize those semigroups for which this map is an embedding. This need not always be the case: for example, take S to be the semigroup of subsets of some set X with set-theoretic intersection as the binary operation (this is an example of a semilattice). Since A.A = A holds for all elements of S, this must be true for all generators of G(S) as well: which is therefore the trivial group. It is clearly necessary for embeddability that S have the cancellation property. When S is commutative this condition is also sufficient[13] and the Grothendieck group of the semigroup provides a construction of the group of fractions. The problem for non-commutative semigroups can be traced to the first substantial paper on semigroups.[14][15] Anatoly Maltsev gave necessary and sufficient conditions for embeddability in 1937.[16]

Semigroup theory can be used to study some problems in the field of partial differential equations. Roughly speaking, the semigroup approach is to regard a time-dependent partial differential equation as an ordinary differential equation on a function space. For example, consider the following initial/boundary value problem for the heat equation on the spatial interval (0, 1) ⊂ R and times t ≥ 0:

${\displaystyle {\begin{cases}\partial _{t}u(t,x)=\partial _{x}^{2}u(t,x),&x\in (0,1),t>0;\\u(t,x)=0,&x\in \{0,1\},t>0;\\u(t,x)=u_{0}(x),&x\in (0,1),t=0.\end{cases}}}$

Let X = L²((0, 1) R) be the L^p space of square-integrable real-valued functions with domain the interval (0, 1) and let A be the second-derivative operator with domain

${\displaystyle D(A)={\big \{}u\in H^{2}((0,1);\mathbf {R} ){\big |}u(0)=u(1)=0{\big \}},}$

where H² is a Sobolev space. Then the above initial/boundary value problem can be interpreted as an initial value problem for an ordinary differential equation on the space X:

${\displaystyle {\begin{cases}{\dot {u}}(t)=Au(t);\\u(0)=u_{0}.\end{cases}}}$

On an heuristic level, the solution to this problem "ought" to be u(t) = exp(tA)u₀. However, for a rigorous treatment, a meaning must be given to the exponential of tA. As a function of t, exp(tA) is a semigroup of operators from X to itself, taking the initial state u₀ at time t = 0 to the state u(t) = exp(tA)u₀ at time t. The operator A is said to be the infinitesimal generator of the semigroup.

The study of semigroups trailed behind that of other algebraic structures with more complex axioms such as groups or rings. A number of sources[17][18] attribute the first use of the term (in French) to J.-A. de Séguier in Élements de la Théorie des Groupes Abstraits (Elements of the Theory of Abstract Groups) in 1904. The term is used in English in 1908 in Harold Hinton's Theory of Groups of Finite Order.

Anton Sushkevich obtained the first non-trivial results about semigroups. His 1928 paper "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit" ("On finite groups without the rule of unique invertibility") determined the structure of finite simple semigroups and showed that the minimal ideal (or Green's relations J-class) of a finite semigroup is simple.[18] From that point on, the foundations of semigroup theory were further laid by David Rees, James Alexander Green, Evgenii Sergeevich Lyapin, Alfred H. Clifford and Gordon Preston. The latter two published a two-volume monograph on semigroup theory in 1961 and 1967 respectively. In 1970, a new periodical called Semigroup Forum (currently edited by Springer Verlag) became one of the few mathematical journals devoted entirely to semigroup theory.

The representation theory of semigroups was developed in 1963 by Boris Schein using binary relations on a set A and composition of relations for the semigroup product.[19] At an algebraic conference in 1972 Schein surveyed the literature on B_A, the semigroup of relations on A.[20] In 1997 Schein and Ralph McKenzie proved that every semigroup is isomorphic to a transitive semigroup of binary relations.[21]

In recent years researchers in the field have become more specialized with dedicated monographs appearing on important classes of semigroups, like inverse semigroups, as well as monographs focusing on applications in algebraic automata theory, particularly for finite automata, and also in functional analysis.

If the associativity axiom of a semigroup is dropped, the result is a magma, which is nothing more than a set M equipped with a binary operation that is closed M × M → M.

Generalizing in a different direction, an n-ary semigroup (also n-semigroup, polyadic semigroup or multiary semigroup) is a generalization of a semigroup to a set G with a n-ary operation instead of a binary operation.[22] The associative law is generalized as follows: ternary associativity is (abc)de = a(bcd)e = ab(cde), i.e. the string abcde with any three adjacent elements bracketed. N-ary associativity is a string of length n + (n − 1) with any n adjacent elements bracketed. A 2-ary semigroup is just a semigroup. Further axioms lead to an n-ary group.

A third generalization is the semigroupoid, in which the requirement that the binary relation be total is lifted. As categories generalize monoids in the same way, a semigroupoid behaves much like a category but lacks identities.

Infinitary generalizations of commutative semigroups have sometimes been considered by various authors.[note 3]

• Absorbing element
• Biordered set
• Empty semigroup
• Generalized inverse
• Identity element
• Light's associativity test
• Quantum dynamical semigroup
• Semigroup ring
• Weak inverse