Primer on Mathematical Proof

Math 150s Proof and Mathematical Reasoning A Primer on Mathematical Proof A proof is an argument to convince your audience that a mathematical statement is true. It can be a calculation, a verbal argument, or a combination of both. In comparison to computational math problems, proof writing requires greater emphasis on mathematical rigor, organization, and communication. A typical theorem may have the form: Theorem. Under Conditions A, Statement B is true. Here, A is called the hypothesis or assumptions, and B is called the conclusion. Note that mathematicians use the word ”hypothesis“ differently than it is used in the scientific method. For a mathematician, a ’hypothesis’ is not an statement with an absolute ’true’ or ’false’ value, it is a description of a situation in which the conclusion of the theorem holds. A proof is a series of statements, each following logically from the previous, to reach the conclusion – using only the hypotheses, definitions, and known true statements. Example of a Theorem and Proof √ √ Theorem 1. Let a and b be real numbers. Suppose that 0 < a ≤ b. Then a ≤ b. √ Note that, for a nonnegative real number x, x denotes the nonnegative square root of x. Proof. Since a ≤ b by assumption, it follows that (b − a) ≥ 0. We know that a and b are both positive, so their square roots are defined. Thus, we can use a difference of squares expansion to write: √ √ √ √ ( b − a)( b + a) = (b − a) ≥ 0. √ √ √ √ Since a and b are strictly positive, so are a and b. Thus ( b + a) > 0, and we can divide through the above expression without changing the direction of the inequality. We get: √ √ (b − a) 0 ( b − a) = √ √ ≥ √ √ =0 ( b + a) ( b + a) and so we conclude that √ b≥ √ a. There is some discretion involved in writing proofs in deciding which statements are well-known or selfevident and which need further justification. For example, in the above proof, we used the fact that positive numbers have positive square roots without justification. Common Mistakes in Proof-Writing Common Mistake #1. Starting with the conclusion, and working backwards toward the hypotheses. This approach can be a good way to brainstorm how the proof will work – but it is not appropriate for the final write-up of the proof. At best, such arguments are poor exposition, and at worst they are logically unsound. Always start a proof with the hypotheses and known truths, and work toward the conclusion. Page 1 of 7 Math 150s Proof and Mathematical Reasoning Common Mistake # 2. Checking the conclusion in a few specific examples, and extrapolating that it always holds. A proof must give a rigorous argument that the conclusion holds in all situations satisfying the hypotheses. For example, if you want to prove that some property holds for all real numbers, then assign a variable (such as x) to represent an arbitrary real number, and prove that property holds for this arbitrary number x. Because x can represent any real number, you can conclude that the property holds for every real number. It is not enough to simply plug in a few numbers for x and check in those cases. In contrast, you can disprove a statement by finding a single example where the hypotheses hold but the statement fails. Common Mistake #3. Assuming the conclusion. Suppose, for example, you want to prove that two quantities or expressions A and B are equal. It is a common error to start this proof by equating A = B and then simultaneously manipulating both sides of the equation. This is not a valid approach to the proof. Do not start a proof that A = B with the statement A = B. It is possible to “prove” false statements this way. Instead, choose one side of the equation (A or B) and work through a sequence of equalities until you arrive at the other side. For example, the following is a proof that (x − y)2 + 4xy = (x + y)2 for all real numbers x and y: (x − y)2 + 4xy = (x2 − 2xy + y 2 ) + 4xy = x2 + y 2 − 2xy + 4xy = x2 + y 2 + 2xy = (x + y)2 Common Mistake #4. Making steps in the proof without adequate justification. For this course, you should give justification for any facts that aren’t obvious. If you invoke a result that was proved earlier in the course, then you should cite the result and explicitly verify that its hypotheses are satisfied. As a general guideline, the arguments in your proof should be detailed enough to convince someone with the background of a student in this course. Use your judgment about how much to write. Be sure, too, that the overall structure of the proof is clear. A series of statements or computations are not a complete proof unless it is explained how they connect and why they imply the final result. Most proofs should include full English sentences. Keep in mind that the main goal of the proof is to communicate a mathematical argument to the reader. Common Mistake #5. Overlooking special cases. For example, if a step in the proof involves dividing by an unknown real number x, you will need to separately treat the case that x = 0. Common Mistake #6. Undeclared variables and undefined notation. A symbol such as x is meaningless until it is assigned a meaning. A proof should include a declaration of all the objects involved, for example “let x be a real number”, or “let f be a continuous function from R to R”. Similarly, any nonstandard notation or shorthand should be defined. Communicate! Page 2 of 7 Math 150s Proof and Mathematical Reasoning Common Mistake # 7. Imprecise statements. An argument cannot be rigorous if it involves ambiguous or poorly defined statements. Be specific. Use mathematical terminology, and use it correctly. For example, Imprecise Sentence: “The sine function looks the same every 2π.” Better Sentences: “The sine function takes on the same value at any two points in its domain that have a difference of 2π.” “For every real number x, sin(x) = sin(x + 2π).” “The sine function is periodic with period 2π.” Common Mistake #8. General bad communication. If you were writing an essay, you would not invent your own words, symbols, or shorthand. You would not write idea fragments without context or support. You would not write a chaotic jumble of ideas across the page with a network of arrows directing your reader in circles. Please treat your proofs the same way. Remember that the primary purpose of your write-up is to communicate your reasoning to your reader. Please write neatly, grammatically, and in a sensible linear order. The proofs in the textbook (and in class) are good models for proper formatting. It is good practice to re-read your proofs, imagining how they would look to someone else. Is it clear what all the words and symbols represent? Is it clear what order the proof should be read in? Is it clear which statements are assumptions, which are statements that you are about to prove, and which are deductions? Is the purpose of each line clear – what is being deduced, and why this deduction is logically sound? Does the proof start with known facts, and progress toward the desired conclusion? Or, alternatively, start with one side of a desired equation, and progress through a sequence of equalities toward the other side? Consider having a second person proofread your work, and tell you which aspects need clarification. Example of a False Statement and Counterexample To prove that a statement is true, you must show that the conclusion holds in every situation that satisfies the hypotheses. You can, however, prove that a statement is false by finding a single instance where the hypotheses hold but the conclusion fails. This is called a counterexample to the statement. False Statement. For all real numbers a and b, |a + b| = |a| + |b|. Counterexample. Consider the example a = 1, b = −1. Then |a + b| = |0| = 0 but |a| + |b| = 1 + 1 = 2. It is therefore not always true that |a + b| = |a| + |b|. Logic: Conditional Statements and Equivalence Implication Let A and B denote properties or mathematical statements. The following notation means “A implies B”: A =⇒ B. Page 3 of 7 Math 150s Proof and Mathematical Reasoning Other ways to write this: • If A is true, then B is true. • A is true only if B is true. • B is true whenever A is true. • B is true if A is true. • Everything with property A also has property B. • The set of things with property A is contained in the set of things with property B. We write A 6=⇒ B to mean “A does not imply B”. This means that there is at least one example where A holds, but B fails. Examples of Conditional Statements “An integer n must be even if it is divisible by 4.”     n is divisible by 4 =⇒ n is even “A real number r can be greater than 10 only if it is strictly positive.”     r > 10 =⇒ r > 0 “The composition g ◦ f of two functions f and g is continuous whenever both functions are continuous.”     f and g are continuous =⇒ g ◦ f is continuous “Any differentiable function f is continuous.”     f is differentiable =⇒ f is continuous Contrapositive The conditional statement Property A holds =⇒ Property B holds is logically equivalent to its contrapositive, the statement that Property B fails =⇒ Property A fails Both of these implications mean precisely that there is no situation where A holds and B fails. Example of a Statement and its Contrapositive For example, the statement “If n is an integer, then n is a rational number” has precisely the same meaning as the statement “If n is not a rational number, then n cannot be an integer”. Both say that the set of integers is contained in the set of rational numbers. Page 4 of 7 Math 150s Proof and Mathematical Reasoning Converse The conditional statement A =⇒ B is not equivalent to the statement B =⇒ A, which is called its converse. Example of a True Implication with a False Converse Let N be an integer. It is true that:     N is divisible by 6 =⇒ N is divisible by 3 . The converse statement, however, is false.     N is divisible by 3 6=⇒ N is divisible by 6 . Be careful not to confuse a conditional statement with its converse! Two-Way Implication We write A ⇐⇒ B to mean “A is true if and only if B is true”. We say that A and B are equivalent. Proving an “if and only if” statement requires t̆wo steps: showing A =⇒ B, and showing B =⇒ A. Examples of Two-Way Implication Theorem 2. Let P (x) be a polynomial in x, and let r be a real number. Then P (r) = 0 if and only if (x − r) is a factor of P . Theorem 3. Let a and b be real numbers. Then |a + b| = |a| + |b| if and only if (ab) ≥ 0. A Warning About Definitions There is an unfortunate convention in mathematics to write definitions as “if” statements, even though they should be interpreted as meaning “if and only if”. For example, the statement “An interval I is called open if it does not contain its endpoints” should be understood to mean “An interval I is open if and only if it does not contain its endpoints”. Page 5 of 7 Math 150s Proof and Mathematical Reasoning Proof Techniques Technique #1: Proof by Contradiction Suppose that the hypotheses are true, but that the conclusion is false. Reach a contradiction. Deduce that if the hypotheses are true, the conclusion must be true too. Example of a Proof by Contradiction Theorem 4. If |x| <  for every real number  > 0, then x = 0. Proof. Suppose for the sake of eventual contradiction that |x| <  for every positive number , but x 6= 0. Since x 6= 0, necessarily |x| |x| > 0, so in particular |x| <  for the positive number  = > 0. This means 2 2 |x| < |x| . 2 But, |x| 6= 0 by assumption, so we can divide both sides by |x| to conclude that 1 < 21 , a contradiction! Thus, if |x| <  for every real number  > 0, it must be the case that x = 0. Technique #2: Proof by Exhaustion This involves breaking down the proof into a number of cases. Argue that any instance of the theorem falls into one of the cases, and show that the theorem is true in every case. Example of a Proof by Exhaustion Theorem 5. For any real number a, |a|2 = a2 . Proof. Since a must satisfy either a ≥ 0 or a < 0, it suffices to prove the result for these two cases. If a ≥ 0, then |a| = a, so |a|2 = a2 . If a < 0, then |a| = −a, so |a|2 = (−a)2 = (−1)2 a2 = a2 . In all cases, |a|2 = a2 . Technique #3: Proof by Induction This is a technique used to prove a mathematical proposition P (n) involving a natural number n is true for every value of n. P (n) might be a formula for example, 1 2 + 2 2 + · · · + n2 = n(n + 1)(2n + 1) 6 or a statement involving a variable n for example, “For every natural number n, n3 + 2n is divisible by 3.” A proof by induction is structured as follows: Page 6 of 7 Math 150s Proof and Mathematical Reasoning 1. The Base Case. Prove that the proposition holds when n = 1 2. The Inductive Step. Prove that, under the assumption that proposition holds for n = k for some natural number k, it follows that it holds for the subsequent number n = k + 1. The inductive step involves proving a conditional statement: If P (n) holds when n = k, then P (n) holds when n = k + 1. 3. Conclusion. Conclude that the proposition holds for every natural number n. Because the proposition holds when n = 1, the inductive step implies that it must hold when n = 2, and therefore it must hold when n = 3, and when n = 4, and so forth, for every natural number n. The reasoning behind a proof by induction is often compared to ’the domino effect’. An example of a proof by induction in given in Section 1.8. Homework 1. Read through this handout. Make note of any questions you have, or parts of the handout you found confusing. 2. Briefly explain why a mathematical statement of the form “Under conditions A, conclusion B is true“ cannot be proven with a single example, but it can be disproven with a single example. 3. Briefly explain why a conditional statement A =⇒ B is equivalent to its contrapositive. 4. Suppose we know that A =⇒ B and and we are in a situation where A is false. What can we conclude about B? (Trick question!) 5. Write the following conditional statements in the form A =⇒ B, and write the converses. For each statement, indicate whether the statement is true or false, and indicate whether its converse is true or false. (a) If n is an integer, then 2n is an integer. (b) A number 5n is rational only if n is rational. (c) Let a and b be real numbers. If |a| < |b|, then a < b. Page 7 of 7