Introducing Induction
Our familiarity with the natural numbers can make us almost arrogant, of course we understand the simplest of numbers, but in truth they can demonstrate and give rise to incredibly powerful mathematical tools. Here we are going to look at two of those impressive tools: Axioms and Induction.
Axioms
Axioms are statements which are taken to be self-evidently true, the word is dervied from ancient Greek, it means 'what is thought fitting'. Many abstract structures in mathematics are defined upon different axioms. You can think of them as the particular set of rules for whichever mathematical board game you're playing; they define the players, the moves and the consequences of each action. As a concept themselves they can seem quite abstract, but we can use the familiar natural numbers to see how they work.
Italian mathematician Giuseppe Peano proposed the following 5 axioms for the natural numbers in 1889. Notably this is a long, long time after the natural numbers started to be used by humans. There is evidence of people counting, writing tally-like markings on bones, which is thought to date as far back as 44 000 BCE. We must appreciate, therefore, that Peano's writing of these axioms is a much more difficult task than making up the rules for a board game. Instead he was trying to write the rules for a game that already existed, that had been played by hundreds of thousands of humans tens of thousands of years before he was even born. See what you think of his attempt.
-
1 is a natural number.
-
Every natural number has a successor (one that comes after it) and the successor is a natural number too.
-
1 is not the successor of any natural number. (This guarantees that 1 comes first)
-
If two natural numbers have the same successor, then the two numbers are the same. (So for example, if x is immediately followed by 11 and y is immediately followed by 11, then x and y are the same, in this case x=y=10)
-
If a statement is true for 1 and the truth of the statement for a natural number implies the truth of the statement for its successor then the statement is true for all natural numbers. (Don't worry, we're going to break this one down next)
Hopefully as you read through axioms 1-4 you can agree that Peano has done a decent job of writing some true things about the natural numbers. 1 is one of them, true and simple enough. Every natural number is followed by the next natural number, true and in fact very clever. After the first axiom there is only one guaranteed natural number, 1. When the second axiom is introduced, now every natural number must be followed by another, so because 1 exists 2 must exist, so 3 must exist, so 4 must exist, so on and so forth. All of a sudden there must be infintely many natural numbers. The third axiom says that 1 is never next, true because 1 is the first (this can be replaced by 0 should you wish to include it). The fourth axiom is true as illustrated by the example above, but this one is deeper than it might seem; it implies the infinitely long 'queue' formed by the natural numbers, there are no two different routes to any one of them, we can only start at the beginning and move one by one to each successor. So we can agree that Peano's first 4 axioms do reflect the nature of the natural numbers. It might occur to you though that what he has done is written down some things that everybody already knew were true, why? To what end? To see the power in this we will look more closely at that much wordier fifth axiom: the axiom of induction.
The Axiom of Induction
A good portion of the mathematician's work is to spot patterns, to develop ideas about the underlying rules which give rise to those patterns and then to set about proving that those rules are true. The proof part tends to be the most onerous, unless we can be clever about it.
Now, since the natural numbers are our most familiar and simple numbers, we should like to think that proving something for them should be simple enough. But there is an infinitely long queue of natural numbers to deal with, infinitely many cases to prove, we would need infinite time in order to tick them off one by one. Enter, the axiom of induction.
'If a statement is true for 1 and the truth of the statement for a natural number implies the truth of the statement for its successor, then the statement is true for all natural numbers.'
To understand this, imagine the infinite queue. Let's say we want to prove that everyone in the infinite queue is queuing for chips (seems sensible). One way to do this is to start at the beginning and check with everyone in turn that they are waiting in the queue for chips. As previously mentioned though this would require infinite time. An alternative method would be: to check that the first person is queuing for chips, to check that if any one person is queuing for chips, then the next person is also queuing for chips. If both of those things are true, then in fact the entire queue must be waiting for chips because the first person is, and if they are then the second person is too, and if they are then the third person is too, and if they are then the fourth person is too, so on and so forth. So rather than trying to prove infinitely many little statements requiring infinite time we can prove only two more cleverly chosen statements and that is the simple beauty of induction.
Proof by Induction: An example
You should recognise the relationship in this proof from studying the sequence of triangle numbers. The full proof is below or watch the video for a step-by-step explanation.
Prove it
Try proving each of these statements using the principle of induction.
Remember you can always assume the statement holds for the natural number 'k' and use that to prove that it holds for 'k+1'. Separately check that it holds for 1 and then you can conclude that it holds for all natural numbers by induction.
When you are happy with your proof you can check them on the next page.