202 CHAPTER 4 Abstract Algebra
relation is symmetric. How about the transitivity? This involves a
more work, but a bit of thought reveals the following. IfP denotes the
above matrix, and ifP^2 has nonzero entries in exactly the same places
asP, then the relation is also transitive.
Let S be a set and letRbe an equivalence relation onS. For any
elements∈Swe denote by [s] the set
[s] = {s′∈S|sRs′}⊆S,and call this set theequivalence classinS containings∈S. Note
that ifs 1 Rs 2 then [s 1 ] = [s 2 ] becauses 1 ands 2 are equivalent to exactly
the same elements ofS.
Proposition. LetRbe an equivalence relation on the setSand let[s]
and[s′]be two equivalence classes inS. Then either[s] = [s′], in which
casesRs′or[s]∩[s′] =∅, where thensRs 6 ′.
Proof. Assume that [s]∩[s′] 6 = ∅, say that there is some element
t∈[s]∩[s′]. Therefore sRtands′Rtwhich implies by symmetry that
sRt andtRs′. Using transitivity, we see thatsRs′ which means that
s, s′ are equivalent to exactly the same elements of S. From this it
follows that [s] = [s′]. The only other possibility is that [s]∩[s′] =∅in
which case one obviously hassRs 6 ′.
As a result of the above proposition we see that an equivalence re-
lationRon a setS partitions the set into disjoint equivalence classes.
In light of this, let’s take a look at a few examples.
(i) Consider the equivalence relation “≡ (mod 7)” on the set Z of
integers. We have the following decomposition ofZinto exactly 7
equivalence classes:[0] ={...,− 14 ,− 7 , 0 , 7 , 14 , ...}
[1] ={...,− 13 ,− 6 , 1 , 8 , 15 , ...}
[2] ={...,− 12 ,− 5 , 2 , 9 , 16 , ...}
[3] ={...,− 11 ,− 4 , 3 , 10 , 14 , ...}