#jsDisabledContent { display:none; } My Account |  Register |  Help

# Semigroup

Article Id: WHEBN0000027799
Reproduction Date:

 Title: Semigroup Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### 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) in that no element had to have an inverse, thus the name semigroup.

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). The operation is required to be associative so that (x·y)·z = (y·z) for all x, y and z, but need not be commutative so that x·y does not have to equal y·x (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).

## Contents

• Definition 1
• Examples of semigroups 2
• Basic concepts 3
• Identity and zero 3.1
• Subsemigroups and ideals 3.2
• Homomorphisms and congruences 3.3
• Structure of semigroups 4
• Special classes of semigroups 5
• Structure theorem for commutative semigroups 6
• Group of fractions 7
• Semigroup methods in partial differential equations 8
• History 9
• Generalizations 10
• Notes 12
• References 13

## Definition

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

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

More succinctly, a semigroup is an associative magma.

## Basic concepts

### Identity and zero

Every semigroup, in fact every magma, has at most one identity element. A semigroup with identity is called a monoid. (A semigroup may have one or more left identities but no right identity,[1] or vice versa, but it is not then a monoid.) A semigroup without identity may be embedded into a monoid simply by adjoining an element e \notin S to S\ and defining e \cdot s = s \cdot e = s for all s \in S \cup \{e\}.[2][3] The notation S1 denotes a monoid obtained from S by adjoining an identity if necessary (S1 = S for a monoid).[3]

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 S, one defines S0, a semigroup with 0 that embeds S.

### Subsemigroups and ideals

The semigroup operation induces an operation on the collection of its subsets: given subsets A and B of a semigroup S, their product A · B, written commonly as AB, is the set { ab | a in A and b in B }. In terms of this operations, a subset A is called

• a subsemigroup if AA is a subset of A,
• a right ideal if AS is a subset of A, and
• a left ideal if SA is a subset of A.

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 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 its every element commutes with any other element of the semigroup is called the center (algebra) of the semigroup.[4] The center of a semigroup is actually a subsemigroup.[5]

### Homomorphisms and congruences

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

f(ab) = f(a)f(b).

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.

A semigroup homomorphism between monoids preserves identity if it is a monoid homomorphism. But there are semigroup homomorphisms which are not monoid homomorphisms, e.g. the canonical embedding of a semigroup S without identity into S^1. Conditions characterizing monoid homomorphisms are discussed further. Let f:S_0\to S_1 be a semigroup homomorphism. The image of f is also a semigroup. If S_0 is a monoid with an identity element e_0, then f(e_0) is the identity element in the image of f. If S_1 is also a monoid with an identity element e_1 and e_1 belongs to the image of f, then f(e_0)=e_1, i.e. f is a monoid homomorphism. Particularly, if f is surjective, then it is a monoid homomorphism.

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 semigroup congruence \sim is an equivalence relation that is compatible with the semigroup operation. That is, a subset \sim\;\subseteq S\times S that is an equivalence relation and x\sim y\, and u\sim v\, implies xu\sim yv\, for every x,y,u,v in S. Like any equivalence relation, a semigroup congruence \sim induces congruence classes

[a]_\sim = \{x\in S\vert\; x\sim a\}

and the semigroup operation induces a binary operation \circ on the congruence classes:

[u]_\sim\circ [v]_\sim = [uv]_\sim

Because \sim is a congruence, the set of all congruence classes of \sim forms a semigroup with \circ, called the quotient semigroup or factor semigroup, and denoted S/\sim. The mapping x \mapsto [x]_\sim is a semigroup homomorphism, called the quotient map, canonical surjection or projection; if S is a monoid then quotient semigroup is a monoid with identity [1]_\sim. 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 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 subsemigroup, the Rees factor semigroup via the congruence x ρ y   ⇔   either x = y or both x and y are in I.

## Structure of semigroups

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 { xn | n is a positive integer }. 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[8] whereas only four of these are monoids and only two form groups. For more on the structure of finite semigroups, see Krohn–Rhodes theory.

## Special classes of semigroups

• A monoid is a semigroup with identity.
• A subsemigroup is a subset of a semigroup that is closed under the semigroup operation.
• A band is a semigroup the operation of which is idempotent.
• A cancellative semigroup is one having the cancellation property:[9] a · b = a · c implies b = c and similarly for b · a = c · a.
• 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: QQ 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.
• C0-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 Zd. These semigroups have applications to commutative algebra.

