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

Personally, I'd always assumed that if you ran out of digits going down the list you'd take the rest to be zeros... so, on your first table, you'd generate 0.1111111111, which is obviously not in the list. It seems a bit arbitrary to stop adding digits just 'cause you haven't written 0.1 as 0.100000000...

As for whether the argument as applied to an infinite list works without assuming the existance of infinitely long numbers... I'm not sure. On the other hand, a rational can have an arbitrarily long decimal expansion... no, in fact, a rational can have an infinitely long decimal expansion because it can be a recurring decimal...

So, even assuming the non-existance of real numbers, you could make an infinitely wide table... infinitely long, too. It's been shown that the rationals are countable... so any number produced using the diagonal method would have to be irrational, if the method works... does taking a different digit from each of an infinite number of different rational numbers, and adding one to each, guarantee an irrational number?

*shrug*

Incidentally, there is a slight problem with the version of Cantor's Diagonal thingummy which you've used in your article... because '0.1000000000...' and '0.09999999999...' are the same number, as are all similar pairs of numbers, letting your new number contain zeros or nines complicates matters...

The simple solution is to use, for instance, the digit '5' whenever the digit you come across isn't a five, and the digit '6' when it is. No nines, so no problem...

They're good articles, either way... I haven't really got the time to contribute properly, but I hope you don't mind if I drop by and post annoying comments on occasion

In that vein... the PTB prefer you to use ' instead of ", in most cases... just a minor thing, but there you go.

26199

Hmmmm. I just noticed that, in fact, the other article was written by someone else. Also, you've already got ' in all the right places. Must've been the last article I was looking at that didn't

Sorry. I'll post that last bit over there, instead...

26199

I'd say it's just as arbitrary to start adding zeros when I didn't have them there in the first place. (Particularly since I explicitly said that I was enumerating N digit decimals. I start off by only generating decimals of fixed length to illustrate that this is broken for the finite case. Of course it is - all finite sets are countable, but since the point of this proof is to try and illustrate that there are uncountable infinities, I think starting with the axiom that there is such a thing as an infinite decimal is not on!) But to answer your point in a slightly less flippant fashion I think your observation is an interesting one to make - your assumption that there is an implicit infinite number of zeros there indicates straight off that you are already entirely happy with the idea of infinite decimals, which implies you already have a sufficiently deep understanding of infinities and decimals not to need this proof!

And as for rationals, well I'm not trying to count the rationals, I'm trying to count decimals. Again this sounds like a glib answer, but I am actually being serious. If I attempt to convert certain rationals into decimal, I find that I never get an exact representation, but that after a while the digits settle down into a repeating pattern. Your conclusion here is that a rational has an infinitely long decimal expansion. But if someone new to this topic were to conclude that certain rationals simply don't have a decimal representation, how would you go about explaining to them that they were wrong? (Assuming you believe they are wrong.)

Remember what I really object to is that Cantor's proof seems to get introduced to people fairly early on when they don't yet fully understand the issues of countability in sets of numbers. So I think you need to be *really* careful about what you presume as background knowledge when interpretting the proof. I have yet to see anyone successfully use this proof to demonstrate the existence of non-countably infinite sets without presuming the existence of non-countably infinite sets. I.e. I believe this application of Cantor's Diagonal Slash is intrinsically circular.

Your sentence "It's been shown that the rationals are countable... so any number produced using the diagonal method would have to be irrational, if the method works..." I think sums it up perfectly - it's that last bit "if the method works" which is crucial. Why on earth should it work? Unless we take as read the very thing we were trying to proove!

Ahh, well, in that last bit I was just trying to consider whether there was any reason why a number generated by Cantor's method from a list containing just rationals would have to be irrational. I can't quite get my head around that question, so I had to stop there

Hmmm. You don't have to assume an infinite number of implicit zeros... just as many implicit zeros as there are numbers in the list. At no point when dealing with finite lists does this become a problem...

For it to be a problem, in fact, you have to have an infinitely long list. So perhaps your objection to Cantor's proof requires you to have already accepted that an infinite list has meaning?

It seems to me, though, that even if you do accept that infinitely long decimals are meaningful, it isn't immediately obvious that the rationals aren't countable. Having already accepted the former, I found Cantor's proof absolutely fascinating...

As for proving that all rationals have a decimal representation... I'd give 'em the typographical rules involved in dividing one integer by another, and hopefully from those would follow the fact that they can be applied to any two integers... then, I'd give a general method of how to convert an infinite, repeating-decimal rational back into the two integers, and hopefully show that it could applied to any repeating decimal.

That would do it, I think

Are you in the UK? To my surprise, my (A-level) further maths group was recently taught Cantor's proof as part of the syllabus... you're probably right about it being taught too early, though, 'cause I don't think many people really appreciated it. Then again, most of them aren't particularly enthusiastic about mathematics in general

26199

I think accepting that there is such a thing as an infinite list is at least part of the problem. But it goes further than that - accepting it is one thing, understanding it is another.

The key problem I had with this argument right from the first time it was presented to me is that (1) there is an easy way of enumerating decimals of finite length (I came up with the scheme I present in the article during the maths lesson in questions...), and (2) the finite case shows a clear pattern for increasing length of decimals that is quite substantially different from the conclusion you are supposed to draw from the infinite case.

Another way of summarising it is this: for decimals of length N, the number of decimals is 10^N. If N is finite and integral, 10^N is also clearly finite and integral (and so the enumeration is countable). 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?

How about proof by induction that Cantor's proof doesn't work:

(1) For decimals of length 1, Cantor's method doesn't produce a number not already listed in the enumeration.
(2) Given that applying Cantor's method to a decimal of length N doesn't produce a number not already listed in the enumeration, consider the case for a decimal of length N+1. The enumeration for decimals of length N+1 will contain 10 times as many entries. In particular, any number in the enumeration for N will appear in the enumeration for N+1 with an extra digit appended 10 times, once for each possible digit; this will of course be true for the number generated by Cantor's method for N (just as it is for any other number). So what can Cantor's method generate for length N+1? It only has 10 possible options - taking the number for length N (which we took as our sole initial assumption for this section) and appending any of the available 10 digits. But as already discussed, each of these is in the enumeration for N+1, so it doesn't generate a new number.

In summary, if Cantor's method fails to generate a unique number for a decimal of length N, it will also fail to generate a unique number for a decimal of length N+1, for any strictly positive integer N.

(3) Given (1) and (2), then by induction Cantor's method will not generate a number not already in the enumeration for decimals of length N for any N.

Get out of that.

And I'm still not convinced about your proof of rationals having a decimal representation. I work in computing, where getting stuck in an infinite loop is typically regarded as some kind of error.

Yes, I'm in the UK. I did A level maths and further maths back in 1991. (That was the year I took the examination.) I think it was in my lower sixth (or whatever they're calling it these days; the year after GCSEs, but before A levels) that we were shown Cantor's proof. I instantly took against it for the reasons I present here (although I wasn't sufficiently eloquent about it to get my teacher to understand what I regarded as the problem; also back then I simply knew that it didn't appear to make sense, whereas now I understand that it is essentially an inappropriate use of the method). I can't remember whether it was actually part of the syllabus, or whether it was just something the teacher explained to us because he thought it was interesting. (Reductio ad absurdem was a proof definitely *not* on the syllabus which we were taught anyway - came in useful in a university interview once.)

Ahh, but your proof by induction relies on not being able to extend the decimals if you want to... which I still contend is the logical thing to do if you run out of digits.

After all, consider the infinite table that we're trying to prove doesn't exist: somewhere in the table must lie the rational number 0.1, ie 1/10. Now, if you write it without any trailing zeros, Cantor's method appears broken anyway... you come across a row in the table which you can't generate a digit for, because you're run out of digits.

Thus you have to assume implicit trailing zeros even in the infinite case... it would seem, in fact, that Cantor's proof needs implicit zeros to work anywhere, and leaving 'em out is bound to cause problems.

If you're still going to complain, I suggest we move on to discussing 26199's proof, which explicitely states that you've got to allow up to 10^N implicit zeros

Hmmmm... as for proving that all rationals have a decimal representation, I think the problem with infinite loops could be solved using a notation for such loops, a demonstration using typographical methods of division that such loops are indeed infinite and repeat without variation, along with methods of how to spot when you've run into one, and a demonstration that any such infinite decimal can be turned back into its two integer fractions.

