Trapping A Transcendental - Finding numbers that aren't solutions to polynomials
penzba.co.uk
penzba.co.uk
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.
https://news.ycombinator.com/item?id=6967954
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.
Mostly.
It's when you introduce things as constructible/defineable numbers that things gets hairy.
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
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 :-)
> 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.
Thanks.
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.
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.
I'll think about that.
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.
[1]: http://www.cwu.edu/~harperj/472%20Winter%202012/Cantor-rev2....
> ... 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.
<fx: grin />
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 ...
Should be "giving x=1"
Now, how can I buy you a coffee?
Added in edit: Downvote?!? Who would downvote this comment? Bizarre ... <fx: Departs, stage right, shaking head in confusion />
You might be right, but I still find it very very odd.
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.
So, how can I buy you a coffee?
Also if you like that sort of things you would like http://amzn.com/0201038129
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.
And I actually have a copy of "The Surreal Numbers". Still working on how it/they can be presented to a non-technical audience.
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.
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.
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.
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.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?