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
Though it is called "Cantor's Theorem", Cantor never gave a proof in precisely this form. His first proof of the non-denumerability of the reals was was written in 1873 and published in 1874 (see Cantor's first uncountability proof). This does not resemble the theorem at all.
In a famous paper published in 1891 ("Ueber eine elementare Frage der Mannigfaltigkeitslehre"), where the diagonal proof first appears, there is a another proof later in this paper, where he notes that if f is a function defined on X whose values are 2-valued functions on X, then the 2-valued function G(x) = 1 − f(x)(x) is not in the range of f.
Russell has a very similar proof in Principles of Mathematics (1903, section 348, where he shows that that there are more propositional functions than objects. "For suppose a correlation of all objects and some propositional functions to have been affected [sic], and let phi-x be the correlate of x. Then "not-phi-x(x)," i.e. "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value of x." He attributes the idea behind the proof to Cantor.
Ernst Zermelo has a theorem (which he calls "Cantor's Theorem") that is identical to the form above in the paper that became the foundation of modern set theory ("Untersuchungen über die Grundlagen der Mengenlehre I"), published in 1908. See Zermelo set theory.
For one consequence of Cantor's theorem, see beth numbers.The proof
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.History