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:
We'll proceed as follows:
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.
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.
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"?
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).
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."
Building a sequenceLet's look at the section of the number line between 0 and 1. Divide it into three equal pieces, and ask:
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'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:
You can comment on this article on Hacker News: Trapping a Transcendental
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?