Cantor's Theorem

Set Theory · Axiom Academy

The power set of any set is strictly larger than the set itself 1. Statement of Cantor's Theorem Cantor's Theorem: For any set A , the cardinality of A is strictly less than the cardinality of its power set P( A ). In symbols: | A | < |P( A )|. The proof uses a diagonal argument similar to the one showing the reals are uncountable. We show that no function from A to P( A ) can be surjective. Suppose f: A → P(A) is any function. We construct a subset B ⊆ A that is not in the range of f . For each element x in A , we ask: "Is x a member of the set f(x) ?" We put x into B if and only if the answer is "no." Therefore, B is a subset of A that is not equal to f(a) for any a , proving that f is not surjective. 3. The Infinite Hierarchy of Cardinals Applying Cantor's Theorem repeatedly creates an infinite sequence of strictly increasing cardinalities. Starting from the natural numbers, we can construct infinitely many different sizes of infinity. Each level in this hierarchy is obtained by taking the power set of the previous level. This process never terminates, showing that there is no bound on how large sets can be. 4. Implications for Mathematics Cantor's Theorem has profound implications for the foundations of mathematics. It shows that the universe of sets is inexhaustibly rich, with infinitely many distinct sizes of infinity.

This is the written version of the interactive lesson above. See the full Set Theory course.