Fact-checked by Grok 2 weeks ago

Semigroup

A semigroup is a mathematical structure consisting of a set S equipped with a binary operation \cdot: S \times S \to S that is associative, meaning that for all a, b, c \in S, (a \cdot b) \cdot c = a \cdot (b \cdot c). Unlike groups, semigroups do not require the existence of an identity element or inverses for their elements. While some definitions stipulate that the set must be nonempty, others allow for the empty semigroup as a valid structure. A semigroup that possesses an identity element e \in S such that e \cdot a = a \cdot e = a for all a \in S is known as a monoid. Furthermore, a monoid in which every element has a two-sided inverse is a group, extending the structure to include reversibility under the operation. Semigroups can be commutative (or abelian) if the operation satisfies a \cdot b = b \cdot a for all a, b \in S, and they may be finite or infinite depending on the cardinality of S. Semigroup theory encompasses various subclasses and generalizations, such as regular semigroups, where for every x \in S, there exists y \in S such that x \cdot y \cdot x = x, enabling the study of idempotents and Green's relations for structural analysis. Finite semigroups are particularly well-understood through their representation as transformation semigroups on finite sets, contrasting with groups via Cayley's theorem but without guaranteed invertibility. Numerical semigroups, a special case involving additive operations on nonnegative integers with a finite complement in the naturals, arise in combinatorial contexts like Frobenius coin problems. Beyond abstract algebra, semigroups find applications in diverse fields, including operator theory where C₀-semigroups (or strongly continuous semigroups) model the evolution of linear dynamical systems via abstract differential equations, such as in partial differential equations on Banach spaces. In computer science and combinatorics, semigroup representations underpin automata theory, Markov chains, and permutation group algorithms, while semigroup methods extend to nonlinear evolution equations and ergodic theory.

Fundamentals

Definition

A semigroup is a set S equipped with a binary operation \cdot: S \times S \to S that is associative, meaning that for all a, b, c \in S, (a \cdot b) \cdot c = a \cdot (b \cdot c). This structure requires closure under the operation and associativity but imposes no further axioms, such as the existence of an identity element or inverses for elements. In notation, semigroups are conventionally presented using multiplicative notation, where the operation is denoted by \cdot or simply by juxtaposition (e.g., ab for a \cdot b); additive notation, using +, is employed when the operation resembles addition, such as in the natural numbers under summation. Unlike magmas, which are sets with a binary operation lacking the associativity requirement, semigroups enforce this key property to ensure well-defined iterated operations. They also differ from monoids, which include an identity element, and from groups, which additionally require inverses, highlighting the semigroup's minimal axiomatic framework in abstract algebra. Semigroups may be finite or infinite in cardinality; for instance, the number of nonisomorphic finite semigroups of order n grows rapidly, with 1 for n=1, 5 for n=2, and 24 for n=3. In more general settings, such as functional analysis, continuous (or one-parameter) semigroups arise as strongly continuous families \{T(t)\}_{t \geq 0} of bounded linear operators on a Banach space X, satisfying T(0) = I, T(s+t) = T(s)T(t) for s, t \geq 0, and strong continuity at t=0, though the identity is not inherent to the discrete semigroup definition. These variations underscore the semigroup's versatility across discrete and continuous contexts.

Examples

The set of natural numbers \mathbb{N} (excluding 0) under addition forms an infinite commutative semigroup (\mathbb{N}, +). The operation is closed, as the sum of any two natural numbers is again a natural number, and it is associative, satisfying (a + b) + c = a + (b + c) for all a, b, c \in \mathbb{N}. Similarly, the set (\mathbb{N}, \times) of natural numbers under multiplication is another infinite commutative semigroup, closed under the operation with associativity holding by the properties of multiplication. The set of all n \times n matrices over a field F, equipped with matrix multiplication, constitutes a semigroup (M_n(F), \cdot). Closure follows from the fact that the product of two n \times n matrices is again an n \times n matrix, and associativity is a standard property of matrix multiplication: (AB)C = A(BC) for all A, B, C \in M_n(F). This example is non-commutative for n \geq 2. The free semigroup on a nonempty set A (an alphabet) consists of all finite nonempty words over A, with concatenation as the operation. For words w, v formed from letters in A, the product wv is the concatenated word, which is closed in the set of words and associative because (wv)u = w(vu) for any words w, v, u. If |A| > 1, this semigroup is non-commutative. The full transformation semigroup on a nonempty set X comprises all functions from X to itself, under composition. For functions f, g: X \to X, the product f \circ g is defined by (f \circ g)(x) = f(g(x)) for all x \in X, ensuring closure, and associativity holds as function composition is inherently associative: (f \circ g) \circ h = f \circ (g \circ h). This is non-commutative in general. In graph theory, the path semigroup of a directed graph G = (V, E) is the set of all finite paths in G, with concatenation as the operation where compatible paths are joined end-to-end. This operation is closed on the set of paths and associative, as the concatenation of paths follows the natural chaining property in graphs. The set of positive integers under the maximum operation forms a commutative semigroup (\mathbb{N}^+, \max), where \max(m, n) is the larger of m and n. Closure is immediate, and associativity holds because \max(\max(m, n), p) = \max(m, \max(n, p)) for all positive integers m, n, p. Each element is idempotent, satisfying \max(k, k) = k.

Core Concepts

Identity and Zero Elements

In a semigroup (S, \cdot), an element e \in S is called a left identity if e \cdot a = a for all a \in S, a right identity if a \cdot e = a for all a \in S, and a two-sided identity (or simply identity) if it satisfies both conditions simultaneously. Not every semigroup possesses such elements; for instance, the semigroup of natural numbers under maximum operation, (\mathbb{N}, \max), admits neither a left nor a right identity, as no element e can satisfy \max(e, n) = n for all n \in \mathbb{N} without being smaller than every natural number, which is impossible. If a semigroup has both a left identity and a right identity, then they coincide and form a unique two-sided identity. To see this, suppose e is a left identity and f is a right identity. Then e = e \cdot f = f, using the left property on f and the right property on e. Similarly, if e and f are both two-sided identities, then e = e \cdot f = f. This uniqueness holds without requiring inverses or further structure beyond associativity. An element z \in S is a left zero if z \cdot a = z for all a \in S, a right zero if a \cdot z = z for all a \in S, and a two-sided zero (or simply zero) if it satisfies both. Also known as an absorbing element, a zero "annihilates" all products involving it. For example, consider the two-element semigroup \{0, 1\} with operation defined by $0 \cdot 0 = 0, $0 \cdot 1 = 0, $1 \cdot 0 = 0, and $1 \cdot 1 = 0; this is associative, $0 serves as a two-sided zero, but no identity exists, as neither element neutralizes $1 on both sides. If a semigroup has both a left zero and a right zero, they coincide and form a unique two-sided zero. Suppose z_L is a left zero and z_R is a right zero; then z_L = z_L \cdot z_R = z_R. Likewise, for two two-sided zeros z and z', z = z \cdot z' = z'. A semigroup may possess multiple left zeros or multiple right zeros separately—for instance, in a left zero semigroup where a \cdot b = a for all a, b, every element is a left zero—but the two-sided case is unique when it exists. The presence of a two-sided identity distinguishes monoids from general semigroups: a semigroup equipped with such an element is precisely a monoid.

