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$
2
  • $\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, 2013 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$ Nov 8, 2013 at 7:15

1 Answer 1

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$
6
  • $\begingroup$ That's wrong: $A=\{1\}$, $B=\{2\}$. $\endgroup$ Nov 8, 2013 at 8:08
  • $\begingroup$ Nothing, I've misread the question. Sorry. $\endgroup$ Nov 8, 2013 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$
    – Saturn
    Nov 8, 2013 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, 2013 at 9:00
  • $\begingroup$ Thanks! Why $\phi^{-1}(\{k\})$ and not $\phi^{-1}(k)$ by the way? $\endgroup$
    – Saturn
    Nov 8, 2013 at 9:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .