We’ll now discuss a classic example of a set which is larger than the set of natural numbers, in the sense that it is infinite but not countable. Such sets are called (sarcastic drum-roll) uncountable. The existence of such sets shows that there really are different sizes of infinity.

### Power

The set which we are going to think about is a large collection of sets, so, a set of sets, if you will. Each element of our big collection will be a set of natural numbers. In fact, I want to consider every possible set of natural numbers, and gather all these sets together in one big collection.

Therefore, our big collection includes, for example, the set containing one, two and twenty and nothing else. The (self-explanatory) notation for this set would be {1,2,20}.  Our big collection also contains sets like {1} and {17}, as well as things like {1,2,3,4,5,6,7} and {,2,40,644,9999}, as well as infinite sets like the set of prime numbers, or square numbers, or multiples of 19 and so forth. It is a vast collection. The set I’m describing is the set of all subsets of the natural numbers and is called the power set of the natural numbers.

Remember that our goal is to see if there are sets which are bigger than the natural numbers. The power set of the natural numbers certainly seems very big, but how does one prove that there is no possible way of bijecting the two sets? (I briefly recapped on bijections in the previous post) It does seem rather unlikely that there is some incredibly clever way of pairing off the elements from these two sets, but we would really like to prove that it cannot be done, not only because this eliminates all doubt, but also because it will hopefully help us to better understand exactly why it’s not possible.

### A ‘Diagonal’ Argument

We’ll now walk through a very famous argument, the original idea for which is attributed to Cantor.

Our argument will follow a standard structure: First we’ll assume that a bijection does exists and then proceeds to deduce a contradiction. So, let’s suppose that for each natural number there is precisely one subset of the natural numbers and that for each subset of the natural numbers there is precisely one natural number. Assume that the elements of our two sets are paired off in such a manner.

It turns out that we are still able to describe a set of natural numbers which isn’t yet accounted for, i.e. a set of natural numbers which is not paired off with any natural number and thus contradicts our hypothesis. Describing this nasty set is our goal now.

To describe our evil set we need to specify which natural numbers are included in it and to do this, we’ll go through the numbers one by one. This is the tricky part. For each number, say five for example, we look at the subset of the natural numbers which it is paired off with (remember, in the bijection there is exactly one subset for each number and the bijection exists because we’ve assumed it exists). Suppose that five is paired off with the set {3,7,9,11,13,15,456,600}. Note that five is not an element of the set {3,7,9,11,13,15,456,600}. Since this is the case, we include five in our evil set. Suppose that six is paired off with {2,4,6,8,66,44544}. Since six is an element of the set which it is paired off with, we do not include it in our evil set.

To summarize, (and here’s where it will sound trickier than it is) the evil set contains all those natural numbers which are not elements of the sets they are paired up with.

Let’s pause to think about what’s going on: We have assumed that there is a bijection between the natural numbers and its power set; this means that each subset of the natural numbers is paired off with a natural number. Then we singled out a particular subset which we’ve called the ‘evil’ set. By assumption, this evil set is paired off with a particular natural number, say n.

Here’s the nice part: Despite all the trickery going on, one of two possibilities must be true: Either n is an element of the evil set, or it isn’t. So, we ask the question, “Is n an element of the evil set?”

Actually, it is ridiculous for the answer to be yes: The evil set consists of those natural numbers which are not elements of the set they are paired off with, and n is paried off with evil set!

So we are forced to conclude that the answer is no. However, this is equally ridiculous because it means that n is not an element of the set that it is paired up with and the evil set consists precisely of those elements!

We have thus reached a contradiction. One possibility must hold and yet neither can! This implies that the assumption we made must be false, i.e. that the bijection never existed in the first place.

### Familiarity

Allow me to run through what we’ve done so far in these posts. We’ve introducted the notion of countability. Remember that a countably infinite set is one which bijects with the natural numbers. An uncountable set is an infinite set which does not. We showed that the square numbers formed a countable set (in fact any subset of a countable set is a countable set). The power set of a set is the set of all subsets of that set. We showed that the power set of the natural numbers is uncountable.

One of the criticisms I have so far is that the power set of the natural numbers seems like a very odd and pathological set. It is perhaps no surprise that one can dream up strange sets to fit one’s purpose, which in this case is that they ought to be large. Although one could go on to explain the hypothesis now (it isn’t difficult) I would like to, in the next post, describe a much more reasonable uncountable set called the real numbers. These numbers are the numbers you get when you construct the number line as we did back here. With that having been done we’ll discuss the hypothesis and why its proof evaded mathematicians for so long.