# How to determine the equivalence classes of a relation?

I don't fully understand how to find the equivalence classes of a relation.

Over $\mathcal P(E)$, where $E = \{1,2,3,4,5,6\}$, $ARB \iff |A\cap\{1,2\}| = |B\cap\{1,2\}|$

From what I've seen, people try to make up a formula of some sort that calculates a set with all the elements that relate to an arbitrary element.

Have some set $X \in \mathcal P(E)$, now consider:

$$[X] = \{Y\in \mathcal P(E) : YRX\}$$

$$= \{Y \in \mathcal P(E) : |Y \cap \{1,2\}| = |X \cap \{1,2\}|\}$$

And then they elaborate to make such formula.

I don't really get the point of that. How do you determine the equivalence classes of a relation?

• Well, since $|E| = 6$, there are $2^6$ possible subsets, so you could enumerate them and check. However, basically sets fall into one of three classes. (1) the set does not contain either 1 or 2, (2) the set contains exactly one of 1 or 2 and (3) the set contains 1 and 2. – copper.hat Nov 8 '13 at 7:13
• Following @copper.hat's suggestion, consider that any set containing $\{1,2\}$ will have the same cardinality, all sets containing neither 1 or 2 will have the same cardinality, and all sets containing one of either 1 or 2 will have the same cardinality. This should narrow down your equivalence class search quite drastically. – Jeremy Upsal Nov 8 '13 at 7:15

Let $\phi(A) = |A \cap \{1,2\}|$. We see that $\phi(A) \in \{0,1,2\}$, and $ARB$ iff $\phi(A) =\phi(B)$.
So the equivalence classes are $\phi^{-1} ( \{ k \} )$ for $k=0,1,2$.
• That's wrong: $A=\{1\}$, $B=\{2\}$. – Michael Hoppe Nov 8 '13 at 8:08
• Could you elaborate more on what happened at "$\phi^{-1} ( \{ k \} )$ for $k = 0,1,2$"? I'm a little bit lost there. – Zol Tun Kul Nov 8 '13 at 8:53
• $\phi^{-1}(\{0\})$ is the collection of all sets that do not contain $1$ or $2$. $\phi^{-1}(\{1\})$ is the collection of all sets that contain exactly one of $1,2$ and $\phi^{-1}(\{2\})$ is the collection of all sets that contain both 1 and 2. – copper.hat Nov 8 '13 at 9:00
• Thanks! Why $\phi^{-1}(\{k\})$ and not $\phi^{-1}(k)$ by the way? – Zol Tun Kul Nov 8 '13 at 9:04