# A bijection between $\mathbb{N}$ and $\mathbb{P}(\mathbb{N})$?

I would like to ask for a little help or a hint about a set theory exercise i am stuck in.

Let $f: \mathbb{N}\rightarrow \mathbb{P}(\mathbb{N})$, $\mathbb{P}(\mathbb{N})$ is the power set of the natural numbers, be a map. Consider the subset $A\subset \mathbb{N}$ defined by $A=\{ m\in \mathbb{N} \mid m\notin f(m)\}$. Assume that there is an integer $r\in \mathbb{N}$ such that $f(r)=A$.

(1) What happens if $r\in A$?

Here I think I get to a contradiction by the definition, because $r\in A=\left \{ r\in \mathbb{N}\mid r\notin f(r) \right \}$ but $f(r)=A$ by definition. So it's not surjective, thus there is no bijection.

(2) What happens if $r\notin A$?

Here I get again a contradiction, the same way like in the first question.

Is there a bijection between $\mathbb{N}$ and $\mathbb{P}(\mathbb{N})$?

I think the answer is no, because the function is not surjective.

Are my ideas correct? If you have a remark, I would be very happy if you can share it here. Thank you in advance! Have a nice day :)

• thanks for the edit, Lord_Farin! – Lullaby Sep 18 '13 at 10:54

Yes, your ideas are correct. The only mistake is a small technical one: when you write $r\in A=\{r\in\Bbb N:r\notin f(r)\}$, the first $r$ is the specific one such that $f(r)=A$, but the rest are dummy variables. You shouldn’t use the same symbol with two different meanings in the same expression; you could change it to $r\in A=\{n\in\Bbb N:n\notin f(n)\}$, for instance, and it would be fine.

Your argument is a special case of the proof of Cantor’s theorem, which says that if $A$ is any set, there is no bijection from $A$ to $\wp(A)$; the proof actually shows that no $f:A\to\wp(A)$ can be surjective. You’ve carried it out for $A=\Bbb N$, but the same argument works for any set.

• @Lullaby: You’re welcome. – Brian M. Scott Sep 18 '13 at 19:21

What is interesting to note, is that we didn't use that we were talking about $\Bbb N$. The same proof works for any set $X$.
$$|X| < |\mathcal P(X)|$$
meaning that there is an injection $X \hookrightarrow \mathcal P(X)$ but no bijection, is called Cantor's Theorem.