Proof by Exhaustion

 

 

When they want to prove something most mathematicians begin with a series of axioms that everyone accepts and they then progress from these in a series of very careful logical steps to a conclusion. Because the steps are so careful there is no chance that the conclusion is wrong as long as the axioms at the start are right.

 

However, this is not the only kind of proof that we use in mathematics. There is another method called Proof by Exhaustion, also known as the brute force method, where the statement to be proved is split into a limited number of cases, and each case is proved separately.

 

A proof by exhaustion contains three stages:

1.       splitting the statement up into a limited number of cases

2.       proving that those cases are exhaustive i.e. there are no cases that have been missed out (or to put it more mathematically proving that each instance of the statement to be proved matches the conditions of (at least) one of the cases.)

3.       proving that the statement is true in each of the cases that you have picked out

 

A proof by exhaustion does not always possess the kind of simple beauty of most mathematical proofs but it can still be a formally valid proof.

 

 

Some Examples:

Here is an attempt to prove that every cube number is either a multiple of 9 or is 1 more or 1 less than a multiple of 9.

 

First we begin by working out the different number of cases that there are and proving that we have not missed any cases:

1.       We know that a cube number is what you get when you perform the calculation: n x n x n = cube.

2.       We know that this first is either a multiple of 3, or is 1 more or 1 less than a multiple of 3.

3.       How do we know this? Hereís why! Letís look at what happens with the numbers from 2 to 7, (excluding 1 because 1 is a special case) we have: 2, 3, 4, 5, 6 and 7. Obviously 3 and 6 are multiples of 3, while 2 and 5 are both one less than a multiple of 3 and 4 and 7 are both one more than a multiple of 3. Because multiples of three keep going up in threes you can see that this pattern is going to be repeated forever. So we know that the there are only three possible cases or, to put it another way, the following 3 cases are exhaustive:

         Case 1: If n is a multiple of 3 then the cube of n is a multiple of 27, and so certainly a multiple of 9.

         Case 2: If n is 1 more than a multiple of 3 then the cube of n is 1 more than a multiple of 9.

         Case 3: If n is 1 less than a multiple of 3 then the cube of n is 1 less than a multiple of 9.

 

The next step is to prove that the statement is true for each of those three cases, which can be done with some quite simple algebra.

 

Another example of the use of proof by exhaustion is the first proof of the Four Colour Map Theorem. The Four Colour Map Theorem stated that any map could be coloured in using only four colours so that no two areas that are touching each other are the same colour. This first proof contained of this theorem contained 1,936 cases but it was controversial because the majority of the cases were checked by a computer program, not by hand. The shortest known proof of the four colour theorem today still has over 600 cases.

 

 

How Many Cases are Needed?

There is no upper limit to the number of cases allowed in a proof by exhaustion. Sometimes there are only two or three cases. Sometimes there may be thousands or even millions. For example, rigorously solving a puzzle in chess might involve considering a very large number of possible positions. This is how computer simulators can learn to play such good chess Ė they donít have a strategy, they just work out the consequences of every possible move and see which one is most likely to lead to victory.


However, mathematicians prefer to avoid proofs with large numbers of cases because these proofs feel inelegant, they leave an impression that the theorem is only true by coincidence, and not because of some underlying principle or connection. Nonetheless, there are some important theorems for which no other method of proof has been found.

 

http://ddi.cs.uni-potsdam.de/Lehre/TuringLectures/MathNotions.htm

http://www.statemaster.com/encyclopedia/Proof-by-exhaustion