Mathematical structures, 5

When I commuted from Oxford, the worst part of the journey was the Hammersmith & City line from Paddington to Stepney Green, twelve stops. So I used to count off the twelve weeks of the semester as stops on that line. By that reckoning, we are just pulling in to King’s Cross now.

This week we are talking about the natural numbers and their most important property, induction. I started Tuesday’s lecture by saying “It’s induction week”, and got no response at all; so at least they have good taste in humour.

To foundationists, some form of induction is an axiom. But with my philosophy of coming in at the ground floor, it is a derived property. We know that it is possible (in principle) to count up to any natural number, starting at 1; even if we don’t actually go through all the steps, we could do so if challenged. Mathematicians write {1,2,…,99,100} for what my children, when they were at primary school, used as a quick way to count to 100:

One, two, missed a few,
Ninety-nine, a hundred.

From this, we see that, if S is a subset of natural numbers which contains 1 and has the property that if it contains any number then it contains its successor, then S must contain all natural numbers. Hence, if P is a property of natural numbers for which P(1) is true and P(n) implies P(n+1), then P holds for all natural numbers: the usual technique of proof by induction.

From that, it is possible to prove the technique of strong induction: if P is a property such that the truth of P(m) for all m<n implies the truth of P(n), then P holds for all natural numbers. This looks more complicated, but has two big advantages: first, there is no need to “start the induction”; secondly, the proof is probably going to be easier since the hypothesis is much stronger (viz., P holds for all smaller numbers, not just the immediate predecessor). As an example, I gave them the proof that every natural number greater than 1 has a prime divisor (which we had identified as a gap in Euclid’s proof that there are infinitely many primes, earlier in the semester).

I did the best I could, but to the students induction still looks as if it is somewhere on the scale between magic and fraud. You are assuming what you have to prove, aren’t you? Explanations in terms of domino-toppling make it clear, but when you meet a specific proof, it is hard to avoid this feeling. At the end of the first simple proof, that the sum of the first n natural numbers is n(n+1)/2, I asked for a show of hands for who was not convinced; quite a few people indicated that they were not, and we spent some time working through their objections.

I had hoped to cover greatest common divisors and Euclid’s algorithm; that will have to wait until next week now.

Previous | Next


About Peter Cameron

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

2 Responses to Mathematical structures, 5

  1. jan3grabowski says:

    What doesn’t help matters is that the use of induction can be circumvented in some cases, making it even more susceptible to scepticism. For example, one can prove the formula for the sum of the first n natural numbers using the methods of solving linear inhomogeneous recurrence relations. Even less helpfully, in that case the method produces the formula naturally – without having to guess it first. (There is still a “free” element of choice, in finding particular solutions, but it’s easier to guess what to do.)

    The case of infinitely many primes is more convincing in my view: is there a “reasonable” alternative proof of that result avoiding induction, I wonder?

  2. The students had actually seen Gauss’ method of adding the first n natural numbers on problem sheet 1: write them down in reverse order underneath and add by columns rather than rows. First years are not going to solve linear inhomogeneous recurrence relations.

    I will say more about this in the next instalment.

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