Proofs are not arrived at easily – they often come at the end of a great deal of exploration and false trails. The struggle to provide them occupies the centre ground of the mathematician’s life. A successful proof carries the mathematician’s stamp of authenticity, separating the established theorem from the conjecture, bright idea or first guess.

Qualities looked for in a proof are rigour, transparency and, not least, elegance. To this add insight. A good proof is ‘one that makes us wiser’ – but it is also better to have some proof than no proof at all. Progression on the basis of unproven facts carries the danger that theories may be built on the mathematical equivalent of sand.

Not that a proof lasts forever, for it may have to be revised in the light of developments in the concepts it relates to.

What is a proof?

When you read or hear about a mathematical result do you believe it? What would make you believe it? One answer would be a logically sound argument that progresses from ideas you accept to the statement you are wondering about. That would be what mathematicians call a proof, in its usual form a mixture of everyday language and strict logic. Depending on the quality of the proof you are either convinced or remain sceptical.

The main kinds of proof employed in mathematics are: the method of the counterexample; the direct method; the indirect method; and the method of mathematical induction.

The counterexample

Let’s start by being sceptical – this is a method of proving a statement is incorrect. We’ll take a specific statement as an example. Suppose you hear a claim that any number multiplied by itself results in an even number. Do you believe this? Before jumping in with an answer we should try a few examples. If we have a number, say 6, and multiply it by itself to get 6 × 6 = 36 we find that indeed 36 is an even number. But one swallow does not make a summer. The claim was for any number, and there are an infinity of these. To get a feel for the problem we should try some more examples. Trying 9, say, we find that 9 × 9 = 81. But 81 is an odd number. This means that the statement that all numbers when multiplied by themselves give an even number is false. Such an example runs counter to the original claim and is called a counterexample. A counterexample to the claim that ‘all swans are white’, would be to see one black swan. Part of the fun of mathematics is seeking out a counterexample to shoot down a would-be theorem.

If we fail to find a counterexample we might feel that the statement is correct. Then the mathematician has to play a different game. A proof has to be constructed and the most straightforward kind is the direct method of proof.

The direct method

In the direct method we march forward with logical argument from what is already established, or has been assumed, to the conclusion. If we can do this we have a theorem. We cannot prove that multiplying any number by itself results in an even number because we have already disproved it. But we may be able to salvage something. The difference between our first example, 6, and the counterexample, 9, is that the first number is even and the counterexample is odd. Changing the hypothesis is something we can do. Our new statement is: if we multiply an even number by itself the result is an even number.

First we try some other numerical examples and we find this statement verified every time and we just cannot find a counterexample. Changing tack we try to prove it, but how can we start? We could begin with a general even number n, but as this looks a bit abstract we’ll see how a proof might go by looking at a concrete number, say 6. As you know, an even number is one which is a multiple of 2, that is 6 = 2 ×3. As 6 × 6 = 6 + 6 + 6 + 6 + 6 + 6 or, written another way, 6 × 6 = 2 × 3 + 2 × 3 + 2 × 3 + 2 × 3 + 2 × 3 + 2 × 3 or, rewriting using brackets,

6 × 6 = 2 × (3 + 3 + 3 + 3 + 3 + 3)

This means 6 × 6 is a multiple of 2 and, as such, is an even number. But in this argument there is nothing which is particular to 6, and we could have started with n = 2 × k to obtain

n × n = 2 × (k + k + . . . + k)

and conclude that n × n is even. Our proof is now complete. In translating Euclid’s Elements, latter-day mathematicians wrote ‘QED’ at the end of a proof to say job done – it’s an abbreviation for the Latin quod erat demonstrandum (which was to be demonstrated). Nowadays they use a filled-in square . This is called a halmos after Paul Halmos who introduced it.

The indirect method

In this method we pretend the conclusion is false and by a logical argument demonstrate that this contradicts the hypothesis. Let’s prove the previous result by this method.

Our hypothesis is that n is even and we’ll pretend n × n is odd. We can write n × n = n + n + . . . + n and there are n of these. This means n cannot be even (because if it were n × n would be even). Thus n is odd, which contradicts the hypothesis. 

This is actually a mild form of the indirect method. The full-strength indirect method is known as the method of reductio ad absurdum (reduction to the absurd), and was much loved by the Greeks. In the academy in Athens, Socrates and Plato loved to prove a debating point by wrapping up their opponents in a mesh of contradiction and out of it would be the point they were trying to prove. The classical proof that the square root of 2 is an irrational number is one of this form where we start off by assuming the square root of 2 is a rational number and deriving a contradiction to this assumption.

The method of mathematical induction

Mathematical induction is powerful way of demonstrating that a sequence of statements P₁, P₂, P₃, . . . are all true. This was recognized by Augustus De Morgan in the 1830s who formalized what had been known for hundreds of years. This specific technique (not to be confused with scientific induction) is widely used to prove statements involving whole numbers. It is especially useful in graph theory, number theory, and computer science generally. As a practical example, think of the problem of adding up the odd numbers. For instance, the addition of the first three odd numbers 1 + 3 + 5 is 9 while the sum of first four 1 + 3 + 5 + 7 is 16. Now 9 is 3 × 3 = 3² and 16 is 4 × 4 = 4², so could it be that the addition of the first n odd numbers is equal to n²? If we try a randomly chosen value of n, say n = 7, we indeed find that the sum of the first seven is 1 + 3 + 5 + 7 + 9 + 11 +13 = 49 which is 7². But is this pattern followed for all values of n? How can we be sure? We have a problem, because we cannot hope to check an infinite number of cases individually.

This is where mathematical induction steps in. Informally it is the domino method of proof. This metaphor applies to a row of dominos standing on their ends. If one domino falls it will knock the next one down. This is clear. All we need to make them all fall is the first one to fall. We can apply this thinking to the odd numbers problem. The statement Pn says that the sum of the first n odd numbers adds up to n². Mathematical induction sets up a chain reaction whereby P₁, P₂, P₃, . . . will all be true. The statement P₁ is trivially true because 1 = 1². Next, P₂ is true because 1 + 3 = 1² + 3 = 2², P₃ is true because 1 + 3 + 5 = 2² + 5 = 3² and P₄ is true because 1 + 3 + 5 +7 = 3² + 7 = 4². We use the result at one stage to hop to the next one. This process can be formalized to frame the method of mathematical induction.

Difficulties with proof

Proofs come in all sorts of styles and sizes. Some are short and snappy, particularly those found in the text books. Some others detailing the latest research have taken up the whole issue of journals and amount to thousands of pages. Very few people will have a grasp of the whole argument in these cases.

There are also foundational issues. For instance, a small number of mathematicians are unhappy with the reductio ad absurdam method of indirect proof where it applies to existence. If the assumption that a solution of an equation does not exist leads to a contradiction, is this enough to prove that a solution does exist? Opponents of this proof method would claim the logic is merely sleight of hand and doesn’t tell us how to actually construct a concrete solution. They are called ‘Constructivists’ (of varying shades) who say the proof method fails to provide ‘numerical meaning’. They pour scorn on the classical mathematician who regards the reductio method as an essential weapon in the mathematical armoury. On the other hand the more traditional mathematician would say that outlawing this type of argument means working with one hand tied behind your back and, furthermore, denying so many results proved by this indirect method leaves the tapestry of mathematics looking rather threadbare.

the condensed idea

Signed and sealed