Cantor's theorem

In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A (the power set of A) has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can be seen to be true by a much simpler proof than that given below. Counting the empty subset, subsets of A with just one member, etc. for a set with n members there are 2ⁿ subsets and the cardinality of the set of subsets n < 2ⁿ is clearly larger. But the theorem is true of infinite sets as well. In particular, the power set of a countably infinite set is uncountably infinite. The theorem is named for German mathematician Georg Cantor, who first stated and proved it.

Proof

Two sets are equinumerous (have the same cardinality) if and only if there exists a bijection (a one-to-one correspondence) between them. To establish Cantor's theorem it is enough to show that, for any given set A, no function f from A into the power set of A, can be surjective, i.e. to show the existence of at least one subset of A that is not an element of the image of A under f. Such a subset is given by the following construction, sometimes called the Cantor diagonal set of f: