Georg Cantor proved many theorems, but the one usually called Cantor's theorem is the first nontrivial theorem of Cantor's new set theory: that some infinities are bigger than others; in particular, any infinite cardinal number (or infinite set) generates a larger one by taking the power set.
(The theorem applies to all sets, not just infinite ones, although it's fairly obvious for finite sets.)
Cantor's theorem should not be confused with the Cantor–Schroeder–Bernstein theorem (see cardinal number), which is different (but related, as it is important to justify Cantor's interpretation of his theorem).
Prior to Cantor, people tended to think of infinity (whether they believed in it or not) as an absolute concept: all infinities are equivalent. It had been noticed (by Galileo, for example) that it's possible to give an infinite set a self-injection that is not a surjection; for example, the inclusion of the even integers into the integers by doubling. Thus here are two infinities —the infinity of even integers and the infinity of all integers— that are actually equivalent, even though at first glance it would appear that is smaller.
Cantor showed that such an equivalence fails with the real numbers : no map from to can be surjective (so that is uncountable). His first argument was ad hoc, but he then generalised this with the diagonal argument to show that no map from any set to its power set could be surjective. (This covered the uncountability of , since Cantor found a bijection between and , which we can now regard as an instance of the Cantor–Schröder–Bernstein Theorem.) As there is an obvious injective map (the singleton map) from to , Cantor concluded that the cardinality of the one is strictly smaller than the cardinality of the other.
Cantor's argument, like his whole set theory, was controversial at the time. Those who, like Kronecker, believed that all mathematics should be finite mathematics, considered it meaningless. Even more moderate early constructivists, such as Brouwer and Weyl, found that it had little point. (In particular, it says nothing directly about , since the bijection between and is not constructively valid, although Cantor's original proof that is uncountable can be made to work.)
However, the versions of the theorem stated below are constructively valid, and Theorem is even predicatively valid (as long as one has function sets); modern constructivists generally accept these as theorems. (The interpretation, however, is not so clear.) They are in fact theorems in the internal language of any topos (and Theorem is a theorem in any -pretopos).
(Lawvere's version.)
Given sets and , suppose that there is a surjection from to the function set (also written ). Then every map has a fixed point; that is, for some .
(This generalizes to Lawvere's fixed point theorem.)
Let be any function, and consider the function given by
That is, if one uses currying to interpret as a function from to , then is defined using the diagonal map as
Now suppose that is surjective. Then there must be some element such that . But then
so is a fixed point of .
The presence of the diagonal map here explains why this proof is called the diagonal argument. (This explanation is anachronistic but morally correct.) Lawvere’s proof also explains (in fact generalizes) the ‑ or fixed-point combinator in untyped lambda-calculus, where is a fixed-point for any term .
It immediately follows (even constructively) that if has a self-mapping with no fixed point (such a map is sometimes called a derangement), then no map from to can be a surjection. In fact, we have something slightly stronger than (but classically equivalent to) the failure of to be a surjection: there actually exists an element of that is not equal to any value in the range of . (If has an apartness relation, then you can get an even stronger result for a correspondingly stronger hypothesis on , but that doesn't apply to the versions below.)
Let be the set of truth values, and let be negation. Since has no fixed point, apply Theorem .
Note that although negation doesn't have all of its usual properties in constructive mathematics, is still impossible.
The next version is classically equivalent to the previous version (at least if you check that is inhabited), but not constructively equivalent. (Indeed, unlike Theorem , it apparently has no constructive analogue when is replaced by .) This argument is from Proposition 2.8.8 of Taylor's Practical Foundations (although I don't know if it really originated there).
Let be any function. Define as follows:
If is an injection, then is a retraction of and hence a surjection, which is impossible by Theorem .
Of course, Cantor also proved Theorem , but his proof was not constructive.
We can combine Theorems and into the following even more general statement, taken from D4.1.8 of Johnstone's Elephant.
(Johnstone's version.)
Given a set , its power set cannot be expressed as a subquotient of .
Suppose we had a set , an injection and a surjection . Then the preimage function would be a surjection (because ), as would the image function (because ). Thus their composite would be a surjection , which is impossible by Theorem .
Note that there exists an injection from to , given by the singleton map. So in the arithmetic of cardinal numbers, we have
But as there is no such surjection, there certainly is no bijection, and we have
So we conclude that
That is, each set is strictly smaller in cardinality than its power set.
This interpretation relies on a good relationship between and on the class of cardinal numbers; in particular, the Cantor–Schroeder–Bernstein theorem that is antisymmetric. In constructive mathematics, this relationship is lacking, and it is quite possible for two sets to each be strictly smaller than each other in the sense above. Thanks to Theorem , this is not possible for a set and its power set, but it does mean that the interpretation of as relative size is problematic —indeed almost as problematic as the idea that there are fewer even integers than integers!
Paul Taylor has argued that the essential value of Cantor's Theorem is the lemma, implicit in Cantor's proof, that Bill Lawvere isolated as Theorem . As the main interpretation of Theorem is meaningful only in a specific set-theoretic context (particularly, one where the Cantor–Schroeder–Bernstein theorem holds), it may not survive a ‘revolution’ that overthrows the primacy of that context. But Lawvere's lemma will survive, since it ‘does the work’ while Cantor's theorem ‘takes the credit’. (See Taylor 2009 below for further discussion of ‘Lemmas that do the work and Theorems that take the credit’.)
A theorem analogous to Cantor’s theorem for sets can be formulated for other cartesian closed categories. In particular, one may ask whether it is possible to have a surjection between posets, where the base is not the discrete poset but rather the order .
The answer is there is no such surjection , but this does not follow from a simple application of Lawvere’s fixed-point theorem, where one tries to rule out such by invoking existence of a map that has no fixed point (there is no such poset map !). Nor can we appeal to some crude cardinality argument; for example, if is the ordinal , then is the order (freely adjoin a bottom element to ), which has the same cardinality. So some other proof must be sought.
Proving there is no surjection is an amusing exercise. One line of attack (which internalizes to any topos) may be found here.
Taylor 2009 June 20: On the categories mailing list, Message-ID E1MJ5TV-00066b-BI@mailserv.mta.ca.
On constructivenews, a discussion about Theorem in the case where and are both the set of natural numbers. (Apparently this fails in certain realizability toposes.)
Last revised on September 19, 2021 at 05:21:23. See the history of this page for a list of all contributions to it.