Franklin's Notes


Cantor's Theorem

Cantor's Theorem states, in plain language, that every set has strictly fewer elements than it has subsets. That is, there exists no injection $f:2^A\to A$ for any set $A$. This is a fundamental relationship between the cardinality of a set and its power set.

Cantor's Theorem. For any set $A$, $|A|<|2^A|$.

Proof. We clearly have that $|A|\leq |2^A|$, since the map $a\mapsto {a}$ is an injection from $A$ to $2^A$. However, $|A|\ne |2^A|$, because, as we will see, there cannot exist a bijection between $A$ and $2^A$.

Suppose, for the sake of contradiction, that there exists a bijection $f:A\to 2^A$. We will show that there must exist some element $A'\in 2^A$ such that $A'$ is not the image under $f$ of any element of $A$. In particular, define If there existed $a'\in A$ such that $f(a')=A'$, we would have a contradiction, since $a'\in A'\iff a'\notin A'$! Thus, $f$ cannot be surjective, and therefore cannot be a bijection. Hence, $|A|\ne |2^A|$, and so $|A|< |2^A|$ as claimed. $\blacksquare$

set-theory

cardinality

back to home page