h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

But I can turn your argument on it's head: every time you produce yet another number which isn't in there, I can extend the enumeration.

We simply alternate - you add a number, I extend the enumeration, you add a number, I extend the enumeration, and so on ad nauseam. Why should either one of us get the upper hand in the infinite case?

If you claim to produce a number but don't tell me how long it is, then I can say this: if your number has an accurate decimal representation of length N (where N is an integer), then my enumeration is of size 10^N and contains your number. If your number doesn't have an accurate representation of length N (where N is an integer), then I claim that you have presupposed the existence of the reals, and I claim my 5 pounds.

OK, so you accept that the integers are countable. (I didn't expect you to disagree with this - that is after all, as you point out, more or less the definition...) So do you accept that every integer has a decimal representation?

Yes, we can carry on for an infinite amount of time... but every time I win! I show that your enumeration N doesn't work, so you produce enumeration N+1... then I show that that enumeration doesn't work, and you produce enumeration N+2... and we carry on for an infinite length on time - until it's demonstrated that *none* of your enumerations work...

Ahh, but here's the thing: I tell you that my decimal does indeed terminate, ie it's finite, but I don't tell you when. There's no way you can produce an enumeration which guarantees to contain it. The enumeration exists, certainly... the fact that you can tell me how to find it isn't impressive, because I could just write down the number itself and have an enumeration containing it... the fact is, you can't even produce an enumeration which contains any arbitrarily large decimal, never mind infinite ones...

Does every integer have a decimal representation? Hmmm. I'm going to say yes... but, with one important point: none of them are infinitely long. They can be arbitrarily large, but they must terminate... because I'm fairly sure infinite integers don't come into what I normally mean by 'integer'.

26199

But every time *I* win too! You produce a number, so I show you an enumeration that contains it. You show me another number, and I show you an enumeration that contains it.

This infinite regress appears to indicate *deadlock*. Neither of us wins. (You're assertion that *you* win is just arbitrary - what's so magic about what you're doing? We're just alternating for ever, so neither of us wins.) So apparently it proves nothing.

No, I can guarantee to produce an enumeration. You just told me that your decimal was finite. From this we know that there is an exact representation of your number as a decimal with a finite length. I have proven that for *all* decimals of length N (where N is an integer). So there is an enumeration that contains your number - the fact that it was finite is all I needed to know to prove this.

OK, so I have 2 questions: (1) is there an integer which does not have a decimal representation? (2) is there a non-fractional decimal (i.e. a decimal with no numbers to the right of the decimal point) which is not an integer?

No, because I'm not asserting that you can't produce an enumeration for my number... my *only* assertion is that your current enumeration is broken, and that proves true in every single case. So I win every time. Each new enumeration you produce is simply introducing a new case which you hope will prove me wrong, but it never does.

I *know* there is an enumeration which contains my number. There's an enumeration which contains any number you care to mention, including all of the reals. The point is, you can't tell me *which* enumeration it is without knowing how long my decimal is, and you can't produce a single enumeration which guarantees to contain it, simply because my number can always be bigger than your enumeration.

What I am saying is this: there exists a finite, terminating decimal, let's call it X. Can you now describe, in enough detail that I could write it out in full, an enumeration which guarantees to contain X? No, you can't... you can merely say that an enumeration exists, but that's obvious - here's one I made earlier:

X

Much simpler than producing a long list of decimals the same length as X, don't you agree? Such a feat is hardly impressive... now, if you could produce an enumeration which contains X knowing only that X is a terminating decimal, I would be impressed. But you can't.

In answer to your questions: All integers have a finite decimal representation; therefore any *infinite* non-fractional decimal might, in fact, not be an integer. So 1) no, 2) yes.

26199

Well for any specific number you produce I'm *only* asserting that it's also broken because there's an enumeration that contains it.

Woah, hold on! You think there's an enumeration that contains the reals? That's not actually true. (Even though using Cantor's method to 'prove' the non-countability of the reals tends to point in the other direction if you don't already know about the non-countability.)

If you don't have to tell me which decimal it is, why do I have to tell you which enumeration it is? Given the fact that it's a finite decimal, I can prove to you that there is an enumeration that contains it. If you want to find out which enumeration it is (or rather which the minimal enumeration that my scheme generates is), you'll have to tell me which decimal it is. But if you're not prepared to tell me, it doesn't matter - I can still demonstrate that one exists given no more information than the fact that the decimal is finite.

