# equivalence classes of P(N)

• Feb 13th 2010, 12:57 AM
afterdarkk
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.
• Feb 13th 2010, 01:24 AM
afterdarkk
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.
• Feb 13th 2010, 04:36 AM
Plato
Quote:

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 $\left| N \right| < \left| {\mathcal{P}(N)} \right|$
If A is the set of all finite subsets of $N$ then $|\mathcal{A}|=|N|.$
Now note that if $X\in \mathcal{P}(N) \setminus\mathcal{A}$ then $X$ is in the same equivalence class as $N$.
So what do you conclude?
• Feb 13th 2010, 07:37 AM
afterdarkk
Quote:

Originally Posted by Plato
You do know that $\left| N \right| < \left| {\mathcal{P}(N)} \right|$
If A is the set of all finite subsets of $N$ then $|\mathcal{A}|=|N|.$
Now note that if $X\in \mathcal{P}(N) \setminus\mathcal{A}$ then $X$ is in the same equivalence class as $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).
• Feb 13th 2010, 08:26 AM
Plato
Quote:

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 $\mathcal{A} \mapsto \mathbb{Z}^+$.
That shows that it is countable.