3 ,,uoh "gram 3 Eww 3 m T mm H a 3 .2 ' m w .,.m.av>v 3. m. @3on we geonwoaoa mm H "with M'nr H E. wads + we A at. ES 0 3.8V WEE 3563 mo wow 23 E m \"9H .3 avgmeMm\" mnemagouom Aggy\" wudMHvanmnooavmuoag . 538 vwugd 33; , D MESA. . Wm Math 280 Strategies of Proof Fall 2009 Class Notes 3.1 Proving Universal Statements The method of proof used to prove a mathematical statement is determined by the statement's logical structure. We can determine the logical structure by writing the statement in symbolic form, so this is the first step in the proof of any mathematical statement. Almost all of the statements which you'll be concerned with proving in your mathematics courses will involve one or more quantifiers. So we want to begin our examination of proof techniques by discussing how to prove the general universal statement and how to prove the general existential statement. The overwhelming majority of mathematical theorem statements are universally quantified statements of the general form x p(x), where the propositional function p(x) may be either simple or compound. We may also have more than one variable involved. The universal statement x p(x) is true provided that the propositional function p(x) is true for all elements x in the domain D. So to prove the statement x p(x) is true, we need to show that, for each element x in the domain D, the propositional function p(x) is true. There are two basic approaches to proving a universal statement: proof by exhaustion and proof by arbitrary element. Proof by Exhaustion When the domain D is a finite set, we can prove that x p(x) is true by systematically checking that p(x) is true for each x D. This method of proof is called proof by exhaustion. Here are two examples of proofs by exhaustion. Example. Prove: For all positive integers n with 1 n 10, n2 n + 11 is a prime number. Solution. Define the propositional function p(n) : n2 n + 11 is a prime number. The statement has symbolic form n p(n), where the domain for n is the set D = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Proof. For a proof by exhaustion of n p(n), we need to show that p(n) is true for each value of n in the domain D. Substituting each value of n into the propositional function, we have p(1) : p(2) : p(3) : p(4) : p(5) : p(6) : p(7) : p(8) : p(9) : p(10) : 12 1 + 11 = 11 is a prime number. 22 2 + 11 = 13 is a prime number. 32 3 + 11 = 17 is a prime number. 42 4 + 11 = 23 is a prime number. 52 5 + 11 = 31 is a prime number. 62 6 + 11 = 41 is a prime number. 72 7 + 11 = 53 is a prime number. 82 8 + 11 = 67 is a prime number. 92 9 + 11 = 83 is a prime number. 102 10 + 11 = 101 is a prime number. Since each of these statements is true. then n p(n) is true, which proves this statement. 55 56 Chapter 3 Proof Techniques Example. Let be an irrational number. A rational number a0 /b0 is called a good approximation to provided that for every rational number a/b with 1 b < b0 , a a 0 < . b0 b This condition means a0 /b0 is closer to than every other rational number with a smaller denominator. We assume all rational numbers are in lowest terms. Show that 13/4 is a good approximation to . Solution. To show that 13/4 is a good approximation to , we need to show the condition in the definition is true with = and a0 /b0 = 13/4: " # 13 a (a/b) < , 4 b where the domain for a/b is the set of rational numbers with 1 b < b0 = 4. Define the propositional function 13 a p(a/b) : < . 4 b So we need to show (a/b) p(a/b) . Proof. We need to show that p(a/b) is true for all rational numbers a/b with 1 b < 4. Since 1 b < 4, then b = 1, 2, or 3. We only need to show that p(a/b) is true for the rational numbers with these denominators that are closest to . For instance, when b = 1, then 3/1 and 4/1 are closer to is closer than any other rational number with denominator 1, so we only need to show p(a/b) is true for 3/1 and 4/1. So we need to show that p(a/b) is true for these rational numbers: a 3 4 6 7 9 10 = , , , , , . b 1 1 2 2 3 3 We can skip 62 and 93 since these both equal 3. Note 13 = 0.108407 4 to six decimal places. We then have 13 3 p(3/1) : < = 0.141593 4 1 13 4 p(4/1) : < = 0.858407 4 1 13 7 p(7/2) : < = 0.353407 4 2 13 10 p(10/3) : < = 0.191741 4 3 Each of these inequalities is true. Therefore (a/b) p(a/b) is true. Thus 13/4 is a good approximation to . Even though 13/4 is a good approximation to , it is still relatively far from . We can obtain better approximations to by finding good approximations with larger denominators. For instance, some other good approximations to = 3.141593 are 22/7 = 3.142857, 333/106 = 3.141509, and 355/113 = 3.141593, all accurate to six decimal places. 3.1 57 Proving Universal Statements Proof by Arbitrary Element Proof by exhaustion can, in theory, be used whenever the domain of the variable in the propositional function is finite. The method is only practical, however, when the domain is relatively small, although computers can be employed to examine all the elements in a relatively large domain for certain types of statements. The method that we employ to prove universal statements when proof by exhaustion is not feasible is called proof by arbitrary element. The idea behind a proof by arbitrary element of a universal statement x p(x) is the following. We suppose that x represents a particular but arbitrarily chosen element of the domain D, and then prove that p(x) is true for this element x. We can then conclude that p(x) must be true for all elements in the domain D, and hence x p(x) is true. This method of proof is also called the generalizing from the generic particular. We are supposing that x represents an arbitrary, or generic, element from the domain. We then show that the propositional function is true using an argument that applies, or can be generalized, to all elements of the domain D. Procedure: Proof by Arbitrary Element To prove a universal statement of the form (x D) p(x): 1. Suppose x is an arbitrary element of the domain D. We start by supposing x is a particular but arbitrarily chosen element of the domain D. This lets the reader know what the variable x represents in the proof. Most proofs may involve several dierent variables, some arbitrary and some related to previously introduced variables. Whenever a new variable is introduced during the writing of a proof, it's important to specify what the variable represents. 2. Show that p(x) is true for the arbitrary element x. We need to construct a logically valid argument showing that the propositional function p(x) must be true using definitions, axioms, previously proved results, and the laws of logic. Since x is assumed to be a generic element of the domain, we can only use properties which are common to all elements of the domain. We cannot make any assumptions about x that are not true for all elements in the domain D. The reason for this is that when we show that p(x) is true, we need to construct a proof that will apply to all elements in the domain, not to just some of the elements in the domain. So for instance, if the domain D is the set of all real numbers, we cannot construct a proof that p(x) is true that applies only when x is positive. Or, if the domain D is the set of all integers, we cannot construct a proof that p(x) is true that applies only when x is even. Functions Before we can get started proving results, we need to have some basic definitions available to us. We'll start with the definition of a function. Definition. Let A and B be sets. A function f from A into B is a rule or correspondence which associates with each element a A a unique element b B. The set A is called the domain and the set B is called the codomain of the function. We denote the function with the notation f : A B. The element b B associated with an element a A is denoted f (a) and we write b = f (a). The element b = f (a) is called the image of a under f . The range of f is the set of all images under f . (Note that some texts use the term range instead of codomain and image in place of range.) f a b = f(a) Range Domain Codomain 58 Chapter 3 Proof Techniques We can now define properties of functions and determine whether or not specific functions satisfy these properties. Definition. A real-valued function f : A R is even provided that for all x A, f (x) = f (x). A real-valued function f : A R is odd provided that for all x A, f (x) = f (x). x2 for each x R. Show that f is even. x2 + 1 Solution. To show that f is an even function, we need to show Example. Let f : R R be defined by f (x) = (x R) [f (x) = f (x)]. Since this is a universal statement with an infinite domain, then we use a proof by arbitrary element. Proof. Suppose x is an arbitrary real number. We need to show f (x) = f (x). According to the definition of the function, f (x) = (x)2 x2 = = f (x) (x)2 + 1 x2 + 1 Therefore f (x) = f (x), as required. Since x was assumed to be an arbitrary real number, this proves the universal statement (x R) [f (x) = f (x)]. Thus f is an even function. 2 Example. Let f : R R be defined by f (x) = x + 3x3 ex for each x R. Show that f is odd. Solution. To show that f is an odd function, we need to show (x R) [f (x) = f (x)]. Proof. Suppose x is an arbitrary real number. We need to show f (x) = f (x). According to the definiton of the function, 2 2 2 f (x) = (x) + 3(x)3 e(x) = x 3x3 ex = x + 3x3 ex = f (x) Therefore f (x) = f (x), as required. Since x was assumed to be an arbitrary real number, this proves the universal statement (x R) [f (x) = f (x)]. Thus f is an odd function. Definition. A real-valued function f : A R has an absolute maximum at a point x = c provided that for all x A, f (x) f (c). A real-valued function f : A R has an absolute minimum at a point x = c provided that for all x A, f (x) f (c). The diagram illustrates a function with domain [a, b] with an absolute maximum at the right endpoint x = b and an absolute minimum at an interior point of the interval. An absolute maximum corresponds to the highest point of the graph over its domain, and an absolute minimum to the lowest point of the graph over its domain. y absolute maximum a absolute minimum b x 3.1 59 Proving Universal Statements Example. Let f : R R be defined by f (x) = 10 x2 for all x R. Show, without using calculus, that f has an absolute maximum at x = 0. Solution. To show that f has an absolute maximum at x = 0, we need to show (x R) f (x) f (0) . Proof. Suppose x is an arbitrary real number. We need to show f (x) f (0). Since f (x) = 10 x2 and f (0) = 10 02 = 10, then we need to show 10 x2 10. Since x is a real number, then x2 0 so x2 0. Adding 10 to both sides of this inequality, we obtain 10 x2 10, as required. Therefore f (x) 10. Since x was assumed to be a real number, this proves the universal statement (x R) f (x) f (0) . Thus f has an absolute maximum at x = 0. So far, our proofs have dealt only with properties of specific functions. We now want to consider some more general proofs. We first state some additional definitions. Definition. Let f and g be two functions from A to B. The sum of f and g is the function f + g : A B defined by (f + g)(x) = f (x) + g(x) for each x A. The product of f and g is the function f g : A B defined by (f g)(x) = f (x) g(x) for each x A. Definition. Let f : A B and g : B C be functions. The composition of f and g is the function g f : A C defined by (g f )(x) = g f (x) for each x A. The composition of two functions can be represented pictorially as shown. Since f : A B, then f maps elements of the set A into elements of B, and since g : B C, then g maps elements of B into elements of C. The composition g f maps elements of A directly into elements of C, bypassing the middle set B. gf f g a f (a) A B ! ! g f (a) C 60 Chapter 3 Proof Techniques Example. Prove: The sum of any two odd functions is odd. Solution. The keyword \"any\" tells us this is a universal statement. We want to write this in symbolic form. To do this, we first rewrite the statement in a more standard form using variables: For all odd functions f and g, their sum f + g is odd. The statement then has symbolic form f g [f + g is odd] where the domain for f and g is the set of all odd functions. In order for the sum f + g to be defined, the two functions f and g must have the same domain so we can assume f and g both have domain A. Also, the definition of an odd function requires that the functions have codomain R. Therefore we can assume f : A R and g : A R. This is all implied in the statement to be proved and is left to you, the student, to recognize on your own. We're now ready to prove this statement. Since this is a universal statement, we use a proof by arbitrary element. Proof. Suppose f and g are arbitrary odd functions from A to R. We need to show f + g is odd. According to the definition of an odd function, to show this, we need to show (x A) (f + g)(x) = (f + g)(x) . This is another universal statement, so to prove this, we use a proof by arbitrary element. Suppose x is an arbitrary element of the domain A. We need to show (f + g)(x) = (f + g)(x). According to the definition of the sum f + g, (f + g)(x) = f (x) + g(x) Since f is assumed to be an odd function, then f (x) = f (x), and since g is assumed to be an odd function, then g(x) = g(x). Then (f + g)(x) = f (x) + g(x) = f (x) + g(x) = f (x) + g(x) = (f + g)(x) (by the definition of f + g) (since f and g are both odd) (by the distributive law) (by the definition of f + g again) Therefore (f + g)(x) = (f + g)(x). Sincex was assumed to be an arbitrary element of A, this proves (x A) (f + g)(x) = (f + g)(x) , so f + g is odd. Since f and g were assumed to be arbitrary odd functions, this proves f g [f + g is odd]. Thus the sum of any two odd functions is odd. In order to prove the universal statement in the preceding example f g [f + g is odd], we use a proof by arbitrary element. In the course of this proof, we needed to prove the universal statement (x A) (f + g)(x) = (f + g)(x) , arising from the definition of an odd function. To prove this statement, we use another proof by arbitrary element. This is typical of many proofs in containing one proof nested inside another proof. 3.1 61 Proving Universal Statements Example. Prove: The composition of any two odd functions is odd. Solution. This can be rewritten in the form For all odd function f : A B and g : B C, their composition g f : A C is odd. In order for the composition to be defined, the domain of g must be the same as the codomain of f . Furthermore, in order for f and g to be odd, we must assume that B and C are both sets of real numbers. The statement then has symbolic form f g [g f is odd], where the domain for f and g is the set of odd functions. Proof. Suppose f : A B and g : B C are arbitrary odd functions. We need to show To show this, we need to show g f is odd. (x A) (g f )(x) = (g f )(x) . To prove this, suppose x is an arbitrary element of A. We need to show (g f )(x) = (g f )(x). Applying the definitions of the composition and of an odd function, we obtain (g f )(x) = g f (x) (by the definition of g f ) = g f (x) (since f is odd) (since g is odd) = g f (x) (by the definition of g f again) = (g f )(x) Therefore g f is odd. Since f and g were assumed to be arbitrary odd functions, then the result follows. Example. Let D be the set of all nonzero real numbers and let f : D R be defined by x1 f (x) = for all x D. x Show that for all x D, (f f f )(x) = x. Solution. In symbolic form, we need to show (x D) (f f f )(x) = x . Proof. Suppose x is an arbitrary nonzero real number. We need to show (f f f )(x) = x. Applying the definition of the composition and of the function, we obtain x1 1 x1 (x 1) x 1 x (f f (x) = f f (x) = f = = = x1 x x1 x1 x Then 1 1 1 1 (x 1) x x1 = (f f f )(x) = f (f f )(x) = f = = =x 1 x1 1 1 x1 as required. Thus (f f f )(x) = x for all x in D. 62 Chapter 3 Proof Techniques A proof by arbitrary element can also be used to prove universally quantified statements with more than one variable. For instance, to prove that a universal statement x y q(x, y) is true, we suppose that x and y represent particular but arbitrarily chosen elements in their respective domains, and then prove that q(x, y) is true for these elements x and y. We can then conclude that q(x, y) must be true for all elements in the domains, and hence x y q(x, y) is true. Definition. Let D be a set of ordered pairs (x, y). A function f of two variables is a rule that assigns to each ordered pair (x, y) in D a unique real number denoted by f (x, y). The set D is the domain of f . We denote the function with the notation f : D R. Example. Let n be a positive integer. A function f of two variables is homogeneous of degree n provided that for all ordered pairs (x, y) in D and for all real numbers t, f (tx, ty) = tn f (x, y). Let f be defined by f (x, y) = x2 y + 2xy 2 + 5y 3 for all ordered pairs of real numbers (x, y). Show that f is homogeneous of degree 3. Solution. To show that f is homogeneous of degree 3, we need to show (x, y) (t R) f (tx, ty) = t3 f (x, y) . Proof. Suppose (x, y) is an arbitrary ordered pair of real numbers and suppose t is an arbitrary real number. We need to show f (tx, ty) = t3 f (x, y). According to the definition of the function, f (tx, ty) = (tx)2 (ty) + 2(tx)(ty)2 + 5(ty)3 = t3 (x2 y) + t3 (2xy 2 ) + t3 (5y 3 ) = t3 [x2 y + 2xy 2 + 5y 3 ] = t3 f (x, y) Therefore f is homogeneous of degree 3. Directions for Writing Proofs In your earlier mathematics courses, you may have written up proofs using a far more informal style. For instance, in a precalculus course, when asked to prove that a specific function, such as the function f : R R defined by f (x) = x + 3x3 for each x R, is odd, simply writing out f (x) = (x) + 3(x)3 = x 3x3 = f (x) may have been considered sucient. In this course and in your upper-division mathematics courses to follow, you are generally going to be expected to write your proofs using a more formal style, adhering to certain guidelines. Over the years the rules of style have become fairly standard for writing proofs. In later courses, as you become more experienced in writing proofs, you may be able to omit one or more of the following rules. As you're starting out in this course, however, you should be sure to follow each one. 1. Write the statement to be proved in symbolic form. The symbolic form of the statement will determine the method of proof to be attempted. As part of writing the statement in symbolic form, you will need to identify the domain of each variable. 2 Clearly indicate the formal beginning of your proof. Textbooks and your mathematics instructors will typically write the word \"Proof\" to indicate the formal beginning of the proof. 3.1 63 Proving Universal Statements 3. Specify each variable that is used in the proof. This means you should identify each variable used in the proof in the body of the proof. Each time you introduce a variable, you should state whether the variable is arbitrary or arises from applying a definition or theorem, and what kind of object it is. In introducing variables at the beginning of a proof, you will generally say something like \"Suppose m and n are arbitrary integers\" or \"Let x be an arbitrary real number.\" Later on in a proof, you may introduce a variable that arises from applying a definition. For instance, if you know that an integer n is even, then you can write n = 2k. But when you do this, you must specify that k is an integer. In this case, k is not arbitrary but follows from the definition of n being even, so you should state \"Since n is even, then there exists an integer k such that n = 2k.\" 4. Write proofs in complete English sentences. At each stage of a proof, where appropriate, you should clearly indicate you're supposing and what you're trying to prove. You should provide reasons for the steps in your proofs. When you reach the end of a proof, clearly state that you've proved the desired conclusion. Your proofs should be neatly written up using correct and complete English sentences. Of course, you will use mathematical symbols to denote sets, elements, functions, etc., but mathematical expressions should always read properly within the context of the sentence. You should not use logical symbols, such as (for all), (there exists), or (implies) in place of the English words in a sentence. Such symbols should only be used as part of a logical statement, which will generally appear in a display. You also should not make up your own mathematical symbols or shorthand. The Beginning of a Proof Before beginning a proof, you should first rewrite the statement to be proved formally, with appropriate variables. You can then readily translate the statement to symbolic form. The starting point for your proof then consists of specifying the names of your variables and what kinds of mathematical objects they represent, and any hypotheses. You should then state what you are trying to prove. You can do this for any theorem statement, whether or not you understand the terms used, since the beginning of a proof depends only upon the logical structure of the statement to be proved. Example. Write the beginning of a proof of the following theorem statement. Every cyclic group is abelian. Solution. This statement can be rewritten in the standard form For every cyclic group G, G is abelian. which then has symbolic form G [G is abelian] where the domain for G is the set of cyclic groups. The beginning of the proof will then be Proof. Suppose G is an arbitrary cyclic group. We need to show G is abelian. At this point in the proof, we need to know the definition of an abelian group. The next line would be \"To show G is abelian, we need to show . . . \" 64 Chapter 3 Proof Techniques Disproving Universal Statements A universal statement x p(x) is false provided that there exists at least one counterexample x in the domain for which the propositional function p(x) is false. So to disprove the universal statement x p(x), we need to show that there exists such a counterexample. For instance, suppose we wish to disprove the statement: For all real numbers x and y, (x + y)2 = x2 + y 2 . This has symbolic form x y [(x + y)2 = x2 + y 2 ]. To disprove this universal statement, we need to find a counterexample. We can choose x = 1 and y = 5, for instance, and compute (x + y)2 = (1 + 5)2 = 42 = 16 and x2 + y 2 = (1)2 + 52 = 26. Since 16 6= 26, this shows that the statement x y [(x + y)2 = x2 + y 2 ] is false, which disproves the statement. A common, but logically incorrect, approach to disproving the statement x y [(x + y)2 = x2 + y 2 ] is to write: Suppose x and y are arbitrary real numbers. Then (x + y)2 = (x + y)(x + y) = x2 + 2xy + y 2 6= x2 + y 2 While this might appear to be a convincing argument, this is not a logically correct approach to disproving the statement. To disprove a universal statement, we need to find a specific counterexample, and in general, should not argue using arbitrary elements. In fact, the assertion (x + y)2 6= x2 + y 2 in the above argument is not true for arbitrary elements of the domain. In particular, in the case that one of x or y equals 0, then equality holds. Common Errors in Proving Universal Statements The following are some of the common errors that arise in proving universally quantified statements. 1. Arguing from examples. We cannot conclude that a universally quantified statement x p(x) is true by showing that the propositional function p(x) is true only for one or even several specific values of x in the domain. The propositional function may be true for many values of x without being true for all x in the domain. For instance, suppose we want to prove the statement: The product of any two odd integers is odd. This can be written formally as: For all odd integers m and n, their product mn is odd. This has symbolic form m n [mn is odd] where the domain for both m and n is the set of odd integers. Here is an example of arguing from examples to prove this statement: Let m = 7 and n = 15. Both m and n are odd and their product mn = 7(15) = 105 is odd. Therefore the product of any two odd integers is odd. 3.1 2. 3. 4. 5. Proving Universal Statements 65 While this argument has verified the propositional function for two integers m and n, this is not sucient to prove that the universal quantified statement is true. There are many cases of propositional functions which are true for many special cases of the variables which are not true for all elements in the domain. What makes this argument appear valid to many people is the original form of the statement: \"The product of any two odd integers is odd.\" It might appear from the statement that we get to choose any two odd integers we like and then verify that their product is odd. We need to recognize, however, that this is in fact a universally quantified statement written in informal English. Assuming specific forms for arbitrary elements. In a proof by arbitrary element of the statement x [p(x)], we suppose x is an arbitrarily chosen element of the domain and show that p(x) is true. The point of having x be an arbitrary (or generic) element of the domain is to construct a proof that can be generalized to any element of the domain. We cannot assume that the arbitrary element x has any specific properties that are not satisfied by all elements in the domain. For instance, if the domain of x is the set of all real numbers, we cannot verify the propositional function is true while assuming x is positive. If the domain is the set of real-valued functions, we cannot prove the propositional function while assuming the variable is an even function. If the proof applies to the arbitrary element x, then everything we deduce about x in the proof must be true about any other element of the domain. Using the same letter to represent two dierent things. When working through a proof, several variables may be involved. These may be introduced at the beginning of the proof or as we work through the steps of the proof. We need to be careful not to use the same letter to represent two dierent variables. For instance, in the proof earlier that the composition of two odd functions is odd, we do not want to use the same letter to represent both of the functions. For another example, suppose a proof involves two even integers m and n. Since m is even, then there exists an integer k such that m = 2k, and since n is even, then there exists an integer l such that n = 2l. A common error is to assume that both m and n equal 2k for the same integer k. But this would mean that m and n are themselves equal, which we may not be able to assume. Assuming the conclusion (or begging the question). While this may seem to be an obvious error, when working through a proof, we often move back and forth between what is assumed and what is to be proved. We need to be careful during this process not to accidently assume what is to be proved. Many times this results from confusing what is being supposed or hypothesized and what needs to be shown. This is one of the reasons why you should always begin your proof by stating the hypotheses and identifying what you are trying to show. Misuse of the word \"if.\" While this error is not serious in itself, it reflects imprecise thinking that sometimes leads to problems in a proof. This error involves using the word \"if\" when the word \"since\" or \"because\" is really meant. For instance, consider the statement: Suppose m is an even integer. If m is even, then there exists an integer k such that m = 2k. The use of the word \"if\" in the second sentence is not appropriate since it suggests that we do not know whether or not m is even. But according to the first sentence, we know (or are supposing) m is even. The correct word to use in the second sentence is \"since\" or \"because.\