Cantor's theorem

Theorem:

$|A|<|\mathbb{P}(A)|$ - the cardinality of a set is strictly less than the cardinality of its powerset.

Proof: Let $f$ be any map from $A$ to $\mathbb{P}(A)$, and consider the set $B=\{x\in A|x\notin f(x)\}$.

$B$ is a subset of $A$ so $B\in \mathbb{P}(A)$.

Assume with the aim of contradiction that $f$ is surjective (which would imply that $|A|\ge |\mathbb{P}(A)|$). Then there exists $\xi$ such that $f(\xi )=B$.

Then from "$\text{for all }x\in A[x\in B⟺x\notin f(x)]$", we can substitute in $\xi$ to get $\xi \in B⟺\xi \notin B$, since $f(\xi )=B$.

This is a contradiction, so $f$ cannot be surjective.

We know there exist injective functions from $A$ to $\mathbb{P}(A)$, e.g. $g:A\to \mathbb{P}(A)$ such that $g(x)=x$. Therefore $|A|<|\mathbb{P}(A)|$.

Explanation: Cantor’s theorem says that there cannot exist a surjective function $f$ from $A$ to $\mathbb{P}(A)$ because that would imply the existence of a set $B\in \mathbb{P}(A)$ and an element $\xi \in A$ such that $\xi \in B⟺\xi \notin B$, which is a contradiction.

Cantor does this by setting $B$ to be the set $\{x\in A|x\notin f(x)\}$, i.e. the elements of $A$ that are not contained in their image under $f$. $B\in \mathbb{P}(A)$ because $B$ is a subset of $A$ and $\mathbb{P}(A)$ contains every subset of $A$. Since $f$ is surjective, there is some $\xi$ such that $f(\xi )=B$. But then $\xi \in B⟺\xi \notin B$, and hence the contradiction.