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