# Determining the equivalence classes of a given relation

I would like help with the specific problem:

We take the set $C$ to be $C={1, 2, 3, 4}$ and the relation $\sim$ over $\mathcal{P}(\mathbb{N})$ defined as

$A\sim B$ iff $A \cap C = B \cap C$

a) Prove that $\sim$ is an equivalence relation.

b) Find the equivalence classes of $\emptyset$, of $\{1\}$ and of $\{1, 8\}$.

c) How many equivalence classes are there?

The first part of the problem I was able to resolve fairly easily. A~A is trivially true, so the conditions of reflexivity are met, if A~B then B~A is also easy to prove, and (I took D instead of C for transitivity because C is used in the exercise) if A~B and B~D, then A~D. My proofs for these statements were all quite simple because the relationship is an equality. Hopefully I didn't make any wrong assumptions there.

to give an idea, for transitivity, I wrote:

A~B: $A\cap C$ = $B\cap C$

B~D: $B\cap C$ = $D\cap C$

Then $A\cap C$ = $B\cap C$ = $D\cap C$, thus $A\cap C$ = $D\cap C$, thus A~D.

Now, I'm rather stuck on the second and third parts of the problem. I don't know how to see the equivalence relations here.

b) A set $A$ is equivalent to $\emptyset$ iff $A\cap C=\emptyset$. What does it mean? What's the biggest such $A$?
Note that $\{1\}\sim\{1,8\}$.
c) You can find a full representative set of all equivalence classes within $C$.
Alternatively, consider the mapping $\mathcal P(\Bbb N) \to\mathcal P(C)$: $$A\mapsto A\cap C$$ Show that it's surjective and has kernel $\sim$.
• Thank you, Berci. I was able to determine the equivalence classes of those values as well as that there are $2^4$ equivalence classes in total, which is equal to #$\mathcal P(C)$. – Jake S May 3 '18 at 23:16