2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Hints:

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$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Jake S May 3 '18 at 23:16

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.