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

• Peter Cameron says:

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!

This site uses Akismet to reduce spam. Learn how your comment data is processed.