Identity and zero A
left identity of a semigroup S (or more generally,
magma) is an element e such that for all x in S, e\cdot x = x. Similarly, a
right identity is an element f such that for all x in S, x\cdot 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\notin S to S and defining e\cdot s = s\cdot e =s for all s\in S\cup\{e\}. The notation S^1 denotes a monoid obtained from S by adjoining an identity if necessary (S^1 = S for a monoid). 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^0, 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 A\cdot B, written commonly as AB, is the set \{ab\mid a\in A\text{ and }b\in 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. The center of a semigroup is actually a subsemigroup.
Homomorphisms and congruences A
semigroup homomorphism is a function that preserves semigroup structure. A function f:S\to 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 S^1. Conditions characterizing monoid homomorphisms are discussed further. Let f:S_0\to S_1 be a semigroup homomorphism. The image of f is also a semigroup. If S_0 is a monoid with an identity element e_0, then f(e_0) is the identity element in the image of f. If S_1 is also a monoid with an identity element e_1 and e_1 belongs to the image of f, then f(e_0)=e_1, 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\to T. Isomorphic semigroups have the same structure. A
semigroup congruence \sim is an
equivalence relation that is compatible with the semigroup operation. That is, a subset \sim\,\subseteq S\times S that is an equivalence relation and x\sim y and u\sim v implies xu\sim yv for every x, y, u, v in S. Like any equivalence relation, a semigroup congruence \sim induces
congruence classes : [a] = \{x\in S\mid x\sim a\} and the semigroup operation induces a binary operation \circ on the congruence classes: : [u]\circ [v] = [uv]. Because \sim is a congruence, the set of all congruence classes of \sim forms a semigroup with \circ, called the
quotient semigroup or
factor semigroup, and denoted S/\!\sim. The mapping x\mapsto [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. 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. Every ideal I of a semigroup induces a factor semigroup, the
Rees factor semigroup, via the congruence \rho defined by x\rho y if either x=y, or both x and y are in I.
Quotients and divisions The following notions 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, is a quotient of , using the morphism consisting of taking the remainder modulo 2 of an integer. A semigroup
T divides a semigroup
S, denoted 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 ==