Editing Semigroup (section)

== Basic concepts ==

=== Identity and zero ===
A '''[[left identity]]''' of a semigroup ''S'' (or more generally, [[magma (algebra)|magma]]) is an element ''e'' such that for all ''x'' in ''S'', {{nowrap|1=''e'' ⋅ ''x'' = ''x''}}.  Similarly, a '''[[right identity]]''' is an element ''f'' such that for all ''x'' in ''S'', {{nowrap|1=''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 '''[[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 ''S'' without identity may be [[embedding|embedded]] in a monoid formed by adjoining an element {{nowrap|''e'' ∉ ''S''}} to ''S'' and defining {{nowrap|1=''e'' ⋅ ''s'' = ''s'' ⋅ ''e'' = ''s''}} for all {{nowrap|''s'' ∈ ''S'' ∪ {{mset|''e''}}}}.{{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 ''S''<sup>1</sup> denotes a monoid obtained from ''S'' by adjoining an identity ''if necessary'' ({{nowrap|1=''S''<sup>1</sup> = ''S''}} 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 ''S'', one can define ''S''<sup>0</sup>, a semigroup with 0 that embeds ''S''.

=== Subsemigroups and ideals ===

The semigroup operation induces an operation on the collection of its subsets: given subsets ''A'' and ''B'' of a semigroup ''S'', their product {{math|''A'' · ''B''}}, written commonly as ''AB'', is the set {{math|{{mset| ''ab'' | ''a'' &isin; ''A'' and ''b'' &isin; ''B'' }}.}} (This notion is defined identically as [[Product of group subsets|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 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'' → ''T''}} between two semigroups is a homomorphism if the equation
: {{math|1=''f''(''ab'') = ''f''(''a'')''f''(''b'')}}.
holds for all elements ''a'', ''b'' in ''S'', i.e. the result is the same when performing the semigroup operation after or before applying the map ''f''.

A semigroup homomorphism between monoids preserves identity if it is a [[monoid homomorphism]]. But there are semigroup homomorphisms that are not monoid homomorphisms, e.g. the canonical embedding of a semigroup ''S'' without identity into ''S''<sup>1</sup>. Conditions characterizing monoid homomorphisms are discussed further. Let {{math|''f'' : ''S''<sub>0</sub> → ''S''<sub>1</sub>}} be a semigroup homomorphism. The image of ''f'' is also a semigroup. If ''S''<sub>0</sub> is a monoid with an identity element ''e''<sub>0</sub>, then ''f''(''e''<sub>0</sub>) is the identity element in the image of ''f''. If ''S''<sub>1</sub> is also a monoid with an identity element ''e''<sub>1</sub> and ''e''<sub>1</sub> belongs to the image of ''f'', then {{math|1=''f''(''e''<sub>0</sub>) = ''e''<sub>1</sub>}}, 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 '''[[isomorphism|isomorphic]]''' if there exists a [[bijective]] semigroup homomorphism {{math|''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 {{math|~ ⊆ ''S'' × ''S''}} that is an equivalence relation and {{math|''x'' ~ ''y''}} and {{math|''u'' ~ ''v''}} implies {{math|''xu'' ~ ''yv''}} for every ''x'', ''y'', ''u'', ''v'' in ''S''. Like any equivalence relation, a semigroup congruence ~ induces [[equivalence class|congruence class]]es
: [''a'']<sub>~</sub> = {{mset|''x'' ∈ ''S'' | ''x'' ~ ''a''}}
and the semigroup operation induces a binary operation ∘ on the congruence classes:
: [''u'']<sub>~</sub> ∘ [''v'']<sub>~</sub> = [''uv'']<sub>~</sub>

Because ~ is a congruence, the set of all congruence classes of ~ forms a semigroup with ∘, called the '''quotient semigroup''' or '''factor semigroup''', and denoted {{math|''S'' / ~}}. The mapping {{math|''x'' ↦ [''x'']<sub>~</sub>}} 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]<sub>~</sub>. 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 ''S'' is one that is the kernel of an endomorphism of ''S''.{{sfn|ps=|Lothaire|2011|p=463}}

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''.{{sfn|ps=|Lothaire|2011|p=465}}

Every ideal ''I'' of a semigroup induces a factor semigroup, the [[Rees factor semigroup]], via the congruence ρ defined by {{math|''x'' ρ ''y''}} if either {{math|1=''x'' = ''y''}}, or both ''x'' and ''y'' are in ''I''.

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