I could probably write a predictably terminating algorithm to figure out the decimal expansion of a rational, in fact, which would settle the matter... I'll give that a shot

(I work in computing too... well, plan to - heading to university for a Comp Sci degree when I leave college)

Yeah, they still call it lower sixth... further maths students are taught the Cantor stuff at the end of l6th, single maths students never learn it.

Anyhow. Your turn

26199

Here we go... about the most horrific piece of spaghetti programming I've produced in a while, but there are no unbounded loops involved so it must always terminate with an answer in a finite amount of time:

DEFINT A-Z
CLS
PRINT "Enter integer a,b where a < b"
INPUT a, b
DIM past(b)
past(0) = -1
FOR n = 1 TO b
d = 0
e = -1
FOR c = 0 TO a
IF e = -1 THEN d = d + b
IF d > a AND e = -1 THEN e = c
NEXT
a = a - b * e
a = a * 10
past(n) = a
IF done = 0 AND p = 1 THEN Decimal$ = Decimal$ + RIGHT$(STR$(e), 1)
p = 1
FOR f = 0 TO n - 1
IF done = 0 THEN
IF a = past(f) THEN
done = 1
IF f <> 1 THEN
Start$ = LEFT$(Decimal$, f - 1)
IF LEN(Decimal$) - f + 1 > 0 THEN
Decimal$ = RIGHT$(Decimal$, LEN(Decimal$) - f + 1)
ELSE
Decimal$ = ""
END IF
END IF
END IF
END IF
NEXT
NEXT
PRINT "Decimal expansion:"
PRINT "0." + Start$ + Decimal$
PRINT "Repeating section: " + Decimal$

Just give it integers a and b and it'll work out the infinite decimal expansion of a/b, no trouble.

(I don't usually program in QBASIC, honest, I just like its immediacy for small problems of this sort )

26199

Well all your program shows is that if you try to generate a decimal expansion of a rational, either you can, or you end up getting stuck in a repeating loop, in which case you know that you never can because you are doomed to keep churning out more and more digits, getting progressively more accurate but never actually achieving an exact representation. The program terminates, but only by detecting the loop - the fact remains that you can't write the number down as a decimal. Your introduction of a new notation is very interesting, but moves us away from the original problem of dealing with decimals - for one thing I'm not exactly sure how to apply Cantor's argument to your notation.

Your assertion that we should allow trailing zeros simply ignores my whole argument! My proof is founded on proving statements for decimals of fixed length. You are simply saying something akin to "ah but if the decimals are not of fixed length...". Well yes, OK, but they *are*. The proof has nothing to say about anything other than decimals of a fixed length. (Well, stage (1) is specifically about decimals of length 1, and stage (2) is parameterised, but is always talking about some specific length N. The final step however covers all specific lengths of decimal.)

If you think the proof is incorrect on its own terms, then please say why. The fact that it breaks Cantor's method is very much the point - it's supposed to be a proof that Cantor's method doesn't work, so I don't regard that as being a flaw in the proof! (Note that I'm not taking the brokenness of Cantor's method as an axiom, I'm merely not taking exception to its self-evident brokenness when applied to decimals of fixed length.)

Starting from the point of view of considering the infinite table is not helpful, since we are starting from a lack of understanding of what the properties of such a table might be in the first place! So such reasoning is effectively out of bounds.

Adding an extra digit is *not* the logical thing to do if you run out of digits. Essentially I am asking this question: Given the enumeration of decimals of length N, is Cantor's method capable of generating a decimal of length N which is not in the enumeration? I believe my proof demonstrates this to be true for any N if N is a strictly positive integer. I think I've pinned down what I'm saying precisely enough, so do you agree or disagree with it?

*tock!* Ball's in your court.

Nope, I disagree...

Just because a decimal is of fixed length doesn't mean it can't have implicit zeros after it - it doesn't change the value of the number at all. 0.1 is the same as 0.10000, so why can't I write it that way if I want?

Have to go now, so this is just a hasty reply... I shall probably be back

26199

Okay... let's see...

Given all the decimals of length N, you're entirely correct that Cantor's method can't produce another, unique decimal of length N.

What I'm saying, basically, is that it can always produce another, different decimal of length N+something, and that this method is applicable in every case up to and including the infinite one.

