# 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 funtion 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 funtion surjective?

-
Note that every element in the image of your map is a finite set. –  Adam Saltz Jan 21 '13 at 16:37
Can you find $x\in \mathbb{N}$ such that $f(x)=\mathbb{N}$ ? –  Amr Jan 21 '13 at 16:39
Yes, this is a recursion, but hardly transfinite. –  Asaf Karagila Jan 21 '13 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}$. –  andybenji Jan 21 '13 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 '13 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!! –  Damaru Jan 21 '13 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" –  Damaru Jan 21 '13 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}$. –  Paul Raff Jan 21 '13 at 16:52