Hubbry Logo
SemigroupSemigroupMain
Open search
Semigroup
Community hub
Semigroup
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Semigroup
Semigroup
Semigroup
View on Wikipedia
from Wikipedia
Algebraic structures between magmas and groups: A semigroup is a magma with associativity. A monoid is a semigroup with an identity element.

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

The binary operation of a semigroup is most often denoted multiplicatively (just notation, not necessarily the elementary arithmetic multiplication): x ⋅ y, or simply xy, denotes the result of applying the semigroup operation to the ordered pair (x, y). Associativity is formally expressed as that (x ⋅ y) ⋅ z = x ⋅ (y ⋅ z) for all x, y and z in the semigroup.

Semigroups may be considered a special case of magmas, where the operation is associative, or as a generalization of groups, without requiring the existence of an identity element or inverses.[a] As in the case of groups or magmas, the semigroup operation need not be commutative, so x ⋅ y is not necessarily equal to y ⋅ x; a well-known example of an operation that is associative but non-commutative is matrix multiplication. If the semigroup operation is commutative, then the semigroup is called a commutative semigroup or (less often than in the analogous case of groups) it may be called an abelian semigroup.

A monoid is an algebraic structure intermediate between semigroups and groups, and is a semigroup having an identity element, thus obeying all but one of the axioms of a group: existence of inverses is not required of a monoid. A natural example is strings with concatenation as the binary operation, and the empty string as the identity element. Restricting to non-empty strings gives an example of a semigroup that is not a monoid. Positive integers with addition form a commutative semigroup that is not a monoid, whereas the non-negative integers do form a monoid. A semigroup without an identity element can be easily turned into a monoid by just adding an identity element. Consequently, monoids are studied in the theory of semigroups rather than in group theory. Semigroups should not be confused with quasigroups, which are generalization of groups in a different direction; the operation in a quasigroup need not be associative but quasigroups preserve from groups the notion of division. Division in semigroups (or in monoids) is not possible in general.

The formal study of semigroups began in the early 20th century. Early results include a Cayley theorem for semigroups realizing any semigroup as 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.[1] In other areas of applied mathematics, semigroups are fundamental models for linear time-invariant systems. In partial differential equations, a semigroup is associated to any equation whose spatial evolution is independent of time.

There are numerous special classes of semigroups, semigroups with additional properties, which appear in particular applications. Some of these classes are even closer to groups by exhibiting some additional but not all properties of a group. Of these we mention: regular semigroups, orthodox semigroups, semigroups with involution, inverse semigroups and cancellative semigroups. There are also interesting classes of semigroups that do not contain any groups except the trivial group; examples of the latter kind are bands and their commutative subclass – semilattices, which are also ordered algebraic structures.

Algebraic structures
Group-like
Group theory
Ring-like
Ring theory
Lattice-like
Module-like
Algebra-like

Definition

[edit]

A semigroup is a set S together with a binary operation ⋅ (that is, a function ⋅ : S × S → S) that satisfies the associative property:

For all a, b, c ∈ S, the equation (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c) holds.

More succinctly, a semigroup is an associative magma.

Examples of semigroups

[edit]

Basic concepts

[edit]

Identity and zero

[edit]

A left identity of a semigroup S (or more generally, magma) is an element e such that for all x in S, e ⋅ x = x. Similarly, a right identity is an element f such that for all x in S, x ⋅ 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 ∉ S to S and defining e ⋅ s = s ⋅ e = s for all s ∈ S ∪ {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 can define S0, a semigroup with 0 that embeds S.

Subsemigroups and ideals

[edit]

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 ∈ A and b ∈ B }. (This notion is defined identically as it is for groups.) In terms of this operation, 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 a semigroup with no minimal ideal is the set of positive integers under addition. The minimal ideal of a commutative semigroup, when it exists, is a group.

Green's relations, a set of five equivalence relations that characterise the elements in terms of the principal ideals they generate, are important tools for analysing the ideals of a semigroup and related notions of structure.

The subset with the property that every element commutes with any other element of the semigroup is called the center of the semigroup.[4] The center of a semigroup is actually a subsemigroup.[5]

Homomorphisms and congruences

[edit]

A semigroup homomorphism is a function that preserves semigroup structure. A function f : S → T 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 that are not monoid homomorphisms, e.g. the canonical embedding of a semigroup S without identity into S1. Conditions characterizing monoid homomorphisms are discussed further. Let f : S0 → S1 be a semigroup homomorphism. The image of f is also a semigroup. If S0 is a monoid with an identity element e0, then f(e0) is the identity element in the image of f. If S1 is also a monoid with an identity element e1 and e1 belongs to the image of f, then f(e0) = e1, 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 → T. Isomorphic semigroups have the same structure.

A semigroup congruence ~ is an equivalence relation that is compatible with the semigroup operation. That is, a subset ~ ⊆ S × S that is an equivalence relation and x ~ y and u ~ v implies xu ~ yv for every x, y, u, v in S. Like any equivalence relation, a semigroup congruence ~ induces congruence classes

[a]~ = {x ∈ S | x ~ a}

and the semigroup operation induces a binary operation ∘ on the congruence classes:

[u]~ ∘ [v]~ = [uv]~

