Cantor's Theorem

See Power Set for some background.

Proof
Let $f:A\to \mathcal{P}(A)$ be any map. We'll find some $B\subseteq A$ such that $B\notin \text{image}(f)$, since that shows the opposite of being onto.

First note that $\mathrm{\forall }a\in A$, either $a\in f(a)$ or $a\notin f(a)$, but only one of these is true. Let $B$ be:

We claim that $B\notin \text{image}(f)$. Assume for contradiction that it was. Then $\mathrm{\exists }a\in A$ such that $f(a)=B$.

1. If $a\in B$, then since $B=f(a)$ then $a\in f(a)$ which contradicts our construction of $B$ that $a\notin f(a)$.
2. Then $a\notin B$ right? Well then that would mean that $a\in f(a)=B$ is a contradiction.
   No matter what we get a contradiction, so then our assumption was false. Then $B\notin \text{image}(f)$, so then $f$ must be onto.
   ☐
   Let's apply this idea to $\mathbb{N}=A$. Then Cantor's Theorem says that any function $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ requires $f$ be not onto (surjective). As a result, the $\mathbb{N}\nsim \mathcal{P}(\mathbb{N})$ so then $\mathcal{P}(\mathbb{N})$ must be uncountable. We can show even that the following is true:

Proof

☐