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 :)

  • $\begingroup$ thanks for the edit, Lord_Farin! $\endgroup$ – 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.

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

Your ideas are correct.

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

This result, often denoted as a statement about cardinalities:

$$|X| < |\mathcal P(X)|$$

meaning that there is an injection $X \hookrightarrow \mathcal P(X)$ but no bijection, is called Cantor's Theorem.


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.