Some Help on Reading Mathematics and Creating Proofs     rev. 1/21/03

Math 109 is an introduction to proofs and some mathematical concepts.  Some written sources of advice are

People are sometimes confused about what needs to be proved when "if" appears.  Here are the three main cases:

The importance of a comment attributed to E. Bishop (1985) cannot be overemphasized: "Do not ask whether a statement is true until you know what it means."  Many students often attempt to prove something without understanding what they are trying to prove.  Rather than leading to understanding, it usually reveals that the student doesn't understand the statement.  To know what a statement means, you must understand all the concepts in the statement separately and also how the statement says they are related to one another.

This leads to an important question: What is a definition?  Although the answer sounds obvious, people often miss the fact that "definition" is used in two different ways.  An extracted definition is based on the common usages of a word.  It may not say precisely what the word means; for example, the definition of when objects are called "chairs".  As common usage shifts, extrracted definitions shift.  A stipulated definition spells out precisely what a concept means in terms of other known concepts.  This is usually the situation in games; for example, the definition of "touchdown" in football.  Mathematical definitions are stipulated: They explain precisely in terms of previous concepts what a new concept means.  Inevitably, there are some basic concepts that mathematicians don't define such as "point" and "line" in Euclidean geometry.  This leads to another question: Why be so precise?  Without such precision, it becomes unclear what has been proved and whether the proof is correct.  Such uncertainty affects more than mathematics: Would you want to fly on an airplane whose design depended in part on mathematical computations based on numerical methods for solving differential equations to within a desired degree of accuracy that we think are correct? Would you like your doctor to rely on a CAT scan (which uses mathematically based image reconstruction techniques) if the techniques are based on flawed mathematics?  As a scientist, would you be willing to reject a theory if sophisticated mathematical computations showed that it contradicted experimental results, but you weren't sure the mathematics was correct?

In doing mathematics, we deduce results from stipulated definitions and from other results that have been previously deduced from stipulated definitions.  Hence it is very important to understand what a definition means.  This understanding should be on two levels.  The formal level, which is essential for deducing results, is the understanding of the statement so that you can decide when something fulfills the conditions in the definition; for example, when a figure is an isosceles triangle or when a differential equation is exact.  The informal level, which is not always present,  is an understanding that let's you see what might be true.  It may be in the notation or it may be a way of thinking about the concept.  For example, a derivative is defined precisely in terms of a limit of ratios and is written dx/dt as if it were actually a ratio --- which it is not.  This leads to an informal treatment of a derivative as if it were actually a ratio, which usually leads to correct results.  However, it is not a proof of those results.  Another example: checkmate in chess can be thought of as "the king can be captured on the next move".  This is not quite correct since there would be no next move and since it includes the possibility of stalemate.

Reading Mathematics (from Mathematical Methods in Artificial Intelligence)

Many people learn mathematics the way I learned history in high school.  The exams contained two columns and the goal was to match each date in column A with one of the persons, places, and events in column B.  Being lazy, I learned the "whens'' of history but never the "whys.''  I missed a whole world of ideas.

When mathematics is taught and learned by rote, students miss a world of ideas.  Mathematics should be learned as an aid to thinking, not as a replacement for it.  Learning mathematics is a skill that's seldom taught.  If, like many students, you haven't mastered it, the following comments should be helpful.

The key is to work on understanding -- not on memorization.  How can you do this?

Let's begin with definitions.  Whenever you meet a new concept, develop an understanding of it by relating it to ideas you already know and by looking at what it means in specific cases.  For instance, when learning what a polynomial is, look at specific polynomials; when learning what continuity is, see what it means for a specific function like x^2.  The importance of understanding the general through the specific cannot be overemphasized -- even by using italics.  The discussions and examples that immediately precede and follow definitions are often designed to foster understanding.  If a definition refers to an earlier, unclear concept, stop!  If you proceed, you may end up wandering aimlessly in a foggy landscape filled with shadowy concepts and mirages.  Go back and improve your understanding of the earlier concepts so that they're practically solid objects that you can touch and manipulate.  Finally, ask yourself why a definition has been introduced: What is the important or useful concept behind it?  You may not be able to answer that question until you've read further in the text, but you can prepare your mind to recognize the answer when you see it.

What about theorems?  The comments for definitions apply here, too: Look at specific examples, try to relate the theorem to other things you know, ask why it's important.  Be sure you're clear on what the theorem claims and on what its words mean.  In addition, attempt to see why the result seems reasonable before you read the proof.  Reading and understanding the proof is the last step.  If the proof is long, it may be helpful to make an outline of it.  But don't mistake the ability to reproduce a proof for understanding.  That's like expecting a photograph to understand a scene.  There are better tests of understanding: Do you see where all of the assumptions are used?  Can you think of a stronger conclusion than that in the theorem?  If so, can you see why the stronger conclusion is not true, or at least why the proof is insufficient to establish the stronger conclusion?  Examples play a key role in mathematics.  In practically every mathematics text, they fall into three categories.

