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

Question

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?

Answer 1

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

Answer 2

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