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

438 ALGEBRAIC SYSTEMS [APP. B

Fundamental Theorem of Semigroup Homomorphisms

Recall that the image of a functionf:S→S′, writtenf(S)of Imf, consists of the images of the elements
ofSunderf. Namely:

Imf={b∈S′|there existsa∈Sfor whichf(a)=b}

The following theorem (proved in Problem B.5) is fundamental to semigroup theory.

Theorem B.4: Letf: S → S′be a semigroup homomorphism. Leta∼biff(a)= f(b). Then:
(i)∼is a congruence relation onS. (ii)S/∼is isomorphic tof(S).

EXAMPLE B.9

(a) LetFbe the free semigroup onA={a, b}. The functionf:F→Zdefined by

f (u)=l(u)

is a homomorphism. Notef(F)=N. ThusF/∼is isomorphic toN.

(b) LetMbe the set of 2×2 matrices with integer entries. Consider the determinant function det:M→Z.We

note that the image of det isZ. By Theorem B.4,M/∼is isomorphic toZ.

Semigroup Products
Let (S 1 ,∗ 1 )and (S 2 ,∗ 2 )be semigroups. We form a new semigroupS=S 1 ⊗S 2 , called the direct product
ofS 1 andS 2 , as follows.

(1) The elements ofScome fromS 1 ×S 2 , that is, are ordered pairs(a, b)wherea∈S 1 andb∈S 2

(2) The operation∗inSis defined componentwise, that is,

(a, b)∗(a′,b′)=(a∗ 1 a′,b∗ 2 b′) or simply (a, b)(a′,b′)=(aa′,bb′)

One can easily show (Problem B.3) that the above operation is associative.

B.4Groups

LetGbe a nonempty set with a binary operation (denoted by juxtaposition). ThenGis called agroupif the
following axioms hold:

[G 1 ] Associative Law: For anya,b,cinG, we have(ab)c=a(bc).
[G 2 ] Identity element: There exists an elementeinGsuch thatae=ea=afor everyainG.
[G 3 ] Inverses: For eachainG, there exists an elementa−^1 inG(theinverseofa) such that

aa−^1 =a−^1 a=e

A groupGis said to beabelian(orcommutative)ifab=bafor everya,b∈G, that is, ifGsatisfies the
Commutative Law.
When the binary operation is denoted by juxtaposition as above, the groupGis said to be writtenmultiplica-
tively. Sometimes, whenGis abelian, the binary operation is denoted by+andGis said to be writtenadditively.
In such a case the identity element is denoted by 0 and it is called thezeroelement; and the inverse is denoted by
−aand it is called thenegativeofa.
The number of elements in a groupG, denoted by|G|, is called theorderofG. In particular,Gis called a
finite groupif its order is finite.
SupposeAandBare subsets of a groupG. Then we write:

AB={ab|a∈A, b∈B} or A+B={a+b|a∈A, b∈B}