# Why isn't this function $f:\mathbb N \to \mathcal P(\mathbb N)$ a surjection?

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?

• Note that every element in the image of your map is a finite set. Jan 21, 2013 at 16:37
• Can you find $x\in \mathbb{N}$ such that $f(x)=\mathbb{N}$ ?
– Amr
Jan 21, 2013 at 16:39
• Yes, this is a recursion, but hardly transfinite. Jan 21, 2013 at 17:05
• @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}$. Jan 21, 2013 at 17:29
• @andybenji Sure. I was just giving a short comment that shows him/her that this the function is not a surjection
– Amr
Jan 21, 2013 at 18:05

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

• Thank you very much!! It really helped me!! 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).

• 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" Jan 21, 2013 at 16:47
• 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}$. Jan 21, 2013 at 16:52