2
$\begingroup$

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.

They usually start with something like this:

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – copper.hat Nov 8 '13 at 7:13
  • $\begingroup$ 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. $\endgroup$ – Jeremy Upsal Nov 8 '13 at 7:15
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ That's wrong: $A=\{1\}$, $B=\{2\}$. $\endgroup$ – Michael Hoppe Nov 8 '13 at 8:08
  • $\begingroup$ Nothing, I've misread the question. Sorry. $\endgroup$ – Michael Hoppe Nov 8 '13 at 8:13
  • $\begingroup$ Could you elaborate more on what happened at "$\phi^{-1} ( \{ k \} )$ for $k = 0,1,2$"? I'm a little bit lost there. $\endgroup$ – Zol Tun Kul Nov 8 '13 at 8:53
  • 1
    $\begingroup$ $\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. $\endgroup$ – copper.hat Nov 8 '13 at 9:00
  • $\begingroup$ Thanks! Why $\phi^{-1}(\{k\})$ and not $\phi^{-1}(k)$ by the way? $\endgroup$ – Zol Tun Kul Nov 8 '13 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.