Problems On The Diagonal

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

Problems on the diagonal

So let's start with something I think we can all agree with:

• Students find Cantor's proof of the
  uncountability of the real numbers
  by diagonalisation really hard.

• Why do they find it hard?
• Does it matter?
• Should we help?
• If so, what should we do to help?

So let's start with a few observations:

• Lots of students find proof by contradiction hard
• Lots of students have trouble with the concept of bigger infinities
• There are several common objections to Cantor's diagonalisation proof, including:
• You've constructed another, why not just add it in?
• Why doesn't this also prove the rationals are uncountable?

Well, for one thing, it's proof by contradiction. That in itself seems to be a real stumbling point for many students. They say: "Wait - we assume the opposite?", and they never really grasp what's going on. For them we can consider two options.

One is that they will never really get Proof by Contradiction (PbC). In that case, they'll never get Cantor's proof, and trying to work through it endlessly just leads to increasing frustration, and ultimately to just giving up in despair. For them, there seems little point in presenting the proof at all.

The other option is that they may at some point understand PbC, and once they do, Cantor's Diagonalisation Proof will become fairly straight-forward. In this case, though, I ask - can we help them understand PbC without the complete bizarreness of uncountability? Why not help them with these two different concepts one at a time, and give them the best possible chance of mastering them?

So for those who struggle with PbC, perhaps this is not the place to be using it quite so explicitly.

But what can we do instead?

I offer the following ideas.

Firstly, we usually start talking about infinities by showing lots of things are all equi-numerous. Counting numbers, integers, rationals, infinitely many buses of infinitely many tourists. We are almost setting them up to be upset when we demonstrate a set that's bigger. Suddenly they need to deal with:

• Proof by contradiction
• A set that's unexpected
• Only producing one thing not on the list

So instead, why not explicitly go hunting for something bigger. We have the set of counting numbers - call its size S.

• Do we get something bigger if we add 1 to it?
• No.
• Do we get something bigger if we add 2 to it?
• No.
• Do we get something bigger if we add n to it?
• No.
• Do we get something bigger if we add S to it?
• No.

• ... what about 3S - is that bigger?
• No.
• ... what about 4S - is that bigger?
• No.
• ... what about nS - is that bigger?
• No.
• ... what about SxS - is that bigger?
• No.

• What about $S^3$ - is that bigger?
• No.
• What about $S^n$ - is that bigger?
• No.

So instead of pushing back when we suggest such a thing can happen, they become curious as to how it can happen. They are no longer hostile to the idea, and we've removed that potential barrier.

But what about PbC - how can we avoid that? Maybe we can't avoid it, but maybe we can avoid some of the problems.

Let's start with something slightly more specific - how does the Diagonalisation Proof use it PbC, and can we do better?

One objection voiced by students is:

• But you've only produced one thing not on the list,
  so just add it on, and you're OK.

So instead of using the Diagonalisation Proof, let's use a different proof. Here's an example, expressed succinctly here, and needing expansion before use with actual students.

So ...

The real numbers can be thought of as all the points on the number line. We'll show that we can't write them all in a list. (Yes, this is a Proof by Contradiction, but bear with me.)

Actually, @TobyBailey says that you can't argue from some vague notion of the reals being a model of the line, you have to argue from the fact that the reals are the completion of the rationals. In truth, Cantor's argument uses decimal expansions, and there's work to be done showing that decimal expansions give us the completion of the rationals. Then we have to worry about the "ending in all 9's" problem. And so on. That's why I think it's better just to talk about distances from the origin to a place on the line, and so we're actually talking about the line. Not least, that's what the students seem to have in mind, and we usually talk about uncountability before talking about completions of the rationals.

So take a list of reals, any list of reals. Cover the first one with a line segment of length 1/2. (diagram required). We can imagine punching out a section of the real line, or colouring it red, or something.

Now find the second real from the list and cover it with a line segment of length 1/4. Colour it red. Then cover the third with a line segment of length 1/8, and so on. In particular, cover the $n^{th}$ real with a piece of line of length $2^{-n}.$

When we've done this, all the reals on our list will be covered, along with a(n increasingly) small neighbourhood. But certainly each real on our list will be covered.

But we've only used a total length of 1. Virtually all of the number line remains uncovered, uncoloured, and otherwise untouched.

We're not just showing that the list of reals we started with is incomplete, we've shown that's it's woefully incomplete. There's no way we can just "add them in" to our original list.

Using this approach seems to avoid many of the pitfalls of the usual Diagonalisation Proof, and might give a better idea of just how big the cardinality of the continuum really is. It's not just one thing missing from every list, it's that lists are completely inadequate.

So there are some half-baked, badly expressed thoughts about helping students understand c better, as well as wondering whether this is actually a good idea. I'd be interested in getting reactions, creating a dialogue, and maybe doing a better job of conveying how fascinating and counter-intuitive this topic can be.

Send me an email.