3 ms·
To take your points: > There are two well-known arguments from Cantor: > http://en.wikipedia.org/wiki/Cantor's_first_uncountability_p... > http://en.wiki
by ColinWright 13y ago
To take your points:
> 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.
- Tloewald 13y ago> 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.
- gjm11 13y ago> 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.