Deleted text in red / Inserted text in green

WM

HEADERS_END

!! 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.

I'd like to start a dialogue about this, and try to get to

the heart of several questions:

* Why do they find it hard?

* Does it matter?

* Should we help?

* If so, what should we do to help?

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:

* 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?

[[[>50 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.

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

~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

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.*/

* 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.

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

* ... 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.

So now EQN:S^2 isn't bigger.

* What about EQN:S^3 - is that bigger?

** No.

* What about EQN:S^n - is that bigger?

** No.

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:

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

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

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.

[[[>50 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 real students.

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.)

[[[>50 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 EQN:n^{th} real with a piece of

line of length EQN: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.