I suppose that's what it boils down to: when it comes to infinite lengths, you can always add on as many more digits as you want without anyone noticing - and that's why Cantor's method works.

I agree that reasoning about an infinite table might get a little dodgy, but I contend that my argument - that terminating decimals without implicit trailing zeros causes problems *anyway* - still stands, because it also applies to finite lists. Consider, for example:

0.1
0.2
0.4895
0.3281

Here, applying the method without assuming implicit trailing zeros leads to the result 0.2... already in the table. Applying it *with* implicit trailing zeros leads to 0.2100, which isn't in the table. The second method clearly works better...

My program tells you the exact decimal expansion of any rational... just because it doesn't write the whole thing out doesn't mean it hasn't been explicitly described! And, anyway, the idea was to show that every rational has a decimal expansion, infinite in length or not... my program is an explicit method of finding the decimal expansion in any case, so I reckon it's pretty good evidence in that direction...

Either a decimal is of length 5 or it isn't. 0.1 is a decimal of length 1, 0.10000 is of length 5. They happen to be different representations for the same number, but they're of different lengths.

And yes, Cantor's method can always produce a number of length N+1 that isn't in the enumeration for N. But my proof also shows that the number it generates *will* be in the enumeration for N+1. So any number it produces will always be a member of *some* countable enumeration. (The fact that it's not in the enumeration for N doesn't really matter - we're just trying to prove countability, so if it's in the enumeration for N+1, that's sufficient for the purposes of the proof.)

And I would also argue that 0.1 is a different thing from 0.100. It may represent the same number, but it's a different representation. And representation is crucial to the mechanism behind Cantor's method, so I don't think it's right to gloss over issues of representation.

Likewise in your example 0.1 is not a member of the set of 4 digit decimals. (I'm assuming we're counting the digits after the point incidentally.)

There *is* no exact decimal representation of a rational unless you accept the existence of an infinite decimal expansion - that's the whole point of my argument! (Because if you accept the meaningful of an infinite decimal expansion, recurring or not, you have accepted that the sum of an infinite geometric progression is defined. (After all, what's a decimal other than a notation for the sum of a geometric progression?) From what I remember, in order to accept that the sum of an infinite GP is meaningful you *have* to invent the reals first! So we're back to a circular argument again.)

This is perhaps a key point...

When N is infinite, N and N+1 are the same, so if you produce a number which isn't in the list of decimals of length N, it's also not in the list of decimals of length N+1.

Admittedly, that's using a fact about infinities... perhaps you'd agree, though, that if you accept that infinity+1 is the same as infinity, you have to accept Cantor's proof?

26199

So my inductive proof is fine, but an inductive proof just proves things for any N where N is a member of the set of integers? So if it doesn't hold for infinity, you're presumably saying that infinity is not a member of the set of integers? (Although of course the set of integers is infinite.)

Well OK, if you say that inductive proofs don't hold for infinity that's fine. But of course Cantor's method is inductive in its nature too isn't it?

Hmmmm... I'm not sure if your inductive proof works when you allow decimals of length N+1... it becomes something of a circular argument, doesn't it?

Assume Cantor's method doesn't work on decimals of length N... this now relies on it also not working for decimals of length N+1... which is what you're trying to prove...

Right (or not)?

26199

Uh, no. The 2nd step in the proof is to demonstrate that if the property holds for N it also holds for N+1. This is a fundamentally important part of proof by induction. It doesn't work without it!

Re: your 2nd paragraph, no that's not what I"m saying at all. What I'm saying is: Assume Cantor's method doesn't work on decimals of length N. I then went on to *show* that given this, it also doesn't work for decimals of length N+1.

Then by showing that it doesn't work for some specific length (e.g. 1), we know that it doesn't work for *any* length.

I'm not taking it as an axiom that the method is broken for decimals of length N+1. Part (2) was all about *proving* that this was true, not presuming it!

Ahh, I think we're talking at cross-purposes here...

You said:

'And yes, Cantor's method can always produce a number of length N+1 that isn't in the enumeration for N. But my proof also shows that the number it generates *will* be in the enumeration for N+1. So any number it produces will always be a member of *some* countable enumeration. (The fact that it's not in the enumeration for N doesn't really matter - we're just trying to prove countability, so if it's in the enumeration for N+1, that's sufficient for the purposes of the proof.)'

