1 Comments on mathematical proofs Since deductive reasoning and logical proofs play an extremely important role in the mathematical sciences, we shall summarize some of the main points here, describing some of the standard methods and strategies, illustrating these with some examples from high school mathematics and calculus, and pointing out some common mistakes and how to avoid them. Since we are simply trying to illustrate the techniques, our setting for now is informal, and in particular for the time being we shall not worry about things like how one proves the Intermediate Value Theorem that plays such an important role in calculus. This is technically an example of a concept called local deduction, in which one only shows how to get from point A to point B, postponing questions about reaching point A to another time or place. Some proofs use direct arguments, while others use indirect arguments. The direct arguments are often the simplest, and many simple problem solving methods from elementary mathematics (algebra, in particular) are really just very simple examples of direct proofs. Example. If 2x + 1 = 5, show that x = 4. SOLUTION: If 2x + 1 = 5, then by subtracting 1 from each side we obtain 2x = 4. Next, if we divide both sides of 2x = 4 by 2, we obtain x = 2. In contrast, an indirect argument usually involves considering the negation of either the hypothesis or the conclusion. This generally involves proof by contradiction, in which one assumes the conclusion is false and then proves part of the hypothesis is false, and it is related to the law of the contrapositive: A statement P ⇒⇒⇒⇒ Q is true if and only if the contrapositive statement not Q ⇒⇒⇒⇒ not P is true. When you have eliminated the impossible, whatever remains, however improbable [or questionable it may seem], must be the truth. A. C. Doyle (1859 – 1930), Sherlock Holmes – Sign of the Four A general “rule of thumb” is to consider using an indirect argument if either no way of using a direct argument is apparent or if a direct approach seems to be getting very long and complicated. There is no guarantee that an indirect argument will be any better, but if you get stuck trying a direct approach there often is not much to lose by seeing what happens if you try an indirect approach; in some cases, attempts to give an indirect argument may even lead to a valid or better direct proof. Example. Show that if L and M are two lines then they have at most one point in common. SOLUTION: Suppose the conclusion is false, so that x and y are two distinct points on both L and M. Then both L and M are lines containing these two points. Since there is only one line N containing the two distinct points x and y, we know that L must be equal to N and similarly M must be equal to N, which means that L and M must be equal. This contradicts our original assumption; the problem arose because we added an assumption that x and y belonged to both lines. Therefore L and M cannot have two (or more) points in common.2 An important step in such indirect arguments is to make sure that the negation of the conclusion is accurately stated. Mistakes in stating the negation usually lead to mistakes in arguments intended to prove the original result. Forward and backwards reasoning. Very often it is helpful to work backwards as well as forwards (see the quotation below). For example, if you want to show that P implies Q, in some cases it might be easier to find some statement R that implies Q, and then to see if it is possible to prove that P implies R. Of course, there may be several intermediate steps of this type. In solving a problem of this sort, the grand thing is to be able to reason backwards. That is a very useful accomplishment, and a very easy one, but people do not practice it much ... and ... [it] comes to be neglected. Sherlock Holmes – A Study in Scarlet Example. Show that the polynomial f(x) = x5 – x – 1 has a real root. SOLUTION: We know that polynomials are continuous and that continuous functions have the Intermediate Value Property. Therefore if we can show that the polynomial is positive for some value of x and negative for another, then we can also show that this polynomial has a real root. One way of doing this is simply to calculate the value of the polynomial for several different values of the independent variable. If we do so, then we see that f(0) = – 1 and f(2) = 29. Therefore we know that f(x) has a root, and in fact by the Intermediate Value Theorem from first year calculus we know there is a root which lies somewhere between 0 and 2. Proofs by cases. Frequently it is convenient to break things up into all the different cases and to check them individually, and in some cases this is simply unavoidable. Example. Let sgn(x) be the function whose value is 1 if x is positive, – 1 if x is negative, and 0 if x = 0. Prove that sgn (xy) = sgn (x) sgn(y). Here one has three possibilities for x (positive, negative, zero) and likewise for y, leading to the following list of nine possibilities for x and y: [+,+], [+,0], [+,–], [0,+], [0,0], [0,–], [–,+], [–,0], [–,–] One can then handle each case (or various classes of cases) separately; for example, the five cases where at least one number is zero follow because in all these cases we have xy = sgn(x) sgn(y) = 0. In all proofs by cases, it is important to be absolutely certain that all possibilities have been listed. The omission of some cases is an automatic mistake in any proof. Interchanging roles of variables. This is a basic example of proofs by cases in which it is possible to “leverage” one case of the proof and obtain the other(s) with little or no additional work. Example. Show that if x and y have opposite signs, then we have |x – y| = |x| + |y|. SOLUTION: Suppose first that x is positive and y is negative. Then the left hand side is just x + |y| = |x| + |y|. Now suppose y is positive and x is negative. Then if we apply the preceding argument to y and x rather than to x and y we then obtain the equation |y – x| = |y| + |x|. Since the left hand side is equal to |x – y| and the right hand side is equal to |x| + |y|, we get the same conclusion as before. In a situation of3 this type we often say that the second case follows from the first by reversing the roles of x and y.