## How We Know What We Know – Diagonal Proof

(This post continues a series that I started writing last year. Click on the “How we know what we know” tag to read those earlier posts. In particular, if you’re not familiar with the concept of proof by contradiction, you might want to read the third post before reading this.)

The idea of infinity is one that has caused a lot of people a lot of trouble, over the years, from theologians asking whether an omnipotent God is capable of creating a stone he can’t lift, to physicist David Deutsch, whose 2011 book The Beginning Of Infinity tries, among other things, to use trans-finite mathematics to prove that Britain’s thoroughly broken electoral system is actually the best possible system.

A lot of these problems come from the fact that we use ‘infinity’ as a number, when in fact it’s no such thing – it’s the place where numbers break down. It’s a placeholder for something that doesn’t exist. Thinking of ‘infinity’ as a number is like thinking of the word ‘person’ as a person – it’s a category error.

Infinity doesn’t behave like a number. If you multiply it by anything, you get infinity. If you add anything to it, you get infinity. If you divide it by anything, you get infinity. If you take anything away from it, you get infinity.

So it should hardly be surprising that the whole idea of talking about ‘infinity’ is wrong. We should, in fact, be talking about infinities.

Because there are infinities of different sizes. This was proved by Georg Cantor in his famous ‘diagonal proof’.

In mathematics, two sets are the same size if there is what is called a one-to-one correspondence between them. So, for example, the set containing all the natural numbers [FOOTNOTE These are the ‘counting numbers’ – one, two, three and so on] is exactly the same size as the set containing all the even numbers, because for every natural number you can assign an even number to it:

1 – 2
2 – 4
3 – 6
4 – 8

And so forth. No matter how far you go, you will always be able to find an even number that is double any natural number, so the set of even numbers is the same size as the set of natural numbers.

The same goes for the odd numbers:

1 – 1
2 – 3
3 – 5
4 – 7

This makes a kind of sense, even though it seems a bit odd. There are only half as many even numbers as there are natural numbers, but half of infinity is still infinity.

But now let’s look at the real numbers. These are all the decimal numbers – 0.5, 1.2548356, and so on. To make it simple, we’ll look just at those decimal numbers that are greater than 0 and less than 1.

We can try to match these up with the naturals, too. It doesn’t really matter what order we match them up in, so long as we can match each one up with a single natural number:

1 – 0.123456… [FOOTNOTE – Here an ellipsis means the number carries on indefinitely]
2 – 0.135468…
3 – 0.954651…
4 – 0.154684…
5 – 0.364548…
6 – 0.584678…

And so on. So far, so good, right? Natural numbers, matched up with decimal numbers.

What Cantor then did was take the first digit of the first number, the second digit of the second number, and so on:

1 – 0.123456…
2 – 0.135468…
3 – 0.954651…
4 – 0.154684…
5 – 0.364548…
6 – 0.584678

This gives, in our example, the number 0.134648…

The clever thing Cantor then did was to add one to each digit (ticking over so that nine becomes zero), getting, in our example, the number 0.245759…

That number is now very interesting, because it does not appear anywhere on the list, no matter how far you go down. Its first digit is different from the first digit of the first number, so it can’t be the first number. Its second digit is different from the second digit of the second number, so it can’t be the second number. The seven-billion-and-sixty-ninth digit, if we continued looking that far, would be different from the seven-billion-and-sixty-ninth digit of the seven-billion-and-sixty-ninth number.

So this number doesn’t appear anywhere on the list. It can’t.

This can only mean one thing – that there are more real numbers between zero and one than there are natural numbers. So some infinities are bigger than others.

For a long time, people thought that Cantor’s proof must be mistaken in some way, that it must be the equivalent of those ‘proofs’ you sometimes see that one equals two, most of which have a division by zero hidden in them somewhere. Surely infinity just meant infinity. The idea of a smaller and a larger infinity (which Cantor labelled “aleph-null” and “aleph-one”) made no sense to anyone. Those who did think about it thought it was mostly a curiosity, rather than a particularly important result.

But then in the twentieth century, Cantor’s argument became the basis of a mathematical proof which completely changed how mathematicians think about what they do, and which in turn led to the invention of the computer. We’ll pick up on that next time…

This entry was posted in computing, science and tagged , , , , , . Bookmark the permalink.

### 5 Responses to How We Know What We Know – Diagonal Proof

1. Richard says:

With maximum pedant mode on:

“There are only half as many even numbers as there are natural numbers…”

except there aren’t because you’ve just proved that there are *exactly as many* even numbers as there are natural numbers.

You might be better off saying “the even numbers are half as *frequent* as the natural numbers” or something like that. :)

• Andrew Hickey says:

Yeah, I was trying to convey the odd counter-intuitiveness of it, and missed. I’ll try to reword it in the book version.

• Richard says:

I do see that.

Good piece otherwise – I’ve always liked the hierarchy of infinities :)

• Gavin Robinson says:

“There are only half as many even numbers as there are natural numbers…”

That is true in a finite sequence. It just stops being true in an infinite sequence. Maybe another case of the verb ‘to be’ causing confusion and we should all start writing in E-Prime.

2. plok says:

Yup, I was gonna say that too. I guess I’ll just add that the idea there’s just as many even numbers as there are even+odd numbers probably gets you to the “counterintuitive” place quite nicely?