Cantor's Theorem

Theorem

There is no surjection from a set $S$ to its power set for any set $S$.

Proof

Suppose $S$ is a set with a surjection $f: S \to \mathcal P \left({S}\right)$.

	\(\displaystyle \)	\(\displaystyle \forall x \in S: f \left({x}\right)\)	\(\in\)	\(\displaystyle \mathcal P \left({S}\right)\)	\(\displaystyle \)	By Hypothesis
	\(\displaystyle \implies\)	\(\displaystyle \forall x \in S: f \left({x}\right)\)	\(\subseteq\)	\(\displaystyle S\)	\(\displaystyle \)	Definition of Power Set

Now by the Law of the Excluded Middle, there are two choices for every $x \in S$:

• $x \in f \left({x}\right)$
• $x \notin f \left({x}\right)$

Let $T = \left\{{x \in S: x \notin f \left({x}\right)}\right\}$.

As $f$ is supposed to be a surjection, $\exists a \in S: T = f \left({a}\right)$.

Thus:

• $a \in f \left({a}\right) \implies a \notin f \left({a}\right)$
• $a \notin f \left({a}\right) \implies a \in f \left({a}\right)$

This is a contradiction, so the initial supposition, i.e. that there is such a surjection, must be wrong.

$\blacksquare$

Comment

Compare this with Russell's Paradox.

Source of Name

This entry was named for Georg Cantor.

Sources

• Seth Warner: Modern Algebra (1965): $\S 17$: Exercise $17.14$
• A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 2.5$: Theorem $6$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 14$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $4.11$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.6$: Theorem $\text{A}.6.1$