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

436 ALGEBRAIC SYSTEMS [APP. B

EXAMPLE B.6

(a) LetAandBdenote, respectively, the set of even and odd positive integers. Then (A,×)and (B,×)are

subsemigroups of (N,×)sinceAandBare closed under multiplication. On the other hand, (A,+)isa

subsemigroup of (N,+) sinceAis closed under addition, but (B,+) is not a subsemigroup of (N,+) since

Bis not closed under addition.

(b) LetFbe the free semigroup on the setA={a, b}. LetHconsist of all even words, that is, words with even

length. The concatenation of two such words is also even. ThusHis a subsemigroup ofF.

Congruence Relations and Quotient Structures

LetSbe a semigroup and let∼be an equivalence relation onS. Recall that the equivalence relation∼induces

a partition ofSinto equivalence classes. Also, [a] denotes the equivalence class containing the elementa∈S,

and that the collection of equivalence classes is denoted by S/∼.

Suppose that the equivalence relation∼onShas the following property:

Ifa∼a′andb∼b′,thenab∼a′b′.

Then∼is called acongruence relationonS. Furthermore, we can now define an operation on the equivalence
classes by

[a]∗[b]=[a∗b] or,simply, [a][b]=[ab]

Furthermore, this operation onS/∼is associative; henceS/∼is a semigroup. We state this result formally.

Theorem B.3: Let∼be a congruence relation on a semigroupS. ThenS/∼, the equivalence classes under∼,
form a semigroup under the operation[a][b]=[ab].

This semigroupS/∼is called the quotient ofSby∼.

EXAMPLE B.7

(a) LetFbe the free semigroup on a setA. Defineu∼u′ifuandu′have the same length. Then∼is an

equivalence relation onF. Furthermore, supposeu∼u′andv∼v′, say,

l(u)=l(u′)=m and l(v)=l(v′)=n

Thenl(uv)=l(u′v′)=m+n, and souv∼u′v′. Thus∼is a congruence relation onF.

(b) Consider the integersZand a positive integerm>1. Recall (Section 11.8) that we say thatais congruent

tobmodulom, written

a≡b(modm)

ifmdivides the differencea−b. Theorem 11.21 states that this relation is an equivalence relation onZ.

Furthermore, Theorem 11.22 tells us that ifa≡c(modm)andb≡d(modm)then:

a+b≡c+d(modm) and ab≡cd (modm)

In other words, this relation is a congruence relation onZ.