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 is clearly larger (2ⁿ > n). 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.

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:

This means, by definition, that for all x in A, x ∈ B if and only if x ∉ f(x). For all x the sets B and f(x) cannot be the same because B was constructed from elements of A whose images (under f) did not include themselves. More specifically, consider any x ∈ A, then either x ∈ f(x) or x ∉ f(x). In the former case, f(x) cannot equal B because x ∈ f(x) by assumption and x ∉ B by the construction of B. In the latter case, f(x) cannot equal B because x ∉ f(x) by assumption and x ∈ B by the construction of B.

...
Wikipedia