Homomorphism and Quotient Semigroup

The concept of homomorphism helps to understand the structural similarity between two given algebraic structures.

Let (S , *) and (T , D ) be any two semigroups. A mapping g : S ® T such that for any two elements a, b S,
g (a * b) = g (a) D g (b) is called semigroup homomorphism.

Remark:

Homomorphism essentially preserves the behavior of the operations on the mapped elements.


A semigroup homomorphism is called a semigroup monomorphism, epimorphism or isomorphism depending on
whether the mapping is "one - one", "onto", or "one - one and onto " respectively. A semigroup homomorphism
onto itself is called endomorphism.

Two semigroups (S , *) and (T , D ) are said to be isomorphic if there exists a semigroup isomorphism mapping from
S onto T.

Example 1:

Consider the semigroup (Z , ·) and (N, ·). Define f : Z ® N by f(x) = |x|.
Then, for all, x, y Z , f(x , y) = |x · y| = |x| · |y| = f(x). f(y).Thus f is homomorphism.
f is also onto, since for every n Î N, there exists –n, n Î Z such that f(n) = |n| = n and f(-n) = |-n| = n.
But, f is not one-one for, f(3) = f(-3) = 3, but 3 ¹ -3.

Example 2:

Define g : (Z , ·) ®(N₀ , ·) by g(x) = 0. Then g is homomorphism.

For, g(x · y) = g(xy) = 0 = 0 · 0 = g(x) · g(y), for all x , y Z.

Example 3:

Let (N₀ , +) be the semigroup of natural numbers and (S , *) be the semigroup on S ={e, 0, 1} with the operation *
given by the following table.



A mapping g : N₀ ® S given by g(0) = 1 and g( j ) = 0 for j ¹ 0, is homomorphism,

for, .

Therefore from the table of (S , * ) , we have g(a + b) = g(a) * g(b).

Thus, g is a semigroup homomorphism. But g does not map the identity element 0 (zero) of the semigroup (N , +) onto the
identity element e of (S , *).


From the Example 3 of semigroup homomorphism, one can observe that semigroup homomorphism not necessarily always
maps an identity element onto identity element. Thus, we have the following definition for the monoid homomorphism.

Let, (M , * , e_M) and (T , D , e_T) be any two monoids. A mapping g : M ® T such that for any two elements, a, b Î M ,
g(a * b) = g(a) D g(b) and g(e_M ) = e_T is called a monoid homomorphism.

Example 1 of semigroup homomorphism is also monoid homomorphism, since it maps the identity element 1 of (Z , ·) onto
the identify element 1 of (N , ·).

Theorem 2.2.1 :

Let (S , *) be a semigroup. Then H, the set of all endomorphism on S is a semigroup with respect to the operation composition
of mapping.

Proof :

Let H be the set of all endomorphism on a semigroup (S , *).
Let f, g Î H and let x, y Î S.
Then, (f g) (x * y) = f (g(x * y))

= f(g(x) * g(y))

= f(g(x)) * f(g(y))

= (f g)(x) * (f g)(y).
Thus, f g Î H.
Hence (H , ) is a semigroup, since the composition of mapping '' is associative.

Theorem 2.2.2 :

Let (S , *) be a given semigroup. There exits a homomorphism g : S ® S^S, where (S^S, ) is a semigroup of mappings from S
into S under the operation of composition of mappings.

Proof :

Let (S , *) be a given semigroup. For each a Î S, define g : S ® S^S by g(a) = f_a , where f_a(x) = a * x, for all x Î S.
Then, f_{a * b} (x) = (a * b) * x
= a * ( b * x)
= f_a ( b * x)
= f_a(f_b(x))
= f_a f_b (x), for all x Î S.
Thus, f_{a * b} = f_a f_b .
Now, g(a * b) = f_a*b = f_a f_b = g(a) g(b).
Hence, g is a semigroup homomorphism from S into S^S.

Remark 1:

Let g(S) denote the image set of S under the mapping g. Therefore by the Theorem 2.2.2, g (S) Í S^S. That is, S can be
identified as a substructure of S^S . Therefore every semigroup can be visualized as a substructure of S^S.

Theorem 2.2.3:

Let (M , * , e) be a monoid. Then there exists a subset T Í M ^M such that (M , * , e) is isomorphic to the monoid T.

Proof:

For any element a M , define g (a) = f _a , where f _a (x) = a * x, for all x Î M.
Then f_a Î M^M .
Let T = {f_a Î M^M / f_a=a * x , for all a Î M and for all x Î M }.
Then by the Theorem 2.2.1, g is a homomorphism from M into T.
Also, for each f_a Î T, there exist a Î M such that g(a) = f_a.
Thus, g is onto.