But to answer your specific challenge, yes I can describe to you the process in detail. You have told me that X is a finite (aka terminating) decimal fraction. It will have some length N, where N is finite and integer - this is just an alternative way of stating the fact that it's a finite integer. Generate the set of integers which can be represented as decimals of fixed length N, with all leading zeroes present. (Remember these are not really numbers - think of it as a set of text strings each of length N if you like. It so happens that you can treat these text strings as the coefficients of a polynomial which, if you feed in the number 10 will generate the number you first thought of, but that's just the definition of a decimal really.)

So if N=1, your set would look like this: { "00, "01", "02", "03", "04", "05, "06", "07", "08", "09", "10", "11" ... [I'm sure you don't need me to fill the rest in for you] ... "99" }. I'm sure you could agree that this can be generated mechanically for any X you choose to supply (so long as it meets the criterion you specified, i.e. it has an accurate representation of length N).

Now take this set and generate a new set, which contains all the strings in the previous set, only each one has a "." prepended to it. You can see that it doesn't matter what N was for your X (remember N is the number of digits), a mechanical process exists for building an enumeration. And it doesn't matter what value X has - the enumeration will contain it.

What is it that made you think I couldn't do that? (You may argue that I'm cheating because I need to know N. Actually I don't - I'm just trying to prove that an enumeration exists. This should be sufficient - I don't actually have to go as far as telling you what it is!)

Let me take a step back from here and make the following statement: it is possible to define the set of enumerations that my method will generate. Call this set F. It can be constructed thus: for all N (where N is any strictly positive integer) there exists a member of F which is a set whose size will be 10^N, and which will contain strings of length N, one for possible each N digit combination of the digits 0-9, preceded by a decimal point.

The joy of discrete mathematics is that I can define the existence of such a set up front. It's an infinite set, but that doesn't matter - I've shown how to generate it. If you want I can produce code to produce any member of set F (just tell me which value of N you want the member for), but I suspect you don't need me to write this for you - I'm pretty sure you can see for yourself that it's not hard to generate this.

So, the beauty of this technique is that I've put all of my cards on the table in advance. I've pre-empted your arguments which are based (spuriously I think) on the order in which things get generated by showing you everything I've generated up front. (Or at least providing you with a formal definition for the set of things I can generate, which amounts to the same thing. This after all is the only way that we are able to talk about infinite sets such as the set of integers.)

I now defy you to claim that your X's decimal representation is not a member of F. Show me an X, *any* X, that conforms to your requirements (a terminating decimal) whose decimal representation isn't a member of any of the members of F.

X's decimal representation is contained by a member of F (actually you'll find it in an infinite number of members of F) and not only do I not need to know X's value in order to make this claim, I now don't even need to know how long it is!


I think that's irrefutable, but I'm sure you'll see it differently. (Incidentally, I'm also confident that the construction I just presented has no bearing on the non-countability of the reals, remember I'm just making statements about finite decimals in this particular posting.)

But back to my other line of argument: So you accept that all integers have a decimal representation. However you claim that there are non-fractional decimals that aren't integers. Can you give an example of such a decimal (which I won't ask you to write down just show a construction for it), and if it's not an integer, tell me what kind of number it *is*. (Is it a real? A rational? An imaginary number? Or is it not in fact a number at all? (My favourite feature of maths co-processors on computers is that they actually have representations for 'NaN' - Not a Number!))

Yes, there is an enumeration which contains any real you care to mention. Here's the one for Pi:

Pi

See? There doesn't exist one which contains *all* the reals, but for any specific real you can generate an enumeration which includes it. This is why I'm not at all impressed by the fact that you can generate an enumeration for any specific X... nor am I impressed that you've proved an enumeration must exist for any specific X... because that's obvious.

What I'm trying to get at is the fact that N, whilst finite, can be arbitrarily large... and you can't write down a finite enumeration which is guaranteed to contain it, even though you can guarantee that one exists. Certainly your enumeration F contains any X I could care to mention, but it's an infinite set... so all you've shown is that the rationals are countable, which I accepted anyway. Actually, I forget what the point of this point was... never mind...

I thought my previous answer was fairly clear... I don't consider an infinitely long decimal to be an integer, so anything with an infinite number of digits followed by a decimal point and a zero is a non-fractional decimal which is not an integer. As far as I'm aware, such a decimal is meaningless... although, I suppose, if you divide one by infinity you get a real

26199

Ah, when I hear "an enumeration which contains any XXX you care to mention", I hear an implied "for all XXX". Hence the disagreement - you are hearing an implied "for some specific XXX". OK, given your version, I agree with that. If you accept the existence of a real, you can trivially construct a set containing it.

However as I think I demonstrated with my constructed set, this doesn't really matter - I can show that there is a *single* enumeration that contains *all* decimals of a particular length. And there's also a set that contains all enumerations for any length of decimal. Of course to make it even simpler, I can just take the union of all the members of the set F I constructed last time, and this of course is the set of all possible finite decimals. (And I believe it should be obvious, given this construction, that it's a countable set.)

Doesn't that deal with your complaint about trivially-constructed enumerations (e.g. enumerations of size 1)? I don't need to build an enumeration specially to hold your X. I've now got The One True Enumeration, and whatever finite decimal fraction you would care to choose, it's in there. Therefore the set of all finite decimal fractions is countable.

(If you really want to drag it back to Cantor's method, then consider this: either you have to stop somewhere or go on forever. If you stop, what you have is a finite decimal fraction, and it's in my enumeration. (This is what I meant when I said it's broken for the finite case.) If you never stop, then you don't have a finite decimal fraction, nor do you have any reason to suppose that you'll end up with a number at the end of it, not least because "at the end of it" is meaningless if we never stop. And this is really where we came in - is it meaningful to talk about the *result* of an infinite generative process? This really is the crux of the matter, and is something you have to solve before you can consider using Cantor's method.)

Your previous answer was clear inasmuch as I understood that you don't think an infinitely long non-fractional decimal is an integer. So my next question was: what do you think it is then? But your answer that it's meaningless is what I was looking for. My quick question: (1) if an infinite string of decimals is meaningless, why does it become meaningful if you stick a decimal point on the front? (You are not allowed to presume the existence of the reals, remember.) For my longer question, I will assume that you will accept that the digits decimal notation can be considered as the coefficients of a polynomial where the variable is given the value 10. E.g. the number 98742 is the same thing as 9x^4 + 8x^3 + 7x^2 + 4x^1 + 2 if x is 10. Given this, is the idea of any infinite sum of a geometric progression meaningless? If not, how would I tell a meaningful one from a meaningless one?

Yeah, 's my fault for the ambiguous grammar there. It means I get to have been right for once, though

Yeah, your F has my arguments fairly nicely circumvented. What can you do, hmmm?

Leaving that for a while so's I can try and recall where my arguments were *supposed* to be heading... I'll answer your question

An infinite decimal (left of the .) is meaningless, I think, because whichever way you try to parse it you come across a problem: if you try and parse it left-to-right, you're starting with digits which represent infinite powers of ten and therefore have no real meaning... if you try and parse it right-to-left, each additional digit changes your answer more than the previous one, which means you never have any idea where you're going to end up...

Of course, the idea of 'parsing' an infinite decimal is meaningless, but that's how I intuitively think about it.

Anyhow. When you have the infinite decimal to the *right* of the decimal point, ever digit you move along you get closer to the actual figure... which, to my mind, makes it much easier to deal with. Of course, parsing it right-to-left still doesn't work...

When it comes to the geometric progressions: 's easy. A converging infinite series is meaningful; a diverging one is not. Admittedly that's something I've been taught, but it seems to make sense and I can accept it...

After all, it solves the whole Xeno paradox, which is quite a nice result - since, quite clearly, it *is* possible to move.

Anyhow. I contend that an infinite decimal moved to the right of the decimal point becomes meaningful because all of the digits then have a finite value.

26199

Well, the Xeno paradox requires you to accept the existence of *some* sums of infinite GPs. But typically only ones whose value happens to be a valid rational. As I understand it though, it's not really possibly to except this as a general rule without also inventing the reals to accept all the other infinite (but non-diverging) sums of infinite GPs.

Anyway, I guess the most simple summary of my arguments is: infinity is a mind bending concept.

And I think I'll leave it at that, since I'm only arguing that a particular proof cannot be understood without first understanding infinities, rather than disagreeing with its conclusions.

Fair enough

*twiddles thumbs*

Hmmm...



26199

Please forgive me if I sound harsh here. It is not my intention to seem arrogant or anything like that. I'm just trying to be concise and answer all questions.

1. There is no point in trying to prove that Cantor was wrong. Not under the standard system of axioms, anyway. It's called a proof (as opposed to an attempted proof) because it is true. It can, however, be interesting to _look_ for flaws and see why they don't exist.

2. Talking about finite forms of Cantor's proof is irrelevant, for two reasons: a) what he wanted to prove had to do with infinites, and b) finite cases of a certain concept often have very little or nothing to do with the infinite cases. In the case of Cantor, that's exactly what things are like.

3. The argument concerning trailing zeroes is irrelevant as 0.1 = 0.10 = 0.1000... recurring. They are all _the same number_, just written in different ways. What makes you think they're not the same thing is probably that you've been working too much with computers, where trailing zeroes _can_ in fact be an issue. In mathematics, however, they're not. For the finite/infinite parts of this discussion, see point 2.

4. You cannot prove anything regarding infinites by mathematical induction, as that is a method that can be applied solely to problems of finite nature. All that you proved was, in other words, that Cantor's method would not work for any finite list. Actually, you didn't even prove that, but that's beside the point.

5. Cantor's proof is not inductive, it's deductive. More precisely, it's indirect, aka proof by contradiction, aka reductio ad absurdum. He assumes that the reals are countable and then reaches a contradiction, thus proving they are not countable.

6. Rationals don't have a decimal representation. Fractions do. And if I'm not entirely mistaken, all you really need to worry about there is the definition of division. And the fact that the decimal representation of a certain fraction is infinite (in the sense of a recurring pattern) doesn't mean it doesn't exist. It only means you can't write it down [within a finite period of time].

7. Concerning "So what's different about 10^(infinity)? The number of digits in a non-terminating decimal is presumably countably infinite, so why does raising 10 to the power of a countable infinity yield something different?"
Wow...this is a long-answer one. Find a book on elementary set theory and read about cardinal numbers. That should explain it.

8. Denoting infinity by oo, then oo = 1+oo = 2*oo = oo^2, and similarly for +*^ with any other real number. This goes for all infinities (or transfinite cardinals, if you like), both Aleph Null (countable infinity) and Continuum (uncountable infinity) in particular.

9. All integers are finite.

10. Pi will not "always not be on the list". Pi is real. Very real. =)

I hope this sorts everything out in this particular thread.

Oooh... I'll have to look up that 10^(infinity) thing, just as soon as I get a break in my busy schedule ()... either that or ask my maths teacher, d'you reckon I could get him to waste (ahem, contructively use) a week's lessons on it?

I wouldn't mind taking maths further (ie degree level at the moment), but I'm more of a computer scientist, I think...

26199

If you can get your maths teacher to spend a very constructive week explaining transfinite cardinals is entirely dependant on 3 things:

1) The level you are at
2) The areas of interest of the teacher
3) If your coursemates think it seems like a good idea

This is a very interesting area of set theory though. I'm in the process of writing entries about it all, but my only finished entry on set theory so far is the one on the cantor set - do a search for that. cardinality is coming up next and counting laws for cardinal numbers (which is the one you'll want to read) will be coming around new year.

Good luck with the convincing! =)

I have no trouble with Cantor's proof, but I can see why it might not be immediately convincing that there are infinitely more reals than rationals.

But try this: there is a denumerable infinity of rationals, as many as there are counting numbers. This means that, if we place a series of intervals over the successive, numbered, rationals between 0 and 1, then we can easily cover the rationals. However, by choosing the intervals to have lengths 1/5, 1/25, 1/125, 1/5**n,... we can ensure that, at most, 1/4 of the line from 0 to 1 is covered. So there are (at least) 3 times as many reals as rationals. And we can choose our series of intervals to be as small as we like; so we can prove there are as many more reals as we like.

More precisely, the measure of any set of rationals (not to mention algebraic reals, or even computable reals) is 0, but the measure of all the reals in an interval is the length of the interval.