Tuesday, August 12, 2008

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.


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 , ·) ®(N0 , ·) 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 (N0 , +) 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 : N0 ® 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 , * , eM) and (T , D , eT) 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(eM ) = eT 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 ® SS, where (SS, ) 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 ® SS by g(a) = fa , where fa(x) = a * x, for all x Î S.
Then, fa * b (x) = (a * b) * x
= a * ( b * x)
= fa ( b * x)
= fa(fb(x))
= fa fb (x), for all x Î S.
Thus, fa * b = fa fb .
Now, g(a * b) = fa*b = fa fb = g(a) g(b).
Hence, g is a semigroup homomorphism from S into SS.

Remark 1:

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

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.


For any element a M , define g (a) = f a , where f a (x) = a * x, for all x Î M.
Then fa Î MM .
Let T = {fa Î MM / fa=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 fa Î T, there exist a Î M such that g(a) = fa.
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.


Let Y be the set of n generators of S, consisting of y1,y2, … ,yn and let x1, x2, … ,xn be the n elements of X.

Define g(xi) = yi, for i = 1,2, … ,n.
Then, for any string a = x1, x2 … xn of X*, we define g(a ) = g(x1) Å g(x2) ÅÅ g(xm) .
Then, for any b = , we have
g (a b ) = g (x1x2 … xm)
= g(x1) Å g(x2) ÅÅ g(xm) Å 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 x1 , x2 Î X.
(x1 E ) and (x2
E ) then (x1 x2 ) E ( ), where , Î X.
That is, if x1 is related to and x2 is related to , then the result of x1 and x2 by the binary operation , i.e., x1 x2 ,
is related to , the result of the binary operation on the related elements and. More precisely, x1 is related
to and x2 is related to then x1 x2 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
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.


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 x1, x2 , and Î S such that xR and x2R.
Then g(x1 * x2) = g(x1) D g(x2) (since g is a homomorphism.)
= g() g() (since x1R and x2R, so g(x1) = g() and g(x2) = g()]
= g( * ) (since g is a homomorphism.).
Therefore, by definition of R, x1 * x2 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.


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.

No comments: