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