Mathematical Structures: coda

At the end of last term, my colleague Konstantin Ardakov took the final week of lectures in Mathematical Structures so I could go to Lisbon. This week, I am repaying the debt. The module is Introduction to Algebra; many of the students already took Structures but there is a sizeable contingent of second-years who didn’t, so I am going over some of the material again.

This morning I talked about proving implications, and started on induction. Having the two topics in the same lecture, I noticed a small but maybe important pedagogical point.

First, I offered the students three different ways to prove the implication P ⇒ Q:

  1. Assume P, and prove Q.
  2. Use contradiction: assume that P is true and Q is false and reach an impossible situation.
  3. Prove the contrapositive (not Q) ⇒ (not P).

We had seen that the contrapositive of an implication is equivalent to the original.

The scheme for induction is usually stated like this: “To prove a statement P(n): First prove P(1); then assume P(n) and prove P(n+1); it follows by induction that P(n) holds for all natural numbers n.” This leads to some confusion; for example, some students think that you are assuming the statement P(n) that you are trying to prove.

In fact the scheme (as I outlined it to the class) is this:

  1. First, write down clearly the statement P(n) you are trying to prove.
  2. Prove that P(1) is true.
  3. Prove the implication P(n) ⇒ P(n+1).
  4. Conclude, by induction, that P(n) holds for all natural numbers n.

As well as (hopefully) avoiding the above confusion, this is more flexible; we already talked about proving an implication, and saw three different ways to do it.

Previous | Next


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in teaching and tagged , , . Bookmark the permalink.

2 Responses to Mathematical Structures: coda

  1. Joseph Nebus says:

    I’d be interested to know whether outlining induction in that precision does avoid confusion. I remember in my learning what what you’ve identified as the third step was the one that I most often tripped on (I suppose it’s most often the actually hard part), but my experience is almost always the unusual one.

    • One source of confusion is this. You write down P(n), your assumption for this step. You then forget that this is for a specific n, and regard it as being a general statement, in which it is legitimate to replace n by n+1. Miraculously, the job is done!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s