1
$\begingroup$

For the question

Let $X = \{1, 2, 3, 4, 5\}$ , $Y = \{3, 4\}$. Define a relation $R$ on the power set of $X$ by $A R B \iff A \cup Y = B \cup Y$. How many equivalence classes are there?

I am completely stumped as to how to start this problem. I know the power set of X is $\{\}, \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\},\{3,4\}, \{3,5\}, \{4,5\}, \{1,2,3\}, \{1,2,4\}, \{1,2,5\}, \{1,3,4\}, \{1,3,5\}, \{1,4,5\}, \{2,3,4\}, \{2,3,5\}, \{2,4,5\}, \{3,4,5\}, \{1,2,3,4\}, \{1,2,3,5\}, \{1,2,4,5\}, \{1,3,4,5\}, \{2,3,4,5\}, \{1,2,3,4,5\}$.

But I have no idea how to find the equivalence classes. My guess is that they are $\{\}, \{1,2\}, \{3\}, \{4,5\}$, since equivalent classes can't have any overlapping elements.

$\endgroup$
1
$\begingroup$

First of all, it is important to notice that the equivalence classes are subsets of the power set of $X$, hence each of them is a collection of sets unlike your guess.

Now you already started well by writing down all elements in the power set. To divide them into equivalence classes you start with a random element, e.g. $\{\}$. Mark it with some color, say green. Now which sets are equivalent to $\{\}$? Clearly, $\{1\}$ is not because $\{\} \cup \{3,4\} \neq \{1\} \cup \{3,4\}$. Mark it with a different color, say blue. Next one is $\{2\}$. By the same argument, it is not in the green class nor in the blue class. Mark it red. Next one is $\{3\}$. As $\{\} \cup \{3,4\} = \{3\} \cup \{3,4\}$, $\{3\}$ is in the green class. And so on, I am sure you can proceed.

| cite | improve this answer | |
$\endgroup$

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.