Let $f:\mathbb N \to \mathcal P(\mathbb N)$ be a function which maps to each odd natural number an unitary set from $P(\mathbb N)$. Then, we map the even, non-four multiples with the sets formed by two elements. Recursively, we map the numbers whose rest of the division by $2^k$ is $2^{k-1}$ with the sets formed by $k$ elements.

I've studied that there is no surjection from $\mathbb N$ to $\mathcal P(\mathbb N)$, so why is not my function surjective?

  • 4
    $\begingroup$ Note that every element in the image of your map is a finite set. $\endgroup$
    – Adam Saltz
    Jan 21, 2013 at 16:37
  • $\begingroup$ Can you find $x\in \mathbb{N}$ such that $f(x)=\mathbb{N}$ ? $\endgroup$
    – Amr
    Jan 21, 2013 at 16:39
  • $\begingroup$ Yes, this is a recursion, but hardly transfinite. $\endgroup$
    – Asaf Karagila
    Jan 21, 2013 at 17:05
  • $\begingroup$ @Amr Having a single element (or finitely many, or countably infinitely many elements) omitted from the image set doesn't help, because we can use the "Hilbert Hotel" method and define $g(n) = \begin{cases} \mathbb{N} \mbox{ if } n = 1 \\ f(n-1) \mbox{ if } n > 1 \end{cases}$. $\endgroup$ Jan 21, 2013 at 17:29
  • $\begingroup$ @andybenji Sure. I was just giving a short comment that shows him/her that this the function is not a surjection $\endgroup$
    – Amr
    Jan 21, 2013 at 18:05

2 Answers 2


The nice thing about Cantor's diagonal argument is that it's fairly constructive, and we can explicitly write down a set that your method doesn't produce.

Your map is more well-defined than most that people give when they have your question, so we can actually apply it. You still allow the freedom of choosing the order in which we assign sets, so I will choose them reverse lexicographically. (e.g. 01 < 02 < 12 < 03 < 13 < 23 < 04 < ...)

I'll add in one thing you omitted: I'll define $f(0) = \{ \} $.

Now, I am going to construct a set $S_f$.

  • I will put $0$ into $S_f$, because $f(0) = \{ \}$ doesn't contain 0.
  • I will put $1$ into $S_f$, because $f(1) = \{ 0 \} $ doesn't contain 1.
  • I will put $2$ into $S_f$, put because $f(2) = \{ 0,1 \} $ doesn't contain 2.
  • I will put $3$ into $S_f$, because $f(3) = \{ 1 \} $ doesn't contain 3.
  • I will put $4$ into $S_f$, put because $f(4) = \{ 0,1,2 \} $ doesn't contain 4.
  • I will put $5$ into $S_f$, put because $f(5) = \{ 2 \} $ doesn't contain 5.
  • I will put $6$ into $S_f$, put because $f(6) = \{ 0,2 \} $ doesn't contain 6.
  • I will put $7$ into $S_f$, put because $f(7) = \{ 3 \} $ doesn't contain 7.
  • I will put $8$ into $S_f$, put because $f(8) = \{ 0,1,2,3 \} $ doesn't contain 8.
  • ...

The pattern becomes clear: you can show that $n \notin f(n)$, therefore I'm going to put every natural number into $S_f$, so $S_f = \mathbb{N}$. There cannot be a value $m$ such that $f(m) = S_f$, because $m \notin f(m)$ and $m \in S_f$. Therefore, $f$ is not surjective.

You mention that you can easily fix up $f$ to make a new function $g$ such that there is a value $a$ with $g(a) = \mathbb{N}$. If you do, then we can use the same recipe above to construct $S_g$....

  • $\begingroup$ Thank you very much!! It really helped me!! $\endgroup$
    – Damaru
    Jan 21, 2013 at 21:40

You are only mapping $\mathbb{N}$ to subsets of $\mathbb{N}$ that have finite cardinality (except the empty set).

What maps to $\mathbb{N}$? Nothing in your example.

The set of all finite subsets of $\mathbb{N}$ is countable, and you give a nice example of a bijection to the set of all finite subsets of $\mathbb{N}$ (again, excluding the empty set, but we can fix that easily).

  • $\begingroup$ Yes, I've commited a mistake, but like you've said, we can fix that easily. But, my question was that why my function wasn't surjective, so it can't be a "nice example of bijection" $\endgroup$
    – Damaru
    Jan 21, 2013 at 16:47
  • $\begingroup$ Okay - I clarified. I meant you had a nice bijection between $\mathbb{N}$ and the set of all finite subsets of $\mathbb{N}$. Your example isn't a surjection to $\mathcal{P}(\mathbb{N})$ since nothing maps to any infinite subset of $\mathbb{N}$. $\endgroup$
    – Paul Raff
    Jan 21, 2013 at 16:52

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.