A proof is a logical argument that establishes, beyond any doubt, that something is true. How do you go about constructing such an argument? And why are mathematicians so crazy about proofs?
Which way around?
What can maths prove about sheep?
In everyday life, when we're not just being completely irrational, we generally use two forms of reasoning. One of them, called inductive reasoning, involves drawing a general conclusion from what we see around us. For example, if all the sheep you have ever seen were white, you might conclude that all sheep are white. This form of reasoning is very useful — scientists form their theories based on the observations they make in a similar way — but it's not water tight. Since you can't be sure that you have seen every single sheep in the Universe, you can never be sure that there isn't a black one hiding somewhere, so you can't be sure your conclusion is really true. If you use inductive reasoning, you have to be open to revising your conclusion when new evidence comes to light, and that's what scientists generally do.
The other form of reasoning, called deductive reasoning, goes the other way around. You start from a general statement you know for sure is true and draw conclusions about a specific case. For example, if you know for a fact that all sheep like to eat grass, and you also know that the creature standing in front of you is a sheep, then you know with certainty that it likes grass. This form of reasoning is water tight. It can only go wrong if your premise is false, that is if you're wrong about all sheep liking grass, or if your observation is wrong, that is, the creature you're looking at is not actually a sheep. But if those two things are correct, then your conclusion follows necessarily from your premise: it is true everywhere and for eternity.
It's all about axioms
A flawed proof
Mathematics is all about proving that certain statements, such as Pythagoras' theorem, are true everywhere and for eternity. This is why maths is based on deductive reasoning. A mathematical proof is an argument that deduces the statement that is meant to be proven from other statements that you know for sure are true. For example, if you are given two of the angles in a triangle, you can deduce the value of the third angle from the fact that the angles in all triangles drawn in a plane always add up to 180 degrees.
The importance of deductive reasoning in maths has been known since the ancient Greeks. Euclid of Alexandria, known as the father of geometry, came up with a collection of axioms, statements he thought were clearly true and needed no further justification (click here to see them). These included (in a slightly different form) the statement that the internal angles of a triangle add up to 180 degrees. Any other statement about geometry, for example Pythagoras' theorem, should be deduced from these axioms by deductive reasoning. Euclid's famous maths book The Elements was based on this approach. It's one of the most successful books in history — some say that it has gone through more editions than the bible.
But of course, you still need to be very careful with deductive reasoning as mistakes can easily slip in. To be certain your conclusion is right, you need to be certain that your general assumptions are correct and that you've used them correctly. For example, the proof in the box on the right only makes use of basic assumptions on how to manipulate equations, but it's conclusion is that 1=2. Can you spot the flaw?
Do we need proofs?
Why do mathematicians insist on proving everything? In normal life, we're not as pedantic. If all the evidence in a murder case points to a particular suspect, we're happy to convict them and say their guilt has been proved "beyond reasonable doubt". But then, we can never be really sure. As any innocent convict will tell you, there's always a chance they didn't do it.
Mathematics is perhaps the only field in which absolute certainty is possible, which is why mathematicians hold proofs so dearly. Also, if we don't insist on proofs, mistakes can creep in that aren't easily spotted otherwise. A famous example comes from the above-mentioned triangles. One of Euclid's axioms is equivalent to saying that the sum of the internal angles of all triangles is 180 degrees — he thought this was so obvious, we should just accept it. Mathematicians that came after him, however, thought they could do better. They tried to derive this fact from Euclid's other axioms. That way, we don't just have to believe it, but can consider it as proven (assuming the other axioms are correct).
Mathematicians were struggling with this proof for hundreds of years. During the 19th century it even became a bit of an obsession, so much so that the mathematician Farkas Bolyai felt compelled to warn his son János to stay away from it:
"For God's sake, I beseech you, give it up. Fear it no less than sensual passions and because it, too, may take all your time, and deprive you of your health, peace of mind and happiness in life."
![[IMAGE: Circle limit IV]](/issue18/xfile/hyperbolic.jpg)
M.C. Escher's Circle limit IV illustrates a model of the hyperbolic plane.
All M.C. Escher works © 2002 Cordon Art - Baarn - Holland (www.mcescher.com).
But János Bolyai persevered and, along with everyone else, failed to prove that the angles in a triangle always sum to 180 degrees. The reason is that it isn't always true. It only works if you draw your triangle on a flat plane. If you draw it on a sphere, say an orange, the interior angles add up to more than 180 degrees. In the attempt to prove the 180 degree result mathematicians (including Bolyai) stumbled across another very strange surface, called the hyperbolic plane, on which the angles in a triangle add up to less than 180 degrees.
The hyperbolic plane is hard to visualise, but it is similar to a kale leaf that gets more and more crinkly as you move towards the edge (see here to find out more). Although we don't come across that strange surface in everyday life, it is very important. Einstein's special theory of relativity is formulated using hyperbolic geometry. Out of special relativity grew the general theory of relativity, without which modern satnav devices and GPS enabled phones wouldn't work.
Do we need people?
Mathematicians often pride themselves on the fact that all they need to do their work is their brain and a pencil and paper. But over the recent decades this has begun to change: computers have entered mathematics and sparked a lot of controversy. The controversy doesn't concern making the odd calculation using a calculator or computer. Mathematicians use those devices to make their life easier, just like everyone else. It concerns whole proofs that rely on computers.
There are two ways in which this can happen. In computer assisted proofs a computer is used to perform a large number of steps that a single human couldn't possibly manage in any reasonable amount of time. The logic of the proof itself still comes from a human, but if no single person can check through all the calculations a computer performed, you can't be 100% certain that the proof doesn't contain a mistake, so some would consider such proofs as invalid. See here for more on computer assisted proofs.
Over recent years computer scientists have also developed automated theorem provers (ATPs) — computer programs that can derive a result from some basic premises using the rules of logic and thereby prove it. So far ATPs still need a lot of human input to work properly, but it's conceivable that in the future they will become far more potent. Whether or not they will ever be able to replace humans remains to be seen, and it's a topic that's hotly debated. See The future of proof for more information.
The limits of maths
Does mathematics really live up to the noble claim that every statement it makes can be proven true or false beyond any doubt? Unfortunately not entirely. At the beginning of the twentieth century people worked had to put all of mathematics, rather than just sub-areas like plane geometry, on a rigorous footing, making sure that every true statement can be derived from a few basic axioms. It wasn't an easy task. A famous attempt by Bertrand Russell and Alfred North Whitehead made the maths pretty hard going: a proof that 1+1 = 2, based on their choice of axioms, spanned a few hundred pages. Their system also contained a flaw. They couldn't show that it didn't contain any contradictions.
Kurt Gödel
A few years later a young Austrian mathematician by the name of Kurt Gödel delivered a fatal blow to their dream. Suppose you have chosen a set of axioms you think should underlie all of maths. That set of axioms would be no good if it didn't allow you to define and draw conclusions about the natural numbers and their arithmetic, so let's also assume that your set of axioms is strong enough to do that. Let's also assume that as you build up all of mathematics from your axioms, proving one statement after the other, you don't encounter any contradictions: the system you can build with your axioms is contradiction-free. What Gödel proved is that in the resulting system there will always be mathematical statements you can't prove to be either true or false using your axioms: there will always be undecidable statements.
This is quite a shocking result: it means that no matter what set of axioms you choose, the mathematics you can build up from it will always be incomplete. This is why Gödel's results (there were in fact two separate ones) are called the incompleteness theorems. Mathematicians have concrete examples of statements that cannot be proved using the accepted axioms of mathematics. When you come across such an undecidable statement, you essentially have to make up your own mind as to whether you believe it's true or not. (To find out more about the incompleteness theorems see here.)
Unfortunately though, Gödel's results don't serve as an excuse to tear up your tax bill on the grounds that you don't believe it. The kind of maths people use every day, be it to calculate taxes or build airplanes, is undisputed. The undecidable statements mathematicians have found so far (see here for some examples) don't enter into these areas. If one day undecidable statements do interfere with our technologies and calculations, then mathematicians will have to revert to the scientists' approach and base their opinions as to what's true or false on their observations of what's happening around them.
Further reading
Find out more about proofs in the following series of articles:
- The origins of proof
- The origins of proof II: Kepler's proofs
- The origins of proof III: Proof and puzzles through the ages
- The origins of proof IV: The philosophy of proof
You can see all Plus articles to do with proofs here.
About the author
Marianne Freiberger is Editor of Plus.
Comments
The Flawed Proof
Please explain the flawed proof!! I came across a variation on that bloody thing a few years ago and still don't know why it's wrong. Obviously it is...but where do the operations go wrong??
Careful what you cancel...
Consider the second equation, i.e. a^2 = ab. Subtracting ab from both sides gives you a^2 - ab = 0. If you look at the last equation (with the a's and b's in it) and substitute in 0 for the expression a^2 - ab as just obtained, on both sides, you have 2 x 0 = 1 x 0, i.e. 0 = 0 which is perfectly correct. The error is to cancel on both sides an expression that you've shown to be equal to zero, otherwise you can "prove" an infinite number of absurdities, e.g. if 1 x 0 = 100 x 0, then cancelling the zeros on each side would "prove" that 1 = 100, etc.
Why this cancellation is invalid
It should be noted that "cancelling" in the sense used here is a short version of what's really going on. Consider this equation:
a*x = a * y
The justification for being able to cancel the "a" on both sides is that you can multiply both sides of the equation by any number except zero. In this case, the desired choice is the reciprocal of a, i.e. 1/a
When doing so, the equation now looks like:
(1/a) * a * x = (1/a) * a * y
which can be rewritten as:
(a/a) * x = (a/a) * y
Given that a/a = 1 for any number except zero, the equation can be written as:
1 * x = 1 * y
and since 1 * n = n for any number, we can simply write it as:
x = y
In the original "false proof", the cancellation goes as:
...
2(a^2 - ab) = 1(a^2 - ab)
2(a^2 - ab) / (a^2 - ab) = 1(a^2 - ab) / (a^2 - ab)
But since a^2 - ab = 0, this step divides by zero, which is invalid.
I just wanted to point out that the reason "cancelling" zero like this is invalid is because it requires dividing by zero, which is invalid.
Flawed Proof
If a = b then a^2-ab = 0.
Canceling a zero factor is not allowed.
e.g. 0*5 = 0*2 if you divide by 0 you obtain 5= 2. You can get anything you want.
Robert Pour
absolute certainty?
Some proofs may be so clear cut as to be described as absolutely certain...but surely that is not generally true.
There are surely proofs which are accepted as true by a high fraction of experts in a specialised area, but such highly complicated, longwinded and technical proofs aren't properly described as absolutely certain.
'Proof"? Really?
Just because a theory can be described mathematically, does not mean that the theory is actually correct - it only means that math can be used to describe the theory.
Proof and Theory
I thought a Theory implied some evidence was available to confirm it otherwise it was an hypothesis. Does a mathematical proof make an hypothesis into a theory or does it remain an hypothesis until proven by other evidence eg experimentation or observation?
Yes, proof
Proofs in mathematics never claim to be absolutely correct. In fact many mathematical theories contain seemingly contradicting axioms, example:
Euclidean geometry, parralel postulate: Given Line L, Point P, there exists exactly 1 line that passes through P parralel to L
Hyperbolic geometry, parralel postulate: Given Line L, Point P, there exists infinitely many lines that pass through P parralel to L
Those statements do not contradict each other because they are never true at the same time. You are either working in the framework of the euclidean geometry or hyperbolic, or some other geometry. There is no absolute truth in mathematics. (rather, any theorem should be read as "if axioms: ... are true, then theorem: ... is true")
Mathematics does not shows truths, it shows consequences.