View source for Semigroup

{{Short description|Algebraic structure consisting of a set with an associative binary operation}}
<!-- Commenting out the following image file that may be replaced by something more appropriate, as this image does not properly clarify what associative property (of string concatenation or anything else) is and creates confusion rather than explains anything:
[[File:Semigroup associative image.svg|thumb|right|upright=1.75|The associative property of string concatenation.]] -->{{Confused|quasigroups}}{{Dark mode invert|[[File:Magma_to_group2.svg|thumb|right|300px|Algebraic structures between [[Magma (algebra)|magmas]] and [[Group (mathematics)|groups]]: A ''semigroup'' is a [[magma (algebra)|magma]] with [[Associative property|associativity]]. A [[monoid]] is a ''semigroup'' with an [[identity element]].]]}}
In mathematics, a '''semigroup''' is an [[algebraic structure]] consisting of a [[Set (mathematics)|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]]): <math>x\cdot y</math>, or simply <math>xy</math>, denotes the result of applying the semigroup operation to the [[ordered pair]] <math>(x,y)</math>. Associativity is formally expressed as that <math>(x\cdot y)\cdot z=x\cdot (y\cdot z)</math> for all <math>x</math>, <math>y</math> and <math>z</math> in the semigroup.

Semigroups may be considered a special case of [[magma (algebra)|magmas]], where the operation is associative, or as a generalization of [[group (mathematics)|groups]], without requiring the existence of an identity element or inverses.{{efn|The closure axiom is implied by the definition of a binary operation on a set. Some authors thus omit it and specify three axioms for a group and only one axiom (associativity) for a semigroup.}} As in the case of groups or magmas, the semigroup operation need not be [[commutativity|commutative]], so <math>x\cdot y</math> is not necessarily equal to <math>y\cdot x</math>; 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 [[abelian group|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 [[string (computer science)|strings]] with [[concatenation]] as the binary operation, and the empty string as the identity element. Restricting to non-empty [[string (computer science)|strings]] gives an example of a semigroup that is not a monoid. Positive [[integer]]s with addition form a commutative semigroup that is not a monoid, whereas the non-negative [[integer]]s 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 [[quasigroup]]s, which are generalization of groups in a different direction; the operation in a quasigroup need not be associative but quasigroups [[Group (mathematics)#Division|preserve from groups]] the notion of [[Division (mathematics)|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 [[Transformation semigroup#Cayley representation|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]]<!-- {{sfn|ps=|Eilenberg|1973}} -->.  In [[probability theory]], semigroups are associated with [[Markov process]]es.{{sfn|ps=|Feller|1971}} In other areas of [[applied mathematics]], semigroups are fundamental models for [[linear time-invariant system]]s.  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 semigroup]]s, [[orthodox semigroup]]s, [[semigroup with involution|semigroups with involution]], [[inverse semigroup]]s and [[cancellative semigroup]]s. There are also interesting classes of semigroups that do not contain any groups except the [[trivial group]]; examples of the latter kind are [[band (mathematics)|bands]] and their commutative subclass – [[semilattice]]s, which are also [[:Category:Ordered algebraic structures|ordered algebraic structure]]s.

{{Algebraic structures |Group}}

== Definition ==

A semigroup is a [[set (mathematics)|set]] <math>S</math> together with a [[binary operation]] <math>\cdot</math> (that is, a [[function (mathematics)|function]] <math>\cdot: S\times S\to S</math>) that satisfies the [[associative property]]:
: for all <math>a,b,c\in S</math>, the equation <math>(a\cdot b)\cdot c = a\cdot (b\cdot c)</math> holds.

More succinctly, a semigroup is an associative [[magma (algebra)|magma]].

== Examples of semigroups ==
* [[Empty semigroup]]: the [[empty set]] forms a semigroup with the [[empty function]] as the binary operation.
* [[Semigroup with one element]]: there is essentially only one (specifically, only one [[up to]] [[isomorphism]]), the singleton <math>\{a\}</math> with operation <math>a \cdot a = a</math>.
* [[Semigroup with two elements]]: there are five that are essentially different.
* A [[null semigroup]] on any nonempty set with a chosen zero, or a [[null semigroup|left/right zero semigroup]] on any set.
* The "flip-flop" monoid: a [[semigroup with three elements]] representing the three operations on a switch – set, reset, and do nothing. This monoid plays a central role in [[Krohn–Rhodes theory|Krohn-Rhodes theory.]]
* The set of positive [[integer]]s with addition. (With 0 included, this becomes a [[monoid]].)
* The set of [[integer]]s with minimum or maximum. (With positive/negative infinity included, this becomes a monoid.)
* Square [[Nonnegative matrix|nonnegative matrices]] of a given size with matrix multiplication.
* Any [[ring ideal|ideal]] of a [[ring (algebra)|ring]] with the multiplication of the ring.
* The set of all finite [[string (computer science)|strings]] over a fixed alphabet <math>\Sigma</math> with [[concatenation]] of strings as the semigroup operation—called the [[free semigroup]] over <math>\Sigma</math>. With the empty string included, this semigroup becomes the [[free monoid]] over <math>\Sigma</math>.
* A [[probability distribution]] <math>F</math> together with all [[convolution power]]s of <math>F</math>, with convolution as the operation. This is called a convolution semigroup.
* [[Transformation semigroup]]s and [[transformation monoid|monoids]].
* The set of [[continuous function]]s  from a [[topological space]] to itself with composition of functions forms a monoid with the [[identity function]] acting as the identity. More generally, the [[Endomorphism|endomorphisms]] of any object of a [[Category (mathematics)|category]] form a monoid under composition.
* The product of faces of an [[arrangement of hyperplanes]].

== Basic concepts ==

=== Identity and zero ===
A '''[[left identity]]''' of a semigroup <math>S</math> (or more generally, [[magma (algebra)|magma]]) is an element <math>e</math> such that for all <math>x</math> in <math>S</math>, <math>e\cdot x = x</math>. Similarly, a '''[[right identity]]''' is an element <math>f</math> such that for all <math>x</math> in <math>S</math>, <math>x\cdot f = x</math>. 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 '''[[monoid]]s'''. 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 <math>S</math> without identity may be [[embedding|embedded]] in a monoid formed by adjoining an element <math>e\notin S</math> to <math>S</math> and defining <math>e\cdot s = s\cdot e =s</math> for all <math>s\in S\cup\{e\}</math>.{{sfn|ps=|Jacobson|2009|p=30|loc=ex. 5}}{{sfn|ps=|Lawson|1998|p=[{{Google books|plainurl=y|id=_F78nQEACAAJ|page=20|text=adjoining an identity}} 20]}} The notation <math>S^1</math> denotes a monoid obtained from <math>S</math> by adjoining an identity if necessary (<math>S^1 = S</math> for a monoid).{{sfn|ps=|Lawson|1998|p=[{{Google books|plainurl=y|id=_F78nQEACAAJ|page=20|text=adjoining an identity}} 20]}}

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 <math>S</math>, one can define <math>S^0</math>, a semigroup with 0 that embeds <math>S</math>.

=== Subsemigroups and ideals ===

The semigroup operation induces an operation on the collection of its subsets: given subsets <math>A</math> and <math>B</math> of a semigroup <math>S</math>, their product <math>A\cdot B</math>, written commonly as <math>AB</math>, is the set <math>\{ab\mid a\in A\text{ and }b\in B\}</math>. (This notion is defined identically as [[Product of group subsets|it is for groups]].) In terms of this operation, a subset <math>A</math> is called
* a '''subsemigroup''' if <math>AA</math> is a subset of <math>A</math>,
* a '''right ideal''' if <math>AS</math> is a subset of <math>A</math>, and
* a '''left ideal''' if <math>SA</math> is a subset of <math>A</math>.

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

If <math>S</math> is a semigroup, then the intersection of any collection of subsemigroups of <math>S</math> is also a subsemigroup of <math>S</math>.
So the subsemigroups of <math>S</math> 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 relation]]s that characterise the elements in terms of the [[principal ideal]]s 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 (algebra)|center]]''' of the semigroup.<ref name="KilpKilʹp2000">{{Cite book|first1=Mati |last1=Kilp |first2=U. |last2=Knauer |first3=Aleksandr V. |last3=Mikhalev |title=Monoids, Acts, and Categories: With Applications to Wreath Products and Graphs : a Handbook for Students and Researchers |url=https://books.google.com/books?id=4gPhmmW-EGcC&pg=PA25 |year=2000 |publisher=Walter de Gruyter |isbn=978-3-11-015248-7 |page=25 |zbl=0945.20036}}</ref> The center of a semigroup is actually a subsemigroup.<ref name="Li͡apin1968">{{Cite book|first=E. S. |last=Li͡apin|title=Semigroups|url=https://books.google.com/books?id=G8pWKPp4tKwC&pg=PA96|year=1968|publisher=American Mathematical Soc.|isbn=978-0-8218-8641-0|page=96}}</ref>

=== Homomorphisms and congruences ===

A '''semigroup [[homomorphism]]''' is a function that preserves semigroup structure.  A function <math>f:S\to T</math> between two semigroups is a homomorphism if the equation
: <math>f(ab)=f(a)f(b)</math>.
holds for all elements <math>a</math>, <math>b</math> in <math>S</math>, i.e. the result is the same when performing the semigroup operation after or before applying the map <math>f</math>.

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 <math>S</math> without identity into <math>S^1</math>. Conditions characterizing monoid homomorphisms are discussed further. Let <math>f:S_0\to S_1</math> be a semigroup homomorphism. The image of <math>f</math> is also a semigroup. If <math>S_0</math> is a monoid with an identity element <math>e_0</math>, then <math>f(e_0)</math> is the identity element in the image of <math>f</math>. If <math>S_1</math> is also a monoid with an identity element <math>e_1</math> and <math>e_1</math> belongs to the image of <math>f</math>, then <math>f(e_0)=e_1</math>, i.e. <math>f</math> is a monoid homomorphism. Particularly, if <math>f</math> is [[surjective]], then it is a monoid homomorphism.

Two semigroups <math>S</math> and <math>T</math> are said to be '''[[isomorphism|isomorphic]]''' if there exists a [[bijective]] semigroup homomorphism <math>f:S\to T</math>. Isomorphic semigroups have the same structure.

A '''semigroup congruence''' <math>\sim</math> is an [[equivalence relation]] that is compatible with the semigroup operation. That is, a subset <math>\sim\,\subseteq S\times S</math> that is an equivalence relation and <math>x\sim y</math> and <math>u\sim v</math> implies <math>xu\sim yv</math> for every <math>x, y, u, v</math> in <math>S</math>. Like any equivalence relation, a semigroup congruence <math>\sim</math> induces [[equivalence class|congruence class]]es
: <math>[a] = \{x\in S\mid x\sim a\}</math>
and the semigroup operation induces a binary operation <math>\circ</math> on the congruence classes:
: <math>[u]\circ [v] = [uv]</math>.

Because <math>\sim</math> is a congruence, the set of all congruence classes of <math>\sim</math> forms a semigroup with <math>\circ</math>, called the '''quotient semigroup''' or '''factor semigroup''', and denoted <math>S/\!\sim</math>. The mapping <math>x\mapsto [x]</math> is a semigroup homomorphism, called the '''quotient map''', '''canonical [[surjection]]''' or '''projection'''; if <math>S</math> is a monoid then quotient semigroup is a monoid with identity <math>[1]</math>. Conversely, the [[Kernel (set theory)|kernel]] of any semigroup homomorphism is a semigroup congruence. These results are nothing more than a particularization of the [[Isomorphism theorems#First Isomorphism Theorem 4|first isomorphism theorem in universal algebra]].  Congruence classes and factor monoids are the objects of study in [[string rewriting system]]s.

A '''nuclear congruence''' on <math>S</math> is one that is the kernel of an endomorphism of <math>S</math>.{{sfn|ps=|Lothaire|2011|p=463}}

A semigroup <math>S</math> satisfies the '''maximal condition on congruences''' if any family of congruences on <math>S</math>, 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 <math>S</math>.{{sfn|ps=|Lothaire|2011|p=465}}

Every ideal <math>I</math> of a semigroup induces a factor semigroup, the [[Rees factor semigroup]], via the congruence <math>\rho</math> defined by <math>x\rho y</math> if either <math>x=y</math>, or both <math>x</math> and <math>y</math> are in <math>I</math>.

=== Quotients and divisions ===
The following notions<ref>{{cite book|last1=Pin|first1=Jean-Éric|title=Mathematical Foundations of Automata Theory|date=November 30, 2016|page=19|url=http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf}}</ref> 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, {{nowrap|('''Z'''/2'''Z''', +)}} is a quotient of {{nowrap|('''Z'''/4'''Z''', +)}}, using the morphism consisting of taking the remainder modulo 2 of an integer.

A semigroup ''T'' divides a semigroup ''S'', denoted {{nowrap|''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 ==
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 {{math|{{mset| ''x''<sup>''n''</sup> | ''n'' ∈ '''Z'''<sup>+</sup> }}}}. 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 semigroup|monogenic]] (or [[Cyclic semigroup|cyclic]]). If a monogenic semigroup is infinite then it is isomorphic to the semigroup of positive [[integer]]s 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 (ring theory)|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 {{math|{{mset|''a'', ''b''}}}}, eight form semigroups{{efn|Namely: the trivial semigroup in which (for all ''x'' and ''y'') {{math|1=''xy'' = ''a''}} and its counterpart in which {{math|1=''xy'' = ''b''}}, the semigroups based on multiplication modulo 2 (choosing {{math|''a''}} or {{math|''b''}} as the identity element 1), the groups equivalent to addition modulo 2 (choosing {{math|''a''}} or {{math|''b''}} to be the identity element 0), and the semigroups in which the elements are either both left identities or both right identities.}} 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 ==
{{Main|Special classes of semigroups}}
* A [[monoid]] is a semigroup with an [[identity element]].
* A [[group (mathematics)|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]]:{{sfn|ps=|Clifford|Preston|2010|p=3}} {{nowrap|1=''a'' · ''b'' = ''a'' · ''c''}} implies {{nowrap|1=''b'' = ''c''}} and similarly for {{nowrap|1=''b'' · ''a'' = ''c'' · ''a''}}. Every group is a cancellative semigroup, and every finite cancellative semigroup is a group.
* A [[band (algebra)|band]] is a semigroup whose operation is [[idempotent]].
* A [[semilattice]] is a semigroup whose operation is idempotent and [[commutativity|commutative]].
* [[0-simple]] semigroups.
* [[Transformation semigroup]]s: any finite semigroup ''S'' can be represented by transformations of a (state-) set ''Q'' of at most {{nowrap|{{abs|''S''}} + 1}} states. Each element ''x'' of ''S'' then maps ''Q'' into itself {{nowrap|''x'' : ''Q'' → ''Q''}} and sequence ''xy'' is defined by {{nowrap|1=''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 {{nowrap|1=''pq'' = 1}}.
* [[C0-semigroup|C<sub>0</sub>-semigroups]].
* [[Regular semigroup]]s. Every element ''x'' has at least one inverse ''y'' that satisfies {{nowrap|1=''xyx'' = ''x''}} and {{nowrap|1=''yxy'' = ''y''}}; the elements ''x'' and ''y'' are sometimes called "mutually inverse".
* [[Inverse semigroup]]s 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 Z<sup>d</sup>.  These semigroups have applications to [[commutative algebra]].

== Structure theorem for commutative semigroups ==

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

Given a homomorphism {{math|''f'' : ''S'' → ''L''}} from an arbitrary semigroup to a semilattice, each inverse image {{math|1=''S''<sub>''a''</sub> = {{itco|''f''}}<sup>−1</sup>{{mset|''a''}}}} is a (possibly empty) semigroup.  Moreover, ''S'' becomes '''graded''' by ''L'', in the sense that {{math|''S''<sub>''a''</sub>''S''<sub>''b''</sub> ⊆ ''S''<sub>''a''∧''b''</sub>}}.

If ''f'' is onto, the semilattice ''L'' is isomorphic to the [[quotient]] of ''S'' by the equivalence relation ~ such that {{math|''x'' ~ ''y''}} if and only if {{math|1=''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 ''S''<sub>''a''</sub> are all [[Special classes of semigroups|Archimedean semigroups]].  An Archimedean semigroup is one where given any pair of elements ''x'', ''y '', there exists an element ''z'' and {{math|''n'' > 0}} such that {{math|1=''x''<sup>''n''</sup> = ''yz''}}.

The Archimedean property follows immediately from the ordering in the semilattice ''L'', since with this ordering we have {{math|''f''(''x'') ≤ ''f''(''y'')}} if and only if {{math|1=''x''<sup>''n''</sup> = ''yz''}} for some ''z'' and {{math|''n'' > 0}}.

== Group of fractions ==
The '''group of fractions''' or '''group completion''' of a semigroup ''S'' is the [[group (mathematics)|group]] {{nowrap|1=''G'' = ''G''(''S'')}} generated by the elements of ''S'' as generators and all equations {{nowrap|1=''xy'' = ''z''}} that hold true in ''S'' as [[presentation of a group|relations]].<ref>{{Cite book|first=B. |last=Farb |title=Problems on mapping class groups and related topics |publisher=Amer. Math. Soc. |year=2006 |isbn=978-0-8218-3838-9 |page=357 }}</ref>  There is an obvious semigroup homomorphism {{nowrap|''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:<ref>{{Cite book|first1=M. |last1=Auslander |first2=D. A. |last2=Buchsbaum |title=Groups, rings, modules |publisher=Harper & Row |year=1974 |isbn=978-0-06-040387-4 |page=50 }}</ref>  given any group ''H'' and any semigroup homomorphism {{nowrap|''k'' : ''S'' → ''H''}}, there exists a unique [[group homomorphism]] {{nowrap|''f'' : ''G'' → ''H''}} with {{nowrap|1=''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 {{nowrap|1=''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,{{sfn|ps=|Clifford|Preston|1961|p=34}} 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.{{sfn|Cain|2012|loc=Theorem 6.1}}  The problem for non-commutative semigroups can be traced to the first substantial paper on semigroups.{{sfn|ps=|Suschkewitsch|1928}}<ref>{{Cite book|url=http://www.gap-system.org/~history/Extras/Preston_semigroups.html|title=Personal reminiscences of the early history of semigroups|first=G. B.|last=Preston|year=1990|access-date=2009-05-12|author-link=Gordon Preston|url-status=dead|archive-url=https://web.archive.org/web/20090109045100/http://www.gap-system.org/~history/Extras/Preston_semigroups.html|archive-date=2009-01-09}}</ref>  [[Anatoly Maltsev]] gave necessary and sufficient conditions for embeddability in 1937.<ref>{{Cite journal| doi=10.1007/BF01571659 | last=Maltsev | first=A. | author-link=Anatoly Maltsev | title=On the immersion of an algebraic ring into a field | journal=Math. Annalen | volume=113 | year=1937 | pages=686–691 | s2cid=122295935 }}</ref>

== Semigroup methods in partial differential equations ==
{{further|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 (mathematics)|interval]] {{nowrap|(0, 1) ⊂ '''R'''}} and times {{nowrap|''t'' ≥ 0}}:
: <math>\begin{cases} \partial_{t} u(t, x) = \partial_{x}^{2} u(t, x), & x \in (0, 1), t > 0; \\ u(t, x) = 0, & x \in \{ 0, 1 \}, t > 0; \\ u(t, x) = u_{0} (x), & x \in (0, 1), t = 0. \end{cases}</math>

Let {{nowrap|1=''X'' = ''L''<sup>2</sup>((0, 1) '''R''')}} be the [[Lp space|''L''<sup>''p''</sup> space]] of square-integrable real-valued functions with domain the interval {{nowrap|(0, 1)}} and let ''A'' be the second-derivative operator with [[domain of a function|domain]]
: <math>D(A) = \big\{ u \in H^{2} ((0, 1); \mathbf{R}) \big| u(0) = u(1) = 0 \big\},</math>
where <math>H^2</math> 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'':
: <math>\begin{cases} \dot{u}(t) = A u (t); \\ u(0) = u_{0}. \end{cases}</math>

On an heuristic level, the solution to this problem "ought" to be
<math display="block">u(t)=\exp(tA)u_0.</math>
However, for a rigorous treatment, a meaning must be given to the [[exponentiation|exponential]] of ''tA''.  As a function of ''t'', exp(''tA'') is a semigroup of operators from ''X'' to itself, taking the initial state ''u''<sub>0</sub> at time {{nowrap|1=''t'' = 0}} to the state {{nowrap|1=''u''(''t'') = exp(''tA'')''u''<sub>0</sub>}} at time ''t''.  The operator ''A'' is said to be the [[C0 semigroup#Infinitesimal generator|infinitesimal generator]] of the semigroup.

== History ==
The study of semigroups trailed behind that of other algebraic structures with more complex axioms such as [[group (mathematics)|groups]] or [[ring (algebra)|rings]]. A number of sources<ref>{{cite web| url = http://jeff560.tripod.com/s.html| title = Earliest Known Uses of Some of the Words of Mathematics}}</ref><ref name=Hollings>{{cite web| url = http://uk.geocities.com/cdhollings/suschkewitsch3.pdf| archive-url = https://www.webcitation.org/5kmeaTTMB?url=http://uk.geocities.com/cdhollings/suschkewitsch3.pdf| url-status = dead| archive-date = 2009-10-25| title = An account of Suschkewitsch's paper by Christopher Hollings}}</ref> 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 semigroup]]s and showed that the minimal ideal (or [[Green's relations]] J-class) of a finite semigroup is simple.<ref name=Hollings/> From that point on, the foundations of semigroup theory were further laid by [[David Rees (mathematician)|David Rees]], [[James Alexander Green]], {{ill|Evgenii Sergeevich Lyapin|fr|Evgueni Liapine}}, [[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 relation]]s on a set ''A'' and [[composition of relations]] for the semigroup product.<ref>B. M. Schein (1963) "Representations of semigroups by means of binary relations" (Russian), [[Matematicheskii Sbornik]] 60: 292–303 {{mr|id=0153760}}</ref>  At an algebraic conference in 1972 Schein surveyed the literature on B<sub>''A''</sub>, the semigroup of relations on ''A''.<ref>B. M. Schein (1972) ''Miniconference on semigroup Theory'', {{mr|id=0401970}}</ref> In 1997 Schein and [[Ralph McKenzie]] proved that every semigroup is isomorphic to a transitive semigroup of binary relations.<ref>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|id=1370647}}</ref>

In recent years researchers in the field have become more specialized with dedicated monographs appearing on important classes of semigroups, like [[inverse semigroup]]s, as well as monographs focusing on applications in [[algebraic automata theory]], particularly for finite automata, and also in [[functional analysis]].

== Generalizations ==
{{Group-like structures}}
If the associativity axiom of a semigroup is dropped, the result is a [[magma (mathematics)|magma]], which is nothing more than a set ''M'' equipped with a [[binary operation]] that is closed {{nowrap|''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 [[arity|''n''-ary operation]] instead of a binary operation.<ref>{{Cite journal|last=Dudek |first=W.A. |title=On some old problems in ''n''-ary groups |url=http://www.quasigroups.eu/contents/contents8.php?m=trzeci |archive-url=https://web.archive.org/web/20090714003319/http://www.quasigroups.eu/contents/contents8.php?m=trzeci |url-status=dead |archive-date=2009-07-14 |journal=Quasigroups and Related Systems |year=2001 |volume=8 |pages=15–36 }}</ref> The associative law is generalized as follows: ternary associativity is {{nowrap|1=(''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 {{nowrap|''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|''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.{{efn|See references in Udo Hebisch and Hanns Joachim  Weinert, ''Semirings  and  Semifields'', in particular, Section 10, ''Semirings  with  infinite sums'', in M.  Hazewinkel, Handbook of Algebra, Vol. 1, Elsevier, 1996. Notice that in this context the authors use the term ''semimodule'' in place of ''semigroup''.}}

== See also ==
* [[Absorbing element]]
* [[Biordered set]]
* [[Compact semigroup]]
* [[Empty semigroup]]
* [[Generalized inverse]]
* [[Identity element]]
* [[Light's associativity test]]
* [[Principal factor]]
* [[Quantum dynamical semigroup]]
* [[Semigroup action]]
* [[Semigroup ring]]
* [[Weak inverse]]

== Notes ==
{{notelist}}

== Citations ==
{{reflist}}

== References ==
{{refbegin}}
=== General references ===
* {{Cite book|last= Howie|first= John M.|author-link=John Mackintosh Howie|title=Fundamentals of Semigroup Theory|year=1995|publisher=Clarendon Press|isbn=978-0-19-851194-6|zbl=0835.20077}}
* {{Cite book|first1=Alfred Hoblitzelle |last1=Clifford |first2=Gordon Bamford |last2=Preston |title=The Algebraic Theory of Semigroups |url=https://books.google.com/books?id=4vXG2rjCUmUC |year=1961 |publisher=American Mathematical Society |isbn=978-0-8218-0271-7 |volume=1 |author-link1= Alfred H. Clifford |author-link2=Gordon Preston |zbl=0111.03403}}
* {{Cite book|last1=Clifford|first1=Alfred Hoblitzelle|url=https://books.google.com/books?id=756KAwAAQBAJ|title=The algebraic theory of semigroups|last2=Preston|first2=Gordon Bamford|publisher=[[American Mathematical Society]]|year=2010|isbn=978-0-8218-0272-4|volume=2|author-link=Alfred H. Clifford|author-link2=Gordon Preston|orig-year=1967}}
* {{Cite book|first=Pierre Antoine|last=Grillet|title=Semigroups: An Introduction to the Structure Theory|url=https://books.google.com/books?id=yM544W1N2UUC|year=1995|publisher=Marcel Dekker|isbn=978-0-8247-9662-4|zbl=0830.20079}}
* {{Cite book|first=Pierre Antoine|last=Grillet|title=Commutative Semigroups|url=https://books.google.com/books?id=7QOOxYbCpggC|year=2001|publisher=Springer Verlag|isbn=978-0-7923-7067-3|zbl=1040.20048}}
* {{Cite journal|last=Hollings|first=Christopher|date=2009|title=The Early Development of the Algebraic Theory of Semigroups|journal=[[Archive for History of Exact Sciences]]|volume=63|issue=5 |pages=497–536|doi=10.1007/s00407-009-0044-3|s2cid=123422715 }}
* {{Cite book|first=Christopher |last=Hollings|title=Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups|year=2014|publisher=American Mathematical Society|isbn=978-1-4704-1493-1|zbl=1317.20001}}
* {{Cite book|first=Mario |last=Petrich|title=Introduction to Semigroups|year=1973|publisher=Charles E. Merrill|isbn=978-0-675-09062-9|zbl=0321.20037}}
* {{Cite book|first=Alan J. |last=Cain |title=Nine Chapters on the Semigroup Art |url=https://archive.org/details/cain_semigroups_a4_screen |year=2012 |location=Lisbon |publisher=Ebook}}

=== Specific references ===
<!-- there's not enough here about connections with automata to use these as references.
* {{cite book|last=Eilenberg|first=Samuel|authorlink=Samuel Eilenberg|title=Automata, Languages, and Machines |volume=A |publisher=[[Academic Press]]|year= 1973|isbn=0-12-234001-9}}
* {{cite book|last=Eilenberg|first=Samuel|author-link=Samuel Eilenberg|title=Automata, Languages, and Machines |volume=B|publisher=Academic Press|year= 1976|isbn=0-12-234002-7}}
-->
* {{cite book| last1=Feller | first1=William | author1-link=William Feller | title=An introduction to probability theory and its applications |volume=II | publisher=Wiley |edition=2nd | mr=0270403  | year=1971}}
* {{cite book| last1=Hille | first1=Einar | author-link1=Einar Hille | last2=Phillips | first2=Ralph S. | author-link2=Ralph Phillips (mathematician) | title=Functional analysis and semi-groups | publisher=[[American Mathematical Society]] | mr=0423094  | year=1974 |isbn=978-0821874646 |url=https://books.google.com/books?id=gf2VAwAAQBAJ}}
* {{cite journal| last1=Suschkewitsch | first1=Anton | author-link=Anton Sushkevich |title=Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit | doi=10.1007/BF01459084 | mr=1512437  | year=1928 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=99 | issue=1 | pages=30–50| hdl=10338.dmlcz/100078 | s2cid=121081075 | hdl-access=free }}
* {{cite book|first=Shmuel |last=Kantorovitz |title=Topics in Operator Semigroups |url=https://books.google.com/books?id=bQdLAAAAQBAJ&pg=PP5 |year=2009 |publisher=Springer |isbn=978-0-8176-4932-6 |zbl=1187.47003}}
* {{Cite book| last=Jacobson| first=Nathan| author-link=Nathan Jacobson| year=2009| title=Basic algebra| edition=2nd| volume = 1 | publisher=Dover| isbn = 978-0-486-47189-1}}
* {{cite book|last1=Lawson|first1=Mark V.|title=Inverse semigroups: the theory of partial symmetries|year=1998|publisher=World Scientific|isbn=978-981-02-3316-7|zbl=1079.20505}}
* {{cite book| last=Lothaire | first=M. | author-link=M. Lothaire | title=Algebraic combinatorics on words | orig-year=2002 | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
{{refend}}

[[Category:Semigroup theory]]
[[Category:Algebraic structures]]