Cantors First Proof

Links to this page
Edit this page
Entry portal
Advice For New Users

The setting

One of the bits of math that we popularisers often talk about is the fact that there is more than one size of infinity. Usually people ignore the fact that there are different types of infinity, and the development of trans-finite arithmetic, but that's OK. The idea is to present something cool, weird, non-intuitive, unexpected, and yet true.

So Cantor's wonderful diagonalisation argument is brought out, along with all the usual consequent problem of "Well, why not just add that new one in?" and other such questions.

But the diagonalisation argument was not Cantor's first proof. It's an example of how the original idea gets honed to its essentials, and presented in its entirety with a hint of the magic trick - "Ta Da! Look - new number!"

I prefer an earlier proof, one that to my mind better lays bare the real reason why any list of real numbers is incomplete. One that doesn't rely on decimal expansions, and one that doesn't have the problem of numbers that end all in 9s being somehow inferior. It also lets one see how given a list of reals we can create not just one missing number, but lots of missing numbers, showing not just that the list is incomplete, but that it's somehow very incomplete.

Cantor's original paper was, ostensibly, showing that there are reals that are not so-called "algebraic" - numbers that satisfy a polynomial equation with integer (or rational) coefficients. I do need to do some homework about the exact and actual paper, but here's my take on it.

Creating a new number

So you have a list of real numbers. We'll construct a number not on that list, but more, it will be clear that we can construct as many as you want.

An interval is a section of the line, all the points between two endpoints, that you can choose. So [ 3/4, 6.5 ] is an interval
So pick an interval, any interval. We'll construct a number in there that's not on your original list. We start by running down your list, crossing off numbers that are outside your interval. There are two possibilities.

The first possibility is that we end up crossing off everything. So that means that everything in your interval is not on your list. That's infinitely many things, and so we're done.

The second possibility is that we reach a number that is in your interval. In that case we choose a smaller interval, inside your original one, but excluding this number we've found. Now everything on your list up to and including this number is outside this new, smaller interval. Now we carry on.

Again, we cross off numbers from your list until we come to one inside the interval. Again, if there isn't one then everything in the interval is not on your list, and hence we're done. But again, if we do find one, we choose a smaller interval to avoid it, and carry on.

So what do we end up with? We get an infinite collection of nested intervals. How does that help?

Look at the left-hand endpoints. They increase, but can't increase forever because they can never go past the right-hand end of the original interval you choose. So let's consider the least possible upper bound of those left-hand endpoints.

We can make the observation that it's inside the first interval you choose. In fact, it's also in the second interval. And the third. Carrying on, we can see that it must be in every interval that we looked at.

But that means it's not the first number on your list. It's not the second either. Or the third. At each stage the numbers from your list were excluded. For every number in your list, at some stage, some interval was chosen that did not include it.

So this least upper bound of the left-hand endpoints is the chosen one - it's a number that wasn't on your original list.

But you promised!

Yes, I promised you lots of numbers not on your list, and not just one. So here's how we can do that.

When you choose an interval to avoid the number from your list, instead, choose two smaller intervals, non-overlapping, both inside, both avoiding the problem number. Then carry on with each of these intervals. Every time choose two intervals.

Now you end up with as many new numbers as you like. You want 100 new numbers? You got 'em after just 7 steps. You want a million? Just 20 steps needed.

So yes, you can get as many new numbers as you want.

Part of the Farrago of Fragments.
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout