Proving Cantor’s Theorem

“No one will drive us from the paradise which Cantor created for us” — David Hilbert

What better way to spend in isolation than to ponder the infinite? Let’s prove perhaps the simplest and most elegant proof in mathematics: Cantor’s Theorem.

I said simple and elegant, not easy though!

Part I: Stating the problem

Cantor’s theorem answers the question of whether a set’s elements can be put into a one-to-one correspondence (‘pairing’) with its subsets. (Technically speaking, a ‘bijection’). This sort of problem is to do with a mathematical concept called ‘cardinality’. We can view a one-to-one correspondence as some sort of set-theoretic mathematical dating: we want every element in the set to find its romantic match in another set, but want to avoid polygamy, and we want to avoid mathematical objects being single.

For instance, the set {1,2,3} has 3 elements: 1, 2, 3.

It has 8 subsets: {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {}, {1,2,3}

where {} is known as the ‘empty set’. You can ignore it happily for now if it makes you uncomfortable: it won’t be important. Alternatively, view the above as three balls numbered 1,2,3 and the subsets as the different ways you can put balls in a small sack. One thing you can do is put nothing in the sack: the empty set.

So far, so *easy*. After all, for finite sets this turns out to be quite obvious. If a set has N elements, then the set of subsets has 2**n elements. In the above the set {1,2,3} has 3 elements, and the set of subsets (it’s a mouthful and confusing to read, but look at the example to unconfuse yourself!) has 8 elements. 8 = 2*2*2 = 2**3 as I promised.

***The statement ‘the set of subsets’ can be a bit daunting. To feel a bit more comfortable, first assure yourself that a subset is a sensible mathematical object. If I have some mathematical objects, I can group some of them together and leave others out. You can view the original set as all your football players, and the set of subsets as all potential teams you can make from those players, of any size. When we get to an ‘infinite’ number of players, things can get a little harder to conceptualise, but the basic idea is the same.***

But Cantor had set his sights bigger. What about sets with an infinite number of elements? Can we compare the size of two sets with an infinite number of elements? (Spoiler: yes.)

Step II: The Proof

Cantor supposes that you have found a pairing which works.

That is, you have a function, which you put in an element of a set, and the output is a subset. Not only that, but for every subset you can point to an element which gets ‘mapped’ or ‘sent’ by the function into that subset. Also, no two elements get sent to the same subset.

In the example above, someone might propose the function which sends 1 to the set {1}, 2 to the set {2,3} and 3 to the set {1,2}. But nothing is sent to {1,2,3} so clearly this doesn’t work.

To generalise this, Cantor asks us to consider ‘the set of elements which are not contained in the subset they are mapped to’. E.g., in the above 3 is sent to {1,2} but 3 isn’t in {1,2} so fits the criterion nicely.

In our mathematical set-theoretic dating function, this set, too, needs a partner. But who can be this set’s partner? If an element is sent to this set, then if it is contained in that set then it cannot be. (i.e. a contradiction). Why? Because it is then contained in the subset of elements it was mapped to! What about if it is not in that set? Then that too is a contradiction, as if it is not in the set, by the definition of the set, it must be in the set because it is not contained in the subset it is mapped to.

And so Cantor’s black magic is done. By assuming our magical mathematical dating function worked, we found an example where it couldn’t work.