If you neglect any of these three types of examples, your mathematical text will be most useful to you as a doorstop.
Why do We Need Proofs?

It's clear why we need to prove mathematically something that's not obvious, like the Pythagorean Theorem, but why should we prove something that "common sense" tells us is obviously true.

First, if something cannot be proved, there may be something missing.  For example, suppose we set up some equations that describe a physical system and it is obvious that the solution exists and is unique (e.g., equations of motion).  It may happen that sometimes the equations have no solutions or have more than one solution.  This may indicate that something is missing in our translation of a phyical problem into a mathematical one.

Second, if something is obvious to common sense, it might be wrong.  For example, at one time common sense taught people that the only possible geometry was Euclidean.  We know that is wrong.  Here is another example.

What strategy should the team adopt?  Clearly a guess only has a 50/50 chance of being right.  Also, the more guesses there are greater the chance of a wrong guess being made.  Therefore it is obvious that the team should select a spokesperson who guesses at random.  We've just proved this by appealing to obvious facts and common sense.  It is wrong.  There is a strategy that lets the team win 3/4 of the time!  You can find out about this in The Mathematical Intelligencer vol. 24 no. 4 (2002).

A Possible Taxonomy of Proof Types

Here is a possible way of describing the various types of proofs.  Other people can have a different way.  In each case, a theorem is given with at least part of the proof.

Excerpts from Introduction to the Theory of Computability by M. Sipser

The following are a few tips for producing a proof.

Advice by J. H. Silverman (Amer. Math. Monthly, 1999) in a book review

What, roughly, are some of the meta-mathematical tools (as opposed to mathematical techniques such as induction) that every mathematician keeps close at hand when tackling a mathematical problem?  In no particular order, the following (non-definitive and non-disjoint) list comes to mind:  [I've indicated those I think are most effective for textbook problems and those I think are least effective.--Ed B.]

In addition, every mathematician must acquire various meta-mathematical skills, such as:

The last item is, in some sense, the most important lesson for a student to absorb.

Comments on Negation

People are sometimes confused about what needs to be proved when "if" appears.  Here are the three main cases:

The following issues about negation often cause confusion

CONTRAPOSITIVE: Suppose we have a statement "If A, then B."  The contrapositive is "If not B, then not A."  A statement is true if and only if its contrapositive is true.  This is the only "if...then" combination of A and B with negation for which this is the case.
Example: "If it rained, then the grass is wet."  has the contrapositive "If the grass is dry, then it did not rain."  Another combination: "If it did not rain, then the grass is dry." may be false because the grass could have been watered.
Example: "A if and only if B." means "(If A, then B) and (if B, then A)."  Using the contrapositive, the latter is equivalent to "(If A, then B) and (if not A, then not B)."  Hence "A if and only if B" is sometimes proved by showing (i) if A is true, then B is true, and (ii) if A is false, then B is false.

PROOF BY CONTRADICTION: Suppose we want to prove a statement.  To give a proof by contradiction, we show that, if the statement is not true, we can obtain an absurdity (i.e., a contradiction).  
Example: "There are an infinite number of primes." Suppose false. Let p1,..., pn be the primes.  Let m = p1 X...X pn + 1.   Let q be a prime dividing m. (Possibly q = m.)  By assumption q is some pk.  This is impossible since dividing m by pk gives a remainder of 1.
Example: The negation of "If A, then B." is "A is true and B is false."  Thus, to give a proof by contradiction of "If A, then B," we assume that A is true and B is false and derive a contradiction.

NEGATING QUANTIFIED STATEMENTS: The phrases "for some X" and "there exists X" mean the same thing and are called existential.  The phrases "for all X", "for every X", and "for each X" mean the same thing amd are called universal.  We can move a "not" through an existential or a universal quantifier provided we switch from one type to the other, and we can repeat the process.
Example: The negation of "Every dog has its day." is "Some dog does not have its day."
Example: Continuity of f(x) at x = a is defined by
                      for every e>0 there is a d>0 such that for every x (if |x-a|<d, then |f(x)-f(a)|<e).
In words, for every positive e there is (at least one) positive d such that, whenever x is within d of a, f(x) is within e of f(a).
Let's negate it step by step [In the last line, ">=" means "greater than or equal to."]:
                      not (for every e>0 there is a d>0 such that for every x (if |x-a|<d, then |f(x)-f(a)|<e)).
                      for some e>0 not (there is a d>0 such that for every x (if |x-a|<d, then |f(x)-f(a)|<e)).
                      for some e>0 and every d>0 not (for every x (if |x-a|<d, then |f(x)-f(a)|<e)).
                      for some e>0 and every d>0 there is an x such that not (if |x-a|<d, then |f(x)-f(a)|<e).
                      for some e>0 and every d>0 there is an x such that ( |x-a|<d and |f(x)-f(a)|>=e).
That completes the negation process.  In words, to show that f(x) is not continuous at a, we must find a positive e such that, for every positive d we can find an x such that x is within d of a and f(x) is not within e of f(a).