Problems On The Diagonal

Links to this page
Edit this page
Entry portal
Advice For New Users

Problems on the diagonal

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

I'd like to start a dialogue about this, and try to get to the heart of several questions:

I'm going to start with several observations and thoughts, mostly without too much justification or discussion, and then expand, enhance, and revise as necessary. This isn't a study backed by proper research, and there are no clear conclusions, but I hope the discussion will prove interesting and possibly useful.

So let's start with a few observations:

I'd like also to have a bit of a meta-rant.

It's pretty clear that for most students, there will come a point where they give up on academic maths and turn to more practical concerns. For those students there is likely to be a point where they just don't get it. Proof by contradiction is often that point, and maybe this is where we should just let that happen. Maybe trying to teach them about uncountability is not in their best interests, and the time could be better spent helping them with material and ideas that have a wider and deeper impact on a greater range of topics.

So why do students find Cantor's Diagonalisation proof hard?

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:

It's almost as if we want them to reject the idea, it's almost as if we're setting them up for failure.

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

This last thing we can call 2S, so ...

So now $S^2$ isn't bigger.

By this stage students are becoming disappointed that we haven't produced a bigger infinity, and are genuinely interested to see if there is some way of doing so.

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:

We know that's not valid, because we know that we've shown that every list is incomplete, and "add that one in" is irrelevant.
Of course, there's an argument to say that maybe we shouldn't. There are hard ideas in maths, and if we continue to remove the difficulties, then the students won't have to work, won't develop the abilities, and in the end, won't be well-served. Maybe we shouldn't make this easy.

An interesting point of view ...

But still the students will say it, and if we can avoid it, maybe we should.

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.

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout