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.