Because ~ is a congruence, the set of all congruence classes of ~ forms a semigroup with ∘, called the quotient semigroup or factor semigroup, and denoted S / ~. The mapping x ↦ [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.[6]

A semigroup S satisfies the maximal condition on congruences if any family of congruences on S, ordered by inclusion, has a maximal element. By Zorn's lemma, this is equivalent to saying that the ascending chain condition holds: there is no infinite strictly ascending chain of congruences on S.[7]

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

Quotients and divisions

[edit]

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

A semigroup T is a quotient of a semigroup S if there is a surjective semigroup morphism from S to T. For example, (Z/2Z, +) is a quotient of (Z/4Z, +), using the morphism consisting of taking the remainder modulo 2 of an integer.

A semigroup T divides a semigroup S, denoted T ≼ S if T is a quotient of a subsemigroup S. In particular, subsemigroups of S divides T, while it is not necessarily the case that there are a quotient of S.

Both of those relations are transitive.

Structure of semigroups

[edit]

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

A subsemigroup that 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[b] 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

[edit]
Main article: Special classes of semigroups
  • A monoid is a semigroup with an identity element.
  • A group is a monoid in which every element has an inverse element.
  • A subsemigroup is a subset of a semigroup that is closed under the semigroup operation.
  • A cancellative semigroup is one having the cancellation property:[9] a · b = a · c implies b = c and similarly for b · a = c · a. Every group is a cancellative semigroup, and every finite cancellative semigroup is a group.
  • A band is a semigroup whose operation is idempotent.
  • A semilattice is a semigroup whose operation is idempotent and commutative.
  • 0-simple semigroups.
  • Transformation semigroups: any finite semigroup S can be represented by transformations of a (state-) set Q of at most |S| + 1 states. Each element x of S then maps Q into itself x : Q → Q and sequence xy is defined by q(xy) = (qx)y for each q in Q. Sequencing clearly is an associative operation, here equivalent to function composition. This representation is basic for any automaton or finite-state machine (FSM).
  • The bicyclic semigroup is in fact a monoid, which can be described as the free semigroup on two generators p and q, under the relation pq = 1.
  • C0-semigroups.
  • Regular semigroups. Every element x has at least one inverse y that satisfies 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

[edit]

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

Given a homomorphism f : S → L from an arbitrary semigroup to a semilattice, each inverse image Sa = f−1{a} is a (possibly empty) semigroup. Moreover, S becomes graded by L, in the sense that SaSb ⊆ Sa∧b.

If f is onto, the semilattice L is isomorphic to the quotient of S by the equivalence relation ~ such that x ~ y if and only if 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 ~ 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 Sa 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 xn = yz.

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

Group of fractions

[edit]

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

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

Semigroup methods in partial differential equations

[edit]
Further information: C0-semigroup

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

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

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

On an heuristic level, the solution to this problem "ought" to be 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

[edit]

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

Anton Sushkevich obtained the first non-trivial results about semigroups. His 1928 paper "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit" ("On finite groups without the rule of unique invertibility") determined the structure of finite simple semigroups and showed that the minimal ideal (or Green's relations J-class) of a finite semigroup is simple.[19] From that point on, the foundations of semigroup theory were further laid by David Rees, James Alexander Green, Evgenii Sergeevich Lyapin [fr], 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 published by Springer Verlag) became one of the few mathematical journals devoted entirely to semigroup theory.

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

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

[edit]
Group-like structures
Total Associative Identity Divisible Commutative
Partial magma Unneeded Unneeded Unneeded Unneeded Unneeded
Semigroupoid Unneeded Required Unneeded Unneeded Unneeded
Small category Unneeded Required Required Unneeded Unneeded
Groupoid Unneeded Required Required Required Unneeded
Magma Required Unneeded Unneeded Unneeded Unneeded
Quasigroup Required Unneeded Unneeded Required Unneeded
Unital magma Required Unneeded Required Unneeded Unneeded
Loop Required Unneeded Required Required Unneeded
Semigroup Required Required Unneeded Unneeded Unneeded
Monoid Required Required Required Unneeded Unneeded
Group Required Required Required Required Unneeded
Abelian group Required Required Required Required Required

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

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

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

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

See also

[edit]

Notes

[edit]

Citations

[edit]
  1. ^ Feller 1971
  2. ^ Jacobson 2009, p. 30, ex. 5
  3. ^ a b Lawson 1998, p. 20
  4. ^ Kilp, Mati; Knauer, U.; Mikhalev, Aleksandr V. (2000). Monoids, Acts, and Categories: With Applications to Wreath Products and Graphs : a Handbook for Students and Researchers. Walter de Gruyter. p. 25. ISBN 978-3-11-015248-7. Zbl 0945.20036.
  5. ^ Li͡apin, E. S. (1968). Semigroups. American Mathematical Soc. p. 96. ISBN 978-0-8218-8641-0.
  6. ^ Lothaire 2011, p. 463
  7. ^ Lothaire 2011, p. 465
  8. ^ Pin, Jean-Éric (November 30, 2016). Mathematical Foundations of Automata Theory (PDF). p. 19.
  9. ^ Clifford & Preston 2010, p. 3
  10. ^ Grillet 2001
  11. ^ Farb, B. (2006). Problems on mapping class groups and related topics. Amer. Math. Soc. p. 357. ISBN 978-0-8218-3838-9.
  12. ^ Auslander, M.; Buchsbaum, D. A. (1974). Groups, rings, modules. Harper & Row. p. 50. ISBN 978-0-06-040387-4.
  13. ^ Clifford & Preston 1961, p. 34
  14. ^ Cain 2012, Theorem 6.1.
  15. ^ Suschkewitsch 1928
  16. ^ Preston, G. B. (1990). Personal reminiscences of the early history of semigroups. Archived from the original on 2009-01-09. Retrieved 2009-05-12.
  17. ^ Maltsev, A. (1937). "On the immersion of an algebraic ring into a field". Math. Annalen. 113: 686–691. doi:10.1007/BF01571659. S2CID 122295935.
  18. ^ "Earliest Known Uses of Some of the Words of Mathematics".
  19. ^ a b "An account of Suschkewitsch's paper by Christopher Hollings" (PDF). Archived from the original (PDF) on 2009-10-25.
  20. ^ B. M. Schein (1963) "Representations of semigroups by means of binary relations" (Russian), Matematicheskii Sbornik 60: 292–303 MR 0153760
  21. ^ B. M. Schein (1972) Miniconference on semigroup Theory, MR 0401970
  22. ^ B. M. Schein & R. McKenzie (1997) "Every semigroup is isomorphic to a transitive semigroup of binary relations", Transactions of the American Mathematical Society 349(1): 271–85 MR 1370647
  23. ^ Dudek, W.A. (2001). "On some old problems in n-ary groups". Quasigroups and Related Systems. 8: 15–36. Archived from the original on 2009-07-14.

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Semigroup

View on Grokipedia
from Grokipedia
A semigroup is a mathematical structure consisting of a set SS equipped with a binary operation ⋅:S×S→S\cdot: S \times S \to S that is associative, meaning that for all a,b,c∈Sa, b, c \in S, (a⋅b)⋅c=a⋅(b⋅c)(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∈Se \in S such that e⋅a=a⋅e=ae \cdot a = a \cdot e = a for all a∈Sa \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⋅b=b⋅aa \cdot b = b \cdot a for all a,b∈Sa, b \in S, and they may be finite or infinite depending on the cardinality of SS. Semigroup theory encompasses various subclasses and generalizations, such as regular semigroups, where for every x∈Sx \in S, there exists y∈Sy \in S such that x⋅y⋅x=xx \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 SS equipped with a binary operation ⋅:S×S→S\cdot: S \times S \to S that is associative, meaning that for all a,b,c∈Sa, b, c \in S, (a⋅b)⋅c=a⋅(b⋅c)(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., abab for a⋅ba \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 nn grows rapidly, with 1 for n=1n=1, 5 for n=2n=2, and 24 for n=3n=3. In more general settings, such as functional analysis, continuous (or one-parameter) semigroups arise as strongly continuous families {T(t)}t≥0\{T(t)\}_{t \geq 0} of bounded linear operators on a Banach space XX, satisfying T(0)=IT(0) = I, T(s+t)=T(s)T(t)T(s+t) = T(s)T(t) for s,t≥0s, t \geq 0, and strong continuity at t=0t=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 N\mathbb{N} (excluding 0) under addition forms an infinite commutative semigroup (N,+)(\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)(a + b) + c = a + (b + c) for all a,b,c∈Na, b, c \in \mathbb{N}. Similarly, the set (N,×)(\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×nn \times n matrices over a field FF, equipped with matrix multiplication, constitutes a semigroup (Mn(F),⋅)(M_n(F), \cdot). Closure follows from the fact that the product of two n×nn \times n matrices is again an n×nn \times n matrix, and associativity is a standard property of matrix multiplication: (AB)C=A(BC)(AB)C = A(BC) for all A,B,C∈Mn(F)A, B, C \in M_n(F). This example is non-commutative for n≥2n \geq 2. The free semigroup on a nonempty set AA (an alphabet) consists of all finite nonempty words over AA, with concatenation as the operation. For words w,vw, v formed from letters in AA, the product wvwv is the concatenated word, which is closed in the set of words and associative because (wv)u=w(vu)(wv)u = w(vu) for any words w,v,uw, v, u. If ∣A∣>1|A| > 1, this semigroup is non-commutative. The full transformation semigroup on a nonempty set XX comprises all functions from XX to itself, under composition. For functions f,g:X→Xf, g: X \to X, the product f∘gf \circ g is defined by (f∘g)(x)=f(g(x))(f \circ g)(x) = f(g(x)) for all x∈Xx \in X, ensuring closure, and associativity holds as function composition is inherently associative: (f∘g)∘h=f∘(g∘h)(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)G = (V, E) is the set of all finite paths in GG, 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 (N+,max⁡)(\mathbb{N}^+, \max), where max⁡(m,n)\max(m, n) is the larger of mm and nn. Closure is immediate, and associativity holds because max⁡(max⁡(m,n),p)=max⁡(m,max⁡(n,p))\max(\max(m, n), p) = \max(m, \max(n, p)) for all positive integers m,n,pm, n, p. Each element is idempotent, satisfying max⁡(k,k)=k\max(k, k) = k.

Core Concepts

Identity and Zero Elements

In a semigroup (S,⋅)(S, \cdot), an element e∈Se \in S is called a left identity if e⋅a=ae \cdot a = a for all a∈Sa \in S, a right identity if a⋅e=aa \cdot e = a for all a∈Sa \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, (N,max⁡)(\mathbb{N}, \max), admits neither a left nor a right identity, as no element ee can satisfy max⁡(e,n)=n\max(e, n) = n for all n∈Nn \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 ee is a left identity and ff is a right identity. Then e=e⋅f=fe = e \cdot f = f, using the left property on ff and the right property on ee. Similarly, if ee and ff are both two-sided identities, then e=e⋅f=fe = e \cdot f = f. This uniqueness holds without requiring inverses or further structure beyond associativity. An element z∈Sz \in S is a left zero if z⋅a=zz \cdot a = z for all a∈Sa \in S, a right zero if a⋅z=za \cdot z = z for all a∈Sa \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}\{0, 1\} with operation defined by 0⋅0=00 \cdot 0 = 0, 0⋅1=00 \cdot 1 = 0, 1⋅0=01 \cdot 0 = 0, and 1⋅1=01 \cdot 1 = 0; this is associative, 00 serves as a two-sided zero, but no identity exists, as neither element neutralizes 11 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 zLz_L is a left zero and zRz_R is a right zero; then zL=zL⋅zR=zRz_L = z_L \cdot z_R = z_R. Likewise, for two two-sided zeros zz and z′z', z=z⋅z′=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⋅b=aa \cdot b = a for all a,ba, 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 SS is a nonempty subset T⊆ST \subseteq S such that for all a,b∈Ta, b \in T, the product ab∈Tab \in T. Since the binary operation on SS is associative, the restricted operation on TT inherits this property, making TT a semigroup in its own right. If SS is a monoid with identity element ee, then a subsemigroup TT is a submonoid if it also contains ee. The subsemigroup generated by a nonempty subset X⊆SX \subseteq S, denoted ⟨X⟩\langle X \rangle, is the smallest subsemigroup of SS containing XX. It consists of all finite products of elements from XX (including the empty product if SS has an identity). For a singleton X={a}X = \{a\}, the monogenic subsemigroup ⟨a⟩={an∣n≥1, an∈S}\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 SS is a nonempty subset I⊆SI \subseteq S such that SI⊆IS I \subseteq I; a right ideal satisfies IS⊆II 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 II remain in II by the ideal property applied to elements of SS. In commutative semigroups, the notions of left, right, and two-sided ideals coincide. If SS has a zero element 00, then {0}\{0\} forms a two-sided ideal. The principal left ideal generated by an element a∈Sa \in S is the set S1a=Sa∪{a}S^1 a = S a \cup \{a\} (where S1=SS^1 = S if SS has an identity, or S1=S∪{1}S^1 = S \cup \{1\} otherwise), which is the smallest left ideal containing aa. Similarly, the principal right ideal is aS1a S^1, and the principal two-sided ideal is S1aS1S^1 a S^1. These are the intersections of all left (resp. right, two-sided) ideals containing aa. For example, in the additive semigroup (N0,+)(\mathbb{N}_0, +) of non-negative integers, the set of even non-negative integers 2N02\mathbb{N}_0 is a subsemigroup but not an ideal, while the principal two-sided ideal generated by 2 is {k∈N0∣k≥2}\{ 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=N0×N0B = \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))(m,n)(p,q) = (m + p - \min(n,p), q + \max(n,p) - \min(n,p)), the set Im={(x,y)∣x≥m, y∈N0}I_m = \{ (x,y) \mid x \geq m, \, y \in \mathbb{N}_0 \} forms a principal right ideal generated by any element (m,n)∈B(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 ϕ:S→T\phi: S \to T between semigroups (S,⋅S)(S, \cdot_S) and (T,⋅T)(T, \cdot_T) such that ϕ(a⋅Sb)=ϕ(a)⋅Tϕ(b)\phi(a \cdot_S b) = \phi(a) \cdot_T \phi(b) for all a,b∈Sa, b \in S. This preserves the associative binary operation, ensuring that the structure of products in SS is mirrored in TT. The image of ϕ\phi, denoted Im⁡(ϕ)={ϕ(a)∣a∈S}\operatorname{Im}(\phi) = \{\phi(a) \mid a \in S\}, forms a subsemigroup of TT. The kernel of ϕ\phi, defined as the relation Ker⁡(ϕ)={(a,b)∈S×S∣ϕ(a)=ϕ(b)}\operatorname{Ker}(\phi) = \{(a, b) \in S \times S \mid \phi(a) = \phi(b)\}, is a congruence on SS. 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 AA into its ambient semigroup SS, where ι(a)=a\iota(a) = a for a∈Aa \in A, which is a homomorphism preserving the operation. Another is the map ϕ:(N0,+)→(S,⋅)\phi: (\mathbb{N}_0, +) \to (S, \cdot) sending n↦ann \mapsto a^n for a fixed a∈Sa \in S, which is a homomorphism generating a monogenic subsemigroup. For isomorphisms, the exponential map n↦2nn \mapsto 2^n from (N0,+)(\mathbb{N}_0, +) to ({2n∣n∈N0},⋅)(\{2^n \mid n \in \mathbb{N}_0\}, \cdot) is bijective with inverse log⁡2\log_2.

Relations and Equivalences

Congruences

A congruence on a semigroup SS is an equivalence relation ∼\sim on SS such that for all a,b,c,d∈Sa, b, c, d \in S, if a∼ba \sim b and c∼dc \sim d, then ac∼bdac \sim bd. This compatibility condition ensures that the relation respects the semigroup operation, allowing the equivalence classes to form a partition of SS that is preserved under multiplication. The equivalence classes of a congruence ∼\sim, denoted ={b∈S∣b∼a} = \{b \in S \mid b \sim a\} for a∈Sa \in S, partition SS into subsets where the operation induces a well-defined semigroup structure on the quotient set S/∼S / \sim. Specifically, the product of classes =[ac] = [ac] is independent of the representatives chosen, due to the congruence property. A principal congruence on SS is the smallest congruence containing a specified pair (e,f)∈S×S(e, f) \in S \times S, generated by identifying ee and ff and closing under the semigroup operation and equivalence transitivity. For instance, Green's relations, such as the left relation L\mathcal{L} where aLba \mathcal{L} b if there exist x,y∈Sx, y \in S with a=xba = x b and b=yab = y a (the principal left ideal generated by aa equals that by bb), can be used to define associated principal congruences by symmetrization and closure. The set of all congruences on SS, denoted Con(S)\mathrm{Con}(S), forms a lattice under the partial order of refinement: ρ≤σ\rho \leq \sigma if ρ⊆σ\rho \subseteq \sigma as relations on S×SS \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 SS. Examples include the trivial congruence, the equality relation Δ={(a,a)∣a∈S}\Delta = \{(a, a) \mid a \in S\}, which yields the discrete quotient isomorphic to SS, and the universal congruence ∇=S×S\nabla = S \times S, producing the trivial one-element semigroup. In the semigroup of natural numbers under addition, the congruence modulo nn identifies numbers differing by multiples of nn, partitioning into nn classes preserved under addition.

Quotient Semigroups

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

Division of Semigroups

In semigroup theory, a semigroup SS divides a semigroup TT, denoted S≾TS \precsim T, if there exists a subsemigroup UU of TT and a surjective homomorphism ϕ:U→S\phi: U \to S. This notion captures a form of embedding where SS arises as a "factor" within TT, generalizing direct subsemigroup inclusions (when ϕ\phi is the identity) and quotients (when U=TU = 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≾TS \precsim T if and only if there exists an injective relational morphism τ:S→T\tau: S \to T. Here, a relational morphism τ⊆S×T\tau \subseteq S \times T satisfies: (i) for all s∈Ss \in S, sτ≠∅s\tau \neq \emptyset; and (ii) for all s,t∈Ss, t \in S, (sτ)(tτ)⊆(st)τ(s\tau)(t\tau) \subseteq (st)\tau, where the relational product is defined by (sτ)(tτ)={xy∣x∈sτ,y∈tτ}(s\tau)(t\tau) = \{xy \mid x \in s\tau, y \in t\tau\}. The morphism is injective if, whenever sτ∩s′τ≠∅s\tau \cap s'\tau \neq \emptyset, then s=s′s = s', ensuring distinct elements of SS map to disjoint non-empty subsets of TT. 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∈Sa, b \in S if they generate the same two-sided principal ideal, i.e., SaS=SbSS a S = S b S. This captures mutual two-sided divisibility: aa divides bb (and vice versa) in the sense that b∈SaSb \in S a S and a∈SbSa \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 SS embeds as a subsemigroup of the full transformation semigroup TXT_X on a set XX with ∣X∣=∣S∣|X| = |S|, via the action on left cosets or regular representation; thus, S≾TXS \precsim T_X. For instance, the symmetric group SnS_n (permutations on nn points) divides the full transformation semigroup TnT_n, as SnS_n is itself a subsemigroup of TnT_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 R\mathcal{R} is defined by aRba \mathcal{R} b if and only if the principal right ideals generated by aa and bb coincide, that is, Sa=SbSa = Sb, where Sa={sa∣s∈S}Sa = \{sa \mid s \in S\}. Similarly, the left Green's relation L\mathcal{L} is given by aLba \mathcal{L} b if and only if aS=bSaS = bS. The intersection H=R∩L\mathcal{H} = \mathcal{R} \cap \mathcal{L} captures elements that generate the same principal left and right ideals, while the two-sided relation J\mathcal{J} arises from equality of principal two-sided ideals, SaS=SbSSaS = SbS. The relation D\mathcal{D}, the smallest equivalence containing both R\mathcal{R} and L\mathcal{L}, coincides with J\mathcal{J} in finite semigroups but may differ in infinite ones. These relations partition the semigroup into classes: R\mathcal{R}-classes correspond to distinct right ideals, L\mathcal{L}-classes to left ideals, H\mathcal{H}-classes to their intersections, D\mathcal{D}-classes to unions of R\mathcal{R}-classes within the same two-sided ideal, and J\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 J\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,Λ;P)M(G; I, \Lambda; P) consists of triples (i,g,λ)(i, g, \lambda) with i∈Ii \in I, λ∈Λ\lambda \in \Lambda, g∈Gg \in G, and multiplication defined by (i,g,λ)(i′,g′,λ′)=(i,gPλ,i′g′,λ′)(i, g, \lambda)(i', g', \lambda') = (i, g P_{\lambda, i'} g', \lambda'), where P=(Pλ,i)P = (P_{\lambda, i}) is a Λ×I\Lambda \times I-matrix with entries in GG. 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 ee, satisfying e2=ee^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)E(S) of all idempotents forms a subsemigroup that is a band (idempotent semigroup), and under the natural partial order e≤fe \leq f if e=ef=fee = e f = f e, it constitutes a commutative semilattice where the meet e∧f=efe \wedge f = e f satisfies associativity, commutativity, and idempotence. This semilattice E(S)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 SS is defined by a≤ba \leq b if there exists s∈Ss \in S such that a=sba = s b (right preorder) or symmetrically for left, refined in regular cases to a≤ba \leq b if a=abaa = a b a and ab=baa b = b a ensuring antisymmetry. This order is compatible with multiplication in the sense that if a≤ba \leq b, then for any c∈Sc \in S, ac≤bca c \leq b c and ca≤cbc 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)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 aa in a finite semigroup SS satisfies ak=ak+ma^k = a^{k+m} for sufficiently large kk and some m≥1m \geq 1, implying that some power of aa is idempotent, i.e., ak′=(ak′)2a^{k'} = (a^{k'})^2 for some k′≥1k' \geq 1. This result, established by Moore in 1902, ensures that the subsemigroup generated by aa stabilizes to an idempotent after finitely many multiplications, bounding the growth of powers and facilitating structural analysis. For any element aa in a finite semigroup, the cyclic subsemigroup ⟨a⟩={a,a2,a3,… }\langle a \rangle = \{a, a^2, a^3, \dots \} has a well-defined index mm and period rr, where m≥1m \geq 1 and r≥1r \geq 1 are the smallest integers such that am+r=ama^{m+r} = a^m. This structure partitions ⟨a⟩\langle a \rangle into a transient chain of length m−1m-1 (elements before the cycle) followed by a cyclic group of order rr generated by ama^m, which is idempotent if r=1r=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→a2a \to a^2 cycling as a2→a3=a2a^2 \to a^3 = a^2. The Krohn-Rhodes theorem provides a global decomposition, stating that every finite semigroup SS 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 SS as a coordinated product of simple building blocks, with the complexity of SS defined as the minimal number of group levels in such a decomposition, bounding the "depth" of relational structures in SS. For instance, the full transformation semigroup on nn points decomposes into n−1n-1 flip-flops wreathing the symmetric group SnS_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×nn \times n arrays for ∣S∣=n|S| = n encoding the operation via row-column entries, allowing direct computation of structural invariants. Regularity of an element s∈Ss \in S is detectable if ss appears in its own row (or column) in the table, indicating the existence of an inverse tt such that s=stss = s t s. Green's relations, which partition SS into equivalence classes based on principal ideals (e.g., LL-classes for left ideals, RR-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 nn growing rapidly: 1 for n=1n=1, 1 for n=2n=2, 2 for n=3n=3, 5 for n=4n=4, and 15 for n=5n=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 nn. 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 SS is isomorphic to the semilattice product of a commutative idempotent semigroup (a semilattice) Y=S/ρY = S / \rho and the family of Archimedean semigroups {Ae∣e∈Y}\{A_e \mid e \in Y\}, where ρ\rho is the canonical congruence relation defined below, and each AeA_e is the ρ\rho-class corresponding to ee. 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 SS is Archimedean if, for every pair of elements a,b∈Sa, b \in S, there exists a positive integer nn such that aS∩bSn≠∅aS \cap bS^n \neq \emptyset. Equivalently, in additive notation, for the semigroup (S,+)(S, +), this means a+S∩b+nS≠∅a + S \cap b + nS \neq \emptyset. The congruence ρ\rho on SS is defined by aρba \rho b if and only if there exist positive integers m,nm, n such that aSm∩bSn≠∅aS^m \cap bS^n \neq \emptyset; the ρ\rho-classes form the Archimedean components of SS, each of which is itself an Archimedean semigroup, and the quotient S/ρS / \rho is a semilattice under the induced operation. Within these components, elements satisfy properties such as abak=ak+1ba b a^k = a^{k+1} b for sufficiently large kk, 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 00 such that the product of any two elements is 00, 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 (N0,+)(\mathbb{N}_0, +), where N0={0,1,2,… }\mathbb{N}_0 = \{0, 1, 2, \dots \}, is Archimedean because for any a,b∈N0a, b \in \mathbb{N}_0, the sets a+N0=N0a + \mathbb{N}_0 = \mathbb{N}_0 and b+nN0=N0b + n \mathbb{N}_0 = \mathbb{N}_0 (for any n≥1n \geq 1) intersect non-trivially. Thus, it appears as a single Archimedean component in its own decomposition, embeddable into the abelian group Z\mathbb{Z}. On the other hand, the direct product of two chains under componentwise meet operation, such as [0,1]×[0,1][0,1] \times [0,1] with (x1,y1)∧(x2,y2)=(min⁡(x1,x2),min⁡(y1,y2))(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 SS is left cancellative if, for all a,b,c∈Sa, b, c \in S, the equation ab=acab = ac implies b=cb = c. Similarly, SS is right cancellative if ba=caba = ca implies b=cb = 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 SS (assumed to be a monoid with identity 11), the group of fractions G(S)G(S) is constructed as the set of equivalence classes of pairs S×SS \times S under the relation (a,b)∼(c,d)(a, b) \sim (c, d) if and only if ad=bcad = bc. The group operation is defined by (a,b)⋅(c,d)=(ac,bd)(a, b) \cdot (c, d) = (ac, bd), which is well-defined under appropriate conditions. The embedding ι:S→G(S)\iota: S \to G(S) maps each a∈Sa \in S to the class of (a,1)(a, 1), preserving the semigroup operation. In this group, elements of SS gain inverses: the inverse of ι(a)\iota(a) is the class of (1,a)(1, a), since (a,1)⋅(1,a)=(a,a)∼(1,1)(a, 1) \cdot (1, a) = (a, a) \sim (1, 1) by cancellativity. However, for the construction to yield a group in which SS embeds injectively, SS must satisfy the Ore condition. A semigroup satisfies the left Ore condition if, for all a,b∈Sa, b \in S, the intersection aS∩bS≠∅aS \cap bS \neq \emptyset, meaning there exist x,y∈Sx, y \in S such that ax=byax = by. Ore's theorem states that a left cancellative semigroup satisfying the left Ore condition embeds into a group of left fractions S−1SS^{-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 SS as a subsemigroup. Representative examples illustrate the construction. The multiplicative semigroup (N∖{0},×)(\mathbb{N} \setminus \{0\}, \times) of positive integers is commutative and cancellative, satisfying the Ore condition, and embeds into the positive rational numbers (Q+,×)(\mathbb{Q}^+, \times), where fractions p/qp/q correspond to classes (p,q)(p, q). Similarly, the free semigroup on a set XX (words over XX under concatenation) is cancellative and satisfies the Ore condition, embedding into the free group on XX, where inverses allow reduction of words to group elements.

Free Semigroups

In abstract algebra, the free semigroup on a nonempty set AA, often denoted F(A)F(A) or A+A^+, consists of all nonempty finite sequences of elements from AA (known as words over the alphabet AA), 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)F(A) the "freest" possible semigroup generated by AA. The set AA serves as a basis for F(A)F(A), and the cardinality of AA is called the rank of the free semigroup. The free semigroup F(A)F(A) satisfies a universal property: for any semigroup SS and any function f:A→Sf: A \to S, there exists a unique semigroup homomorphism f‾:F(A)→S\overline{f}: F(A) \to S such that f‾\overline{f} restricted to AA equals ff, where the image of a word under f‾\overline{f} is obtained by successively applying ff to its letters and concatenating in SS. This property characterizes F(A)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)F(A) generated by a subset B⊆AB \subseteq A is itself the free semigroup F(B)F(B). Elements of F(A)F(A) admit unique factorizations into letters from AA, with no nontrivial identities holding except those true in all semigroups. The words can be partially ordered by the prefix relation, where u⪯vu \preceq v if uu is an initial segment of vv; this forms a tree-like structure rooted at the single-letter words. Free semigroups contain no idempotents, as the concatenation of any nonempty word ww with itself yields a word of twice the length, which cannot equal ww. Moreover, since free semigroups are cancellative, they embed into the free group on the same generating set AA. A concrete example is the free semigroup F({a,b})F(\{a, b\}), comprising all nonempty finite strings of aas and bbs under concatenation, such as abab, baabbaab, and bbbbbb. The growth of F(A)F(A) is exponential: the number of words of exact length nn is ∣A∣n|A|^n, reflecting the combinatorial explosion of possible sequences. For the singleton case A={a}A = \{a\}, F(A)F(A) is isomorphic to the positive integers under addition, via the map sending the word ana^n to nn. The group of fractions of a free semigroup coincides with the free group on AA.

Presentations

A presentation of a semigroup provides a description in terms of generators and relations. Formally, a presentation is a pair ⟨X∣R⟩\langle X \mid R \rangle, where XX is a set of generators and RR is a set of relations, each consisting of an equality u=vu = v with u,vu, v nonempty words over the alphabet XX. The semigroup defined by this presentation is the free semigroup on XX quotiented by the congruence generated by RR. The congruence of a presentation ⟨X∣R⟩\langle X \mid R \rangle is the smallest congruence σ\sigma on the free semigroup X+X^+ such that all pairs (u,v)(u, v) for relations u=v∈Ru = v \in R satisfy uσvu \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=vu = v, the number of occurrences of each generator from XX is the same in uu and vv; 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 xx along with a relation expressing xx 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 ⟨a∣an=an+1⟩\langle a \mid a^n = a^{n+1} \rangle for n≥1n \geq 1, which yields a finite null semigroup of order nn. The elements are a,a2,…,ana, a^2, \dots, a^n, with multiplication defined by aiaj=ai+ja^i a^j = a^{i+j} if i+j≤ni+j \leq n and aiaj=ana^i a^j = a^n otherwise, where ana^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 ee, satisfying e⋅s=s⋅e=se \cdot s = s \cdot e = s for all elements ss 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⋅b=a⋅ca \cdot b = a \cdot c implies b=cb = c, and similarly for right multiplication), admit a monoid of fractions under suitable conditions such as the Ore property: for all a,ba, b in the monoid, there exist c,dc, d such that a⋅c=b⋅da \cdot c = b \cdot d. This construction embeds the original monoid into a larger monoid where fractions s/ts/t (with tt cancellative) are defined via equivalence s/t=s′/t′s/t = s'/t' if s⋅t′=s′⋅ts \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 AA, the free monoid F1(A)F_1(A) consists of all finite words (including the empty word ε\varepsilon) over AA, under concatenation, with ε\varepsilon as identity. The free semigroup F(A)F(A) excludes ε\varepsilon, so F1(A)=F(A)∪{ε}F_1(A) = F(A) \cup \{\varepsilon\}. These satisfy the universal property that any map from AA to a monoid extends uniquely to a monoid homomorphism from F1(A)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×nn \times n matrices over a ring RR, comprising all such matrices under matrix multiplication, with the identity matrix as ee. 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 SS in which every element a∈Sa \in S possesses a unique element a−1∈Sa^{-1} \in S, called its inverse, satisfying the equations a=aa−1aa = a a^{-1} a and a−1=a−1aa−1a^{-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)E(S) of all idempotents (elements e∈Se \in S such that e=e2e = e^2) forms a commutative semilattice under the semigroup operation, meaning E(S)E(S) is a commutative idempotent semigroup where every pair of elements has a meet (greatest lower bound). For any a∈Sa \in S, the element aa−1a a^{-1} (or equivalently a−1aa^{-1} a) is the unique idempotent associated to aa, serving as its "source" or "domain" idempotent. Inverse semigroups admit a natural partial order defined by a≤ba \leq b if and only if a=abaa = 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 ae=aa e = a for idempotent ee implies aa is idempotent) as precisely those constructible from a P-semigroup—a structure consisting of a semilattice PP, a group GG, and an action of GG on PP satisfying specific covering and kernel conditions, yielding an inverse semigroup with commutative idempotents forming the semilattice PP. 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 InI_n on a finite set with nn 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 PnP_n, generated by nn partial isometries s1,…,sns_1, \dots, s_n satisfying sisi−1si=sis_i s_i^{-1} s_i = s_i, si−1sisi−1=si−1s_i^{-1} s_i s_i^{-1} = s_i^{-1}, si−1sj=δijes_i^{-1} s_j = \delta_{ij} e (where ee is the identity and δ\delta the Kronecker delta), modeling Cuntz-Krieger algebras in operator theory. The Wagner-Preston theorem asserts that every inverse semigroup SS embeds isomorphically into the symmetric inverse monoid IXI_X on some set XX, where the image consists of partial bijections representing elements of SS 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 HH-classes of an inverse semigroup coincide with groups.

Regular and Completely Regular Semigroups

A regular semigroup is a semigroup SS in which, for every element a∈Sa \in S, there exists an element x∈Sx \in S such that axa=aaxa = 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∈Sa \in S, there exists an x∈Sx \in S such that axa=aaxa = a, xax=xxax = x, and ax=xaax = xa, meaning the inverse commutes with aa. Equivalently, a completely regular semigroup is a union of its maximal subgroups, with every H\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 M0(G;I,Λ;P)\mathcal{M}^0(G; I, \Lambda; P) over a group GG with index sets I,ΛI, \Lambda and a Λ×I\Lambda \times I-matrix PP of nonzero entries from GG. This matrix representation captures the ideal structure and Green's relations, where D\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 YY of idempotents, each y∈Yy \in Y corresponds to a Rees matrix semigroup Sy=M(Iy,Gy,Λy;Py)S_y = \mathcal{M}(I_y, G_y, \Lambda_y; P_y) over a group GyG_y, with translational hulls and homomorphisms θyz:Sy→T(Sz)\theta_{y z}: S_y \to T(S_z) ensuring compatibility under the semilattice operation. Bands, which are idempotent regular semigroups (where a2=aa^2 = a for all aa), form a special case, consisting entirely of idempotents. Representative examples include the full transformation semigroup TXT_X on a set XX, which is regular since for any transformation f∈TXf \in T_X, there exists a cross-section gg such that fgf=ff g f = f. Rectangular bands provide another example: the semigroup on I×ΛI \times \Lambda with multiplication (i,λ)(j,μ)=(i,μ)(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 RR is regular if for every a∈Ra \in R, there exists x∈Rx \in R such that a=axaa = 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 C0C_0-semigroup, also known as a strongly continuous semigroup, is a family of bounded linear operators {T(t)}t≥0\{T(t)\}_{t \geq 0} on a Banach space XX satisfying T(0)=IT(0) = I, the identity operator, and the semigroup property T(s+t)=T(s)T(t)T(s + t) = T(s) T(t) for all s,t≥0s, t \geq 0, with strong continuity lim⁡t→0+T(t)x=x\lim_{t \to 0^+} T(t) x = x for all x∈Xx \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 AA of a C0C_0-semigroup {T(t)}\{T(t)\} is the closed, densely defined operator given by Ax=lim⁡t→0+T(t)x−xtA x = \lim_{t \to 0^+} \frac{T(t) x - x}{t} for xx in its domain, satisfying ddtT(t)x=AT(t)x=T(t)Ax\frac{d}{dt} T(t) x = A T(t) x = T(t) A x for suitable xx. The Hille-Yosida theorem characterizes such generators: AA generates a contraction C0C_0-semigroup if and only if it is densely defined, closed, and maximal accretive, meaning the resolvent set includes the right half-plane {λ∈C:ℜλ>0}\{ \lambda \in \mathbb{C} : \Re \lambda > 0 \} with ∥R(λ,A)∥≤1/ℜλ\| 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 ut=Δuu_t = \Delta u on Rn\mathbb{R}^n with initial data u(0)=f∈Lp(Rn)u(0) = f \in L^p(\mathbb{R}^n), the solution operator forms a C0C_0-semigroup generated by the Laplacian Δ\Delta, explicitly given by convolution with the Gaussian kernel: T(t)f(x)=1(4πt)n/2∫Rnf(y)e−∣x−y∣2/(4t) dy,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 LpL^p spaces. In contrast, the wave equation utt=Δuu_{tt} = \Delta u on a domain with Dirichlet boundaries can be reformulated as a first-order system Ut=AUU_t = A U where U=(u,ut)U = (u, u_t) and A=(0IΔ0)A = \begin{pmatrix} 0 & I \\ \Delta & 0 \end{pmatrix} on the energy space H01(Ω)×L2(Ω)H_0^1(\Omega) \times L^2(\Omega); here AA generates a unitary C0C_0-group (extending the semigroup to negative times), reflecting energy conservation. Semigroup theory applies to the abstract Cauchy problem u′(t)=Au(t)u'(t) = A u(t), u(0)=u0u(0) = u_0, yielding the mild solution u(t)=T(t)u0u(t) = T(t) u_0 when AA generates a C0C_0-semigroup, with well-posedness guaranteed by the Hille-Yosida conditions. For stability, contraction semigroups (∥T(t)∥≤1\|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)∥≤Meωt\|T(t)\| \leq M e^{\omega t} with ω<0\omega < 0), follow from spectral properties of AA, 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 LL over an alphabet Σ\Sigma, the syntactic congruence ∼L\sim_L on Σ+\Sigma^+ is defined by u∼Lvu \sim_L v if and only if, for all x,y∈Σ∗x, y \in \Sigma^*, xuy∈Lx u y \in L if and only if xvy∈Lx v y \in L. The syntactic semigroup SLS_L is the quotient Σ+/∼L\Sigma^+ / \sim_L, which is the smallest semigroup recognizing LL in the sense that there exists a surjective morphism from Σ+\Sigma^+ to SLS_L such that LL 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 LL is regular. The transitions of the minimal deterministic finite automaton (DFA) accepting LL generate a subsemigroup isomorphic to SLS_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)ωz(xyz)ω=(xyz)ω(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 Σ∗a1Σ∗⋯anΣ∗\Sigma^* a_1 \Sigma^* \cdots a_n \Sigma^* for ai∈Σ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 ss, there exists nn such that sn+1=sns^{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 QQ, forming a subsemigroup of the full transformation semigroup TQT_Q. For a DFA with nn states, this semigroup has at most nnn^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 GG equipped with an n-ary operation f:Gn→Gf: G^n \to G that satisfies a generalized associativity condition. Specifically, for all x1,…,x2n−1∈Gx_1, \dots, x_{2n-1} \in G and every i=1,…,ni = 1, \dots, n, the equality f(f(x1,…,xn),xn+1,…,x2n−1)=f(x1,…,xi−1,f(xi,…,xi+n−1),xi+n,…,x2n−1)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=2n=2 recovers the standard associative binary operation. A key property is the existence of a binary retract: fixing n−2n-2 elements appropriately yields a binary semigroup operation on GG. 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,…,ni = 1, \dots, n and fixed elements a1,…,a^i,…,an,b∈Ga_1, \dots, \hat{a}_i, \dots, a_n, b \in G, there exists a unique x∈Gx \in G such that f(a1,…,ai−1,x,ai+1,…,an)=bf(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×GG \times G. Formally, a partial semigroup is a set GG with a partial binary operation ⋅:G×G→G∪{∗}\cdot: G \times G \to G \cup \{*\} (where ∗* denotes undefined) such that whenever x⋅yx \cdot y and y⋅zy \cdot z are both defined, then both (x⋅y)⋅z(x \cdot y) \cdot z and x⋅(y⋅z)x \cdot (y \cdot z) are defined and equal. Totality conditions specify when the operation is total: if the domain is all of G×GG \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 GG uses a ternary operation [x,y,z][x, y, z] satisfying [x,y,[u,v,w]]=[[x,y,u],v,w]=[x,[y,u,v],w][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⋅z[x, e, z] = x \cdot z for some fixed ee. 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. 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)(ab)c = a(bc) for all elements a,b,ca, 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=bax = b and ya=bya = 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 AA and BB in a category C\mathcal{C}, the set hom⁡(A,B)\hom(A, B) forms a semigroup under morphism composition, which is associative by the category axioms, though it may lack an identity unless A=BA = 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⋅a=aa \cdot a = a and a⋅b=b⋅aa \cdot b = b \cdot a for all a,ba, b. Under this operation, interpreted as meet or join, the structure induces a partial order via a≤ba \leq b if a⋅b=aa \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.

References

  1. https://mathworld.wolfram.com/Semigroup.html
  2. https://faculty.etsu.edu/gardnerr/5410/notes/I-1.pdf
  3. https://web.stanford.edu/class/math51h/algebra.pdf
  4. https://math.chapman.edu/~jipsen/structures/doku.php?id=regular_semigroups
  5. https://math.jhu.edu/~mathclub/problems/problems2013/semigroups-solutions.pdf
  6. https://digitalcommons.wku.edu/context/theses/article/1257/viewcontent/NGUYEN_NGOC.pdf
  7. https://www.math.ucdavis.edu/~anne/WQ2022/mat280.pdf
  8. https://www.etd.ceu.edu/2014/fetahu_elona.pdf
  9. https://webpages.charlotte.edu/~ghetyei/courses/old/F21.3163/monoids_optional.pdf
  10. https://mathworld.wolfram.com/Magma.html
  11. https://mathworld.wolfram.com/Monoid.html
  12. https://mathworld.wolfram.com/Group.html
  13. https://personalpages.manchester.ac.uk/staff/Mark.Kambites/events/nbsan/nbsan7_vernitski.pdf
  14. https://www.macajournal.com/article_679854_5ac3e5597ff0061ee9bb3736fc030560.pdf
  15. https://planetmath.org/leftidentityandrightidentity
  16. https://planetmath.org/identityelementisunique
  17. https://planetmath.org/zeroelements
  18. https://carleton.ca/math/wp-content/uploads/Cheaney-Kyle-Honours-Project-An_Introduction_to_Inverse_Semigroups.pdf
  19. https://www-users.york.ac.uk/~varg1/SemigroupTheory.pdf
  20. https://www.mi.fu-berlin.de/math/groups/ag-logik/Lehre/UST-chapter01.pdf
  21. https://docs.gap-system.org/pkg/semigroups/doc/chap14.html
  22. https://core.ac.uk/download/pdf/29824637.pdf
  23. https://bookstore.ams.org/surv-7.1
  24. https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-23/issue-2/Congruences-on-regular-semigroups/pjm/1102991869.pdf
  25. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/41789B1749144CF88F5E9240D69ADEEC/S0017089500001610a.pdf/div-class-title-congruences-and-green-s-relations-on-regular-semigroups-div.pdf
  26. https://link.springer.com/article/10.1007/BF02572819
  27. https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-57/issue-1/The-lattice-of-congruences-on-an-inverse-semigroup/pjm/1102906180.pdf
  28. https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/17350/MichaelTorpeyPhDThesis.pdf
  29. https://www.irif.fr/~jep/Resumes/Varietes.html
  30. https://people.csail.mit.edu/meyer/remarks-on-algebraic-decomposition.pdf
  31. https://u.cs.biu.ac.il/~margolis/papers/My%20recent%20papers/Inverse%20semigroups%20and%20varieties%20of%20finite%20semigroups.pdf
  32. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/E0AEFFF01AEF26349964EB3751E05EBD/S1446788700021649a.pdf/regular_semigroups_fundamental_semigroups_and_groups.pdf
  33. https://arxiv.org/pdf/2204.03377
  34. https://planetmath.org/cayleystheoremforsemigroups
  35. https://hal.science/hal-03434221/document
  36. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/3FBACA8FAE572258B4E1F8F16FF184AE/S0004972700038028a.pdf/the-structure-of-elements-in-finite-full-transformation-semigroups.pdf
  37. https://arxiv.org/abs/1703.04941
  38. https://oeis.org/A001423
  39. https://www.cs.uwyo.edu/~larsko/papers/distler_semigroups_2012.pdf
  40. https://projecteuclid.org/journals/kodai-mathematical-journal/volume-6/issue-4/On-decompositions-of-a-commutative-semigroup/10.2996/kmj/1138843534.full
  41. https://arxiv.org/pdf/2204.10518
  42. https://math.colorado.edu/blast/2019/prenosil.pdf
  43. https://assets.cambridge.org/97805216/94704/excerpt/9780521694704_excerpt.pdf
  44. https://www.ias.ac.in/article/fulltext/reso/019/08/0740-0752
  45. https://bkms.kms.or.kr/journal/download_pdf.php?doi=10.4134/BKMS.2013.50.2.445
  46. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/90D60F0551D9225DD7EFBEA8D4CC1D6C/S0013091500005897a.pdf/on-semigroup-presentations.pdf
  47. https://www.researchgate.net/publication/226005343_Comparing_Semigroup_and_Monoid_Presentations_for_Finite_Monoids
  48. https://www.sciencedirect.com/science/article/pii/S0012365X07003044
  49. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/46FC33D59A7EA448D10D8341C26CBF27/S0008414X00055012a.pdf/div-class-title-some-remarks-on-semigroup-presentations-div.pdf
  50. https://hal.science/hal-00000852v2/document
  51. https://arxiv.org/pdf/2106.11674
  52. https://planetmath.org/freesemigroup
  53. https://www.worldscientific.com/worldscibooks/10.1142/14408
  54. https://kadm.kmath.ru/files/kssbook.pdf
  55. https://personalpages.manchester.ac.uk/staff/Mark.Kambites/events/nbsan/nbsan7_afara.pdf
  56. https://link.springer.com/book/10.1007/978-1-4612-5561-1
  57. https://projecteuclid.org/journals/journal-of-the-mathematical-society-of-japan/volume-1/issue-1/On-the-differentiability-and-the-representation-of-one-parameter-semi/10.2969/jmsj/00110015.full
  58. https://www.irif.fr/~jep/PDF/HandBook.pdf
  59. https://arxiv.org/pdf/1502.03951
  60. https://www.sciencedirect.com/science/article/pii/S0196885897905479
  61. https://www.cs.cmu.edu/~cdm/resources/20-statecomp.pdf
  62. https://link.springer.com/article/10.1007/BF01443322
  63. https://doi.org/10.1007/s00407-009-0044-3
  64. https://doi.org/10.1017/S0305004100017436
  65. https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/word-problem-for-onerelator-semigroups/025C6C8E837DDE6A0D43A4BFB753264F
  66. https://dl.acm.org/doi/10.1145/3636362.3636365
  67. https://arxiv.org/abs/1305.6004
  68. https://www.researchgate.net/publication/263613274_John_Rhodes_and_the_theory_of_finite_semigroups
  69. https://link.springer.com/chapter/10.1007/978-1-4612-1388-8_14
  70. https://ncatlab.org/nlab/show/semigroup
  71. https://www.math.md/files/qrs/v3-n1/v3-n1-%28pp73-88%29.pdf
  72. http://www.quasigroups.eu/contents/download/2001/8_3.pdf
  73. https://math.chapman.edu/~jipsen/structures/doku.php?id=partial_semigroups
  74. https://link.springer.com/article/10.1007/s00233-023-10374-x
  75. https://link.springer.com/article/10.1007/BF02572770
  76. https://www.ams.org/journals/tran/1970-152-02/S0002-9947-1970-0268316-5/S0002-9947-1970-0268316-5.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.