Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

APP. B] ALGEBRAIC SYSTEMS 437

Homomorphism of Semigroups

Consider two semigroups (S,∗) and (S′,∗′). A functionf:S→S′is called asemigroup homomorphism
or, simply, ahomomorphismif

f(a∗b)=f(a)∗′f(b) or,simply f(ab)=f(a)f(b)

Supposefis also one-to-one and onto. Thenfis called anisomorphismbetweenSandS′, andSand S′are said
to beisomorphicsemigroups, writtenS∼=S.

EXAMPLE B.8

(a) LetMbe the set of all 2×2 matrices with integer entries. The determinant of any matrixA=

[

ab

cd

]

is denoted and defined by det(A)=|A|=ad−bc. One proves in Linear Algebra that the determinant is a

multiplicative function, that is, for any matricesAandB,

det(AB)=det(A)·det(B)

Thus the determinant function is a semigroup homomorphism on (M,×), the matrices under matrix multi-

plication. On the other hand, the determinant function is not additive, that is, for some matrices,

det(A+B)=det(A)+det(B)

Thus the determinant function is not a semigroup homomorphism on (M,+).

(b) Figure B-2(a) gives the addition table forZ 4 , the integers modulo 4 under addition; and Fig. B-2(b) gives

the multiplication table forS ={ 1 , 3 , 7 , 9 }inZ 10. (We note thatSis a reduced residue system for the

integersZmodulo 10.) Letf:Z 4 →Sbe defined by

f( 0 )= 1 ,f( 1 )= 3 ,f( 2 )= 9 ,f( 3 )= 7

Fig. B-2

One can show thatfis a homomorphism. Sincefis also one-to-one and onto,fis an isomorphism. Thus

Z 4 andSare isomorphic semigroups.

(c) Let∼be a congruence relation on a semigroupS. Letφ:S→S/∼be thenatural mappingfromSinto the

factor semigroupS/∼defined by

φ(a)=[a]

That is, each elementainSis assigned its equivalence class [a]. Thenφis a homomorphism since

φ(ab)=[ab]=[a][b]=φ(a)φ(b)