Subsemigroups and Ideals

A subsemigroup of a semigroup S is a nonempty subset T \subseteq S such that for all a, b \in T, the product ab \in T. Since the binary operation on S is associative, the restricted operation on T inherits this property, making T a semigroup in its own right. If S is a monoid with identity element e, then a subsemigroup T is a submonoid if it also contains e. The subsemigroup generated by a nonempty subset X \subseteq S, denoted \langle X \rangle, is the smallest subsemigroup of S containing X. It consists of all finite products of elements from X (including the empty product if S has an identity). For a singleton X = \{a\}, the monogenic subsemigroup \langle a \rangle = \{a^n \mid n \geq 1, \, a^n \in S\} is either infinite (isomorphic to the additive semigroup of positive integers) or finite, in which case it contains a unique idempotent element. A left ideal of a semigroup S is a nonempty subset I \subseteq S such that S I \subseteq I; a right ideal satisfies I S \subseteq I; and a two-sided ideal satisfies both conditions simultaneously. Every ideal (left, right, or two-sided) is necessarily a subsemigroup, as products within I remain in I by the ideal property applied to elements of S. In commutative semigroups, the notions of left, right, and two-sided ideals coincide. If S has a zero element $0, then \{0\} forms a two-sided ideal. The principal left ideal generated by an element a \in S is the set S^1 a = S a \cup \{a\} (where S^1 = S if S has an identity, or S^1 = S \cup \{1\} otherwise), which is the smallest left ideal containing a. Similarly, the principal right ideal is a S^1, and the principal two-sided ideal is S^1 a S^1. These are the intersections of all left (resp. right, two-sided) ideals containing a. For example, in the additive semigroup (\mathbb{N}_0, +) of non-negative integers, the set of even non-negative integers $2\mathbb{N}_0 is a subsemigroup but not an ideal, while the principal two-sided ideal generated by 2 is \{ k \in \mathbb{N}_0 \mid k \geq 2 \}, which is a two-sided ideal since the semigroup is commutative. In the bicyclic semigroup B = \mathbb{N}_0 \times \mathbb{N}_0 with operation (m,n)(p,q) = (m + p - \min(n,p), q + \max(n,p) - \min(n,p)), the set I_m = \{ (x,y) \mid x \geq m, \, y \in \mathbb{N}_0 \} forms a principal right ideal generated by any element (m,n) \in B. Such examples illustrate how ideals capture "absorbing" tail structures in semigroups with more complex operations.

Homomorphisms and Isomorphisms

A semigroup homomorphism is a function \phi: S \to T between semigroups (S, \cdot_S) and (T, \cdot_T) such that \phi(a \cdot_S b) = \phi(a) \cdot_T \phi(b) for all a, b \in S. This preserves the associative binary operation, ensuring that the structure of products in S is mirrored in T. The image of \phi, denoted \operatorname{Im}(\phi) = \{\phi(a) \mid a \in S\}, forms a subsemigroup of T. The kernel of \phi, defined as the relation \operatorname{Ker}(\phi) = \{(a, b) \in S \times S \mid \phi(a) = \phi(b)\}, is a congruence on S. An isomorphism is a bijective semigroup homomorphism whose inverse is also a homomorphism. Two semigroups are isomorphic if such a map exists, meaning they have identical algebraic structure up to relabeling of elements. Endomorphisms are semigroup homomorphisms from a semigroup to itself, while automorphisms are isomorphisms from a semigroup to itself, forming the automorphism group of the semigroup. Examples include the inclusion map of a subsemigroup A into its ambient semigroup S, where \iota(a) = a for a \in A, which is a homomorphism preserving the operation. Another is the map \phi: (\mathbb{N}_0, +) \to (S, \cdot) sending n \mapsto a^n for a fixed a \in S, which is a homomorphism generating a monogenic subsemigroup. For isomorphisms, the exponential map n \mapsto 2^n from (\mathbb{N}_0, +) to (\{2^n \mid n \in \mathbb{N}_0\}, \cdot) is bijective with inverse \log_2.

Relations and Equivalences

Congruences

A congruence on a semigroup S is an equivalence relation \sim on S such that for all a, b, c, d \in S, if a \sim b and c \sim d, then ac \sim bd. This compatibility condition ensures that the relation respects the semigroup operation, allowing the equivalence classes to form a partition of S that is preserved under multiplication. The equivalence classes of a congruence \sim, denoted = \{b \in S \mid b \sim a\} for a \in S, partition S into subsets where the operation induces a well-defined semigroup structure on the quotient set S / \sim. Specifically, the product of classes = [ac] is independent of the representatives chosen, due to the congruence property. A principal congruence on S is the smallest congruence containing a specified pair (e, f) \in S \times S, generated by identifying e and f and closing under the semigroup operation and equivalence transitivity. For instance, Green's relations, such as the left relation \mathcal{L} where a \mathcal{L} b if there exist x, y \in S with a = x b and b = y a (the principal left ideal generated by a equals that by b), can be used to define associated principal congruences by symmetrization and closure. The set of all congruences on S, denoted \mathrm{Con}(S), forms a lattice under the partial order of refinement: \rho \leq \sigma if \rho \subseteq \sigma as relations on S \times S. The meet \rho \cap \sigma is the largest common refinement, while the join \rho \vee \sigma is the smallest congruence containing both, obtained by generating from their union. This lattice structure captures the relational hierarchy of compatible equivalences on S. Examples include the trivial congruence, the equality relation \Delta = \{(a, a) \mid a \in S\}, which yields the discrete quotient isomorphic to S, and the universal congruence \nabla = S \times S, producing the trivial one-element semigroup. In the semigroup of natural numbers under addition, the congruence modulo n identifies numbers differing by multiples of n, partitioning into n classes preserved under addition.

Quotient Semigroups

In a semigroup S, given a congruence \sim (an equivalence relation compatible with the semigroup operation, as defined in the section on congruences), the quotient semigroup S / \sim is constructed as the set of equivalence classes = \{ b \in S \mid b \sim a \} equipped with the operation \cdot = [a \cdot b]. This operation is well-defined: if = [a'] and = [b'], then a \cdot b \sim a' \cdot b' because \sim preserves multiplication in both arguments. Associativity follows directly from that in S, since ( \cdot ) \cdot = [ (a \cdot b) \cdot c ] = [ a \cdot (b \cdot c) ] = \cdot ( \cdot ). The canonical projection \pi: S \to S / \sim defined by \pi(a) = is a surjective homomorphism of semigroups, and its kernel \{ (a, b) \in S \times S \mid a \sim b \} is precisely the congruence \sim. This yields the first homomorphism theorem for semigroups: if \phi: S \to T is a homomorphism, then S / \ker \phi \cong \operatorname{im} \phi. Congruences on S thus provide a means to factor S into simpler structures, analogous to normal subgroups in groups. Certain congruences arise from ideals of S: specifically, for a (two-sided) ideal I, the Rees congruence \rho_I identifies all elements of I into a single class (acting as a zero element) while leaving elements outside I in singleton classes, i.e., a \rho_I b if either a = b \notin I or both a, b \in I. The resulting Rees quotient S / \rho_I collapses I to zero, preserving the structure outside while adjoining an absorbing element; it is a semigroup with zero, and if I is proper, the zero is nontrivial. More generally, ideals in S correspond bijectively to kernels of homomorphisms from S onto semigroups with zero, via such Rees constructions. Minimal congruences on S are those generated by a single pair (a, b), forming the smallest equivalence containing (a, b) and closed under the semigroup operation; their quotients reveal the "relations" needed to equate a and b. For example, in the free semigroup A^+ over an alphabet A, imposing relations via a congruence yields presentation quotients, such as transformation semigroups. A key application is the syntactic congruence \sim_L on A^+ for a language L \subseteq A^*, where u \sim_L v if and only if, for all words x, y \in A^*, x u y \in L exactly when x v y \in L; the quotient A^+ / \sim_L is the syntactic semigroup of L, which is finite if and only if L is regular.

