# Equivalence Relations and Partitions

My university "textbook" for discrete math is Schaum's Outline. In this outline he goes over Equivalence Relations and Partitions, and I got confused at a particular theorem.

From the book:

Theorem 2.6: Let R be an equivalence relation on a set S. Then S/R is a partition of S. Specifically:

(i) For each a in S, we have a ∈ [a].

(ii) [a] = [b] if and only if (a,b) ∈ R. (iii) If $[a] \ne [b]$, then [a] and [b] are disjoint. Conversely, given a partition {Ai} of the set S, there is an equivalence relation R on S such that the sets Aiare the equivalence classes. This important theorem will be proved in Problem 2.17.

EXAMPLE 2.13

(a) Consider the relation R = {(1,1),(1,2),(2,1),(2,2),(3,3)} on S = {1,2,3}. One can show that R is reflexive, symmetric, and transitive, that is, that R is an equivalence relation.

Also:  = {1,2}, = {1,2}, = {3} Observe that  =  and that S/R = {,} is a partition of S. One can choose either {1,3} or {2,3} as a set of representatives of the equivalence classes.

My confusion arises from the S/R = {,}. I don't understand how one can subtract a relation from a set of integers. What fundamental understanding am I missing?

• Multiplication corresponds to direct product ($A\times B$ contains all $\langle a,b\rangle$ pairs)