proof of Cantor’s theorem


The proof of this theorem is fairly using the following construction, which is central to Cantor’s diagonal argument.

Consider a function F:X→𝒫⁢(X) from a set X to its power setMathworldPlanetmath. Then we define the set Z⊆X as follows:

Z={x∈X∣x∉F⁢(x)}

Suppose that F is a bijection. Then there must exist an x∈X such that F⁢(x)=Z. Then we have the following contradictionMathworldPlanetmathPlanetmath:

x∈Z⇔x∉F⁢(x)⇔x∉Z

Hence, F cannot be a bijection between X and 𝒫⁢(X).

Title proof of Cantor’s theorem
Canonical name ProofOfCantorsTheorem
Date of creation 2013-03-22 12:44:55
Last modified on 2013-03-22 12:44:55
Owner Wkbj79 (1863)
Last modified by Wkbj79 (1863)
Numerical id 7
Author Wkbj79 (1863)
Entry type Proof
Classification msc 03E17
Classification msc 03E10