Division of Semigroups

In semigroup theory, a semigroup S divides a semigroup T, denoted S \precsim T, if there exists a subsemigroup U of T and a surjective homomorphism \phi: U \to S. This notion captures a form of embedding where S arises as a "factor" within T, generalizing direct subsemigroup inclusions (when \phi is the identity) and quotients (when U = T). The division relation is reflexive and transitive, forming a quasi-order on the class of all semigroups. An equivalent formulation involves relational morphisms: S \precsim T if and only if there exists an injective relational morphism \tau: S \to T. Here, a relational morphism \tau \subseteq S \times T satisfies: (i) for all s \in S, s\tau \neq \emptyset; and (ii) for all s, t \in S, (s\tau)(t\tau) \subseteq (st)\tau, where the relational product is defined by (s\tau)(t\tau) = \{xy \mid x \in s\tau, y \in t\tau\}. The morphism is injective if, whenever s\tau \cap s'\tau \neq \emptyset, then s = s', ensuring distinct elements of S map to disjoint non-empty subsets of T. Variants include strong divisions, where the relational morphism additionally preserves the structure of idempotents, particularly relevant for regular semigroups. Green's relations provide an internal perspective on divisibility within a single semigroup. The D-relation, defined as the join of the left (L) and right (R) relations, equates elements a, b \in S if they generate the same two-sided principal ideal, i.e., S a S = S b S. This captures mutual two-sided divisibility: a divides b (and vice versa) in the sense that b \in S a S and a \in S b S. In finite semigroups, the D-classes form the blocks of the minimal ideal structure, aiding analysis of divisibility hierarchies. Representative examples illustrate division. By the semigroup analogue of Cayley's theorem, every semigroup S embeds as a subsemigroup of the full transformation semigroup T_X on a set X with |X| = |S|, via the action on left cosets or regular representation; thus, S \precsim T_X. For instance, the symmetric group S_n (permutations on n points) divides the full transformation semigroup T_n, as S_n is itself a subsemigroup of T_n. Cyclic groups also divide free groups: the infinite cyclic group embeds as a subsemigroup (generated by a single generator) of the free group on one generator, which is itself infinite cyclic. Division is fundamental in the study of semigroup varieties. Pseudovarieties of finite semigroups—classes closed under finite direct products, homomorphic images, and division—characterize regular languages via Eilenberg's correspondence theorem, linking syntactic semigroups to language recognition. This closure under division ensures that varieties capture "irreducible" algebraic structures, enabling embedding theorems and profinite completions in automata theory.

Structural Results

General Structure Theorems

