Cantor's theorem

Lore & Background

Cantor's theorem is named for Georg Cantor, who first stated and proved it at the end of the 19th century. For finite sets, the theorem can be seen 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 applicable to any set, showing the theorem holds for infinite sets as well.

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.' As a specific 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. The proof is elegant: 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.

Did You Know?

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