# By using a diagonal argument, show that the powerset $P(N) = (S|S ⊆ N)$ is uncountable. [duplicate]

Any tips or solutions for this one?

By using a diagonal argument, show that the powerset $$P(N) = (S|S ⊆ N)$$ is uncountable.

## marked as duplicate by Lee Mosher, Holo, Lord Shark the Unknown, Leucippus, CesareoFeb 13 at 7:33

If $$P(N)$$ were countable, there would be a surjection $$F: N \to P(N)$$. Consider any arbitrary $$F:N \to P(N)$$, we'll show it cannot be surjective.
Proof: $$A=\{n: n \notin F(n)\}$$ (a well-defined set when $$F$$ is given) is a set that is not in $$F[N]$$, because otherwise we'd have some $$m$$ with $$F(m) = A$$, and then $$m \in A$$ iff $$m \in F(m)$$ iff $$m \notin F(m)$$, contradiction. So $$F$$ is not surjective.