Green's relations form a cornerstone of semigroup theory, providing equivalence relations that classify elements based on the principal ideals they generate and reveal the internal structure of arbitrary semigroups. The right Green's relation \mathcal{R} is defined by a \mathcal{R} b if and only if the principal right ideals generated by a and b coincide, that is, Sa = Sb, where Sa = \{sa \mid s \in S\}. Similarly, the left Green's relation \mathcal{L} is given by a \mathcal{L} b if and only if aS = bS. The intersection \mathcal{H} = \mathcal{R} \cap \mathcal{L} captures elements that generate the same principal left and right ideals, while the two-sided relation \mathcal{J} arises from equality of principal two-sided ideals, SaS = SbS. The relation \mathcal{D}, the smallest equivalence containing both \mathcal{R} and \mathcal{L}, coincides with \mathcal{J} in finite semigroups but may differ in infinite ones. These relations partition the semigroup into classes: \mathcal{R}-classes correspond to distinct right ideals, \mathcal{L}-classes to left ideals, \mathcal{H}-classes to their intersections, \mathcal{D}-classes to unions of \mathcal{R}-classes within the same two-sided ideal, and \mathcal{J}-classes to minimal two-sided ideals containing them. Principal ideals are the sets generated by single elements, and the classes determine the "skeleton" of the semigroup's ideal structure, with \mathcal{J}-classes forming the top-level decomposition into orthodox components. Rees's theorem offers a concrete structural description for simple semigroups, stating that a semigroup is completely simple if and only if it is isomorphic to a Rees matrix semigroup over a group. A Rees matrix semigroup M(G; I, \Lambda; P) consists of triples (i, g, \lambda) with i \in I, \lambda \in \Lambda, g \in G, and multiplication defined by (i, g, \lambda)(i', g', \lambda') = (i, g P_{\lambda, i'} g', \lambda'), where P = (P_{\lambda, i}) is a \Lambda \times I-matrix with entries in G. For semigroups with zero, a variant applies to completely 0-simple semigroups, incorporating a zero adjoined to the matrix construction. In the regular case, minimal ideals (Rees quotients) are isomorphic to such matrix semigroups, allowing arbitrary regular semigroups to be decomposed as spined unions of ideals, where the spined product glues components over a spine (a chain or tree-like structure) of the semilattice of idempotents, with each regular ideal structured as a Rees matrix semigroup. This decomposition highlights how general semigroups assemble from simpler building blocks via ideal unions, referencing the theory of subsemigroups and ideals for the ideal framework. Idempotents play a key role in structuring semigroups, particularly through their existence and organization. Every finite non-empty semigroup contains at least one idempotent element e, satisfying e^2 = e, as the cyclic subsemigroup generated by any element is finite and thus must contain a repeated power forming an idempotent by the pigeonhole principle on the sequence of powers. In a regular semigroup, the set E(S) of all idempotents forms a subsemigroup that is a band (idempotent semigroup), and under the natural partial order e \leq f if e = e f = f e, it constitutes a commutative semilattice where the meet e \wedge f = e f satisfies associativity, commutativity, and idempotence. This semilattice E(S) governs the global ordering of idempotents and influences the connectivity between Green's classes. Semigroups admit a characterization as partially ordered sets equipped with a compatible binary operation, where the natural partial order \leq on S is defined by a \leq b if there exists s \in S such that a = s b (right preorder) or symmetrically for left, refined in regular cases to a \leq b if a = a b a and a b = b a ensuring antisymmetry. This order is compatible with multiplication in the sense that if a \leq b, then for any c \in S, a c \leq b c and c a \leq c b, transforming the semigroup into an ordered structure where the operation preserves the order. In finite semigroups, this order interacts with the existence of idempotents to preview deeper structural properties, such as the semilattice of E(S) embedding into the overall poset.

Structure of Finite Semigroups

In finite semigroups, the finiteness condition imposes a combinatorial structure that manifests through periodic behaviors and decompositions into simpler components. Unlike infinite semigroups, every finite semigroup exhibits eventual idempotency and can be analyzed via explicit enumeration and relational partitions, enabling algorithmic classification up to isomorphism. These properties arise from the bounded nature of the set, leading to cycles in the powers of elements and hierarchical decompositions that reflect the semigroup's action on finite sets. A fundamental feature is that every element a in a finite semigroup S satisfies a^k = a^{k+m} for sufficiently large k and some m \geq 1, implying that some power of a is idempotent, i.e., a^{k'} = (a^{k'})^2 for some k' \geq 1. This result, established by Moore in 1902, ensures that the subsemigroup generated by a stabilizes to an idempotent after finitely many multiplications, bounding the growth of powers and facilitating structural analysis. For any element a in a finite semigroup, the cyclic subsemigroup \langle a \rangle = \{a, a^2, a^3, \dots \} has a well-defined index m and period r, where m \geq 1 and r \geq 1 are the smallest integers such that a^{m+r} = a^m. This structure partitions \langle a \rangle into a transient chain of length m-1 (elements before the cycle) followed by a cyclic group of order r generated by a^m, which is idempotent if r=1. Such monogenic semigroups capture the local periodicity of finite semigroups, with the index measuring the "approach to stability" and the period the "oscillation length" thereafter. For example, in the transformation semigroup on a 3-element set, elements may have index 2 and period 2, forming a chain a \to a^2 cycling as a^2 \to a^3 = a^2. The Krohn-Rhodes theorem provides a global decomposition, stating that every finite semigroup S divides a wreath product of groups and "flip-flop" semigroups (the 2-element transformation semigroup where one element acts as identity and the other as a constant map). Introduced by Krohn and Rhodes in 1961, this hierarchical cascade represents S as a coordinated product of simple building blocks, with the complexity of S defined as the minimal number of group levels in such a decomposition, bounding the "depth" of relational structures in S. For instance, the full transformation semigroup on n points decomposes into n-1 flip-flops wreathing the symmetric group S_n, illustrating how finite actions on sets reduce to permutations and resets. This theorem underpins computational semigroup theory, enabling the classification of automata via semigroup divisors. Finite semigroups are concretely represented by their Cayley tables, which are n \times n arrays for |S| = n encoding the operation via row-column entries, allowing direct computation of structural invariants. Regularity of an element s \in S is detectable if s appears in its own row (or column) in the table, indicating the existence of an inverse t such that s = s t s. Green's relations, which partition S into equivalence classes based on principal ideals (e.g., L-classes for left ideals, R-classes for right ideals), emerge from analyzing reachability in the Cayley graph derived from the table, revealing the semigroup's ideal structure without exhaustive enumeration. These relations, briefly connecting to broader theorems, highlight how finite tables encode the H, D, and J-classes that organize idempotents and regular elements. The enumeration of finite semigroups up to isomorphism and anti-isomorphism quantifies their diversity, with the number for order n growing rapidly: 1 for n=1, 1 for n=2, 2 for n=3, 5 for n=4, and 15 for n=5. These counts, computed via exhaustive Cayley table generation and isomorphism testing, stem from algorithmic classifications; for example, the 15 semigroups of order 5 include 7 monoids and various nilpotent types, underscoring the combinatorial explosion beyond small n. Up to anti-isomorphism (reversing the operation), the sequence aligns closely, aiding theoretical bounds on growth rates.

Commutative Case: Structure Theorem

In the commutative case, the structure theorem provides a canonical decomposition of any commutative semigroup into a semilattice of its Archimedean components. Specifically, every commutative semigroup S is isomorphic to the semilattice product of a commutative idempotent semigroup (a semilattice) Y = S / \rho and the family of Archimedean semigroups \{A_e \mid e \in Y\}, where \rho is the canonical congruence relation defined below, and each A_e is the \rho-class corresponding to e. This decomposition, originally established by Tamura and Kimura, simplifies the general structural results for non-commutative semigroups by leveraging commutativity to yield Archimedean components that are intrinsically tied to the semilattice structure. A commutative semigroup S is Archimedean if, for every pair of elements a, b \in S, there exists a positive integer n such that aS \cap bS^n \neq \emptyset. Equivalently, in additive notation, for the semigroup (S, +), this means a + S \cap b + nS \neq \emptyset. The congruence \rho on S is defined by a \rho b if and only if there exist positive integers m, n such that aS^m \cap bS^n \neq \emptyset; the \rho-classes form the Archimedean components of S, each of which is itself an Archimedean semigroup, and the quotient S / \rho is a semilattice under the induced operation. Within these components, elements satisfy properties such as a b a^k = a^{k+1} b for sufficiently large k, reflecting the "absorption" characteristic of Archimedean structure in the commutative setting. This theorem, often referred to as Clifford's theorem in the commutative context, underscores the role of semilattices in organizing the decomposition. The Archimedean components in this decomposition fall into specific classes: null semigroups or Clifford semigroups consisting of groups. A null semigroup is a commutative semigroup with a zero element $0 such that the product of any two elements is $0, making it a trivial Archimedean example where all non-zero elements annihilate each other. In contrast, if an Archimedean component contains an idempotent, it forms a Clifford semigroup, which in the commutative case decomposes as a semilattice of abelian groups; here, the groups capture the cancellative kernel, and the semilattice structure arises from the commuting idempotents. These classes exhaust the possibilities for commutative Archimedean semigroups, providing a refined structural insight beyond the general decomposition. Representative examples illustrate this theorem. The additive semigroup (\mathbb{N}_0, +), where \mathbb{N}_0 = \{0, 1, 2, \dots \}, is Archimedean because for any a, b \in \mathbb{N}_0, the sets a + \mathbb{N}_0 = \mathbb{N}_0 and b + n \mathbb{N}_0 = \mathbb{N}_0 (for any n \geq 1) intersect non-trivially. Thus, it appears as a single Archimedean component in its own decomposition, embeddable into the abelian group \mathbb{Z}. On the other hand, the direct product of two chains under componentwise meet operation, such as [0,1] \times [0,1] with (x_1, y_1) \wedge (x_2, y_2) = (\min(x_1, x_2), \min(y_1, y_2)), decomposes as a semilattice whose Archimedean components correspond to the "levels" or fibers determined by the \rho-relation, each being a rectangular band (idempotent Archimedean) or trivial group in the Clifford sense.

Constructions and Embeddings

Groups of Fractions

A semigroup S is left cancellative if, for all a, b, c \in S, the equation ab = ac implies b = c. Similarly, S is right cancellative if ba = ca implies b = c. A semigroup that is both left and right cancellative is simply called cancellative. In the commutative case, where the operation is commutative, cancellativity ensures that the semigroup embeds into an abelian group via a universal construction. For a cancellative semigroup S (assumed to be a monoid with identity $1), the group of fractions G(S) is constructed as the set of equivalence classes of pairs S \times S under the relation (a, b) \sim (c, d) if and only if ad = bc. The group operation is defined by (a, b) \cdot (c, d) = (ac, bd), which is well-defined under appropriate conditions. The embedding \iota: S \to G(S) maps each a \in S to the class of (a, 1), preserving the semigroup operation. In this group, elements of S gain inverses: the inverse of \iota(a) is the class of (1, a), since (a, 1) \cdot (1, a) = (a, a) \sim (1, 1) by cancellativity. However, for the construction to yield a group in which S embeds injectively, S must satisfy the Ore condition. A semigroup satisfies the left Ore condition if, for all a, b \in S, the intersection aS \cap bS \neq \emptyset, meaning there exist x, y \in S such that ax = by. Ore's theorem states that a left cancellative semigroup satisfying the left Ore condition embeds into a group of left fractions S^{-1}S, and dually for the right case. This theorem, originally for division rings but extended to semigroups, guarantees the existence of the universal group containing S as a subsemigroup. Representative examples illustrate the construction. The multiplicative semigroup (\mathbb{N} \setminus \{0\}, \times) of positive integers is commutative and cancellative, satisfying the Ore condition, and embeds into the positive rational numbers (\mathbb{Q}^+, \times), where fractions p/q correspond to classes (p, q). Similarly, the free semigroup on a set X (words over X under concatenation) is cancellative and satisfies the Ore condition, embedding into the free group on X, where inverses allow reduction of words to group elements.

Free Semigroups

In abstract algebra, the free semigroup on a nonempty set A, often denoted F(A) or A^+, consists of all nonempty finite sequences of elements from A (known as words over the alphabet A), equipped with the operation of concatenation, which appends one sequence after another. This operation is associative by construction, and the structure imposes no additional relations beyond this associativity, making F(A) the "freest" possible semigroup generated by A. The set A serves as a basis for F(A), and the cardinality of A is called the rank of the free semigroup. The free semigroup F(A) satisfies a universal property: for any semigroup S and any function f: A \to S, there exists a unique semigroup homomorphism \overline{f}: F(A) \to S such that \overline{f} restricted to A equals f, where the image of a word under \overline{f} is obtained by successively applying f to its letters and concatenating in S. This property characterizes F(A) up to isomorphism and ensures that any semigroup generated by a set of the same cardinality is a homomorphic image of some free semigroup. Every subsemigroup of F(A) generated by a subset B \subseteq A is itself the free semigroup F(B). Elements of F(A) admit unique factorizations into letters from A, with no nontrivial identities holding except those true in all semigroups. The words can be partially ordered by the prefix relation, where u \preceq v if u is an initial segment of v; this forms a tree-like structure rooted at the single-letter words. Free semigroups contain no idempotents, as the concatenation of any nonempty word w with itself yields a word of twice the length, which cannot equal w. Moreover, since free semigroups are cancellative, they embed into the free group on the same generating set A. A concrete example is the free semigroup F(\{a, b\}), comprising all nonempty finite strings of as and bs under concatenation, such as ab, baab, and bbb. The growth of F(A) is exponential: the number of words of exact length n is |A|^n, reflecting the combinatorial explosion of possible sequences. For the singleton case A = \{a\}, F(A) is isomorphic to the positive integers under addition, via the map sending the word a^n to n. The group of fractions of a free semigroup coincides with the free group on A.

Presentations

A presentation of a semigroup provides a description in terms of generators and relations. Formally, a presentation is a pair \langle X \mid R \rangle, where X is a set of generators and R is a set of relations, each consisting of an equality u = v with u, v nonempty words over the alphabet X. The semigroup defined by this presentation is the free semigroup on X quotiented by the congruence generated by R. The congruence of a presentation \langle X \mid R \rangle is the smallest congruence \sigma on the free semigroup X^+ such that all pairs (u, v) for relations u = v \in R satisfy u \sigma v. This congruence identifies words that can be transformed into one another via the relations and the semigroup operation, ensuring the resulting structure satisfies the specified equalities. Presentations for semigroups differ from those for monoids in that semigroup presentations operate on the free semigroup without an identity element, whereas monoid presentations use the free monoid, which includes the empty word and assumes an identity. Balanced presentations, relevant in both contexts, require that for each relation u = v, the number of occurrences of each generator from X is the same in u and v; this property aids in analyzing deficiency and residual finiteness in semigroup theory. Tietze transformations provide a means to establish equivalence between presentations of the same semigroup. These include: (1) adding a new generator x along with a relation expressing x as a word in existing generators; (2) removing a generator that is redundant due to relations; (3) adding a new relation that follows from existing ones; and (4) removing a relation that is a consequence of the others. Two presentations are equivalent if one can be transformed into the other via a finite sequence of such operations. A representative example is the cyclic semigroup presented by \langle a \mid a^n = a^{n+1} \rangle for n \geq 1, which yields a finite null semigroup of order n. The elements are a, a^2, \dots, a^n, with multiplication defined by a^i a^j = a^{i+j} if i+j \leq n and a^i a^j = a^n otherwise, where a^n acts as a zero element absorbing all products involving it. This presentation constrains the free cyclic semigroup by making higher powers collapse to the absorbing element.

Special Classes

Monoids

A monoid is a semigroup equipped with a two-sided identity element e, satisfying e \cdot s = s \cdot e = s for all elements s in the semigroup. The elements possessing two-sided inverses relative to the binary operation are termed units, and the subset of units constitutes a group under the induced operation. This structure bridges semigroups and groups, incorporating an identity while potentially lacking universal invertibility. Cancellative monoids, where left and right cancellation hold (a \cdot b = a \cdot c implies b = c, and similarly for right multiplication), admit a monoid of fractions under suitable conditions such as the Ore property: for all a, b in the monoid, there exist c, d such that a \cdot c = b \cdot d. This construction embeds the original monoid into a larger monoid where fractions s/t (with t cancellative) are defined via equivalence s/t = s'/t' if s \cdot t' = s' \cdot t, preserving the operation. If the monoid is commutative and cancellative, the resulting structure often yields a group of fractions. Free monoids provide a universal construction: for a set A, the free monoid F_1(A) consists of all finite words (including the empty word \varepsilon) over A, under concatenation, with \varepsilon as identity. The free semigroup F(A) excludes \varepsilon, so F_1(A) = F(A) \cup \{\varepsilon\}. These satisfy the universal property that any map from A to a monoid extends uniquely to a monoid homomorphism from F_1(A). Varieties of monoids are equationally defined classes closed under homomorphic images, submonoids, and arbitrary products, capturing structural properties via identities. Pseudovarieties, focusing on finite monoids, are closed under homomorphic images, finite submonoids, and finite direct products; the variety generated by a pseudovariety consists of all monoids satisfying identities holding in every finite member of the pseudovariety. Prominent examples include the free monoid of strings over an alphabet \Sigma, where elements are finite sequences (including the empty string) and operation is concatenation. Another is the multiplicative monoid of n \times n matrices over a ring R, comprising all such matrices under matrix multiplication, with the identity matrix as e. In any monoid, the submonoid of units forms a group, as invertibility ensures closure, associativity, identity, and inverses.

Inverse Semigroups

An inverse semigroup is a semigroup S in which every element a \in S possesses a unique element a^{-1} \in S, called its inverse, satisfying the equations a = a a^{-1} a and a^{-1} = a^{-1} a a^{-1}. This uniqueness distinguishes inverse semigroups from more general regular semigroups, where inverses exist but may not be unique. The concept was introduced independently by V. V. Wagner in 1952 and G. B. Preston in 1954. A fundamental property of inverse semigroups is that the set E(S) of all idempotents (elements e \in S such that e = e^2) forms a commutative semilattice under the semigroup operation, meaning E(S) is a commutative idempotent semigroup where every pair of elements has a meet (greatest lower bound). For any a \in S, the element a a^{-1} (or equivalently a^{-1} a) is the unique idempotent associated to a, serving as its "source" or "domain" idempotent. Inverse semigroups admit a natural partial order defined by a \leq b if and only if a = a b a, which is compatible with the semigroup operation and refines the structure by ordering elements within and across classes. Under this order, each principal order ideal is itself an inverse subsemigroup. P-semigroups arise in the representation theory of certain inverse semigroups, particularly through McAlister's P-theorem, which characterizes E-unitary inverse semigroups (those where a e = a for idempotent e implies a is idempotent) as precisely those constructible from a P-semigroup—a structure consisting of a semilattice P, a group G, and an action of G on P satisfying specific covering and kernel conditions, yielding an inverse semigroup with commutative idempotents forming the semilattice P. This theorem provides a group-theoretic construction for a broad class of inverse semigroups, emphasizing their partial symmetry aspects. Prominent examples include the symmetric inverse semigroup I_n on a finite set with n elements, comprising all partial bijections (isomorphisms between subsets) under composition, which is the full inverse monoid of partial permutations and embeds all inverse semigroups of order up to certain bounds. Another key example is the polycyclic inverse monoid P_n, generated by n partial isometries s_1, \dots, s_n satisfying s_i s_i^{-1} s_i = s_i, s_i^{-1} s_i s_i^{-1} = s_i^{-1}, s_i^{-1} s_j = \delta_{ij} e (where e is the identity and \delta the Kronecker delta), modeling Cuntz-Krieger algebras in operator theory. The Wagner-Preston theorem asserts that every inverse semigroup S embeds isomorphically into the symmetric inverse monoid I_X on some set X, where the image consists of partial bijections representing elements of S as partial isometries with respect to the semilattice of domains. This representation theorem generalizes Cayley's theorem for groups and highlights inverse semigroups as concrete objects of partial symmetries. In the context of Green's relations (as discussed in general structure theorems), the H-classes of an inverse semigroup coincide with groups.

Regular and Completely Regular Semigroups

A regular semigroup is a semigroup S in which, for every element a \in S, there exists an element x \in S such that axa = a. This condition ensures that every element possesses a "weak inverse" or generalized inverse, allowing for a form of reversibility within the semigroup operation. The notion originates from analogous properties in ring theory and was formalized in the context of semigroup structure theory. A completely regular semigroup is a subclass of regular semigroups where, in addition to the regularity condition, for every a \in S, there exists an x \in S such that axa = a and ax = xa, meaning the weak inverse commutes with a. Equivalently, a completely regular semigroup is a union of its maximal subgroups, with every \mathcal{H}-class forming a group. This commuting property imposes stronger structural constraints, often leading to decompositions into group-like components. The structure of regular semigroups is described by an extension of the Rees theorem, which states that every regular semigroup can be represented as a disjoint union of groups arranged in a Rees matrix construction over a sandwich matrix of coefficients from the groups. Specifically, for completely 0-simple regular semigroups (a minimal ideal case), the theorem provides an isomorphism to a Rees matrix semigroup \mathcal{M}^0(G; I, \Lambda; P) over a group G with index sets I, \Lambda and a \Lambda \times I-matrix P of nonzero entries from G. This matrix representation captures the ideal structure and Green's relations, where \mathcal{D}-classes are indexed by the matrix blocks. For completely regular semigroups, the structure theorem constructs them as semilattices of Rees matrix semigroups over groups. Given a semilattice Y of idempotents, each y \in Y corresponds to a Rees matrix semigroup S_y = \mathcal{M}(I_y, G_y, \Lambda_y; P_y) over a group G_y, with translational hulls and homomorphisms \theta_{y z}: S_y \to T(S_z) ensuring compatibility under the semilattice operation. Bands, which are idempotent regular semigroups (where a^2 = a for all a), form a special case, consisting entirely of idempotents. Representative examples include the full transformation semigroup T_X on a set X, which is regular since for any transformation f \in T_X, there exists a cross-section g such that f g f = f. Rectangular bands provide another example: the semigroup on I \times \Lambda with multiplication (i, \lambda)(j, \mu) = (i, \mu) is idempotent and completely simple over the trivial group, hence regular. This regularity condition in semigroups draws a direct analogy to von Neumann regular rings, where a ring R is regular if for every a \in R, there exists x \in R such that a = a x a, mirroring the weak inverse property and facilitating similar ideal decompositions.

Applications

In Partial Differential Equations

In the context of partial differential equations (PDEs), semigroup theory provides a powerful framework for analyzing evolution equations, particularly those of parabolic and hyperbolic types, by representing solutions as orbits under one-parameter families of operators on Banach spaces. A C_0-semigroup, also known as a strongly continuous semigroup, is a family of bounded linear operators \{T(t)\}_{t \geq 0} on a Banach space X satisfying T(0) = I, the identity operator, and the semigroup property T(s + t) = T(s) T(t) for all s, t \geq 0, with strong continuity \lim_{t \to 0^+} T(t) x = x for all x \in X. This structure arises naturally in operator compositions for time-dependent problems, where associativity ensures the evolution preserves the functional form over time intervals. The infinitesimal generator A of a C_0-semigroup \{T(t)\} is the closed, densely defined operator given by A x = \lim_{t \to 0^+} \frac{T(t) x - x}{t} for x in its domain, satisfying \frac{d}{dt} T(t) x = A T(t) x = T(t) A x for suitable x. The Hille-Yosida theorem characterizes such generators: A generates a contraction C_0-semigroup if and only if it is densely defined, closed, and maximal accretive, meaning the resolvent set includes the right half-plane \{ \lambda \in \mathbb{C} : \Re \lambda > 0 \} with \| R(\lambda, A) \| \leq 1 / \Re \lambda. This theorem, independently established by Hille and Yosida, enables the verification of well-posedness for abstract evolution equations without explicit solution formulas. Prominent examples illustrate these concepts in PDEs. For the heat equation u_t = \Delta u on \mathbb{R}^n with initial data u(0) = f \in L^p(\mathbb{R}^n), the solution operator forms a C_0-semigroup generated by the Laplacian \Delta, explicitly given by convolution with the Gaussian kernel: T(t) f (x) = \frac{1}{(4 \pi t)^{n/2}} \int_{\mathbb{R}^n} f(y) e^{-|x - y|^2 / (4 t)} \, dy, which is analytic and contractive on L^p spaces. In contrast, the wave equation u_{tt} = \Delta u on a domain with Dirichlet boundaries can be reformulated as a first-order system U_t = A U where U = (u, u_t) and A = \begin{pmatrix} 0 & I \\ \Delta & 0 \end{pmatrix} on the energy space H_0^1(\Omega) \times L^2(\Omega); here A generates a unitary C_0-group (extending the semigroup to negative times), reflecting energy conservation. Semigroup theory applies to the abstract Cauchy problem u'(t) = A u(t), u(0) = u_0, yielding the mild solution u(t) = T(t) u_0 when A generates a C_0-semigroup, with well-posedness guaranteed by the Hille-Yosida conditions. For stability, contraction semigroups (\|T(t)\| \leq 1) correspond to dissipative generators via the Lumer-Phillips theorem, a variant of Hille-Yosida, ensuring bounded energy decay; analytic semigroups, generated by sectorial operators, provide smoothing effects crucial for parabolic regularity. Asymptotics, such as exponential decay for stable systems (\|T(t)\| \leq M e^{\omega t} with \omega < 0), follow from spectral properties of A, enabling long-time behavior analysis in dissipative PDEs like damped waves.

In Automata and Formal Languages

Semigroups play a central role in the algebraic theory of automata and formal languages, particularly through the concept of the syntactic semigroup of a regular language. For a regular language L over an alphabet \Sigma, the syntactic congruence \sim_L on \Sigma^+ is defined by u \sim_L v if and only if, for all x, y \in \Sigma^*, x u y \in L if and only if x v y \in L. The syntactic semigroup S_L is the quotient \Sigma^+ / \sim_L, which is the smallest semigroup recognizing L in the sense that there exists a surjective morphism from \Sigma^+ to S_L such that L is the preimage of an idempotent element under this morphism. This structure captures the essential algebraic properties of the language and is finite precisely when L is regular. The transitions of the minimal deterministic finite automaton (DFA) accepting L generate a subsemigroup isomorphic to S_L, linking automata directly to semigroup theory. Eilenberg's variety theorem establishes a profound correspondence between varieties of finite semigroups and certain classes of regular languages. Specifically, there is a bijective correspondence between varieties of finite semigroups (classes closed under subsemigroups, homomorphic images, and finite direct products) and positive varieties of languages (closed under union, \Sigma^*-multiples, and marked concatenation). For example, the variety of commutative semigroups corresponds to the class of languages whose syntactic semigroups are commutative, such as those definable by commutative regular expressions. This theorem enables the classification of language families through algebraic identities, with pseudovarieties (the finite analogues) corresponding to varieties of languages closed under boolean operations. A notable instance is the pseudovariety DA, defined by the pseudoidentity (xyz)^\omega z (xyz)^\omega = (xyz)^\omega, which recognizes languages definable in first-order logic with two variables (FO^2[<]). Simon's theorem characterizes the piecewise testable languages—those that are boolean combinations of languages of the form \Sigma^* a_1 \Sigma^* \cdots a_n \Sigma^* for a_i \in \Sigma—as those whose syntactic semigroups lie in the pseudovariety of J-trivial monoids, a subpseudovariety of the aperiodic DA. The Krohn-Rhodes decomposition theorem decomposes the transition semigroup of any finite automaton into a wreath product of simpler "prime" semigroups, revealing the hierarchical structure of automata complexity. Formally, any finite semigroup divides a wreath product of groups and flip-flop semigroups (cyclic groups of order 2), allowing any DFA to be synthesized as a cascade of basic reset and permutation automata. This decomposition quantifies the "group complexity" of a semigroup as the size of the largest non-trivial group dividing it, aiding in understanding the coordination and synchronization in computational models. For instance, aperiodic semigroups (those with trivial groups) correspond to automata decomposable without non-trivial cyclic components, aligning with star-free languages. Schützenberger's theorem bridges combinatorial and algebraic characterizations of star-free languages, stating that a regular language is star-free (expressible without Kleene star, using union, concatenation, and complement) if and only if its syntactic semigroup is aperiodic, meaning for every element s, there exists n such that s^{n+1} = s^n. Aperiodic semigroups have no non-trivial groups as subsemigroups, ensuring the language avoids periodic behaviors captured by cyclic structures. This result, proved using the Green relations and local structure of finite semigroups, implies that star-free languages are exactly those recognized by aperiodic transition semigroups in their minimal DFAs. For example, the language of words with even length over a unary alphabet has syntactic semigroup the cyclic group of order 2, which is periodic and thus not star-free. A concrete example of semigroup application is the transformation semigroup of a DFA, which consists of all functions induced by words on the state set Q, forming a subsemigroup of the full transformation semigroup T_Q. For a DFA with n states, this semigroup has at most n^n elements and determines the language recognized, as two DFAs accept the same language if and only if their transformation semigroups are isomorphic via state relabeling. The syntactic semigroup embeds into this transformation semigroup, providing a faithful representation for algorithmic purposes like minimization. In the case of pseudovariety DA, the transformation semigroups of DFAs recognizing FO^2[<] languages satisfy the defining pseudoidentity, allowing membership testing via syntactic analysis without full automaton simulation.

History and Development

Origins and Early Contributions

Early inspirations for semigroup theory came from late 19th-century work in group theory, such as Walther von Dyck's 1882 paper on free groups through generators and relations, which provided concepts later adapted for free semigroups. However, the formal study of semigroups as structures lacking inverses developed in the early 20th century, motivated by extensions of group theory and analyses of ring ideals. This work marked steps toward understanding non-cancellative algebraic systems. By the early 20th century, attention turned to transformation semigroups, with foundational results emerging in the Soviet school. The 1920s and 1930s saw pivotal advances led by Alexander Kurosh, whose general algebra framework incorporated semigroups as fundamental structures alongside groups and rings. Anton Suschkewitsch's 1928 theorem established that every finite semigroup embeds into the full transformation semigroup on a finite set, providing a concrete representation and structure theory for finite cases. In the 1940s, David Rees's work further advanced structural understanding with his 1940 matrix representation, showing that completely 0-simple semigroups are isomorphic to Rees matrix semigroups over a group with a suitable sandwich matrix. This complemented Suschkewitsch's results and facilitated classification efforts. Garrett Birkhoff's contemporaneous influence through abstract algebra emphasized lattice-ordered semigroups and their role in ideal theory, bridging semigroups with lattice and order structures. Post-World War II, the field coalesced with A.H. Clifford and G.B. Preston's two-volume The Algebraic Theory of Semigroups (1961, 1967), which synthesized early results into a comprehensive reference, establishing semigroup theory as a distinct algebraic discipline. These foundational contributions were driven by motivations to extend group axioms to weaker associative systems and analyze ring ideals as additive semigroups.

Key Advances and Modern Perspectives

In the mid-20th century, significant progress in semigroup theory was marked by investigations into presentations and decompositions. During the 1960s and 1970s, John M. Howie advanced the understanding of one-relator semigroups through embedding theorems and amalgamation properties, establishing criteria for when such semigroups could be embedded into larger structures while preserving relations. Concurrently, Peter M. Higgins contributed to the study of word problems in one-relator semigroups, developing diagrammatic methods to analyze solvability and structure in the 1980s. A landmark achievement was the Krohn-Rhodes decomposition theorem of 1965, which provided a prime factorization for finite semigroups into simple groups and flip-flops, enabling hierarchical analysis of automaton behaviors and influencing computational models. From the 1990s onward, computational semigroup theory gained momentum with algorithmic approaches to pseudovarieties—classes of finite semigroups closed under homomorphic images, subsemigroups, and finite products. Jean-Éric Pin and collaborators established decidability results for membership in specific pseudovarieties, such as those of aperiodic semigroups, using profinite methods and syntactic monoids for language recognition. These advances facilitated efficient algorithms for problems like equivalence of regular languages, with ongoing work addressing the general decidability of pseudovariety membership. Recent progress (as of 2023) includes algorithmic solutions for subsemigroups of matrix semigroups and further developments in inverse semigroup theory. In recent decades, semigroup theory has intersected with quantum mathematics, particularly through quantum semigroups in operator algebras. Post-2000 developments, including the study of C*-algebras associated to semigroup actions, have generalized classical dynamical systems to non-commutative settings, as explored in works on quantum Markov semigroups for open quantum systems. Applications have extended to AI and string algorithms, where finite semigroup techniques underpin efficient pattern matching and automaton-based learning models, such as in grammatical inference for natural language processing. Despite these strides, key open problems persist, including precise criteria for embeddability of semigroups into groups or monoids, which remain undecidable in general for finitely presented cases. The growth rates of free semigroups and their relatively free variants also pose challenges, with questions about intermediate growth between polynomial and exponential unresolved for many varieties. Semigroup theory continues to integrate deeply with category theory and universal algebra, where varieties of semigroups are modeled as monads on categories, enhancing structural proofs and generalizations across algebraic systems.

Generalizations

N-Ary and Partial Operations

An n-ary semigroup, also known as an n-semigroup, is a set G equipped with an n-ary operation f: G^n \to G that satisfies a generalized associativity condition. Specifically, for all x_1, \dots, x_{2n-1} \in G and every i = 1, \dots, n, the equality f(f(x_1, \dots, x_n), x_{n+1}, \dots, x_{2n-1}) = f(x_1, \dots, x_{i-1}, f(x_i, \dots, x_{i+n-1}), x_{i+n}, \dots, x_{2n-1}) holds, ensuring that the operation can be unambiguously extended to longer sequences. This structure generalizes the binary semigroup, where n=2 recovers the standard associative binary operation. A key property is the existence of a binary retract: fixing n-2 elements appropriately yields a binary semigroup operation on G. Polyadic groups, or n-ary groups, extend n-ary semigroups by requiring the operation to also satisfy quasigroup properties, meaning that for each position i = 1, \dots, n and fixed elements a_1, \dots, \hat{a}_i, \dots, a_n, b \in G, there exists a unique x \in G such that f(a_1, \dots, a_{i-1}, x, a_{i+1}, \dots, a_n) = b. This ensures solvability of equations in each variable, analogous to groups but without a global identity. Such structures maintain the associativity of n-ary semigroups while adding invertibility-like features, and their binary retracts are groups. Partial semigroups generalize semigroups by allowing the binary operation to be partial, defined only on a subset of G \times G. Formally, a partial semigroup is a set G with a partial binary operation \cdot: G \times G \to G \cup \{*\} (where * denotes undefined) such that whenever x \cdot y and y \cdot z are both defined, then both (x \cdot y) \cdot z and x \cdot (y \cdot z) are defined and equal. Totality conditions specify when the operation is total: if the domain is all of G \times G, it reduces to a standard semigroup. Associativity variants for partial operations emphasize "total associativity," holding conditionally on defined subexpressions, preserving structure on subsets where the operation is applicable. Examples of partial semigroups include structures derived from iterative systems, where a partial binary operation is repeatedly applied to form effective n-ary operations on domains ensuring all intermediate steps are defined. For instance, in computational models, partial operations on states may only apply under compatibility conditions, yielding an associative partial structure that simulates higher-arity computations through iteration. Heap structures provide another example: a heap on a set G uses a ternary operation [x, y, z] satisfying [x, y, [u, v, w]] = [[x, y, u], v, w] = [x, [y, u, v], w], which can be viewed as a total 3-ary semigroup but equivalently modeled via partial binary operations by fixing a "reference" element, such as [x, e, z] = x \cdot z for some fixed e. These extensions connect to quasigroups and latin squares through their quasigroup variants. An n-ary quasigroup generalizes the unique solvability of quasigroups, and when associative, it forms an n-ary semigroup; the multiplication "table" of an n-ary quasigroup corresponds to a latin hypercube, a higher-dimensional analog of the latin square for binary quasigroups, where rows, columns, and higher slices contain each symbol exactly once. Partial versions extend this to partial latin squares, linking partial semigroups with unique partial solvability to incomplete combinatorial designs.

Related Algebraic Structures

Semigroups represent a fundamental algebraic structure defined by a set equipped with an associative binary operation, positioning them as a refinement of more general constructs like magmas. A magma, also known as a groupoid in some contexts, consists of a set with a binary operation that lacks any associativity requirement, serving as the most basic non-empty algebraic structure with a single operation. In contrast to semigroups, magmas do not impose the condition (ab)c = a(bc) for all elements a, b, c, allowing for a broader class of examples such as non-associative operations in certain geometric or combinatorial settings. This progression from magma to semigroup highlights associativity as the key axiom that enables deeper structural analysis, such as the study of ideals and congruences. Quasigroups and loops extend the idea of binary operations without relying on associativity, instead emphasizing solvability properties that ensure unique solutions to equations of the form ax = b and ya = b. A quasigroup is a magma where left and right multiplications by any element are bijective, corresponding to the multiplication table forming a Latin square, which guarantees the existence and uniqueness of such solutions but permits non-associativity. Loops refine quasigroups by incorporating an identity element, making them quasigroups with a two-sided unit, yet still without the associativity of semigroups; for instance, the octonions form a non-associative loop under multiplication. These structures differ from semigroups by prioritizing divisibility over associativity, finding applications in design theory and cryptography where Latin square properties are crucial, rather than the concatenation-like behavior in semigroups. In category theory, semigroups arise naturally as the hom-sets between objects, where composition of morphisms provides the associative operation. Specifically, for objects A and B in a category \mathcal{C}, the set \hom(A, B) forms a semigroup under morphism composition, which is associative by the category axioms, though it may lack an identity unless A = B, in which case it becomes a monoid. This embedding distinguishes semigroups from full categories, as monoids correspond to single-object categories with identity, while general semigroups omit the unit; for example, the positive integers under addition form a semigroup that can be viewed as the hom-set in a category of ordered sets. Such a perspective underscores how semigroups capture the essence of partial orders or transformation systems without the full machinery of objects and identities. Semirings and near-rings generalize semigroups by incorporating a second operation, typically addition, while retaining a semigroup-like multiplication. A semiring comprises an abelian monoid under addition and a semigroup under multiplication, with multiplication distributing over addition, as seen in the non-negative reals with standard operations; this extends semigroups by adding a compatible additive structure without requiring additive inverses, unlike full rings. Near-rings relax distributivity further, requiring only right distributivity and allowing non-commutative addition, thus generalizing semirings while preserving the multiplicative semigroup; for instance, the set of functions from a group to itself under pointwise addition and substitution forms a near-ring. These structures highlight semigroups as the multiplicative core, enabling applications in automata theory and optimization where partial orders or weights are modeled. Semilattices provide a concrete example of how semigroups manifest in order theory, defined as commutative, idempotent semigroups where a \cdot a = a and a \cdot b = b \cdot a for all a, b. Under this operation, interpreted as meet or join, the structure induces a partial order via a \leq b if a \cdot b = a, distinguishing it from general semigroups by the additional idempotence and commutativity axioms; the power set of a finite set under intersection exemplifies a meet-semilattice. This idempotent variant contrasts with monoids, which require identity but not idempotence, illustrating how semigroup axioms can specialize to lattice-like behaviors without full lattice completeness.