Basic Methods of Mathematical Proof Content from the guide to life, the universe and everything

Basic Methods of Mathematical Proof

8 Conversations

Numbers | A History of Numbers | Propositional Logic | Logical Completeness | The Liar's Paradox
Logical Consistency | Basic Methods of Mathematical Proof | Integers and Natural Numbers
Rational Numbers | Irrational Numbers | Imaginary Numbers | The Euler Equation

In mathematics you can't just say that something is true; you have to prove it. Mathematical proofs1 have to be rigorous. This means that they have to hold true regardless of what test you may apply to them. If they don't, they aren't proofs at all.

We Hold These Truths to be Self-evident

So you want to prove something, and you want your proof to have no holes in it. Where do you start?

A good place to begin is called 'first principles'. Going back to first principles means going back to the basic facts about mathematics and science which seem so obvious, that you cannot argue with them.

The best known example of a mathematical system that is based on a structure of basic principles (or axioms), is described in the book Elements of Euclid. This was and is and probably will always be the most successful geometry textbook of all time. Euclid was born circa 325 BC, but since the invention of the printing press, his book has been through more than 1000 editions.

Euclid set forth a series of axioms which appear to be self-evident. For centuries, mathematicians viewed these as almost gospel truths. More recently, however, they have realised that instead of being the root of all geometry, Euclid's axioms are more like a set of agreed-upon standards from which to proceed. Even if they aren't gospel, they are very important. Starting with a basis of axioms, or first principles, one can use these to probe the limits of your system. If your axioms are true, you can then find out what else is true. Also, if you have a theory you wish to prove, then if it is true, you can probably deduce it from your axioms. Changing your basic axioms can open up a whole new mathematical system, which might not always be intuitively obvious, but may very well prove just as useful.

There is no such thing as an absolute proof - you will always have to start somewhere.

Proof by Induction

Proof by induction is applicable to integers. If you have a theorem which holds true for some value of n, for example n = k, you then deduce that if this is true it will also be true for n = k + 1. Finally establish that it is true when n = 1. We then know it will be true for n = 2, 3, 4...

A Practical Example2

Suppose I want to prove that if I line up a row of dominoes sufficiently close together, and then push the one on the end, they will all fall over.

  1. First, I push one domino, to see if it will fall over. Assuming it does, I proceed to step 2.

  2. Then I line up two dominoes, close together, and I push the first one over. This should cause the second domino to fall. We observe that a falling domino pushes the next one over.

  3. From this we can deduce that when n = 3, or in fact for all n, pushing the first domino will cause all the rest of them to fall in sequence.

Observing that a falling domino pushes the next one down in step 2 is like proving the (k + 1)th case follows from the kth case. Pushing the first one over yourself proves that it is true for the case of n = 1.

Proof By Contradiction

This is also known as reductio ad absurdam. In this instance, you assume that the opposite of what you expect to prove is true. From this you deduce a propsition you know to be false. If your original assumption led to a false conclusion, the original assumption must have been false, therefore its converse, the thing you were trying to prove, is true.

A Practical Example

A classic proof by contradiction is Euclid's proof that the square root of 2 cannot be expressed as a fraction (in other words a/b, where a and b are integers). You can find this proof in the entry on Irrational Numbers.

What if You Can't Prove it?

Sometimes you may have difficulty using one of the more rigorous proof methods to prove your theory. In this case you may wish to refer to one of the methods listed below3.

For simplicity's sake we will mainly consider the case of a lecturer presenting a lecture course. These 'proofs' can be modified to apply to other situations, like the writing of books or the winning of arguments in the pub.

Reductio ad Nauseam

The aim of this proof is to be boring. This proof succeeds where you have the entire class either asleep, or even better, not taking notes. When you observe that your class is in this state, wipe the blackboard, then write your conclusion on it. You can then announce 'and therefore we have our result', and then state the theorem you were trying to prove. At this point everyone will wake up, write the conclusion down, and make a note to get the rest of the proof of another member of the class at a later date. The strength of this proof is that there are no other class members with the full proof written down - your result is therefore proved.

Reductio ad Erratum

This proof is achieved by introducing an error into your working, hopefully subconsciously, which isn't spotted by the class. You can do this by:

  • Introducing lots of errors, one of which may slip through.

  • Using confusing letters like a lower case p for one quantity, and a small Greek letter rho for another.

  • Writing all the consequences of a statement on random corners of the blackboard, making the error difficult to spot.

Once an error has been introduced and got past the class, it will eventually come to the surface to let you prove your theorem.

Proof by Osmosis

At no point do you ever state the theorem you want to prove by osmosis; you just assume it to be true throughout the course. Eventually, your class will somehow pick it up, as if by osmosis. If you are lecturing this course with someone else, you may assume they will cover it, and they can assume you will cover it.

Proof by Infinite Delay

When you want to use this proof, you say theorem A is true, and that you will prove it in a later lecture... and then don't. The chances are that no one will notice, and even if they do, it will probably be after the course is over.

Proof by Homework Assignment

This is used in books when they say: 'Proof by exercise (left to reader)'. State a theorem, and then say that it is trivial to prove, and that the class can prove it at home or in their own time.

Proof by Sounding Similar

Suppose you have three lemmas4 A, B and C. You can prove 'B therefore C', and you want to be able to say 'A therefore B, therefore C', but you can't prove 'A therefore B'. Prove something similar instead, like 'B therefore A'. Hopefully no one will notice.

Proof by Blatant Assertion

Say 'A therefore B', and sound as if you really mean it. Hopefully no one will dare question you. This is the preferred method of Douglas Adams, who suggests using the phrase 'studies show', on the grounds that nobody ever asks exactly which studies you mean.

Proof by Circular Cross Reference

Suppose you wish to prove A. Assume A for the time being, and use it to prove B. Then use B to prove A. It can sometimes help to do something slightly more complicated; for example, assume A, then do 'A therefore B' and 'B therefore C', and after that 'C therefore A'.

Proof by Publication

This can also be known as 'proof by having friends in high places'. To be successful with this proof, make friends with someone who can get your work published in a journal, skipping the peer-review protocol. This way your proof, even if it doesn't prove anything, will be accepted, and you can say hello to fame and fortune5.

1As opposed to legal, scientific or philosophical proofs.2This example has been borrowed from here, originally by Idris Hsueh-Heng Hsi.3These methods are used at your own risk. The author accepts no responsibility for the failure of a proof listed in this section.4Subsidiary or intermediate theorems, used in the proof of a bigger theorem.5This has actually happened.

Bookmark on your Personal Space


Edited Entry

A387470

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry

Categorised In:


Written by

Credits

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more