## Thursday, November 1, 2012

### Cantor's diagonal argument.

I wrote an article about this following a discussion with a friend and my kids, but I seem to have lost it so I am writing it again.

Cantor's diagonal argument is a neat piece of mathematics that is very easy to understand, and important in understanding how to deal with counting things that are not finite.

The counting (or natural) numbers are the numbers we use to count things in the real world: $$1, 2, 3, \dots$$ In this article we will exclude zero from the counting numbers, but nothing essential changes if you chose to include it.

The counting numbers provide answers to questions "how many $$x$$ are there?" for any finite $$x$$. What does "finite" mean? It means that given some collection of things, if we had enough time we could count them all using the counting numbers. Of course there are large finite numbers for which it is impractical to actually perform the counting - we'd die before we had finished, but that is a detail that isn't important.

Note that there are a few important characteristics of  performing a count. Firstly we start at one, and use the numbers in sequence; we only use each number at most once, and we only count each item once. Another way of thinking about this is that we provide a one-to-one correspondence between all of the counting numbers up to some maximum, and the collection of items to be counted. That is - we have a rule that allows us, in theory at least, to uniquely identify a counted item from one of the counting numbers below the maximum, and also to uniquely identify a counting number given one of the counted items.

To help us along the way in that which follows I'll use a bit of jargon. The size of any collection of items is called its "cardinality". For finite collections the cardinality is simply the size of the collection, that is: the counting number that we get to when we perform a count. Clearly when the cardinality of some collection is given by some counting number, say $$n$$, then it is a finite collection. Its size is given by a specific, finite, counting number.

So far, so good. What happens if we try to count something that is not finite? For example the counting numbers themselves. Clearly we have a problem - for any counting number there is a bigger one - we can just add one to it. If we try to perform a count we will never get to the end, however much time we allow. However we can make a one-to-one correspondence with the counting numbers and themselves, if we forget about the "up to some maximum" bit in the previous paragraph. In a sense this is pointless - we're answering the question "how many counting numbers are there?" by saying: "the same as the number of counting numbers", so we have not made progress. But we can at least give this a name, and  ask whether other infinite collections have the same cardinality. The traditional name for the cardinality of the counting numbers is $$\aleph_0$$. ($$\aleph$$, or "Aleph" is the first letter of the Hebrew alphabet.)

One thing that is clear is that the cardinality $$\aleph_0$$ is a different thing that a cardinality of $$n$$ for any counting number $$n$$, in other words the cardinality of counting numbers is not finite.

Let us consider a couple of other sets that are clearly infinite. The even counting numbers are clearly infinite. For any even counting number we can simply add two - so any attempt to assign a finite cardinality to the even counting numbers is doomed to failure. So instead let us think about establishing a one-to-one correspondence between the even counting numbers and the counting numbers. The obvious thing is to double going one way and to halve going the other. This fits well with our description of a one-to-one correspondence. Every counting number $$n$$ uniquely determines an even counting number $$2n$$ and every even counting number $$2m$$ uniquely determines a counting number $$m$$. So we can say that the cardinality of the even counting numbers is $$\aleph_0$$ - in other words it is the same as the cardinality of the counting numbers.

But wait! Obviously there are "more" counting numbers than there are even counting numbers, I hear you say... are there not? Clearly $$1$$ is a counting number but it is not an even counting number. The trouble here is that intuition about finite collections does not always work exactly as we might expect when we are dealing with infinities.

Part of the problem is that we are so used to our traditional names for the counting numbers that the labels have assumed more importance that they really warrant. Suppose you are learning a new language (forgive the apparent non sequiter things will become clear shortly). You learn that the word for one is "un", for two is "deux", for three: "trois" and so on. So you can count things in your newly learned language by the usual method of assigning counting numbers in sequence uniquely to each member of the collection that you are counting. You have done this with a few collections and establish the the cardinality of collection A is "trois" and of collection B is "un" for example.  But then you are informed that the textbook you were using to learn your new language is in error - "trois" is actually the translation of the number 6, "un" is the translation of the number 2. But has anything essentially changed about the cardinality of the sets? Not really. As far as establishing cardinality goes the only thing that really matters is a one-to-one correspondence with the counting numbers (or any other set equipped with a starting point and a way of getting a new successor from each subsequent element).

So if you can accept this we can go on to figure out that there are lots of subsets of the counting numbers that have the same cardinality - $$\aleph_0$$. There are some supersets that have the same cardinality. Consider the set of positive and negative integers (including zero). As well as the counting numbers we have their negations. But we can still make a one-to-one correspondence with the counting numbers. For example for any counting number $$n$$ go to $$\frac{-1^n . n}2$$ rounding the division towards zero. To go the other way for even numbers simply double and for odd numbers multiply by $$-2$$ and subtract $$1$$. So the integers have the same cardinality as the counting numbers.

It turns out that the rational numbers also have the same cardinality as the counting numbers. I will not spell out all the details here, but to give you a flavour of how it works - consider the positive rational (nothing essential changes if we include negative ones two), arranged in a series of rows - the first row contains all the rationals with 1 as a denominator, the second with two as a denominator and so on. We then start counting in the top left corner of our grid and proceed down the diagonal immediately adjacent to this, then up the next diagonal, down the following one and so on. Some of the numbers we come across will simplify to ones we have already encountered - we simply skip them when counting. It should be clear that this process gives us a one-to-one correspondence with the counting numbers.

At this point we might start to wonder whether there is any infinite collection of numbers that does not have cardinality $$\aleph_0$$. There is a neat argument, originally due to Georg Cantor, that shows that there cannot be a one-to-one correspondence between the irrationals and the counting numbers.

To simplify things we'll just consider the irrationals between 0 and 1. If we can show that they have a larger cardinality than the counting numbers then certainly all the irrationals must be at least as large. So we can construct a list of irrationals in the order implied by this correspondence. Consider the infinite decimal expansions of each of the numbers in the list (just add zeros if need be). Now start with the first number and take the first digit, now add one to that digit modulo 10. From the second number take the second digit and do likewise and continue on through the list making a new number from the resulting digits.

By construction this number differs from each number in the list in at least one digit - therefore it is not in our list and so the assumption that our correspondence included all irrationals in the specified range is false, so there cannot be such a correspondence (since we assumed nothing about the correspondence other than its existence).

The cardinality of the irrationals is known as $$\aleph_1$$, and it's a different cardinality than $$\aleph_0$$ and clearly not finite. In fact it is obviously "larger" than $$\aleph_0$$ - the method of construction in the argument above illustrates that there are more irrationals than counting numbers, however you try to construct a one-to-one correspondence.