Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

The binary operation of a semigroup is most often denoted multiplicatively: x·y, or simply xy, denotes the result of applying the semigroup operation to the ordered pair (x, y). Associativity is formally expressed as that (x·yz = x·(y·z) for all x, y and z 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.[note 1] As in the case of groups or magmas, the semigroup operation need not be commutative, so x·y is not necessarily equal to y·x; 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 (less often than in the analogous case of groups) it may be called an abelian semigroup.

A monoid is an algebraic structure intermediate between groups and semigroups, 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 a generalization of groups in a different direction; the operation in a quasigroup need not be associative but quasigroups preserve from groups a notion of division. Division in semigroups (or in monoids) 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 transformation semigroup, in which arbitrary functions replace the role of bijections from 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.[1] 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.

A two-sided identity (or just 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 (which is therefore the unique one-sided identity).

If A is both a left ideal and a right ideal then it is called an ideal (or a two-sided ideal).

If S is a semigroup, then the intersection of any collection of subsemigroups of S is also a subsemigroup of S. So the subsemigroups of S 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.[4] The center of a semigroup is actually a subsemigroup.[5]

A semigroup homomorphism is a function that preserves semigroup structure. A function f: ST between two semigroups is a homomorphism if the equation

holds for all elements a, b in S, i.e. the result is the same when performing the semigroup operation after or before applying the map f.

Two semigroups S and T are said to be isomorphic if there is a bijection f : ST with the property that, for any elements a, b in S, f(ab) = f(a)f(b). Isomorphic semigroups have the same structure.

A nuclear congruence on S is one which is the kernel of an endomorphism of S.[6]

A semigroup S satisfies the maximal condition on congruences if any family of congruences on S, 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 S.[7]

Every ideal I of a semigroup induces a factor semigroup, the Rees factor semigroup, via the congruence ρ defined by x ρ y if either x = y, or both x and y are in I.

The following notions[8] introduce the idea that a semigroup is contained in another one.

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.

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 : SG(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 : SH, there exists a unique group homomorphism f : GH 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:

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

where H2 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:

On an heuristic level, the solution to this problem "ought" to be u(t) = exp(tA)u0. 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 u0 at time t = 0 to the state u(t) = exp(tA)u0 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 BA, 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 × MM.

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 + (n1) 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]