Editing Semigroup (section)

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