# 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 $$A_i$$ of the set $$S$$, there is an equivalence relation $$R$$ on $$S$$ such that the sets $$A_i$$ are 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] = \{1,2\}$$, $$[2] = \{1,2\}$$, $$[3] = \{3\}$$ Observe that $$[1] = [2]$$ and that $$S/R = \{[1],[3]\}$$ 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 = \{[1],[3]\}$$. I don't understand how one can subtract a relation from a set of integers. What fundamental understanding am I missing?

• This is related
– Pedro
Oct 17, 2012 at 22:50

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