4 Proofs

In mathematics, statements are frequently proven true for infinite sets of numbers. For example, every number which is a multiple of 4 is also a multiple of 2. Of course, there are infinitely many multiples of 4, so how can you check that each one is also a multiple of 2? You could work it out, number by number, over and over again. But how high do you need to count to be certain it’s true for all numbers? 100? 1000? 10000? Ultimately, to be absolutely sure via this method, you’re going to be checking every number from here until eternity.

Instead, you want a proof that works for all numbers. So, first of all: what is a proof? Intuitively, a proof is an argument that leads you from true assumptions, through truth-preserving steps, to a true conclusion. You can make direct proofs about statements concerning infinite sets of numbers, as you would with the example ‘every number which is a multiple of 4 is also a multiple of 2’.

Another type of proof which is used with infinite sets of numbers is called ‘induction’. Proof by induction takes only two steps. Suppose you have a statement you want to prove. You start by proving the statement for the first number. This is called proving the ‘base case’. The next stage is to prove what’s called the ‘induction step’. You look at an arbitrary number, call it k. If you can prove that when the statement is true for k it is also true for the successor of k, then you are finished. You can think about this step by step:

• You have shown the statement is true for the first number.
• You have also shown that when the statement is true for one number, it is automatically true for the following number.
• This means the statement is true for the number following the first number – in other words, it’s true for the second number.
• But this also means the statement is true for the number following the second number, so you know it is true for the third number.

See how this logic shows you that the statement is true for all numbers.

To make another practical analogy, imagine dominoes lined up.

Figure 5 Dominoes in a line

Show description|Hide description

A picture of a row of dominoes labelled with numbers 1, 2, 3. This is followed by a gap, then dominoes labelled k and k+1.

Figure 5 Dominoes in a line

Suppose that:

• The first domino falls.
• If domino k falls, then the next domino k+1 will fall.

These two facts together tell us that all the dominoes will fall.

Proof by induction is a powerful tool in mathematics, used particularly in Number Theory. Just two steps can be all you need to be acquainted with an infinite string of numbers or facts. This is one of the ways in which infinite sets can actually be simpler than finite ones.