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:
- Assume P, and prove Q.
- Use contradiction: assume that P is true and Q is false and reach an impossible situation.
- 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:
- First, write down clearly the statement P(n) you are trying to prove.
- Prove that P(1) is true.
- Prove the implication P(n) ⇒ P(n+1).
- 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.