nLab
Cantor's theorem

Cantor's Theorem

Summary

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).

History

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 EE of even integers and the infinity NN of all integers— that are actually equivalent, even though at first glance it would appear that EE is smaller.

Cantor showed that such an equivalence fails with the real numbers RR: no map from NN to RR can be surjective (so that RR 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 SS to its power set 𝒫S\mathcal{P}S could be surjective. (This covered the uncountability of RR, since Cantor found a bijection between RR and 𝒫N\mathcal{P}N.) As there is an obvious injective map (the singleton map) from SS to 𝒫S\mathcal{P}S, 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 RR, since the bijection between RR and 𝒫N\mathcal{P}N is not constructively valid, although Cantor's original proof that RR is uncountable can be made to work.)

However, the versions of the theorem stated below are constructively valid, and Theorem 1 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 1 is a theorem in any Π\Pi-pretopos).

Statements and proofs

Theorem

(Lawvere's version.)

Given sets SS and VV, suppose that there is a surjection from SS to the function set SVS \to V (also written V SV^S). Then every map n:VVn\colon V \to V has a fixed point; that is, n(x)=xn(x) = x for some x:Vx\colon V.

(This generalizes to Lawvere's fixed point theorem.)

Proof

Let f:S(SV)f\colon S \to (S \to V) be any function, and consider the function g:SVg\colon S \to V given by

g(a)=n(f(a)(a)). g(a) = n(f(a)(a)) .

That is, if one uses currying to interpret ff as a function from S×SS \times S to VV, then gg is defined using the diagonal map Δ S\Delta_S as

SΔ SS×SfVnV. S \stackrel{\Delta_S}\to S \times S \stackrel{f}\to V \stackrel{n}\to V .

Now suppose that ff is surjective. Then there must be some element a:Sa\colon S such that f(a)=gf(a) = g. But then

g(a)=n(f(a)(a))=n(g(a)), g(a) = n(f(a)(a)) = n(g(a)) ,

so g(a)g(a) is a fixed point of nn.

The presence of the diagonal map Δ S\Delta_S 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 YY‑ or fixed-point combinator in untyped lambda-calculus, where Y(n)Y(n) is a fixed-point for any term nn.

It immediately follows (even constructively) that if VV has a self-mapping with no fixed point, then no map from SS to SVS \to V can be a surjection. In fact, we have something slightly stronger than (but classically equivalent to) the failure of ff to be a surjection: there actually exists an element gg of SVS \to V that is not equal to any value in the range of ff. (If VV has an apartness relation, then you can get an even stronger result for a correspondingly stronger hypothesis on nn, but that doesn't apply to the versions below.)

Theorem

(Cantor's version.)

Given a set SS, there is no surjection from SS to the power set 𝒫S\mathcal{P}S.

Proof

Let VV be the set of truth values, and let n:VVn\colon V \to V be negation. Since nn has no fixed point, apply Theorem 1.

Note that although negation doesn't have all of its usual properties in constructive mathematics, p=¬pp = \neg{p} is still impossible.

The next version is classically equivalent to the previous version (at least if you check that 𝒫S\mathcal{P}S is inhabited), but not constructively equivalent. (Indeed, unlike Theorem 1, it apparently has no constructive analogue when 𝒫S\mathcal{P}S is replaced by V SV^S.) This argument is from Proposition 2.8.8 of Taylor's Practical Foundations (although I don't know if it really originated there).

Theorem

(Taylor's version.)

Given a set SS, there is no injection from 𝒫S\mathcal{P}S to SS.

Proof

Let i:𝒫SSi\colon \mathcal{P}S \to S be any function. Define f:S𝒫Sf\colon S \to \mathcal{P}S as follows:

f(a)={b:S|(U:𝒫S),i(U)=abU}. f(a) = \{ b\colon S \;|\; \forall (U\colon \mathcal{P}S),\; i(U) = a \;\Rightarrow\; b \in U \} .

If ii is an injection, then ff is a retraction of ii and hence a surjection, which is impossible by Theorem 2.

Of course, Cantor also proved Theorem 3, but his proof was not constructive.

We can combine Theorems 2 and 3 into the following even more general statement, taken from D4.1.8 of Johnstone's Elephant.

Theorem

(Johnstone's version.)

Given a set SS, its power set 𝒫S\mathcal{P}S cannot be expressed as a subquotient of SS.

Proof

Suppose we had a set BB, an injection i:BSi\colon B \hookrightarrow S and a surjection f:B𝒫Sf\colon B \to \mathcal{P}S. Then the preimage function i *:𝒫S𝒫Bi^*\colon\mathcal{P}S \to \mathcal{P}B would be a surjection, as would the image function f:𝒫B𝒫𝒫S\exists_f\colon \mathcal{P}B \to \mathcal{P}\mathcal{P}S. Thus their composite would be a surjection 𝒫S𝒫𝒫S\mathcal{P}S \to \mathcal{P}\mathcal{P}S, which is impossible by Theorem 2.

Interpretation

Note that there exists an injection from SS to 𝒫S\mathcal{P}S, given by the singleton map. So in the arithmetic of cardinal numbers, we have

|S||𝒫S|. {|S|} \leq {|\mathcal{P}S|} .

But as there is no such surjection, there certainly is no bijection, and we have

|S||𝒫S|. {|S|} \ne {|\mathcal{P}S|} .

So we conclude that

|S|<|𝒫S|. {|S|} \lt {|\mathcal{P}S|} .

That is, each set is strictly smaller in cardinality than its power set.

This interpretation relies on a good relationship between \leq and == on the class of cardinal numbers; in particular, the Cantor–Schroeder–Bernstein theorem that \leq 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 3, this is not possible for a set and its power set, but it does mean that the interpretation of <\lt 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 1. As the main interpretation of Theorem 2 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’.)

References

Revised on March 9, 2014 09:35:29 by Toby Bartels (98.23.139.218)