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

APP. B] ALGEBRAIC SYSTEMS 451

B.3.LetS=N×N. Let∗be the operation onSdefined by (a,b)∗(a′,b′)=(aa′,bb′).

(a) Show that∗is associative. (HenceSis a semigroup.)

(b) Definef:(S,∗)→(Q,×)byf(a,b)=a/b. Show thatfis a homomorphism.

(c) Find the congruence relation∼inSdetermined by the homomorphismf, that is, wherex∼yif

f(x)=f(y). (See Theorem B.4.)

(d) DescribeS/∼. DoesS/∼have an identity element? Does it have inverses?

Supposex=(a, b), y=(c, d), z=(e, f ).

(a) We have

(xy)z=(ac, bd)∗(e, f )=[(ac)e, (bd)f]

x(yz)=(a, b)∗(ce, df )=[a(ce), b(df )]

Sincea, b, c, d, e, f, are positive integers,(ac)e=a(ce)and(bd)f=b(df ). Thus(xy)z=x(yz)and hence∗

is associative. That is, (S,∗) is a semigroup.

(b) fis a homomorphism since

f(x∗y)=f(ac, bd)=(ac)/(bd)=(a/b)(c/d)=f(x)f(y)

(c) Supposef(x)=f(y). Thena/b=c/dand hencead=bc. Thusfdetermines the congruence relation∼onS

defined by(a, b)∼(c, d)ifad=bc.

(d) The image offisQ+, the set of positive rational numbers. By Theorem B.3,S/∼is isomorphic toQ+. Thus

S/∼does have an identity element, and every element has an inverse.

B.4.Prove Theorem B.1. Suppose∗is an associative operation on a setS. Then any producta 1 ∗a 2 ∗...∗an

requires no parenthesis, that is, all possible products are equal.

The proof is by induction onn. Sincenis associative, the theorem holds forn= 1 , 2 ,and 3. Supposen≥4.

We use the notation:

(a 1 a 2 ,···an)=(···((a 1 a 2 )a 3 )···)an and [a 1 a 2 ···an]=any product

We show[a 1 a 2 ···an]=(a 1 a 2 ···an)and so all such products will be equal. Since[a 1 a 2 ···an]denotes some product,

there exists anr<nsuch that[a 1 a 2 ···an]=[a 1 a 2 ···ar][ar+ 1 ···an]. Therefore, by induction,

[a 1 a 2 ···an]=[a 1 a 2 ···ar][ar+ 1 ···an]=[a 1 a 2 ···ar](ar+ 1 ···an)

=[a 1 ···ar]((ar+ 1 ···an− 1 )an)=([a 1 ···ar](ar− 1 ···an− 1 ))an

=[a 1 ···an− 1 ]an=(a 1 ···an− 1 )an=(a 1 a 2 ···an)

Thus the theorem is proved.

B.5.Prove Theorem B.4: Letf:S→S′be a semigroup homomorphism. Leta∼biff(a)=f(b). Then:

(i)∼is a congruence relation; (ii)S/∼is isomorphic tof(S).

(i) First we show that∼is an equivalence relation. Sincef(a)=f(a), we havea∼a.

Ifa∼b, thenf(a)=f(b)orf(b)=f(a); henceb∼a. Lastly, ifa∼bandb∼c, thenf(a)=f(b)and

f(b)=f(c); hencef(a)=f(c). Thusa∼c. That is,∼is an equivalence relation. Suppose nowa∼a′and

b∼b′. Thenf(a)=f(a′)andf(b)=f(b′).

Sincefis a homomorphism,

f(ab)=f(a)f(b)=f(a′)f(b′)=f(a′b′)

Thereforeab∼a′b′. That is,∼is a congruence relation.

(ii) Define:S/∼→f(S)by([a])=f(a). We need to prove: (1)is well-defined, that is,([a])∈f(S), and

if[a]=[b]thenf([a])=f([b]). (2)is an isomorphism, that is,is a homomorphism, one-to-one and onto.