Find equivalence classes: On the power set of $X$ by $A R B \iff A \cup Y = B \cup Y$.

165 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.