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

Your concerns about Cantor's argument stem from a slight misunderstanding of it I think. Cantor's argument is not supposed to prove the existence of the set of real numbers, that can be established in many ways (the two most common are by equivalence classes of Cauchy sequences and Dedekind cuts, more if you're interested). Cantor's argument proves that, given the existence of real numbers and that decimal numbers are well-defined (which can be proved in about 5 lines from the monotone convergence axiom, the basic axiom of real analysis, more if you're interested), the reals must be uncountable. Cantor's argument can then be used to prove the existence of transcendental and irrational numbers. The rational numbers are countable, the reals are uncountable, therefore there are irrational reals. Similarly, the algebraic numbers (the numbers that are the solution of a polynomial equation with integer coefficients) are countable, the reals are uncountable, so there are transcendental numbers (numbers that aren't the solution of any polynomial with integer coefficients). Famous example of transcendentals are Pi and e.

I hope that clears up your problems with Cantor.

Sorry - didn't see your post before. (I only occasionally go and look to see if anyone's discussion my articles.)

As I say at the top of the article, my main complaint is the way in which Cantor's argument is usually introduced (in UK schools at least) - my first exposure to it, and a lot of people I know had the same experience, was to demonstrate the non-countability of reals, but it was about 8 years later before anyone told me about Dedekind cuts. (Not come across Cauchy sequences.) Reading your post confirms my basic suspicion that Cantor's argument is only any good if you already have a deep understanding of real numbers, which you very clearly do.

As a secondary issue I stand by my claim that it's counter intuitive when you start to think about it. The fact is that it manifestly *doesn't* produce something that's not in the 'enumeration so far' for any finite length. So concluding that it somehow does once you consider an infinite sequence requires either (a) a leap of faith or (b) a deep understanding of, say, real numbers. (Or whatever it's being used on. Roger Penrose uses it to prove something in The Emperor's New Mind, something to do with Turing Machines, possibly the halting problem. I found it cute but unconvincing. )

Well, IF you're willing to assume there is a set R with the property that EVERY decimal expansion (say of the form 0.a0 a1 a2 a3 ...) represents a real number (i.e. number in R), and that if two real numbers differ in any digit of their expansion, then the numbers are different THEN the set R is uncountable, and Cauchy's argument works. (There is a slight problem with 0.9999999...=1, but you can deal with this quite easily.) The only problem is construction of the set R. The fact that it doesn't work for finite (or even countable) sets shouldn't be too worrying, because there are lots of properties that only work for infinite sets, for instance a set X is infinite if and only if there is a 1-1 mapping from X to a proper subset of X. So, on the face of it, arguing from "it doesn't work in the finite case", you'd like to assume that there are more integers than even integers, but we know that there is a 1-1 mapping between the two, and so there are the same number of them.

There is a more intuitive way of looking at the real numbers, called measure theory, in which you can study the "size" of subsets of the reals in a way which is more intuitive. For instance, the set [0,1] is uncountably infinite (by Cantor's argument), and so is the set [1,3], but you'd like to think that [1,3] is in some sense bigger than [0,1]. [0,1] is contained in [0,2], so that would be one way to say it was bigger, but [0,1] isn't contained in [1,3], so that argument doesn't work. However, you can say that the length of [0,1] is 1 and the length of [1,3] is 2, and so [1,3] is bigger. Measure theory is about extending the concept of length to strange sets where it isn't obvious what the length is.

Also, the argument in Penrose's book about Turing machines is basically right, it demonstrates that there is no Turing machine which can solve the halting problem, the argument is due to Alan Turing. However, the rest of Penrose's book is a bit more controversial

I'm familiar with the halting problem, but the proof I know doesn't involve Cantor's argument. It's a proof by contradiction based around automata. I wasn't arguing with Penrose's result, just the method.

I have always found almost all of the maths surrounding infinities highly counter intuitive. I suppose my background in computing tends to make me feel that a describing a set as having countably infinite size is really just saying that it's clear you can carry on counting these things and you'll never stop because you can always count one higher (it's Nigel Tufnel in heaven ) so we just admit defeat and give this characteristic a name. And clearly we can observe that counting with an increment of 2 you'll not stop any more than you will with an increment of 1, but it seems like a remarkable thing to me to say that there are the same number of even numbers as odd numbers. It seems more natural to me simply to say that these sequences both share the property that you'll never finish counting either of them.

I suppose it makes me really uncomfortable because talking about properties of infinite sets feels more or less the same as saying "When this non-terminating loop finally finishes..."

I also have trouble getting a deep understanding of problems like this: there is a one to one mapping of the integers onto decimals as I demonstrated in the entry. (Briefly: for each integer, write it as a decimal, reverse the order of the digits and stick a decimal point in front of it.) Given that the set of integers is infinite, why doesn't my enumeration contain numbers like PI if PI can be represented by an infinite decimal? (Oh alright, PI/10, since I'm only working in the range 0-1...) I can see that for any finite decimal I'm only going to have an approximation to PI, but why is your infinite decimal able to represent PI exactly when mine isn't? I don't feel that Cantor's argument gives me any greater insight into what the fundamental difference between these ways of constructing decimals is, particularly since Cantor's mechanism appears to be such an incremental process - the steps of its operation are emminently countable.

I think Penrose's method is sound, although it's a while since I read that book, but I guess if you're not happy with diagonalization (that's Cantor's argument) you wouldn't be happy with his argument either.

The key point here is that there ISN'T a 1-1 mapping of the integers onto the reals, that's what Cantor's argument shows. Your example (reverse the digits and stick 0. at the beginning) defines a 1-1 mapping between finite decimals and integers, but the finite decimals are certainly countable, because every finite decimal is a rational number, and the rationals are countable. Presumably you know the proof that sqrt(2) is irrational, and every finite decimal is also rational, therefore sqrt(2) cannot be written as a finite decimal, and so it doesn't pair off with an integer under your scheme. This is also true of Pi, but it is quite tricky to show that Pi is irrational.

Another way of looking at it is this, which integer does 0.3333333... correspond to under your mapping? Well, it would have to be 3+3*10+3*100+3*1000+..., but that number isn't an integer, because it would have to be infinite, and all integers are finite. Basically, 3+30+300+3000+... is bigger than every integer, so it can't be an integer (if it was an integer N, it wouldn't be bigger than N+1).

What I'm really getting at here is that it's not at all obvious what the difference is between a 1-1 mapping of the integers<->reals and a 1-1 mapping of the integers<->decimals. You further qualify my mapping as being integers<->finite decimals. Why? Is the set of integers finite? I don't ask that as a facetious question, I really feel that it's at the heart of the matter. Why does a 1-1 mapping between the integers (an infinite set) onto another set produce something finite?

The integer which maps to, as you put it, "0.3333333..." is represented by the integer ...3333333 . Again, I'm sounding facetious and I'll admit to being somewhat tongue in cheek with my style, but I still mean what I'm saying. I could characterise this as being a problem with the notation, asking rhetorically: what exactly do you mean by the three dots there? The nature of the notation is, as I understand it, generative - I read that as "dot three three three three three three three recurring". The 'recurring' is an instruction to carry on filling in threes for ever. Of course you can't actually do that in any literal sense, and instead have to resort to proving (or maybe just asserting ) that the sum of an infinite geometric progression is actually meaningful (and in this case happens to be the rational number 1/3).

But this seems like a lot of meaning to hide behind a simple bit of notation. Of course one way of understanding it is to say that all decimals are really just a notation for the sum of an infinite GP, and finite decimals are a special case where only a finite number of the terms are non-zero. I'd be prepared to accept that as a reasonable definition of a decimal, and will happily admit that it defeats my strawman mathematical argument. But I said right from the start that I knew the maths in my argument was flawed - to focus on that is to miss the point of the article: I'm making a pedagogical point, not a mathematical one. (I spend about a quarter of my life teaching by the way (but not maths), which perhaps I should have made clear.)

I'm fully aware that there are flaws in the mathematical argument I present. (I'm rusty on the details again, but I've seen the light in the past... I still find the whole realm of counting infinity deeply counter intuitive though.) The reason for presenting it is to illustrate the problem with the way in which Cantor's argument is used for teaching. It was at least 5 years between my first coming across Cantor's diagonal slash, and my understanding enough to know what is wrong with the enumeration argument I present. (Incidentally I came up with this enumeration in the maths lesson where I was taught Cantor's slash in order to illustrate to the maths teacher why I was uncomfortable with it. Needless to say he wasn't able to explain to my satisfaction. He just resorted to blind assertion about the existence of the reals and some of their properties (fair enough, although it would have been nice at least if he'd offered to demonstrate these properties like you did), taking as axioms things I'd never even come across.)

My basic point is: using Cantor's diagonal slash is inappropriate if you haven't already covered a lot of ground work on things like the existence of the reals, and the proof that the sum of any infinite GP represented by a decimal is always a real. My reason for presenting the counter-'proof', incorrect as it is, is that I would contend that anyone without this amount of background would be unable to tell you what was wrong with the proof. (Other than that it contradicts things they've been told by their maths teacher...)

\cyan{Ah, OK, I think I see where you're coming from now. In fact, when I was originally taught this at school I was in a very similar position to you, my particular difficulty with it was "why does the fact that there is a 1-1 mapping between Z and 2Z (integers and even integers) mean that there are the same number of them?" I pointed out clearly that one was a subset of the other, and so there were clearly more integers than even integers, my maths teacher was unable to give the right answer, which would have been to describe infinite cardinals a little bit and say that the definition of |X|=|Y| is that there is a 1-1 mapping between X and Y. However, I was happpy with Cantor's slash proof.

I agree with your last point, that very few people would be able to say what was wrong with your demonstration of the countability of the reals (in fact, it's a very common mistake which I quite commonly find). The tone of your article certainly suggests that it's an objection to the Cantor argument itself, rather than a point about misuse of it, maybe you could make that a bit more explicit?

Oops, ignore the "\cyan{" bit at the beginning of that post, it's a hangup from another web board I use (a maths one as it happens )

I may revisit the article to adjust the tone a little. (Maybe to cyan, what do you think? ) But I always enjoy the discussions that result from this way of presenting it, so I'm tempted to leave it...

This post has been removed.

Things are often counter-intuitive when you're dealing with infinities. Such is also the case in set theory. The classical example is Banach-Tarski's paradox: it is possible to divide a solid sphere into five parts, and then put the parts back together to form two solid spheres, each with a volume equal to the first sphere. How's that for counter-intuitive? =)

This discussion also confirms what I thought before: most of the problems you are having undrstanding Cantor are due to the fact that you're used to computers. Computers are known to run into trouble when something stops being finite (if they didn't, there'd never be any problems with running out of memory or HDD space, would there? *grin*)

As for the pedagogical question: I first encountered Cantor's argument in year 10 (what's that? key stage 5? too long since i was in a british school), but then again that was in a maths-oriented high school programme. However, at that time I only dealt with it out of interest; I didn't encounter it as part of class until year 12 (this spring), and then it wasn't in arithmetic, but in set theory. I had no problems accepting Cantor's proof once I understood what it actually was that he was trying to prove - cardinality was simply an unknown concept for me until a bit more than a year ago.
To summarize: I think Cantor's proof SHOULD be presented in high school. To those doing A-level maths or equivalent, that is. =) However, it should be presented first after the concept of cardinality (and the |X|=|Y| <=> (f:X->Y is onto and one-to-one) definition) has been explained.

I suggest adding a paragraph at the end of your article explaining why your argument doesn't work. Otherwise people not too familiar with maths might get confused and start having doubts as to whether Cantor was, in fact, right. If you like, I could write that paragraph. Now that I'm studying humanities, I need to deal with maths every now and then to keep in shape. =)

If you want to suggest a paragraph I'd be happy to add it - thanks for the offer!