# Thread: equivalence classes of P(N)

1. ## equivalence classes of P(N)

hi,

I apologize in advance for my phrasing, I'm translating this from another language.

let R be a relation under P(N) where ∀A,B ∈P(N), (A,B)∈R if and only if |A|=|B|.

R is an equivalence relation, therefore it splits P(N) to equivalence classes.

The question is what's the cardinality of the equivalence class that N is a member of. I have a feeling it's c (|R|), but I don't know how to show it.

2. I thought of looking at P(N) as a union of all finite subsets and all countably infinite subsets, the latter are in N's equivalence classes. For each countably infinite set, every number of N is either a member of it or not (2 options). Since there are aleph-null natural numbers, the number of possibilities is 2^(aleph-null)=c.

3. Originally Posted by afterdarkk
let R be a relation under P(N) where ∀A,B ∈P(N), (A,B)∈R if and only if |A|=|B|.
R is an equivalence relation, therefore it splits P(N) to equivalence classes.
The question is what's the cardinality of the equivalence class that N is a member of.
You do know that $\displaystyle \left| N \right| < \left| {\mathcal{P}(N)} \right|$
If A is the set of all finite subsets of $\displaystyle N$ then $\displaystyle |\mathcal{A}|=|N|.$
Now note that if $\displaystyle X\in \mathcal{P}(N) \setminus\mathcal{A}$ then $\displaystyle X$ is in the same equivalence class as $\displaystyle N$.
So what do you conclude?

4. Originally Posted by Plato
You do know that $\displaystyle \left| N \right| < \left| {\mathcal{P}(N)} \right|$
If A is the set of all finite subsets of $\displaystyle N$ then $\displaystyle |\mathcal{A}|=|N|.$
Now note that if $\displaystyle X\in \mathcal{P}(N) \setminus\mathcal{A}$ then $\displaystyle X$ is in the same equivalence class as $\displaystyle N$.
So what do you conclude?
if A is the set of all finite subsets of N and A is countable, it's easy to show that |P(N)-A|=c. But I'm having a hard time showing that A is countable (even with the help of the thread you linked).

5. Originally Posted by afterdarkk
if A is the set of all finite subsets of N and A is countable, it's easy to show that |P(N)-A|=c. But I'm having a hard time showing that A is countable (even with the help of the thread you linked).
In that link, in the response I posted, I showed an injection from $\displaystyle \mathcal{A} \mapsto \mathbb{Z}^+$.
That shows that it is countable.