The powerset of the set of natural numbers - Cantor's Theorem

Question

It is a fact that if $A$ is any set then there is no bijection between $A$ and its powerset $P(A)$. If $A$ is finite, this is pretty clear just by looking at the sizes of $A$ and $P(A)$. But if I don't know this and I try finding a bijection between $\mathbb{N}$ and $P(\mathbb{N})$, what would stop me from trying to build a function that recursively enumerates the contents of $P(\mathbb{N})$?

Answer 1

It seems you are somehow saying that, using recursion, you can define some function which avoids the error.

But the proof that no $f:A\to P(A)$ uses the whole function $f$. If you give me a complete definition of a function $f:A\to P(A)$, I can find an element of $P(A)$ which is not in the image of $f$. Recursion doesn't let you get around this. You can change the function, but that new function also misses some set.

This would be like saying Euclid's proof doesn't prove that the primes are infinite, because, once you find that extra prime, you can just add it to the set, and you still have a finite set of primes.

Answer 2

If you have a function $f:\mathbb N\to\mathcal P(\mathbb N)$, then let $$ B = \{ n\in\mathbb N : n\not\in f(n) \}. $$ Then $B$ is not in the image of $f$. To prove this, suppose $B = f(k)$. Then ask whether $k\in B$ or not. If it is, then it's not, and if it's not, then it is. Either way, you have a contradiction. Hence every such function $f$ fails to be onto the entire set $\mathcal P(\mathbb N)$.