Now, here you assume that any number generated of length N+1 will be in the enumeration for N+1. This is tantatmount to what you are trying to prove for the case N+1, ie that there are no new decimals of the length N+1. But you haven't proved that yet, 'cause your induction argument is currently thinking about the case N...

In other words, I'm saying that your proof by induction doesn't work if you allow decimals of length N+1 to be produced from the table of decimals of length N.

And I still contend that my version of Cantor's method works in every finite case, so where's the argument against it working in the infinite case?

26199

That only looks like an assumption because you take it out of context. If you refer back to my original proof, you will see that I *demonstrate* that any number generated of length N+1 will be in the enumeration for N+1.

I think I may have confused you - some proofs by induction take the case for N-1 and proove for N. I'm not doing this - I'm taking the case for N and proving for N+1. You might like to go back and re-read the proof bearing this in mind - I'm pretty sure everything that you've raised so far is dealt with by the original proof. Step 2 is a little complex, but it deals with the point you raise.

It clearly doesn't work in finite cases. Here's a counterexample: decimals of length 1, the enumeration is:

.0
.1
.2
.3
.4
.5
.6
.7
.8
.9

What decimal of length 1 does Cantor's method produce that isn't in this list? That is the complete list of decimals of length 1. Pick any integer N, and I can provide for you the complete list of decimals of that length. I don't understand how you can possibly consider, say, 0.11 to be a decimal of length 1. It's of length 2!

Yes you can stick a zero on the end of all my numbers and then use Cantor's method to generate a decimal of length 2 that isn't in my list. But that's a red herring - in this specific example I'm not trying to say anything about decimals of length 2, I'm concentrating solely on decimals of length 1. (For now - this part of the argument is specifically constructed to refute your claim that Cantor's method works in finite cases.)

Show me a finite case where it works. Be specific about your value of N Give examples.

I'm not trying to refute your induction argument; there's nothing wrong with it. I just don't think it has anything to say about Cantor's method.

And I understand it perfectly, thanks

Cantor's method works in all finite cases without the limitation on decimal length, which is one you yourself imposed... there's nothing wrong in using that as part of your argument, but I don't think you can really call it a failing of the method...

The point, basically, is that for any list at all you *can* produce a number which isn't in the list... and Cantor's method tells you how to do just that... and nothing you've said has convinced me that there are any cases where it doesn't work.

Now, if you can give me a list of numbers and I can't come up with one which isn't on the list, I'll be convinced

26199

If there's no limitation on decimal length, in what sense is that finite?

Yes you can produce a number that's not in the list. Of course you can - PI for example. Works every time, no need for Cantor's method at all! But mine is a proof about *decimals* not *numbers*! You keep ignoring the issue of representation. Every time you have to extend the representation by adding an extra digit. And every time you do that I can counter by extending my enumeration. If you're allowed to extend the representation by adding another digit, I don't see why I can't extend the enumeration, so even playing by your rules, you'll still never find a number I can't count with Cantor's method.

Let me put it this way: for any number that has a precise decimal expansion of some length N, I can produce a finite enumeration (and I can even tell you the size of the enumeration: 10^N) which I can guarantee includes that number, without you having to tell me what the number you've chosen is.

Let me also put this another way: do you consider the decimal representation of the integers to be countable? If you do, I can show you an alternative version of my proof.

Ahh, but that's the thing, isn't it? Every time you extend the enumeration, I can produce yet another number which isn't in there... which means that table doesn't contain all the reals. Certainly, you can extend the enumeration again... but, once again, I can demonstrate that your table isn't complete by producing yet another number which isn't in there. We can do this an infinite number of times... but, every time, your enumeration fails to produce a complete list of all the reals.

Sure, you can count any arbitrary number I decide upon... but you can't count 'em all! What if I tell you that I have a number, but I'm not going to tell you how long it is? There's no way for you to produce an enumeration which guarantees to include my number...

By 'finite', I meant the decimals could be arbitrarily long but not infinitely long, and the list could contain an arbitrary number of decimals but not an infinite number...

Hmmm. Aren't the integers countable by definition? So I s'pose I'd better accept that, really. I'm interested to see your alternative proof...

26199