Mathematical Proof and the Principles of Mathematics/Preliminaries/Mathematical proof

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Now that we've talked about statements, let's talk about what mathematicians do with them, namely trying to convince people that they're true. A 'proof' in general is an argument intended to do just this. Outside of mathematics, there are many types of proof, for example you might cite a reliable authority. In science you might perform an experiment which tests whether the statement is true. But in mathematics only logical arguments are accepted as valid proofs. Mathematicians may cite results given by another mathematician, otherwise everyone would have to start from scratch, but only if the proof has been independently checked.

In this way mathematics is a very egalitarian science. Everyone, at least theoretically, is held to the same standard when it comes to whether what they claim is believed.

We'll go into much more detail on the logical arguments used in mathematics, but you may be wondering about other types of arguments and why they are not allowed.

Inductive arguments[edit]

One possibility is an inductive argument (not to be confused with proof by induction which will be covered later). To give an example from geometry, suppose that you've measured the angles of 100 triangles and have found that in each case they add up to 180°. You might then form a hypothesis that the angles of a triangle always add up to 180° and ask some other people to test this hypothesis by trying their own triangles in a variety of shapes. If they confirm it the hypothesis becomes accepted as scientific fact.

The problem with this way of arguing is that it's inherently unreliable. Perhaps there is an extremely rare type of triangle where the angles do not add up to 180° and it happens that no one has found it yet. Another possibility is that the rule works for normal sized triangles, but fails if they are smaller than atoms or larger than galaxies.

A statement in mathematics which has not been proved by logical argument, but which seems to true anyway, is called a conjecture. An example of a conjecture that turned out to be false is one made by Leonhard Euler in 1769. It states that there are no integers a, b, c, d so that

a4+b4+c4=d4

Over 200 years later this was shown to be false by Noam Elkies using the methods which did not exist in Euler's time. The smallest values of a, b, c, d which disprove the conjecture are a=2682440, b=15365639, c=18796760, and d=20615673. Something such as this which disproves a conjecture is called a counterexample. There are many conjectures which were eventually proved and many others whose fate is still unknown.

This is not to say that collecting data is useless in mathematics. It can be used to form a hypothesis which might be turned into a theorem, or find a counterexample may prevent wasting time trying to prove something which is false.

Intuition[edit]

Another possibility for proving a mathematical statement is to appeal to intuition and simply declare that it's obvious. Again from geometry, an example might be that the sum of two sides of a triangle is never greater than the third side. Intuition says that if you want to go from A to B then the shortest route is on the line between them, not through some other point C not on the line. But Euclid still felt the need to prove it.

The problem with intuition is that it's notoriously unreliable. One example, known as Simpson's paradox, concerns the way statistical comparisons can change when the data is divided into groups. Suppose there is a university who's preparing a brochure for prospective students, and decides to include some admission statistics to prove that the university's admissions aren't gender biased. The university has two programs, the undergraduate and graduate. The undergraduate program which received 1100 applications for admission, 500 from men and 600 from women. The graduate program which received 500 applications, 300 from men and 200 from women. Both departments followed a strict gender neutral policy and admitted the same percentages of male and female applicants, in fact it turned out that the women had a slight advantage over the men in both departments. It seems like if the women had an advantage in both departments then they would have an advantage overall, but sometimes that's not the case, as you can see in this table:

UG Grad Total
Men 100/500=20% 120/300=40% 220/800=27.5%
Women 126/600=21% 84/200=42% 210/800=26.25%

There are several cases given in the History chapter as well where what was commonly believed turned out to be false. For example in calculus, there was a time when it was believed that a continuous function must have a derivative, at least for all but a few exceptional values. In fact, the Weierstrass function disproves this. Still, intuition is useful as a guide for creating new conjectures and finding proofs for them.

Deductive reasoning[edit]

But deductive reasoning alone has its problems as well. The main issue is that some assumptions must be made which can't be proved. Some statements can be proved with no assumptions, but these are known as 'tautologies' and are not considered interesting from a mathematical point of view. Examples are

Mortals are mortal.
Numbers are either even or not even.

The concept of a tautology is important in logic and even in the study of algorithms, but you could never call one a theorem.

So mathematics must make certain assumptions to start from, so called first principles. They are usually called axioms now but you may also hear them called postulates. But where do axioms come from and how can we tell if they are true? This turns out to be a difficult problem. One approach is to fall back on induction and intuition, but then we are again faced with the problems listed above. Another approach is to treat axioms as more or less arbitrary assumptions, something like the rules in a card game. As different sets of rules produce different games, so different axioms produce different types of mathematics.

Mathematical Statements