Semigroup

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

Uses your system voice; voice and rate in settings.

≈ 9 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. In mathematical analysis, the term also appears in the theory of one-parameter operator semigroups: see C0-semigroup.

The binary operation of a semigroup is most often denoted multiplicatively: x\cdot 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\cdot y)\cdot z=x\cdot (y\cdot z) for all x , y and z in the semigroup. An example of a semigroup is that formed by string concatenation, which glues together strings.

For example, the concatenation of the strings "spot " and "run" is the string "spot " • "run" = "spot run". Associativity means that "See " • ("spot " • "run") = "See " • "spot run" = "See spot run" = "See spot " • "run" = ("See " • "spot ") • "run". 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. 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. Semigroup with one element: there is essentially only one (specifically, only one up to isomorphism), the singleton \{a\} with operation a \cdot a = a . 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.

(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 (this is a monoid). Any ideal of a ring with the multiplication of the ring. The set of all finite strings over a fixed alphabet \Sigma with concatenation of strings as the semigroup operation—called the free semigroup over \Sigma .

With the empty string included, this semigroup becomes the free monoid over \Sigma . 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. A left identity of a semigroup S (or more generally, magma) is an element e such that for all x in S , e\cdot x = x . Similarly, a right identity is an element f such that for all x in S , x\cdot f = x . 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 (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).

A semigroup S without identity may be embedded in a monoid formed 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\} . The notation S^1 denotes a monoid obtained from S by adjoining an identity if necessary ( S^1 = S for a monoid). 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 can define S^0 , a semigroup with 0 that embeds S . 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 that 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 exists a bijective semigroup homomorphism f:S\to T . 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] = \{x\in S\mid x\sim a\} and the semigroup operation induces a binary operation \circ on the congruence classes: [u]\circ [v] = [uv]. 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] 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] . 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 that is the kernel of an endomorphism of S . 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 . Every ideal I of a semigroup induces a factor semigroup, the Rees factor semigroup, via the congruence \rho defined by x\rho y if either x=y , or both x and y are in I . \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 be the L p space of square-integrable real-valued functions with domain the interval 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 H^2 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: \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)u_0.

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 0 at time to the state at time t. The operator A is said to be the infinitesimal generator of the semigroup.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378036854 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001378036854 · captured 2026-10-02 · ledger · version history

Cite this page as: encyclopegia.org, “Semigroup”, snapshot enwiki-001378036854. https://encyclopegia.org/a/semigroup

Sources cited in this revision

8 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.