Trapping A Transcendental

In particular, I gave the example of the real numbers, and how they can be regarded as a natural step in the process of wanting to answer questions. The discussion progressed from the counting numbers (also called "Natural Numbers") through the integers, the rationals, the algebraic numbers and then finally the so-called "Real Numbers." At each stage we added new numbers because the ones we had were insufficient to answer the next type of question.

Here's a brief summary:

We claimed that the last of these needed numbers that "transcend" the algebraic numbers. Indeed, we called them "Transcendentals" and claimed that once we had them, we were done.

But there are two obvious concerns:

• Maybe the algebraics are enough already,
• Even if they aren't, once we have the transcendentals,
  is that really everything?

We'll proceed as follows:

• First, we need to know more about the algebraics so we can avoid them.
• Then we need to know what we mean by "a sequence that looks like it should converge."
• Finally, we need to build such a sequence, avoiding the algebraics.

The Algebraic Numbers

where a, b, c, d, e and f are all integers. (Note that the RHS is always 0, the largest power of x (called the "degree" of the polynomial) is always at least 1, and the coefficient of the largest power must be positive.)

There's an interesting thing about equations like that: we can list them all.

To see how to do that we talk about the "mass" of a polynomial. The "mass" of a polynomial is the sum of the highest power and the absolute value of all the coefficients. So the "mass" of the equation 3.x^2-5.x+12=0 is 2+3+5+12, which is 22.

What are the polynomials of mass 1? The degree must be at least 1, so we have ax^1+b=0. The mass is 1+abs(a)+abs(b), so abs(a)=0. But the leading coefficient must be positive, so there are no polynomials of mass 1.

Some terminology: we are talking about polynomials, p(x). When we talk about "a solution" we mean "a value of x that makes the polynomial have value 0." This is also called a "root" of the polynomial. Thus the polynomial x^2-4 has roots +2 and -2, and the equation x^2-4=0 has solutions +2 and -2. They're saying the same thing.

How many polynomials are there of mass 2? If the degree is 2 then all the coefficients must be 0, and that's no good because the first coefficient must be positive. So the degree must be 1. That leaves us with just 1 for the leading coefficient, so we have 1.x+0=0. There is just one polynomial with mass 2, and because there is only one solution, it gives us just one algebraic: x=0.

Mass 3?

• 1.x^2+0.x+0=0 giving x = 0
• 1.x+1=0 giving x = -1
• 1.x-1=0 giving x = 1
• 2.x+0=0 giving x = 0

From now on we'll follow convention and omit the coefficient if it's 1.

And so it goes on. Each mass has only a finite collection of associated polynomials, so that means we can start with mass 2, then 3, then 4 and so on, and write down all the polynomials.

Then next to each polynomial we can write down the solutions. Some, like x^2+1=0 (mass 4) have no solutions in the reals, others have several, but a quick sketch of a polynomial shows that for degree n there are at most n solutions.

In complex numbers there is a theorem that says a polynomial of degree n has exactly n solutions, although some of those solutions might be repeated.

But these solutions are the algebraic numbers, so we now have a method of writing down all the algebraic numbers. Obviously it would take some time to write them all down, but for any given algebraic number it's guaranteed that it will turn up eventually in a finite amount of time.

So let's label them "first," "second," "third," and so on. Every algebraic number gets a place in line.

We have listed all the algebraics. How does that help?

What does it mean for a sequence to "converge"?

• Can we find a sequence that looks like it should converge, but which doesn't converge to any algebraic?

So what does it mean to say that a sequence "looks like it should converge"?

For our purposes we don't need to answer that question in full generality. We only need to look at a specific type of sequence.

If you take a sequence of numbers that never, ever get smaller, then there seem to be two options. Either the numbers get bigger without limit, or there must be some number they never get past. In this second case the numbers must sort of "pile up" somewhere. So a sequence of numbers that never gets beyond some value must, in some sense, have a limit.

