Proof
Two sets are equinumerous (have the same cardinality) if and only if there exists a one-to-one correspondence between them. To establish Cantor's theorem it is enough to show that, for any given set A, no function f from A into, the power set of A, can be surjective, i.e. to show the existence of at least one subset of A that is not an element of the image of A under f. Such a subset, is given by the following construction:
This means, by definition, that for all x in A, x ∈ B if and only if x ∉ f(x). For all x the sets B and f(x) cannot be the same because B was constructed from elements of A whose images (under f) did not include themselves. More specifically, consider any x ∈ A, then either x ∈ f(x) or x ∉ f(x). In the former case, f(x) cannot equal B because x ∈ f(x) by assumption and x ∉ B by the construction of B. In the latter case, f(x) cannot equal B because x ∉ f(x) by assumption and x ∈ B by the construction of B.
Thus there is no x such that f(x) = B; in other words, B is not in the image of f. Because B is in the power set of A, the power set of A has a greater cardinality than A itself.
Another way to think of the proof is that B, empty or non-empty, is always in the power set of A. For f to be onto, some element of A must map to B. But that leads to a contradiction: no element of B can map to B because that would contradict the criterion of membership in B, thus the element mapping to B must not be an element of B meaning that it satisfies the criterion for membership in B, another contradiction. So the assumption that an element of A maps to B must be false; and f can not be onto.
Because of the double occurrence of x in the expression "x ∉ f(x)", this is a diagonal argument.
Read more about this topic: Cantor's Theorem
Famous quotes containing the word proof:
“Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
—Henry David Thoreau (1817–1862)
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)
“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (1872–1945)