Cantor's theorem

Lore & Background

For finite sets, Cantor's theorem can be seen to be true by simple enumeration: a set with n elements has 2^n subsets, and 2^n > n for all non-negative integers. Much more significant is Cantor's discovery of an argument that is applicable to any set, showing the theorem holds for infinite sets as well. As a consequence, the cardinality of the real numbers, which is the same as that of the power set of the integers, is strictly larger than the cardinality of the integers.

Reader's Guide

Cantor's theorem had immediate and important consequences for the philosophy of mathematics. By iteratively taking the power set of an infinite set and applying Cantor's theorem, one obtains an endless hierarchy of infinite cardinals, each strictly larger than the one before it. Consequently, the theorem implies that there is no largest cardinal number—colloquially, 'there's no largest infinity.' The proof is elegant and remarkably simple: for any function f from a set A to its power set, the set B = { x ∈ A | x ∉ f(x) } cannot be in the image of f, showing no surjection exists. This argument, sometimes called the Cantor diagonal set, uses reductio ad absurdum to establish the result.

Did You Know?

• Cantor's theorem holds for both finite and infinite sets.
• The cardinality of the real numbers is the same as that of the power set of the integers.
• The theorem implies there is no largest cardinal number.
• The proof constructs a diagonal set B = { x ∈ A | x ∉ f(x) } to show no surjection exists.