1
$\begingroup$

This question already has an answer here:

Any tips or solutions for this one?

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.