Learning Mathematics in College

(Mathematical) Proofs

These pages are composed and maintained by Greg McColm, Department of Mathematics, University of South Florida.

One of the less popular kinds of exercises is a proof: proofs tend to be very difficult to do right, and since one already knows the answer (unless the sadistic professor has assigned a trick question) there seems to be little point to it. Why do professors assign proofs?

First of all, just because professor says it's true doesn't make it true. Professor might be mistaken, or lying, or sadistic, or trying to trick or brainwash you. You don't believe your political science professor just because he has a Ph.D., do you? Why should you believe your mathematics professor just because she has a Ph.D.? (And don't say, "because it's easier if I just agree with teacher"; laziness earns you no points in the real world.) Ultimately, a proof is a convincing argument, an argument that will convince your kid sibling, even if (s)he is of the opposite political party. Which brings us to the critical points:

• A legitimate proof will not prove something that is not true. That is the point of a proof: to verify that something is true.
• It takes skill and experience to be able to determine if a proof is legitimate. And the lazy person who can't be bothered, or the unthinking one who just goes by what feels right, is the lawful prey of politicians, advertizers, and opportunistic office mates.

Secondly, proofs are a mathematical version of a kind of exercise we've all seen: given an issue, take a position on it and defend that position. This kind of assignment used be given in rhetoric courses, which covered valid versus invalid arguments. The whole point of rhetoric was to learn how to determine if political, philosophical, social, artistic, scientific, etc. claims were true or not: people relying on "common sense" forget Einstein's characterizion of common sense as "the collection of prejudices acquired by age eighteen." And looking at the nonsensical results of "common sense," and the inability of sensible people to agree on what "common sense" says, we can see that Einstein wasn't just talking about general relativity. Alas, rhetoric courses have gone out of fashion in the last half century (we live in sad times!), but these kinds of rhetoric assignments still show up in content courses. Let's look at an example.

In honor of Calvin & Hobbes, we consider the assignment, "Was Tyrannosaurus rex a predator or a scavenger?" (Since vultures have been known to kill their prey, and since coyotes have been known to eat animals found dead, this probably has an in-between answer. Nevertheless, paleontologists are fighting over this question, so we can, too.) The point of the exercise is not the answer --- as even leading experts disagree, your teacher will not be grading on the answer. The point is the argument supporting the answer.

• Calvin & Hobbes fans may recall Calvin's argument: Tyrannosaurus rex was a predator because that is more cool. Actually, many arguments are such direct appeals to emotion and prejudice (especially in politics) and, oh yes, common sense. The problem is that Mother Nature may not share our prejudices. If the point is that to persuade a skeptic with different notions of coolness, or a skeptic aware of Mother Nature's own indifference to coolness, one needs an argument based more on how Mother Nature herself works.

• First, to acquaint students with the sad reality that the universe doesn't necessarily work the way we want it to. And in fact, their are many quite intelligent (and even cool) people out there who actually believe ... really! ... that Tyrannosaurus rex was a scavenger. And some people are not sure. How do you persuade, or at least sway, such people? You can't just say that, well, it's just logical (we'll discuss what "logical" really means in a moment). You can't just call them names (although this method is very popular in contemporary politics: "you're just being a conservative" "face it, you're a liberal"), especially if you aren't sure what the names mean (quick: what's a conservative? what's a liberal?). Or at least, only stupid people are favorably impressed by name-calling. So if you want to persuade or at least open minds, you need real arguments. That means you have to learn how to construct real arguments. And that is the skill that your teacher is trying to get you to develop when (s)he assigned Tyrannosaurus rex.

