Cardinality, Cantor Diagonalization

Cantor Diagonalization

Cantor (<biography>) stunned the world with this simple, elegant proof.  This is a generalization of the diagonalization argument seen earlier.

Let S be any set and let T be the power set of S.  We know that S maps into T.  Every x in S maps to the set containing x in T.  But there is no bijection mapping S onto T.

Suppose f is such a bijection and build a set W as follows.  For every x in S, x is in W iff x is not in f(x).  Now f maps S onto all of T, and W is a subset of T, so there is some x with f(x) = W.  Yet x ∈ W iff x ∉ W.  Therefore the correspondence cannot exist.

The power set of S is always larger than S.  Keep taking the power set, and the flavors of infinity go on forever, each larger than the previous.