For extra craziness: you can extend the list argument to list all (finite) programs that produce increasing but bounded sequences. We'll call this the computable numbers. The transcendental number described in the article is computable.
But as I've just mentioned, the computable numbers are still countable. This really hurts my head. There's an uncountable set of numbers that aren't expressible in any closed form whatsoever.
Continuous numbers get weirder the harder you look at them.
Problem there is you have to list all finite terminating programs that produce increasing bu bounded sequences. Then you start to have to worry about being really, really careful in your definitions. See here:
That's a classic "paradox" being created by having insufficient care in the definitions.
But yes, most (in a technical sense) reals can't be described or computed, and yes, the reals get more and more weird the harder you look at them. In some sense you never really understand them, you just get used to them.
I don't see the problem here. It shouldn't be a surprise that listing the computable numbers is itself uncomputable as it is equivalent to the halting problem - to determine whether an algorithm will either keep on producing new decimals or halt at some point is clearly undecidable.
It's when you introduce things as constructible/defineable numbers that things gets hairy.
I've found at least one typo in this, there may be more. Before I fix it, what's the easiest way (other than BitCoin) to offer a reward to people who find errors?
Normally I wouldn't look for such things, but since you mention it, there is a period missing at the end of the bullet point "Then we need to know what we mean by "a sequence that looks like it should converge""
Also, at the end of "Later: Build a sequence"
In later bullets too: "We can list them", for example.
I wouldn't normally worry about every last detail of punctuation, especially in lists and/or bullet points, but your comment is perfectly valid, and of value.
Typo: "because there is only one soution" (should be "solution"). I don't like coffee, but you're welcome to buy me a glass of tap water the next time we meet :-).
Just be grateful. I don't think anyone here wants anything for trivial corrections, the fact that you posted an interesting article is more than enough fish for us to eat.
Except that where possible, I use this as an opportunity to meet interesting people. And it's not a question of people wanting anything in return for such corrections, it's more, for me, the point that I'm delighted when someone will interact with and actually help to improve the material.
You might be right, but I still find it very very odd.
Sadly, not everyone has a tarsnap account to which a bounty can be so credited. But nice try.
On a different note, I'd be interested in your comments on this item (and others). If you would care to email me your thoughts I'd be grateful. I could even credit your tarsnap account ...
Describing the sequence at the end as something that seems like it should converge is a bit unconvincing -- it's a sequence explicitly defined not to land on an algebraic number. So the argument is that if you assume you can always pick an interval that doesn't contain a specified algebraic you won't land on an algebraic. This is hardly surprising and kind of presupposes the result.
And why divide the interval into thirds? This seems to be a result of confusing a different Cantor proof (that the measure of the rationals/algebraics in [0,1] is zero, which involves dividing things into thirds) with the first proof. If we accept the argument at all I don't see how it requires three intervals at each step. At most one interval can contain the posited nth algebraic, so you've always got the other interval.
So it's like a mixture of two badly remembered proofs :-)
> So the argument is that if you assume you can always pick an interval that doesn't contain a specified algebraic you won't land on an algebraic.
No, the argument is that there is a sequence that converges to some real number, but that real number is not algebraic, hence there exist non-algebraic real numbers. I do agree that the article doesn't clearly describe how to construct said sequence - perhaps the second page of [1] will be clearer.
Basically we always have an interval (a_n, b_n) where the a_n and b_n are algebraic, and we keep narrowing the interval by going down the list of algebraic numbers until we find two numbers x and y such that a_n < x < y < b_n; then (x, y) is the new interval. The sequence of the a_n converge but not to an algebraic number, because if it did, that number would eventually become an endpoint of the sequence, which is a contradiction.
> ... the article doesn't clearly describe
> how to construct said sequence ...
I thought the construction was clear. In particular, this argument does not use Cantor's construction wherein the interval end-points are always algebraics. Instead, it ...
* Finds the next listed algebraic a in the current interval,
* divides the current interval into three, and
* chooses the left-most sub-interval that neither contains nor touches a.
The sequence is then the left-most endpoints of the intervals. In particular, the sequence is composed entirely of rationals. More, the argument works even if the set being avoided (which must be countable, but need not be the algebraics) is not dense.
The proof constructs a monotone bounded sequence. It thus converges. Dividing into three intervals is to rule out the case where both (closed) intervals contain the point.
You're right, there isn't, but when you use open intervals you'd be surprised how many people get worked up over the fact that some of the points have been omitted. It's easier to avoid the question entirely. It tends only to be people who already know a lot about this that come up with the objections or comments you're making, and usually they realise that actually, yes, it all works.
> There are two well-known arguments from Cantor:
> http://en.wikipedia.org/wiki/Cantor's_first_uncountability_p...
> http://en.wikipedia.org/wiki/Cantor's_diagonal_argument
Yes. And in fact the first uncountability proof comes in two flavours. This is explicitly a re-casting of those two versions of Cantor's first proof.
More explicitly, one version of Cantor's first proof has you list the algebraics, take an interval, find the first two algebraics a and b in the interval, reduce the interval to [a,b], and continue. This has various technical issues. What if there aren't two algebraics in your interval (although there always will be, because they're dense, but the argument goes through for any list, not just algebraics, so we need to consider this possible eventuality if we're using the full generality.) What if the interval doesn't converge to be of length zero? (Which again, for the algebraics, it always will. And again, if we use the argument in general we need to allow for this.) And so on.
The second version of Cantor's first proof avoids some of this by saying: find just the first algebraic in the interval, then choose a smaller sub-interval that avoid it, any carry on. Again, for algebraics the interval will go to length zero, but for a general list that won't necessarily be the case.
> Describing the sequence at the end as something that seems like
> it should converge is a bit unconvincing -- it's a sequence
> explicitly defined not to land on an algebraic number. So the
> argument is that if you assume you can always pick an interval
> that doesn't contain a specified algebraic you won't land on an
> algebraic. This is hardly surprising and kind of presupposes
> the result.
I think you've mis-read the argument. We produce a succession of nested intervals. For a given algebraic, eventually every interval will not include it. That means that no algebraic is in more than finitely many intervals.
The we consider the left end-points. That's an increasing sequence that's bounded above. The reals are complete, so that sequence must converge. But by construction the limit can't be an algebraic.
The comment that the sequence "seems like it should converge" is pointing out that completeness is one of the things we expect of the number line, and it's a way into giving that concept a technical meaning.
> And why divide the interval into thirds? This seems to be
> a result of confusing a different Cantor proof (that the
> measure of the rationals/algebraics in [0,1] is zero, which
> involves dividing things into thirds) with the first proof.
No, it's a way of being explicit in the choice of the sub-interval. I sometimes use fifths. In that way I can discard the end sub-intervals, discard any sub-interval that touches or contains the given algebraic, and thus the end-points are strictly increasing, and not just increasing. I didn't do that here, and you make me wonder if it's worth changing it, so people don't (incorrectly) make the connection with Cantor dust.
But no, this isn't confusing the construction of Cantor dust.
> If we accept the argument at all I don't see how it requires
> three intervals at each step. At most one interval can contain
> the posited nth algebraic, so you've always got the other interval.
The algebraic may be on the boundary, rather than in an interior.
> So it's like a mixture of two badly remembered proofs :-)
With respect, your comments seem like they are generated from an insufficiently careful reading, filtered through an understanding of the existing explanations. It feels like you know about this material, and were assuming this is a simple re-hash.
But I could be wrong. Your comments might have substance that I haven't recognised. If that's the case I'd be delighted if you could expand more on why you think the article is wrong or misleading.
> We produce a succession of nested intervals. For a given algebraic, eventually every interval will not include it. That means that no algebraic is in more than finitely many intervals
Going back over the post -- this number only "exists" because of the least upper bound axiom.
You're right that I probably didn't read it carefully enough but there's no particular reason why the intervals need share any elements (e.g. [0,0.5) [0.5,1]) or contain their boundary points -- we got division and < from the rationals without violating anyone's intuition.
Personally, I've always found these arguments unsatisfying. The proof is of the "existence" of something but in the end we have no idea what it looks like -- is it >0.5? No clue. And the proof relies on an existence axiom that seems contrived. (I guess at heart I'm a constructivist.) The desire for "completeness" flows from a false intuition of the nature of the world -- the surface of this table is a "continuum" right? But it turns out not to be. In contrast, I really liked the discussion of the Reals linked yesterday which sidetracked into a robust description of the Reals with infinitesimals (and infinites) and no, I repeat no, least upper bound axiom.
> in the end we have no idea what it looks like -- is it >0.5? No clue.
No, that isn't true. The proof Colin gives is quite explicit. There's an explicit listing of the algebraic numbers (except that he leaves the order of various things unstated; for present purposes I'll just work with the order of appearance in his writeup). Then there's a procedure that considers these one by one and chooses intervals of exponentially decreasing size to concentrate on. You can get as many decimal places as you like of the transcendental number Colin's constructing, just by doing enough steps.
Let's be more explicit. The first algebraic numbers in Colin's list are 0, 0, -1, 1, 0. (I assume we aren't counting repeated roots of a single polynomial, but also aren't eliminating duplicates between different polynomials in the list.)
So, first we take the intervals [0,1/3], [1/3,2/3], [2/3,1] and the algebraic number 0. We take the leftmost interval not containing 0, namely [1/3,2/3].
Now we subdivide into three again: [1/3,4/9], [4/9,5/9], [5/9,2/3]. And again our algebraic number is 0. The leftmost interval not containing 0 is [1/3,4/9].
(So we've already established that the number is < 0.5.)
In the next three steps we never see an algebraic number inside our interval so we'll just take the leftmost third each time; so we get [1/3,1/3+1/243].
We've now found the first two decimal places of the transcendental number we're constructing, namely 0.33. It would (at least in principle) be easy to computerize the process and find many more decimal places.
> this number only "exists" because of the
> least upper bound axiom.
The whole point of this article is to show that any countable list (because although it does do it specifically in the context of the algabraics, it works for any list) does not contain all the reals. In doing so we have to have some definition of the reals, and this article is, in an unspoken manner, using the definition to be "The Completion of the Rationals." In this context, "completion" means "closure under the taking of Cauchy Sequences", which in turn is equivalent (in the context of the rationals) to be the existence of the least upper bound for every bounded, non-decreasing sequence.
In this sense, the existence of the least upper bound isn't an axiom, it's a definition of the closure.
> ... there's no particular reason why the intervals need
> share any elements (e.g. [0,0.5) [0.5,1]) or contain
> their boundary points ...
We avoid all concerns about whether the intervals are open, closed, contain their end-points, etc., by using three sub-intervals. It side-steps all the necessary detail of who has the end-points. Other choices are equally valid and can be made to work. I don't see why any of them are easier or better than the one made here. You may not share my opinion on that.
> ... we got division and < from the rationals without
> violating anyone's intuition.
?
> Personally, I've always found these arguments unsatisfying.
> The proof is of the "existence" of something but in the end
> we have no idea what it looks like -- is it >0.5? No clue.
We have. I gave an explicit method of enumerating the algebraics, and we can use that to construct this non-algebraic explicitly. Not that that's the point - the real point is that nearly every (real) number is non-algebraic. Indeed, nearly every real number is non-constructable, non-computable, and, in a very real sense, non-visualisable.
> And the proof relies on an existence axiom that seems
> contrived. (I guess at heart I'm a constructivist.) The
> desire for "completeness" flows from a false intuition
> of the nature of the world -- the surface of this table
> is a "continuum" right? But it turns out not to be.
My experience is that most people think of the line as being "complete," and in that sense this seems to match the intuition of most people. However, maybe this doesn't match your intuition, or the way your think. That's fair enough.
More, though, if you have the rationals, you don't have limits of Cauchy Sequences. That alone would be enough to talk about the "missing numbers," and that doesn't really use the line at all.
> In contrast, I really liked the discussion of the Reals
> linked yesterday which sidetracked into a robust description
> of the Reals with infinitesimals (and infinites) and no,
> I repeat no, least upper bound axiom.
It's easy enough to construct the reals as an abstract thing, without reference to the line. Most people have trouble with such abstract concepts and derivations. I suspect this article just isn't for you.
You might prefer the one I'm writing now which starts with naive finite sets and constructs, completely in abstract, Natural Numbers, Integers, Rationals, Reals, Complex Numbers, and Quaternions. Your comment has made me think about the deliberate and explicit separation of the construction from the visualisation of the reals as a model of the line.
Maybe i am nitpicking but the existence of transcendentals was proven by Liouville 30 years before Cantor brought up the considerations about countability. (disclaimer liouville was the advisor of the advisor of the advisor of the advisor of the advisor of the advisor of my advisor)
Nearly 30 years ago, John Horton Conway introduced a new way to construct numbers. Donald E. Knuth, in appreciation of this revolutionary system, took a week off from work on The Art of Computer Programming to write an introduction to Conway's method. Never content with the ordinary, Knuth wrote this introduction as a work of fiction--a novelette. If not a steamy romance, the book nonetheless shows how a young couple turned on to pure mathematics and found total happiness.
Indeed, Liouville proved the existence of transcendentals, exhibiting specific numbers as examples. That was around the 1840s. Cantor showed in 1874 that pretty much every real number is transcendental, and the linked article is a re-casting/adaptation of one version of that paper. Although it shows how to construct a transcendental, it really shows that every list of numbers is incomplete. Taking the algebraics as the list then gives the result.
And I actually have a copy of "The Surreal Numbers". Still working on how it/they can be presented to a non-technical audience.
Not convinced. I've tried to follow their presentations when talking about these topics with different audiences and found that people really just don't follow. There's a difference between teaching material and exposing people to it - both of those works try to teach the topic to people, which isn't really appropriate in a single lecture format, or a math club, or a masterclass.
Well, they are full-length books (Ok, SN is shortish). There aren't many books that can be presented as a single lecture as is. The surreal numbers (as you know, I'm sure) are fairly subtle, and people don't have much intuition for how they should behave.
Even non-technical people have lots of intuition for real numbers (even if some of it is wrong); they know that they can add them, multiply them, compare them, etc, and they even know algorithms to do so. When confronted with the surreal numbers, it's not at all obvious that you can perform those operations, much less how to do so, so there's an enormous weight of basics to build up before you can really do anything interesting (much like how the first week or two of an introductory linear algebra course can be pretty dull).
Games are perhaps easier to motivate and make interesting (in my experience), as you can get to the point of analyzing and reducing simple positions and establishing the addition operation pretty quickly, without getting bogged down in "wait, why would I use this horribly complex approach to what seems at first to be not terribly unlike the real numbers except maybe I can't even do all the operations I know and love". Unfortunately, multiplication of games doesn't really make terribly much sense, so you need to restrict to numbers reasonably quickly to continue developing "conventional" mathematical structures.
TL;DR: for a single lecture format, motivating and defining games and showing that there's a reasonable embedding the natural (or dyadic rational) numbers isn't a bad introduction in my experience.
If all we want to do is prove the existence of transcendental numbers, rather than construct them, that follows as soon as we know:
1. Algebraic numbers are countable.
2. Real numbers aren't countable.
#1 is easy -- the number of polynomials with rational coefficients is obviously countable, and they have finitely many real roots each. So pick your favorite proof of #2 and you're done.
True. And in truth, the linked article is my favorite proof of #2.
And that's the point. This proof is really showing the uncountability of the reals - nowhere does it use any property of the algebraics other the fact that they're countable.
Spivak's Calculus contains a 3-page proof that e is transcendental. I didn't work through it, but it's unsurprisingly based on the famous series expansion of e.
So, he likes what is known as
the completeness property of
the reals. Good. Glad he
likes that! One remark is
"Calculus is the elementary
consequences of the completeness
property of the reals.".
And, yes, calculus is nice stuff.
Newton did nice things with calculus
but may not have understood the
completeness property, i.e., just
took it for granted that his
derivatives and integrals did yield
numbers.
Some of what is true about the reals
is bizarre, nearly beyond belief,
e.g., as in Oxtoby, Measure and
Category.
The main reason for being careful
with fine details going from the
natural numbers to the integers,
rationals, algebraics, and reals
is a theme that started near 1900
of trying to clean up the logical
basement of mathematics and, there,
build everything on just sets so
that, if believe in sets, then could
believe in everything that could
be based on sets, that is,
hopefully all of mathematics.
This goal seemed okay for
about 10 minutes until B. Russell
thought of the set
A = {x|x is not an element of x}
so that A is an element of A if and only
it is not. Bummer. Seventy years later
the gods of axiomatic set theory
came out with a lot of work that
made set theory look more solid.
Okay, that's curious work, and on
a good day with four quarters
will cover a $1 cup of coffee.
There was an article linked yesterday (sorry, don't have the link) which discussed the Reals in considerably more detail and sidetracked into a reformulation of the Reals that rigorously allows for Newton's infinitesimals without being "complete" in the "least upper bound" sense (and indeed, depending on the classes of functions you care about, doesn't even require an uncountable set).
My view is that infinitesimals
were a mistake, a long, festering
sore in math and some of its applications.
Can think intuitively about infinitesimals
if you want, but I see no need to
mess up the now very clean situation
on the foundations of the reals.
Indeed, as a grad student, I had some
results and went to see a world famous
prof to show him what I had and ask
him if my work seemed new to him.
At one point he suggested an improvement,
and, curiously, as a high end pure
mathematician in analysis
did his first cut, intuitive reasoning
in terms of infinitesimals! Fine.
But Dedekind cuts, Cauchy sequences,
etc. make a rock solid foundation for the
reals, and now can we just get on with,
say, Fourier theory and the rest of
analysis and their applications?
But as I've just mentioned, the computable numbers are still countable. This really hurts my head. There's an uncountable set of numbers that aren't expressible in any closed form whatsoever.
Continuous numbers get weirder the harder you look at them.