Let's take an example:

These numbers are always getting bigger, but the number on top is always smaller than the number on the bottom. That means that the numbers in the sequence never get to, and certainly never exceed, 1.

Let's try another:

The rule here is that if we have a/b, the next pair is (a+2b)/(a+b). They bounce around a bit, so let's just use the ones in red:

In this case it's harder to tell, but some algebra will show that these numbers always increase. Further, we can show that they're never going to get to 100. In fact they don't exceed 2, but even that's not the lowest possible bound. We can show that they never exceed sqrt(2).

This is not the technical definition of "convergent," but it's clear that a sequence like this "looks like it should converge." In fact it satisfies the technical definition - it's just not as general.

So we have a sequence that always gets bigger, (or at least, never gets smaller!) but which is bounded above. We would like to say that such a sequence approaches a limit, and thus we say it converges to a limit.

So now our mission is clear. Can we find a sequence that is always increasing, which has an upper bound, and yet which doesn't converge to an algebraic number?

Armed with our list of algebraics, the answer turns out to be "Yes - we can."

What are the algebraics? Roots of polynomials We can list them What sequences should converge? Non-decreasing sequences with an upper bound The limit is the least upper bound Now: Build a sequence

How?

Building a sequence

It might be in none of them, it might be in the interior of one of them, it might be on the border between two of them, but it certainly can't be in all three. Choose the left-most piece that does not contain the first algebraic.

If from now on we stay inside that chosen piece then we are forever separated from that first algebraic, and so that first algebraic certainly cannot be the limit of our sequence.

Now divide that piece into three, and ask: Where is the second algebraic? Again, it might be in none of them, it might be in the interior of one of them, it might be on the border between two of them, but it can't be in all three. Choose the left-most piece that does not contain the second algebraic.

If we stay inside that chosen piece then we are forever separated from the second algebraic, and so the second algebraic certainly cannot be the limit of our sequence.

And now repeat.

We end up with a collection of intervals, each 1/3 the size of the one before, each non-empty, each with endpoints that are rational numbers, and each one does not contain the algebraics considered so far. The left points of these intervals form an increasing (technically non-decreasing) sequence of rationals, and the right most points form a decreasing (again, technically, a non-increasing) sequence. The two sequences get closer and closer, never quite meeting, but getting as close as you like.

But in particular the left-most points form a sequence a rationals that never decrease, and which are bounded above.

We can show that the least upper bound is also the greatest lower bound of the right-most points. In some very real sense, the limits are the same, and lie in the intersection of all the intervals.

What is the least upper bound?

We'd like it to be something. If you specify a small number then eventually it's possible to cover all subsequent intervals with a coin of that size. The points in each sequence look like they ought to converge, we'd like to say they converge, but they certainly can't converge to an algebraic. Any given algebraic is eventually excluded, so no algebraic can lie between the endpoints.

We have constructed a sequence (actually two) that looks like it should converge, but which doesn't converge to an algebraic.

There must be more than just the algebraics.

And thus we have proved that the algebraic numbers are not everything, and there are, indeed, transcendentals.

Comments and further reading

This piece is essentially the same as Cantor's first proof from 1874 that the reals are uncountable. He didn't phrase it like that, and he published it under the title "On a Property of the Collection of All Real Algebraic Numbers."

This proof simply shows that there are transcendentals, but the proof works to avoid any countable collection. Thus if you claim the reals are countable, then you can list them, then you can use nested intervals to create a limit, and that limit is not in the list of numbers you have. Therefore any countable list of reals is incomplete.

You can read more about that here:

• http://rjlipton.wordpress.com/2009/04/18/cantors-non-diagonal-proof/

• http://en.wikipedia.org/wiki/Georg_Cantor
• http://www-history.mcs.st-and.ac.uk/Biographies/Cantor.html

You can comment on (and find) the earlier article here: Some Musings On Mathematics

This is what started it all: Are The Reals Really Uncountable?