How to find the Equivalence class for a given set?

Question

I'm really having trouble understanding these equivalence classes. Could someone please guide me through the following problem step by step, and help explain this. I have a final exam next week, and I'm just so lost.

Let A = {1, 2, 3, 4, 5}. Define a relation on $\mathcal{P}$(A) as follows:

R = {(X, Y) ∈ $\mathcal{P}$(A) × $\mathcal{P}$(A)| X ∩ {1, 3, 5} = Y ∩ {1, 3, 5}}.

What is the equivalence class of {1, 2, 3}?

The answer is the following:

The equivalence class of {1, 2, 3} is equal to
{{1, 3}, {1, 3, 2}{1, 3, 4}, {1, 3, 2, 4}}

Can someone please help me with this. I don't understand the problem, and I don't fully understand what an equivalence class is either. I feel really lost, so if someone could slowly guide me through this, it'd be greatly appreciated! Thanks guys :)

Answer 1

The relation R is "made of" couples : $(X,Y)$, where $X,Y \subset A$ (i.e.$X,Y$ are members of $\mathcal P(A)$, that is the power-set of $A$, where the power-set of $A$ is the set of all subsets of $A$).

Thus $R$ takes as "input" an $X$ (subset of $A$) and "couple" it to an $Y$ (subset of $A$), provided that the "defining condition" is satisfied.

Which is the "defining condition" ? It is :

$X \cap \{ 1, 3, 5 \} = Y \cap \{ 1, 3, 5 \}$.

Now, consider $X = \{ 1, 2, 3 \}$;

what is $X \cap \{ 1, 3, 5 \}$ ? It will be $\{ 1, 2, 3 \} \cap \{ 1, 3, 5 \} = \{ 1, 3 \}$.

We have to find all $Y$ subset of $A$ such that :

$Y \cap \{ 1, 3, 5 \} = \{ 1, 3 \}$.

Thus, in order to find them, we have to list all subsets of $A$ and then check them against the "defining condition"; i.e. to choose all those which contain as members $1$ and $3$.

Answer 2

First of all, let us check that the answer is reasonable. That is, we should check if $\{1,2,3\}$ is equivalent to the sets mentioned. Let us begin by checking that $\{1,2,3\}$ is equivalent to $\{1,3\}$. Then we look up the definition of the relation and see that this equivalence holds if $$\{1,2,3\} \cap \{1,3,5\} = \{1,3\} \cap \{1,3,5\}.$$ So, is that the case? It is, right, because both sides are equal to $\{1,3\}$.

Okay, so that's a start; now you should try to go through the other given subsets as well, checking that they're all equivalent to $\{1,2,3\}$.

Now, by definition, the equivalence class of $\{1,2,3\}$ consists of all the sets that are equivalent to $\{1,2,3\}$, so when you're done with the above, one thing remains to check: that no other subsets are equivalent to $\{1,2,3\}$. At this point, you should be able to see the relevant patterns. For instance, you can immediately rule out all the subsets containing $5$, and you can see that any subset equivalent to $\{1,2,3\}$ has to contain both $1$ and $3$. Then you're pretty much done.