Further, if a ¹ b, then g(a) ¹ g(b). For, suppose g(a) = g(b), then a * x = b * x, for all x Î M, in particular for x Î e also.
Therefore, a * e = b * e, that is, a = b, a contradiction.
Thus, g (a) ¹ g (b).
Hence, g is one - one.
So, g is isomorphism from M to T.
Hence, M T.

Theorem 2.2.4:

Let X be a set containing n elements, let X* denote free semigroup generated by X, and let (S , Å ) be any other semigroup
generated by any n generators. Then there exists a homomorphism g : X^* ® S.

Proof:

Let Y be the set of n generators of S, consisting of y₁,y₂, … ,y_n and let x₁, x₂, … ,x_n be the n elements of X.

Define g(x_i) = y_i, for i = 1,2, … ,n.
Then, for any string a = x₁, x₂ … x_n of X*, we define g(a ) = g(x₁) Å g(x₂) Å … Å g(x_m) .
Then, for any b = … , we have
g (a b ) = g (x₁x₂ … x_m … )
= g(x₁) Å g(x₂) Å … Å g(x_m) Å g() Å g() Å … Å g()
= g(a ) Å g(b ) .
Thus, g is a homomorphism.
Hence the theorem.


Let (X , ) be an algebraic system in which is a binary operation on X. An equivalence relation E on X is said
to have the substitution property with respect to the operation for any x₁ , x₂ Î X.
(x₁ E ) and (x₂ E ) then (x₁ x₂ ) E ( ), where , Î X.
That is, if x₁ is related to and x₂ is related to , then the result of x₁ and x₂ by the binary operation , i.e., x₁ x₂ ,
is related to , the result of the binary operation on the related elements and. More precisely, x₁ is related
to and x₂ is related to then x₁ x₂ can be equivalently substituted for .

Let (X , ) be an algebraic system and E be an equivalence relation on X. The relation E is called a congruence
relation on (X , ) if E satisfies the substitution property with respect to the operation ‘’.

Theorem 2.2.5:

Let (S , *) and (T , D ) be two semigroups and g be a semigroup homomorphism from (S , *) to (T , D ). Corresponding to
the homomorphism g, there exists a congruence relation R on (S , *) defined by xRy, if g(x) = g(y) for x, y Î S.

Proof:

The relation R defined above is an equivalence relation:

Since g(x) = g(x), for all x Î S, xRx, for all x Î S.
Therefore, R is reflexive.
Also, if g(x) = g(y), then g(y) = g(x).
That is, if xRy then yRx .
Therefore, R is symmetry.
Further, if g(x) = g(y) and g(y) = g(z), then g(x) = g(y) = g(z), that is, g(x) = g(z) .
That is, if xRy and yRz then xRz.
Therefore, R is transitive.
Thus, R is an equivalence relation .
Let x₁, x₂ , and Î S such that xR and x₂R.
Then g(x₁ * x₂) = g(x₁) D g(x₂) (since g is a homomorphism.)
= g() g() (since x₁R and x₂R, so g(x₁) = g() and g(x₂) = g()]
= g( * ) (since g is a homomorphism.).
Therefore, by definition of R, x₁ * x₂ R * .
Thus, R is congruence relation on (S , *) .

Theorem 2.2.6:

Let (S , *) be a semigroup and R be a congruence relation on (S , *) on the quotient set
S/R = {[a] / a Î S}, define [a] Å [b] = [a * b], for all [a], [b] Î S/R . Then (S/R , Å ) is a semigroup. Further, there exists a
homomorphism from (S , *) onto (S/R , Å ) called natural homomorphism.

Proof:

Let (S, *) be given semigroup and let [a] denote an equivalence class of a corresponding to the congruence relation R. By the
Theorem 2.2.5 such congruence relation exists.

Claim 1 : The operation Å is well – defined.

For, if [a] = [a'] and [a] = [b'], then aRa' and bRb' .
Since R is congruence relation, we have, a * b R a' * b' .
Thus, [a * b] = [a' * b'] .

Consequently, [a] Å [b] = [a * b] = [a' * b'] = [a'] Å [b'].
Hence the Claim 1.

Claim 2 : (S/R ,Å ) is a semigroup.

For all [a], [b], [c] Î S/R, we have
[a] Å ([b] Å [c] ) = [a] Å [ b * c]
= [a * ( b * c)]
= [ (a * b) * c ]
= [ a * b] Å [c]
= ( [a] Å [b] ) Å [c].
That is, Å is associative.
Hence (S/R , Å ) is a semigroup.
Hence the Claim 2.

Claim 3 : There exists a natural homomorphism.

Define a mapping g : S ® S/R by g(a) = [a] ,for every a Î S .
Then, g(a* b) = [a * b] = [a] Å [b] = g(a) Å g(b) ,for all a , b Î S.
Thus, g is a homomorphism.

Further, for each [a] Î S/R there exist a Î S such that g(a) = [a].
Thus, g is a homomorphism from (S , *) onto (S/R , Å ) .
Hence the Claim 3.

Hence the theorem.