Cantor's theorem

The statement

In set theory, Cantor's theorem states that the set of all subsets of any set A has a strictly greater cardinality than that of A. In particular, the set of all subsets of a countably infinite set is uncountably infinite.

The proof

The proof is a quick diagonal argument. Let f be any one-to-one function from A into the set of all subsets of A. It must be shown that f is necessarily not surjective. To do that, it is enough to exhibit a subset of A that is not in the image of f. That subset is

${\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}.}$ 

To show that B is not in the image of f, suppose that B is in the image of f. Then for some y in A, we have f(y) = B. Now consider whether y ε B or not. If y ε B, then y ε f(y), but that implies, by definition of B, that y not ε B. On the other hand if it is y not ε B, then y not ε f(y) and therefore y ε B. Either way, we get a contradiction.

Consequences

Most mathematicians are aware that the Hebrew letter ${\displaystyle \aleph }$  (aleph) with various subscripts represents various infinite cardinal numbers, but fewer are aware that the second Hebrew letter ${\displaystyle \beth }$  (beth) also occurs. Let

${\displaystyle \beth _{0}=\aleph _{0}}$ 

be the cardinality of countably infinite sets; for concreteness, take the set N of natural numbers to be the typical case. Denote by P(A) the power set of A, i.e., the set of all subsets of A. Then define

${\displaystyle \beth _{\kappa +1}=2^{\beth _{\kappa }}}$ 

so that

${\displaystyle \beth _{0},\beth _{1},\beth _{2},\beth _{3},\dots }$ 

are respectively the cardinalities of

${\displaystyle N,P(N),P(P(N)),P(P(P(N))),\dots .}$ 

Each set in this sequence has cardinality strictly greater than every set preceding it.

More generally, for limit ordinals κ, we define

${\displaystyle \beth _{\kappa }=\sup\{\,\beth _{\lambda }:\lambda <\kappa \,\}.}$ 

If we assume the axiom of choice, then infinite cardinalities are linearly ordered; no two cardinalities can fail to be comparable, and so, since no infinite cardinalities are between ${\displaystyle \aleph _{0}}$  and ${\displaystyle \aleph _{1}}$ , the celebrated continuum hypothesis can be stated in this notation by saying

${\displaystyle \beth _{1}=\aleph _{1}.}$ 

The generalized continuum hypothesis" says the sequence of "beth numbers" thus defined is the same as the sequence of aleph numbers.