Equivalence Classes of a Relation Given as a Set of Ordered Pairs

Question

Question: The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R.

A = {a, b, c, d} R = {(a, a), (b, b), (b, d), (c, c), (d, b), (d, d)}

My work: So when you draw the directed graph you get a loop from a to a, b to b, c to c and d to d There are arrows from b to d and from d to b.

Now this is where I get confused (this solution is from the book):

[a] = {x∈A | x R a} = {a} <- this one makes sense as a is a loop

[b] = {x∈A | x R b} = {b,d} <- why is {b,b} not included?

[c] = {x∈A | x R c} = {c} <- this one makes sense as c is a loop

[d] = {x∈A | x R d} = {b,d} <- again why is d,d not included

Answer: My book says the equivalence classes are {a}{b,d}{c}

I'm not really sure how to go about solving this problem. I would really appreciate any help on what to do.

Answer 1

The equivalence classes are by definition subsets of $A$, not subsets of $R$. The pairs $(b,b)$ and $(d,d)$ are elements of $R$, not elements of $A$.

Answer 2

An equivalence relation is a relation that is Reflexive, Symmetric and Transitive. The one you give is all three of these. You just need to determine the equivalence classes (an equivalence relation always gives rise to equivalence classes).

You are correct that you can just draw a digraph and get each equivalence class as a Strongly-Connected Component of the digraph. The digraph here is

a (self loop), b (self loop) <----> d (self loop), c (self loop)

So the equivalence classes are {a}, {b,d} and {c}.

You ask why $\{b,b\}$ is not included in $b$'s equivalence class? $b$'s class is all elements of $A$ equivalent to $b$ and these are $b$ and $d$. $\{b,b\}$ is not an element of $A$ or of $R$ (because $R$ has ordered pairs).