## Structure theorem for commutative semigroups

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

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

S_a S_b \subseteq S_{a \wedge b}

If f is onto, the semilattice L is isomorphic to the quotient of S by the equivalence relation \sim such that x \sim y iff 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 S, there is a finest congruence \sim such that the quotient of S by this equivalence relation is a semilattice. Denoting this semilattice by L , we get a homomorphism f from S onto L . As mentioned, S becomes graded by this semilattice.

Furthermore, the components S_a are all Archimedean semigroups. An Archimedean semigroup is one where given any pair of elements x, y , there exists an element z and n > 0 such that x^n = y z .

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

## Group of fractions

The group of fractions 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] This has a universal property for morphisms from S to a group.[12] There is an obvious map from S to G(S) by sending each element of S to the corresponding generator.

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, (Suschkewitsch 1928).[14] Anatoly Maltsev gave necessary and conditions for embeddability in 1937.[15]

## Semigroup methods in partial differential equations

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:

\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 = 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

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

where H2 is a Hardy 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:

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

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.

## History

The study of semigroups trailed behind that of other algebraic structures with more complex axioms such as groups or rings. A number of sources[16][17] 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 Suschkewitsch 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.[17] 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.

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.

## Generalizations

 Totality* Associativity Identity Divisibility Group-like structures. The entries say whether the property is required. No Yes No No No No Yes Yes No No No Yes Yes Yes No Yes No No No No Yes No No Yes No Yes No Yes Yes No Yes Yes No No No Yes Yes Yes No No Yes Yes Yes Yes No Yes Yes Yes Yes Yes *Closure, which is used in many sources, is an equivalent axiom to totality, though defined differently.

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 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.[18] 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.

## Notes

1. ^ For instance, the semigroup of three elements e, f, g with, for any x, ex = x, fx = f, and gx = f has exactly one left identity but no right identity.
2. ^ Jacobson (2009), p. 30, ex. 5
3. ^ a b Lawson (1998), p. 20
4. ^ Mati Kilp; M. Kilʹp; U. Knauer; Aleksandr Vasilʹevich Mikhalev (2000). Monoids, Acts, and Categories: With Applications to Wreath Products and Graphs : a Handbook for Students and Researchers. Walter de Gruyter. p. 25.
5. ^ E. S. Li͡apin (1968). Semigroups. American Mathematical Soc. p. 96.
6. ^ Lothaire (2011) p.463
7. ^ Lothaire (2011) p.465
8. ^ Namely: the trivial semigroup in which (for all x and y) xy = a and its counterpart in which xy = b, the semigroups based on multiplication modulo 2 (choosing a or b as the identity element 1), the groups equivalent to addition modulo 2 (choosing a or b to be the identity element 0), and the semigroups in which the elements are either both left identities or both right identities.
9. ^ (Clifford & Preston 1967, p. 3)
10. ^ Grillet, Pierre Antoine (2001), Commutative Semigroups, Springer Verlag
11. ^ B. Farb, Problems on mapping class groups and related topics (Amer. Math. Soc., 2006) page 357. ISBN 0-8218-3838-5
12. ^ M. Auslander and D.A. Buchsbaum, Groups, rings, modules (Harper&Row, 1974) page 50. ISBN 0-06-040387-X
13. ^ (Clifford & Preston 1961, p. 34)
14. ^
15. ^
16. ^ Earliest Known Uses of Some of the Words of Mathematics
17. ^ a b An account of Suschkewitsch's paper by Christopher Hollings
18. ^ Dudek, W.A. (2001), -ary groups"n"On some old problems in , Quasigroups and Related Systems 8: 15–36

## References

General references
• .
• .
• .
• Grillet, Pierre Antoine (1995), Semigroups: an Introduction to the Structure Theory, Marcel Dekker, Inc..
• Grillet, Pierre Antoine (2001), Commutative Semigroups, Springer Verlag.
• Christopher Hollings (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society.
Specific references
• .
• .
• Suschkewitsch, Anton (1928), "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit", .
• Kantorovitz, Shmuel (2010), Topics in Operator Semigroups., Boston, MA: Birkhauser.
• Lawson, M.V. (1998), Inverse semigroups: the theory of partial symmetries, World Scientific,
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.