Cantor's Theorem

We will now look at an prove a very important theorem regarding a set, its power set, and surjectivity.

Theorem 1 (Cantor): If $A$ is a set and $P(A)$ represents the power set of $A$ then there exists no function $f: A \to P(A)$ that is surjective.

• Proof of Theorem (by Contradiction): Suppose that there exists a surjection $f: A \to P(A)$. We note that $f(a) \subseteq A$ (Note that $a \in A$ is mapped to a subset of $A$ in $P(A)$, so this is why $f(a) \subseteq A$).

• Therefore $a \in f(a)$ or $a \not \in f(a)$.

• We will let the set $C$ be the set where $a \in A$ but $a \not \in f(a)$, that is $C = \{ a \in A : a \not \in f(a) \}$.

We note that $C \subseteq A$ and if $f$ is a surjection, then for some $a_0 \in A$, $f(a_0) = C$.

We now have two cases to look at.

• Case 1 ($a_0 \in C$): In this case, if $a_0 \in C$ then $f(a_0) = C$ and we must have $a_0 \in f(a_0)$ which contradicts our definition of $C$.

• Case 2 ($a_0 \not \in C$) In this case, if $a_0 \not \in C$, then $a_0 \not \in f(a_0)$ so then $a_0 \in C$ (since $a_0 \in A$ and $a_0 \not \in f(a_0)$) which is also contradictory.

• Therefore our original assumption that $f$ was surjective was wrong. $\blacksquare$