Edit made on December 03, 2013 by ColinWright at 13:01:26
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.