• There is another reason. Take a look at this description of a BBC program on the Tyrannosaurus rex debate. Notice that there is a lot of facts, and somewhat mechanical arguments based on those facts. What the nasal cavity tells us about the sense of smell, what the contraction force of muscles tell us (mathematical computation time!) about how fast it could run, and so on. In other words, if you are going to construct an argument about Tyrannosaurus rex, you are going to have to not only study, but know a lot about, Tyrannosaurus rex. (In fact, Aristotle said that in a controversial issue, if you cannot construct a plausible argument opposed to your own position, you probably don't understand the issue. This means that no matter what you are going to say on the paper you turn in, you will have to study both arguments.)

All this goes for mathematics as well, and the arguments in mathematics are proofs. Notice the difference between the words "argument" and "proof." The point is that a proof is supposed to be an absolutely foolproof argument. It is absolutely mechanical and there's no way out of it. This makes mathematical proofs different from arguments about Tyrannosaurus rex; in fact, mathematics is probably best defined as the subject for which we have such proofs. But the purpose is the same: to verify that something is true (as opposed to looking true), and to study the issue to understand what is actually going on.

Let's look at the most straightforward kind of proof: verifying a computation. For example, one computational exercise is to come up with a (nice) formula for 1 + 2 + ... + n. The proof version of the exercise is: verify that 1 + 2 + ... + n = (n + n²)/2. The proof is just the computation, which the reader just checks, step by step. For example,

Of course, sometimes we want to prove something that is not a formula.

Let's look at a very famous mathematical problem: are there numbers that are not fractions of integers? Pythagoras had visited Egypt, and returned with a lot of mathematics, and a firm belief that all numbers were rational, i.e., fractions of integers. His precise argument is unknown (nothing he wrote survives: he led a religious group dedicated to an identification of arithmetic and religion), but it was philosophical if not religious, and may have gone something like this:

	Since all things arise out of the first thing, all whole numbers arise out of repeatedly adding one. From these whole numbers, we obtain fractions that represent ratios of arbitrary refinement. Thus for any real number, we must be able to find a ratio of whole numbers for it.

This does not look like a mathematical proof that you'll find in any textbook, although many "heuristic arguments" and "plausibility arguments" look equally mushy. (NOTE: A heuristic or plausibility argument can only serve to tell a reader that the assertion is not silly; but it is not a convincing argument, as we shall soon see.) Indeed, someone --- no one really knows who --- came up with a complicated geometric construction with two line segments, L₁ and L₂, where the ratio between the lengths was not a rational number. So here is a plausibility argument that turns out to be no good: if we are to be certain, we need a proof.

What does a proof look like? As an example, let's look at one of the nicer proofs that the square root of 2 is irrational (recall that the square root of 2 is a number r such that r² = 2).

This will be a proof by contradiction, which works like this. Suppose that you want to prove that A is false. If you prove that "if A, then NONSENSE is true" then, since NONSENSE must be false, it cannot be the case that A is true, so A must be false. For example, if "A implies that the Moon is made of green cheese" then, since the Moon is not made of green cheese, it must be the case that A is false.

One kind of proof by contradiction works like this. Suppose you want to prove that A is false. Set up a situation where some statement H is true. Prove that "if A is true then H is false." But since we already knew that H was true, if A is true, then H would be both true and false, which is nonsense. The only way to prevent the nonsense is to require that A is false.

Notice two things, even before we have gotten to the proof:

• Everything is mechanical. There is no hand-waving, nothing about what something seems like like, or what sounds reasonable. Everything is rigid, and statements are all being clearly labelled TRUE or FALSE.
• Things are getting complicated. People are used to dealing with complications by relying on their intuition (common sense!) to get a sense of whether something looks, sounds, or feels right. But here, intuition is not allowed: you have to follow each thread carefully to determine -- no fudging! -- whether something works or not.

If A is "2 has a rational square root" we will want to prove that A is false. Here is the set-up.

• Suppose, towards contradiction, that A is true. Then it has a rational square root r. This means that there are two integers p and q such that r = p/q.
• Now for H. If r is rational, allowing us to write r = p/q, then we could divide both the numerator and denominator of p/q repeatedly by 2 until either the top or the bottom (or both) were odd. So divide top and bottom of p/q by 2 repeatedly, which doesn't change the value of the fraction (always equalling r), repeatedly to get r = p₀/q₀. Thus we get: H says "either p₀ or q₀ is odd."

Here is the proof that A implies that H is false. A lets us write r = p/q, which (dividing top and bottom by 2 repeatedly) gives us r = p₀/q₀, which by H, has either p₀ odd or q₀ odd. Square both sides of r = p₀/ q₀ to get

• If p₀ is odd, then p₀² is odd, and we have "even number = odd number," which is disallowed NONSENSE.
• The other possibility is that p₀ is even, i.e., divisible by 2. Let s = p₀/2, or 2s = p₀, so
  2 q₀² = p₀² = 4s².
  But then we can divide both sides by 2 to get
  q₀² = p₀² = 2s².
  so q₀² is even, so q₀ is even. But then p₀ and q₀ are both even, contradicting H, which said that at least one of them is false, which again leads to NONSENSE.

Two observations about this proof.

• It was even more complicated than advertized. The contradicting NONSENSE "H is true" & "H is false" was what we got in the "p₀ is even" case; in the "p₀ is odd" case, we got a different bit of nonsense (an even number equaling an odd one). Nevertheless, if you carefully traced each step, you would find that as each step worked (save one, which we'll talk about in a moment), there is no way to refute the proof, so it must be true.
• There was a big leap: notice when H was asserted, I blithely assumed that I couldn't just keep dividing top and bottom by 2. Well, why not? We can keep dividing real numbers by 2. Why can't we just keep dividing integers by 2?

The Greeks discovered a curious problem with proofs: whenever you proved something, you found something that you should have proved something beforehand. Aristotle proposed a way to deal with this problem:

• Start with a collection of hypotheses, which you assume to be true, for the sake of argument. Aristotle divided these hypotheses into axioms or non-controversial assumptions, and postulates or controversial assumptions.
• Have a universally agreed upon method of verifying assertions (called propositions) from previously proven propositions: once you have proven that A, B, and C are true, if you can use a legitimate method (like a proof by contradiction) to prove
  if (A & B & C) then D,
  we can then conclude that D is also true.
• Keep on going until you reach the assertion P that you were trying to prove.

• The book that sold this method for valid argument not only in mathematics, but in philosophy, politics, science, law, etc., was Euclid's Elements, which starts with lists of axioms and postulates, and then constructs the mathematics of ancient Greece. This approach is called the axiomatic method, and is regarded by many philosophers as the primary form of rational argument.
• Aristotle proposed a more rigorous version of this method: the universally agreed upon method of verifying propositions from previous assertions must be a mechanical rule of inference. The axiomatic method using rules of inference is called logic, and when someone claims to have a logical argument, it usually means that they have constructed an axiomatic argument using rules of inference (often using Aristotle's own syllogisms, see his Organon). Of course, sometimes someone claiming that something is logical is either deluded, dishonest, or has watched too much Star Trek.

Admittedly, once one has learned the Axiomatic Method in a mathematics course, there remains the danger that one could apply it to issues one really cares deeply about, and reach unpleasant conclusions. Logic, like life, is not a safe place. But the nervous individual who will not or can not use the Axiomatic Method to at least check arguments is the lawful prey to advertizers, demagogues, and overwheening relatives. The choice is up to you.