Learning Mathematics in College spacer

(Mathematical) Proofs

spacer 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.
When Pythagoras introduced proofs to Europe, he introduced them as a way to settle what he regarded as religious issues: the stakes were high. And in applied mathematics, when the issue is whether the plane will fly or whether the electrical grid will run, the stakes remain high.

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.
Aha! We are beginning to see the reasons why teacher assigned the exercise.
  • 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.)
So the purpose is to learn how to construct arguments, to learn the subject you are arguing about, and then (remember this for future reference when you are planning to argue about welfare or the Mideast or pollution) to understand the subject you are arguing about if you are going to make a good argument.

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 + n2)/2. The proof is just the computation, which the reader just checks, step by step. For example,

1 + 2 + ... + n = 2 (1 + 2 + ... + n)/2
= [(1 + 2 + ... + (n - 1) + n) + (n + (n - 1) + ... + 2 + 1)]/2
= [(1 + n) + (2 + (n - 1)) + ... + (n + 1)]/2
= [(1 + n) + (1 + n) + ... + (1 + n)]/2
= n(1 + n)/2 = (n + n2)/2

To verify, just check each step.

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:
spacer 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. spacer
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, L1 and L2, 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 r2 = 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.
Now let's look at the proof.

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 = p0/q0. Thus we get: H says "either p0 or q0 is odd."
We will prove that if A implies that H is false, i.e., if r is rational then the fraction p0/q0 is a fraction of two even numbers, even though we had divided both top and bottom repeatedly until we got a fraction with an odd numberator or an odd denominator. Thus by the original set-up, H is true, while by A, H is false, which is nonsense. And the only way to get rid of the nonsense is to have A be false, i.e., to have r be irrational, so it cannot be expressed as a fraction p/q of integers to begin with.

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 = p0/q0, which by H, has either p0 odd or q0 odd. Square both sides of r = p0/ q0 to get

2 = r2 = p02/ q02,

or multiplying both sides by q02, we get
2 q02 = p02.

Now comes the problem.
  • If p0 is odd, then p02 is odd, and we have "even number = odd number," which is disallowed NONSENSE.
  • The other possibility is that p0 is even, i.e., divisible by 2. Let s = p0/2, or 2s = p0, so
    2 q02 = p02 = 4s2.

    But then we can divide both sides by 2 to get
    q02 = p02 = 2s2.

    so q02 is even, so q0 is even. But then p0 and q0 are both even, contradicting H, which said that at least one of them is false, which again leads to NONSENSE.
So both "p0 is even" and "p0 is odd" lead to nonsense, so nonsense is unavoidable once we let r be a fraction of integers. So r cannot be a fraction of integers.

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 "p0 is even" case; in the "p0 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 fact that we cannot take an integer and divide it by 2 as many times as we like, and still get an integer, is a fact that we would have to prove first, before proving that the square root of 2 is irrational. Once we had proven that, we would then be able to assert, without a doubt, that the square root of 2 is irrational. Now, you may be familiar with integers, and so you might want to say that of course, if you took an integer and kept dividing by 2, eventually you would reach an odd integer which is not divisible by 2 (just look at 288: 288/2 = 144, 144/2 = 72. 72/2 = 36, 36/2 = 18, 18/2 = 9, and as 9 is odd, 9/2 is not an integer). But this is just your intuition backed by experience: it is not a mechanical proof (how do you know that there isn't out there, somewhere, a nonzero integer that can be divided by 2 repeatedly?). To claim that any integer can be divided by 2 only finitely many times, you need a proof.

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.
Notice that an argument consisting of a list of hypotheses, and then a list of these propositions proven one after another by universally accepted methods, ending with the desired assertion being the last proposition, then this argument is checkable: someone skeptical of the desired assertion can check each step to make sure it is correct. And this is what is regarded as a convincing argument in mathematics.
  • 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.
There are many philosophers who dispute the claims of the Axiomatic Method, but usually it is because they contend that the Axiomatic Method cannot decide certain issues (like the existence of God) one way or the other, or they are complaining that certain arguments that look like they are based on the Axiomatic Method actually aren't, or they disagree with some of the postulates or rules of inference. As the Axiomatic Method makes arguments easier to check, many philosophers still prefer it, if only for providing a good format (and as the Axiomatic Method makes arguments easier to check, crooks and demagogues tend to dislike it). And mathematics is the place where one can learn the Axiomatic Method in an environment where all the issues are most clear (if rather complicated), where even the limits of the Axiomatic Method can be made precise, and where the conclusions to be reached are not so gut-wrenching that students are distracted by fears of reaching unsavory conclusions.

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.


Escape links

Back to the main Homework page

Link to the site map.

Back to the main pedagogy page

Back to my home page

Back to the USF Department of Mathematics Home Page