PPI.pdf Logic and Proofs PDF

78 1 / The Foundations: Logic and Proofs will wake up feeling refreshed.” Then the premises are p → q, ¬p → r, and r → s. The desired conclusion is ¬q → s. We need to give a valid argument with premises p → q, ¬p → r, and...

78 1 / The Foundations: Logic and Proofs will wake up feeling refreshed.” Then the premises are p → q, ¬p → r, and r → s. The desired conclusion is ¬q → s. We need to give a valid argument with premises p → q, ¬p → r, and r → s and conclusion ¬q → s. This argument form shows that the premises lead to the desired conclusion. Step Reason 1. p → q Premise 2. ¬q → ¬p Contrapositive of (1) 3. ¬p → r Premise 4. ¬q → r Hypothetical syllogism using (2) and (3) 5. r → s Premise 6. ¬q → s Hypothetical syllogism using (4) and (5) ◂ 1.6.5 Resolution Computer programs have been developed to automate the task of reasoning and proving theo- rems. Many of these programs make use of a rule of inference known as resolution. This rule Links of inference is based on the tautology ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r). (Exercise 34 in Section 1.3 asks for the verification that this is a tautology.) The final disjunction in the resolution rule, q ∨ r, is called the resolvent. When we let q = r in this tautology, we obtain (p ∨ q) ∧ (¬p ∨ q) → q. Furthermore, when we let r = F, we obtain (p ∨ q) ∧ (¬p) → q (because q ∨ F ≡ q), which is the tautology on which the rule of disjunctive syllogism is based. EXAMPLE 8 Use resolution to show that the hypotheses “Jasmine is skiing or it is not snowing” and “It is snowing or Bart is playing hockey” imply that “Jasmine is skiing or Bart is playing hockey.” Extra Examples Solution: Let p be the proposition “It is snowing,” q the proposition “Jasmine is skiing,” and r the proposition “Bart is playing hockey.” We can represent the hypotheses as ¬p ∨ q and p ∨ r, respectively. Using resolution, the proposition q ∨ r, “Jasmine is skiing or Bart is playing hockey,” follows. ◂ Resolution plays an important role in programming languages based on the rules of logic, such as Prolog (where resolution rules for quantified statements are applied). Furthermore, it can be used to build automatic theorem proving systems. To construct proofs in propositional logic using resolution as the only rule of inference, the hypotheses and the conclusion must be expressed as clauses, where a clause is a disjunction of variables or negations of these variables. We can replace a statement in propositional logic that is not a clause by one or more equivalent statements that are clauses. For example, suppose we have a statement of the form p ∨ (q ∧ r). Because p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), we can replace the single statement p ∨ (q ∧ r) by two statements p ∨ q and p ∨ r, each of which is a clause. We can replace a statement of the form ¬(p ∨ q) by the two statements ¬p and ¬q because De Morgan’s law tells us that ¬(p ∨ q) ≡ ¬p ∧ ¬q. We can also replace a conditional statement p → q with the equivalent disjunction ¬p ∨ q. EXAMPLE 9 Show that the premises (p ∧ q) ∨ r and r → s imply the conclusion p ∨ s. Solution: We can rewrite the premises (p ∧ q) ∨ r as two clauses, p ∨ r and q ∨ r. We can also replace r → s by the equivalent clause ¬r ∨ s. Using the two clauses p ∨ r and ¬r ∨ s, we can use resolution to conclude p ∨ s. ◂  1.6 Rules of Inference 79 1.6.6 Fallacies Several common fallacies arise in incorrect arguments. These fallacies resemble rules of infer- ence, but are based on contingencies rather than tautologies. These are discussed here to show the distinction between correct and incorrect reasoning. The proposition ((p → q) ∧ q) → p is not a tautology, because it is false when p is false and Links q is true. However, there are many incorrect arguments that treat this as a tautology. In other words, they treat the argument with premises p → q and q and conclusion p as a valid argument form, which it is not. This type of incorrect reasoning is called the fallacy of affirming the conclusion. EXAMPLE 10 Is the following argument valid? If you do every problem in this book, then you will learn discrete mathematics. You learned discrete mathematics. Therefore, you did every problem in this book. Solution: Let p be the proposition “You did every problem in this book.” Let q be the proposition “You learned discrete mathematics.” Then this argument is of the form: if p → q and q, then p. This is an example of an incorrect argument using the fallacy of affirming the conclusion. Indeed, it is possible for you to learn discrete mathematics in some way other than by doing every problem in this book. (You may learn discrete mathematics by reading, listening to lectures, doing some, but not all, the problems in this book, and so on.) ◂ The proposition ((p → q) ∧ ¬p) → ¬q is not a tautology, because it is false when p is false and q is true. Many incorrect arguments use this incorrectly as a rule of inference. This type of incorrect reasoning is called the fallacy of denying the hypothesis. EXAMPLE 11 Let p and q be as in Example 10. If the conditional statement p → q is true, and ¬p is true, is it correct to conclude that ¬q is true? In other words, is it correct to assume that you did not learn discrete mathematics if you did not do every problem in the book, assuming that if you do every problem in this book, then you will learn discrete mathematics? Solution: It is possible that you learned discrete mathematics even if you did not do every prob- lem in this book. This incorrect argument is of the form p → q and ¬p imply ¬q, which is an example of the fallacy of denying the hypothesis. ◂ 1.6.7 Rules of Inference for Quantified Statements We have discussed rules of inference for propositions. We will now describe some important rules of inference for statements involving quantifiers. These rules of inference are used exten- sively in mathematical arguments, often without being explicitly mentioned. Universal instantiation is the rule of inference used to conclude that P(c) is true, where c is a particular member of the domain, given the premise ∀xP(x). Universal instantiation is used when we conclude from the statement “All women are wise” that “Lisa is wise,” where Lisa is a member of the domain of all women. Universal generalization is the rule of inference that states that ∀xP(x) is true, given the premise that P(c) is true for all elements c in the domain. Universal generalization is used when we show that ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true. The element c that we select must be an arbitrary, and not a specific, element of the domain. That is, when we assert from ∀xP(x) the existence of an element c in the domain, 80 1 / The Foundations: Logic and Proofs TABLE 2 Rules of Inference for Quantified Statements. Rule of Inference Name ∀xP(x) Universal instantiation ∴ P(c) P(c) for an arbitrary c Universal generalization ∴ ∀xP(x) ∃xP(x) Existential instantiation ∴ P(c) for some element c P(c) for some element c Existential generalization ∴ ∃xP(x) we have no control over c and cannot make any other assumptions about c other than it comes from the domain. Universal generalization is used implicitly in many proofs in mathematics and is seldom mentioned explicitly. However, the error of adding unwarranted assumptions about the arbitrary element c when universal generalization is used is all too common in incorrect reasoning. Existential instantiation is the rule that allows us to conclude that there is an element c in the domain for which P(c) is true if we know that ∃xP(x) is true. We cannot select an arbitrary value of c here, but rather it must be a c for which P(c) is true. Usually we have no knowledge of what c is, only that it exists. Because it exists, we may give it a name (c) and continue our argument. Existential generalization is the rule of inference that is used to conclude that ∃xP(x) is true when a particular element c with P(c) true is known. That is, if we know one element c in the domain for which P(c) is true, then we know that ∃xP(x) is true. We summarize these rules of inference in Table 2. We will illustrate how some of these rules of inference for quantified statements are used in Examples 12 and 13. EXAMPLE 12 Show that the premises “Everyone in this discrete mathematics class has taken a course in computer science” and “Marla is a student in this class” imply the conclusion “Marla has taken Extra a course in computer science.” Examples Solution: Let D(x) denote “x is in this discrete mathematics class,” and let C(x) denote “x has taken a course in computer science.” Then the premises are ∀x(D(x) → C(x)) and D(Marla). The conclusion is C(Marla). The following steps can be used to establish the conclusion from the premises. Step Reason 1. ∀x(D(x) → C(x)) Premise 2. D(Marla) → C(Marla) Universal instantiation from (1) 3. D(Marla) Premise 4. C(Marla) Modus ponens from (2) and (3) ◂ EXAMPLE 13 Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.”  1.6 Rules of Inference 81 Solution: Let C(x) be “x is in this class,” B(x) be “x has read the book,” and P(x) be “x passed the first exam.” The premises are ∃x(C(x) ∧ ¬B(x)) and ∀x(C(x) → P(x)). The conclusion is ∃x(P(x) ∧ ¬B(x)). These steps can be used to establish the conclusion from the premises. Step Reason 1. ∃x(C(x) ∧ ¬B(x)) Premise 2. C(a) ∧ ¬B(a) Existential instantiation from (1) 3. C(a) Simplification from (2) 4. ∀x(C(x) → P(x)) Premise 5. C(a) → P(a) Universal instantiation from (4) 6. P(a) Modus ponens from (3) and (5) 7. ¬B(a) Simplification from (2) 8. P(a) ∧ ¬B(a) Conjunction from (6) and (7) 9. ∃x(P(x) ∧ ¬B(x)) Existential generalization from (8) ◂ 1.6.8 Combining Rules of Inference for Propositions and Quantified Statements We have developed rules of inference both for propositions and for quantified statements. Note that in our arguments in Examples 12 and 13 we used both universal instantiation, a rule of in- ference for quantified statements, and modus ponens, a rule of inference for propositional logic. We will often need to use this combination of rules of inference. Because universal instantia- tion and modus ponens are used so often together, this combination of rules is sometimes called universal modus ponens. This rule tells us that if ∀x(P(x) → Q(x)) is true, and if P(a) is true for a particular element a in the domain of the universal quantifier, then Q(a) must also be true. To see this, note that by universal instantiation, P(a) → Q(a) is true. Then, by modus ponens, Q(a) must also be true. We can describe universal modus ponens as follows: ∀x(P(x) → Q(x)) P(a), where a is a particular element in the domain ∴ Q(a) Universal modus ponens is commonly used in mathematical arguments. This is illustrated in Example 14. EXAMPLE 14 Assume that “For all positive integers n, if n is greater than 4, then n2 is less than 2n ” is true. Use universal modus ponens to show that 1002 < 2100. Solution: Let P(n) denote “n > 4” and Q(n) denote “n2 < 2n.” The statement “For all positive integers n, if n is greater than 4, then n2 is less than 2n ” can be represented by ∀n(P(n) → Q(n)), where the domain consists of all positive integers. We are assuming that ∀n(P(n) → Q(n)) is true. Note that P(100) is true because 100 > 4. It follows by universal modus ponens that Q(100) is true, namely, that 1002 < 2100. ◂ Another useful combination of a rule of inference from propositional logic and a rule of in- ference for quantified statements is universal modus tollens. Universal modus tollens combines universal instantiation and modus tollens and can be expressed in the following way: ∀x(P(x) → Q(x)) ¬Q(a), where a is a particular element in the domain ∴ ¬P(a) 82 1 / The Foundations: Logic and Proofs The verification of universal modus tollens is left as Exercise 25. Exercises 26–29 develop additional combinations of rules of inference in propositional logic and quantified statements. Exercises 1. Find the argument form for the following argument and 5. Use rules of inference to show that the hypotheses determine whether it is valid. Can we conclude that the “Randy works hard,” “If Randy works hard, then he is conclusion is true if the premises are true? a dull boy,” and “If Randy is a dull boy, then he will not get the job” imply the conclusion “Randy will not get the If Socrates is human, then Socrates is mortal. job.” Socrates is human. 6. Use rules of inference to show that the hypotheses “If it does not rain or if it is not foggy, then the sailing race will ∴ Socrates is mortal. be held and the lifesaving demonstration will go on,” “If the sailing race is held, then the trophy will be awarded,” 2. Find the argument form for the following argument and and “The trophy was not awarded” imply the conclusion determine whether it is valid. Can we conclude that the “It rained.” conclusion is true if the premises are true? 7. What rules of inference are used in this famous argu- ment? “All men are mortal. Socrates is a man. Therefore, If George does not have eight legs, then he is not a Socrates is mortal.” spider. 8. What rules of inference are used in this argument? “No George is a spider. man is an island. Manhattan is an island. Therefore, Man- ∴ George has eight legs. hattan is not a man.” 9. For each of these collections of premises, what relevant 3. What rule of inference is used in each of these argu- conclusion or conclusions can be drawn? Explain the ments? rules of inference used to obtain each conclusion from a) Alice is a mathematics major. Therefore, Alice is ei- the premises. ther a mathematics major or a computer science ma- a) “If I take the day off, it either rains or snows.” “I took jor. Tuesday off or I took Thursday off.” “It was sunny on b) Jerry is a mathematics major and a computer science Tuesday.” “It did not snow on Thursday.” major. Therefore, Jerry is a mathematics major. b) “If I eat spicy foods, then I have strange dreams.” “I c) If it is rainy, then the pool will be closed. It is rainy. have strange dreams if there is thunder while I sleep.” Therefore, the pool is closed. “I did not have strange dreams.” d) If it snows today, the university will close. The uni- c) “I am either clever or lucky.” “I am not lucky.” “If I versity is not closed today. Therefore, it did not snow am lucky, then I will win the lottery.” today. d) “Every computer science major has a personal com- puter.” “Ralph does not have a personal computer.” e) If I go swimming, then I will stay in the sun too long. “Ann has a personal computer.” If I stay in the sun too long, then I will sunburn. There- e) “What is good for corporations is good for the United fore, if I go swimming, then I will sunburn. States.” “What is good for the United States is good 4. What rule of inference is used in each of these argu- for you.” “What is good for corporations is for you to ments? buy lots of stuff.” a) Kangaroos live in Australia and are marsupials. f ) “All rodents gnaw their food.” “Mice are rodents.” Therefore, kangaroos are marsupials. “Rabbits do not gnaw their food.” “Bats are not ro- b) It is either hotter than 100 degrees today or the pollu- dents.” tion is dangerous. It is less than 100 degrees outside 10. For each of these sets of premises, what relevant conclu- today. Therefore, the pollution is dangerous. sion or conclusions can be drawn? Explain the rules of in- c) Linda is an excellent swimmer. If Linda is an ex- ference used to obtain each conclusion from the premises. cellent swimmer, then she can work as a lifeguard. a) “If I play hockey, then I am sore the next day.” “I Therefore, Linda can work as a lifeguard. use the whirlpool if I am sore.” “I did not use the d) Steve will work at a computer company this summer. whirlpool.” Therefore, this summer Steve will work at a computer b) “If I work, it is either sunny or partly sunny.” “I company or he will be a beach bum. worked last Monday or I worked last Friday.” “It was e) If I work all night on this homework, then I can an- not sunny on Tuesday.” “It was not partly sunny on swer all the exercises. If I answer all the exercises, I Friday.” will understand the material. Therefore, if I work all c) “All insects have six legs.” “Dragonflies are insects.” night on this homework, then I will understand the “Spiders do not have six legs.” “Spiders eat dragon- material. flies.”  1.6 Rules of Inference 83 d) “Every student has an Internet account.” “Homer 15. For each of these arguments determine whether the argu- does not have an Internet account.” “Maggie has an ment is correct or incorrect and explain why. Internet account.” a) All students in this class understand logic. Xavier is e) “All foods that are healthy to eat do not taste good.” a student in this class. Therefore, Xavier understands “Tofu is healthy to eat.” “You only eat what tastes logic. good.” “You do not eat tofu.” “Cheeseburgers are not b) Every computer science major takes discrete math- healthy to eat.” ematics. Natasha is taking discrete mathematics. f ) “I am either dreaming or hallucinating.” “I am not Therefore, Natasha is a computer science major. dreaming.” “If I am hallucinating, I see elephants run- c) All parrots like fruit. My pet bird is not a parrot. ning down the road.” Therefore, my pet bird does not like fruit. 11. Show that the argument form with premises p1 , p2 , … , pn d) Everyone who eats granola every day is healthy. and conclusion q → r is valid if the argument form with Linda is not healthy. Therefore, Linda does not eat premises p1 , p2 , … , pn , q, and conclusion r is valid. granola every day. 12. Show that the argument form with premises (p ∧ t) → 16. For each of these arguments determine whether the argu- (r ∨ s), q → (u ∧ t), u → p, and ¬s and conclusion q → r ment is correct or incorrect and explain why. is valid by first using Exercise 11 and then using rules of a) Everyone enrolled in the university has lived in a dor- inference from Table 1. mitory. Mia has never lived in a dormitory. Therefore, 13. For each of these arguments, explain which rules of in- Mia is not enrolled in the university. ference are used for each step. b) A convertible car is fun to drive. Isaac’s car is not a a) “Doug, a student in this class, knows how to write convertible. Therefore, Isaac’s car is not fun to drive. programs in JAVA. Everyone who knows how to c) Quincy likes all action movies. Quincy likes the write programs in JAVA can get a high-paying job. movie Eight Men Out. Therefore, Eight Men Out is Therefore, someone in this class can get a high-paying an action movie. job.” d) All lobstermen set at least a dozen traps. Hamilton is a b) “Somebody in this class enjoys whale watching. Ev- lobsterman. Therefore, Hamilton sets at least a dozen ery person who enjoys whale watching cares about traps. ocean pollution. Therefore, there is a person in this 17. What is wrong with this argument? Let H(x) be “x is class who cares about ocean pollution.” happy.” Given the premise ∃xH(x), we conclude that c) “Each of the 93 students in this class owns a personal H(Lola). Therefore, Lola is happy. computer. Everyone who owns a personal computer can use a word processing program. Therefore, Zeke, 18. What is wrong with this argument? Let S(x, y) be “x is a student in this class, can use a word processing pro- shorter than y.” Given the premise ∃sS(s, Max), it fol- gram.” lows that S(Max, Max). Then by existential generaliza- d) “Everyone in New Jersey lives within 50 miles of the tion it follows that ∃xS(x, x), so that someone is shorter ocean. Someone in New Jersey has never seen the than himself. ocean. Therefore, someone who lives within 50 miles 19. Determine whether each of these arguments is valid. If an of the ocean has never seen the ocean.” argument is correct, what rule of inference is being used? 14. For each of these arguments, explain which rules of in- If it is not, what logical error occurs? ference are used for each step. a) If n is a real number such that n > 1, then n2 > 1. a) “Linda, a student in this class, owns a red convertible. Suppose that n2 > 1. Then n > 1. Everyone who owns a red convertible has gotten at b) If n is a real number with n > 3, then n2 > 9. least one speeding ticket. Therefore, someone in this Suppose that n2 ≤ 9. Then n ≤ 3. class has gotten a speeding ticket.” c) If n is a real number with n > 2, then n2 > 4. b) “Each of five roommates, Melissa, Aaron, Ralph, Ve- Suppose that n ≤ 2. Then n2 ≤ 4. neesha, and Keeshawn, has taken a course in discrete 20. Determine whether these are valid arguments. mathematics. Every student who has taken a course in a) If x is a positive real number, then x2 is a positive real discrete mathematics can take a course in algorithms. number. Therefore, if a2 is positive, where a is a real Therefore, all five roommates can take a course in al- number, then a is a positive real number. gorithms next year.” c) “All movies produced by John Sayles are wonder- b) If x2 ≠ 0, where x is a real number, then x ≠ 0. Let a ful. John Sayles produced a movie about coal min- be a real number with a2 ≠ 0; then a ≠ 0. ers. Therefore, there is a wonderful movie about coal 21. Which rules of inference are used to establish the miners.” conclusion of Lewis Carroll’s argument described in d) “There is someone in this class who has been to Example 26 of Section 1.4? France. Everyone who goes to France visits the 22. Which rules of inference are used to establish the Louvre. Therefore, someone in this class has visited conclusion of Lewis Carroll’s argument described in the Louvre.” Example 27 of Section 1.4? 84 1 / The Foundations: Logic and Proofs 23. Identify the error or errors in this argument that sup- David is happy” imply the conclusion “Hillary is a good posedly shows that if ∃xP(x) ∧ ∃xQ(x) is true then girl or David is happy.” ∃x(P(x) ∧ Q(x)) is true. 31. Use resolution to show that the hypotheses “It is not rain- 1. ∃xP(x) ∨ ∃xQ(x) Premise ing or Yvette has her umbrella,” “Yvette does not have 2. ∃xP(x) Simplification from (1) her umbrella or she does not get wet,” and “It is raining 3. P(c) Existential instantiation from (2) or Yvette does not get wet” imply that “Yvette does not 4. ∃xQ(x) Simplification from (1) get wet.” 5. Q(c) Existential instantiation from (4) 32. Show that the equivalence p ∧ ¬p ≡ F can be derived us- 6. P(c) ∧ Q(c) Conjunction from (3) and (5) ing resolution together with the fact that a conditional 7. ∃x(P(x) ∧ Q(x)) Existential generalization statement with a false hypothesis is true. [Hint: Let q = 24. Identify the error or errors in this argument that sup- r = F in resolution.] posedly shows that if ∀x(P(x) ∨ Q(x)) is true then 33. Use resolution to show that the compound proposition ∀xP(x) ∨ ∀xQ(x) is true. (p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q) is not satisfi- 1. ∀x(P(x) ∨ Q(x)) Premise able. 2. P(c) ∨ Q(c) Universal instantiation from (1) ∗ 34. The Logic Problem, taken from WFF’N PROOF, The 3. P(c) Simplification from (2) Game of Logic, has these two assumptions: 4. ∀xP(x) Universal generalization from (3) 1. “Logic is difficult or not many students like logic.” 5. Q(c) Simplification from (2) 2. “If mathematics is easy, then logic is not difficult.” 6. ∀xQ(x) Universal generalization from (5) By translating these assumptions into statements involv- 7. ∀x(P(x) ∨ ∀xQ(x)) Conjunction from (4) and (6) ing propositional variables and logical connectives, de- 25. Justify the rule of universal modus tollens by showing termine whether each of the following are valid conclu- that the premises ∀x(P(x) → Q(x)) and ¬Q(a) for a par- sions of these assumptions: ticular element a in the domain, imply ¬P(a). a) That mathematics is not easy, if many students like 26. Justify the rule of universal transitivity, which states logic. that if ∀x(P(x) → Q(x)) and ∀x(Q(x) → R(x)) are true, b) That not many students like logic, if mathematics is then ∀x(P(x) → R(x)) is true, where the domains of all not easy. quantifiers are the same. c) That mathematics is not easy or logic is difficult. 27. Use rules of inference to show that if ∀x(P(x) → (Q(x) ∧ d) That logic is not difficult or mathematics is not easy. S(x))) and ∀x(P(x) ∧ R(x)) are true, then ∀x(R(x) ∧ S(x)) e) That if not many students like logic, then either math- is true. ematics is not easy or logic is not difficult. 28. Use rules of inference to show that if ∀x(P(x) ∨ Q(x)) and ∗ 35. Determine whether this argument, taken from Kalish and ∀x((¬P(x) ∧ Q(x)) → R(x)) are true, then ∀x(¬R(x) → Montague [KaMo64], is valid. P(x)) is also true, where the domains of all quantifiers If Superman were able and willing to prevent evil, are the same. he would do so. If Superman were unable to pre- 29. Use rules of inference to show that if ∀x(P(x) ∨ Q(x)), vent evil, he would be impotent; if he were unwilling ∀x(¬Q(x) ∨ S(x)), ∀x(R(x) → ¬S(x)), and ∃x¬P(x) are to prevent evil, he would be malevolent. Superman true, then ∃x¬R(x) is true. does not prevent evil. If Superman exists, he is nei- 30. Use resolution to show the hypotheses “Allen is a bad ther impotent nor malevolent. Therefore, Superman boy or Hillary is a good girl” and “Allen is a good boy or does not exist. 1.7 Introduction to Proofs 1.7.1 Introduction In this section we introduce the notion of a proof and describe methods for constructing proofs. A proof is a valid argument that establishes the truth of a mathematical statement. A proof can use the hypotheses of the theorem, if any, axioms assumed to be true, and previously proven theorems. Using these ingredients and rules of inference, the final step of the proof establishes the truth of the statement being proved. In our discussion we move from formal proofs of theorems toward more informal proofs. The arguments we introduced in Section 1.6 to show that statements involving propositions and quantified statements are true were formal proofs, where all steps were supplied, and the rules for each step in the argument were given. However, formal proofs of useful theorems can  1.7 Introduction to Proofs 85 be extremely long and hard to follow. In practice, the proofs of theorems designed for human consumption are almost always informal proofs, where more than one rule of inference may be used in each step, where steps may be skipped, where the axioms being assumed and the rules of inference used are not explicitly stated. Informal proofs can often explain to humans why theorems are true, while computers are perfectly happy producing formal proofs using automated reasoning systems. The methods of proof discussed in this chapter are important not only because they are used to prove mathematical theorems, but also for their many applications to computer science. These applications include verifying that computer programs are correct, establishing that operating systems are secure, making inferences in artificial intelligence, showing that system specifica- tions are consistent, and so on. Consequently, understanding the techniques used in proofs is essential both in mathematics and in computer science. 1.7.2 Some Terminology Formally, a theorem is a statement that can be shown to be true. In mathematical writing, the term theorem is usually reserved for a statement that is considered at least somewhat important. Less important theorems sometimes are called propositions. (Theorems can also be referred to Links as facts or results.) A theorem may be the universal quantification of a conditional statement with one or more premises and a conclusion. However, it may be some other type of logical statement, as the examples later in this chapter will show. We demonstrate that a theorem is true with a proof. A proof is a valid argument that establishes the truth of a theorem. The statements used in a proof can include axioms (or postulates), which are statements we assume to be true (for example, the axioms for the real numbers, given in Appendix 1, and the axioms of plane geometry), the premises, if any, of the theorem, and previously proven theorems. Axioms may be stated using primitive terms that do not require definition, but all other terms used in theorems and their proofs must be defined. Rules of inference, together with definitions of terms, are used to draw conclusions from other assertions, tying together the steps of a proof. In practice, the final step of a proof is usually just the conclusion of the theorem. However, for clarity, we will often recap the statement of the theorem as the final step of a proof. A less important theorem that is helpful in the proof of other results is called a lemma (plural lemmas or lemmata). Complicated proofs are usually easier to understand when they are proved using a series of lemmas, where each lemma is proved individually. A corollary is a theorem that can be established directly from a theorem that has been proved. A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert. When a proof of a conjecture is found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they are not theorems. 1.7.3 Understanding How Theorems Are Stated Extra Before we introduce methods for proving theorems, we need to understand how many mathe- Examples matical theorems are stated. Many theorems assert that a property holds for all elements in a domain, such as the integers or the real numbers. Although the precise statement of such theo- rems needs to include a universal quantifier, the standard convention in mathematics is to omit it. For example, the statement “If x > y, where x and y are positive real numbers, then x2 > y2 ” really means “For all positive real numbers x and y, if x > y, then x2 > y2.” 86 1 / The Foundations: Logic and Proofs Furthermore, when theorems of this type are proved, the first step of the proof usually involves selecting a general element of the domain. Subsequent steps show that this element has the property in question. Finally, universal generalization implies that the theorem holds for all members of the domain. 1.7.4 Methods of Proving Theorems Proving mathematical theorems can be difficult. To construct proofs we need all available am- munition, including a powerful battery of different proof methods. These methods provide the Assessment overall approach and strategy of proofs. Understanding these methods is a key component of learning how to read and construct mathematical proofs. Once we have chosen a proof method, we use axioms, definitions of terms, previously proved results, and rules of inference to com- plete the proof. Note that in this book we will always assume the axioms for real numbers found in Appendix 1. We will also assume the usual axioms whenever we prove a result about ge- ometry. When you construct your own proofs, be careful not to use anything but these axioms, definitions, and previously proved results as facts! To prove a theorem of the form ∀x(P(x) → Q(x)), our goal is to show that P(c) → Q(c) is true, where c is an arbitrary element of the domain, and then apply universal generalization. In this proof, we need to show that a conditional statement is true. Because of this, we now focus on methods that show that conditional statements are true. Recall that p → q is true unless p is true but q is false. Note that to prove the statement p → q, we need only show that q is true if p is true. The following discussion will give the most common techniques for proving conditional statements. Later we will discuss methods for proving other types of statements. In this section, and in Section 1.8, we will develop a large arsenal of proof techniques that can be used to prove a wide variety of theorems. When you read proofs, you will often find the words “obviously” or “clearly.” These words indicate that steps have been omitted that the author expects the reader to be able to fill in. Unfortunately, this assumption is often not warranted and readers are not at all sure how to fill in the gaps. We will assiduously try to avoid using these words and try not to omit too many steps. However, if we included all steps in proofs, our proofs would often be excruciatingly long. 1.7.5 Direct Proofs A direct proof of a conditional statement p → q is constructed when the first step is the as- sumption that p is true; subsequent steps are constructed using rules of inference, with the final step showing that q must also be true. A direct proof shows that a conditional statement p → q is true by showing that if p is true, then q must also be true, so that the combination p true and q false never occurs. In a direct proof, we assume that p is true and use axioms, definitions, and previously proven theorems, together with rules of inference, to show that q must also be true. You will find that direct proofs of many results are quite straightforward. Starting with the hy- pothesis and leading to the conclusion, the way forward is essentially dictated by the premises available at that step. However, direct proofs sometimes require particular insights and can be quite tricky. The first direct proofs we present here are quite straightforward; later in the text you will see some that require some insight. We will provide examples of several different direct proofs. Before we give the first example, we need to define some terminology. Definition 1 The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an integer k such that n = 2k + 1. (Note that every integer is either even or odd, and no integer is both even and odd.) Two integers have the same parity when both are even or both are odd; they have opposite parity when one is even and the other is odd.  1.7 Introduction to Proofs 87 EXAMPLE 1 Give a direct proof of the theorem “If n is an odd integer, then n2 is odd.” Extra Examples Solution: Note that this theorem states ∀nP((n) → Q(n)), where P(n) is “n is an odd integer” and Q(n) is “n2 is odd.” As we have said, we will follow the usual convention in mathematical proofs by showing that P(n) implies Q(n), and not explicitly using universal instantiation. To begin a direct proof of this theorem, we assume that the hypothesis of this conditional statement is true, namely, we assume that n is odd. By the definition of an odd integer, it follows that n = 2k + 1, where k is some integer. We want to show that n2 is also odd. We can square both sides of the equation n = 2k + 1 to obtain a new equation that expresses n2. When we do this, we find that n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1. By the definition of an odd integer, we can conclude that n2 is an odd integer (it is one more than twice an integer). Consequently, we have proved that if n is an odd integer, then n2 is an odd integer. ◂ EXAMPLE 2 Give a direct proof that if m and n are both perfect squares, then nm is also a perfect square. (An integer a is a perfect square if there is an integer b such that a = b2.) Solution: To produce a direct proof of this theorem, we assume that the hypothesis of this con- ditional statement is true, namely, we assume that m and n are both perfect squares. By the definition of a perfect square, it follows that there are integers s and t such that m = s2 and n = t2. The goal of the proof is to show that mn must also be a perfect square when m and n are; looking ahead we see how we can show this by substituting s2 for m and t2 for n into mn. This tells us that mn = s2 t2. Hence, mn = s2 t2 = (ss)(tt) = (st)(st) = (st)2 , using commutativity and associativity of multiplication. By the definition of perfect square, it follows that mn is also a perfect square, because it is the square of st, which is an integer. We have proved that if m and n are both perfect squares, then mn is also a perfect square. ◂ 1.7.6 Proof by Contraposition Direct proofs lead from the premises of a theorem to the conclusion. They begin with the premises, continue with a sequence of deductions, and end with the conclusion. However, we will see that attempts at direct proofs often reach dead ends. We need other methods of prov- ing theorems of the form ∀x(P(x) → Q(x)). Proofs of theorems of this type that are not direct proofs, that is, that do not start with the premises and end with the conclusion, are called indirect proofs. An extremely useful type of indirect proof is known as proof by contraposition. Proofs by contraposition make use of the fact that the conditional statement p → q is equivalent to its contrapositive, ¬q → ¬p. This means that the conditional statement p → q can be proved by showing that its contrapositive, ¬q → ¬p, is true. In a proof by contraposition of p → q, we take ¬q as a premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that ¬p must follow. We will illustrate proof by contraposition with two examples. These examples show that proof by contraposition can succeed when we cannot easily find a direct proof. EXAMPLE 3 Prove that if n is an integer and 3n + 2 is odd, then n is odd. Extra Examples Solution: We first attempt a direct proof. To construct a direct proof, we first assume that 3n + 2 is an odd integer. From the definition of an odd integer, we know that 3n + 2 = 2k + 1 for some integer k. Can we use this fact to show that n is odd? We see that 3n + 1 = 2k, but there does not seem to be any direct way to conclude that n is odd. Because our attempt at a direct proof failed, we next try a proof by contraposition. 88 1 / The Foundations: Logic and Proofs The first step in a proof by contraposition is to assume that the conclusion of the conditional statement “If 3n + 2 is odd, then n is odd” is false; namely, assume that n is even. Then, by the definition of an even integer, n = 2k for some integer k. Substituting 2k for n, we find that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). This tells us that 3n + 2 is even (because it is a multiple of 2), and therefore not odd. This is the negation of the premise of the theorem. Because the negation of the conclusion of the conditional statement implies that the hypothesis is false, the original conditional statement is true. Our proof by contraposition succeeded; we have proved the theorem “If 3n + 2 is odd, then n is odd.” ◂ √ √ EXAMPLE 4 Prove that if n = ab, where a and b are positive integers, then a ≤ n or b ≤ n. √ √ Solution: Because there is no obvious way of showing that a ≤ n or b ≤ n directly from the equation n = ab, where a and b are positive integers, we attempt a proof by contraposition. The first step in a proof by contraposition is to assume that the conclusion √ of the conditional √ statement “If n = ab, where a and b are positive integers, then a ≤ n or b ≤ n” is false. That √ √ is, we assume that the statement (a ≤ n) ∨ (b ≤ n) is false. Using the meaning of disjunction √ √ together with De Morgan’s law, we see that this implies that both a ≤ n and b ≤ n are false. √ √ This implies that a > n and b > n. We can multiply these inequalities together (using the √ √ fact that if 0 < s < t and 0 < u < v, then su < tv) to obtain ab > n ⋅ n = n. This shows that ab ≠ n, which contradicts the statement n = ab. Because the negation of the conclusion of the conditional statement implies that the hy- pothesis is false, the original conditional statement is true. Our proof by contraposition √suc- ceeded; we have proved that if n = ab, where a and b are positive integers, then a ≤ n or √ b ≤ n. ◂ VACUOUS AND TRIVIAL PROOFS We can quickly prove that a conditional statement p → q is true when we know that p is false, because p → q must be true when p is false. Con- sequently, if we can show that p is false, then we have a proof, called a vacuous proof, of the conditional statement p → q. Vacuous proofs are often used to establish special cases of theo- rems that state that a conditional statement is true for all positive integers [i.e., a theorem of the kind ∀nP(n), where P(n) is a propositional function]. Proof techniques for theorems of this kind will be discussed in Section 5.1. EXAMPLE 5 Show that the proposition P(0) is true, where P(n) is “If n > 1, then n2 > n” and the domain consists of all integers. Solution: Note that P(0) is “If 0 > 1, then 02 > 0.” We can show P(0) using a vacuous proof. Indeed, the hypothesis 0 > 1 is false. This tells us that P(0) is automatically true. ◂ Remark: The fact that the conclusion of this conditional statement, 02 > 0, is false is irrelevant to the truth value of the conditional statement, because a conditional statement with a false hypothesis is guaranteed to be true. EXAMPLE 6 Prove that if n is an integer with 10 ≤ n ≤ 15 which is a perfect square, then n is also a perfect cube. Solution: Note that there are no perfect squares n with 10 ≤ n ≤ 15, because 32 = 9 and 42 = 16. Hence, the statement that n is an integer with 10 ≤ n ≤ 15 which is a perfect square is false for all integers n. Consequently, the statement to be proved is true for all integers n. ◂  1.7 Introduction to Proofs 89 We can also quickly prove a conditional statement p → q if we know that the conclusion q is true. By showing that q is true, it follows that p → q must also be true. A proof of p → q that uses the fact that q is true is called a trivial proof. Trivial proofs are often important when special cases of theorems are proved (see the discussion of proof by cases in Section 1.8) and in mathematical induction, which is a proof technique discussed in Section 5.1. EXAMPLE 7 Let P(n) be “If a and b are positive integers with a ≥ b, then an ≥ bn ,” where the domain consists of all nonnegative integers. Show that P(0) is true. Solution: The proposition P(0) is “If a ≥ b, then a0 ≥ b0.” Because a0 = b0 = 1, the conclusion of the conditional statement “If a ≥ b, then a0 ≥ b0 ” is true. Hence, this conditional statement, which is P(0), is true. This is an example of a trivial proof. Note that the hypothesis, which is the statement “a ≥ b,” was not needed in this proof. ◂ A LITTLE PROOF STRATEGY We have described two important approaches for proving theorems of the form ∀x(P(x) → Q(x)): direct proof and proof by contraposition. We have also given examples that show how each is used. However, when you are presented with a theorem of the form ∀x(P(x) → Q(x)), which method should you use to attempt to prove it? We will provide a few rules of thumb here; in Section 1.8 we will discuss proof strategy at greater length. When you want to prove a statement of the form ∀x(P(x) → Q(x)), first evaluate whether a direct proof looks promising. Begin by expanding the definitions in the hypotheses. Start to reason using these hypotheses, together with axioms and available theorems. If a direct proof does not seem to go anywhere, for instance when there is no clear way to use hypotheses as in Examples 3 and 4 to reach the conclusion, try the same thing with a proof by contraposition. (Hypotheses such as x is irrational or x ≠ 0 that are difficult to reason from are a clue that an indirect proof might be your best best.) Recall that in a proof by contraposition you assume that the conclusion of the conditional statement is false and use a direct proof to show this implies that the hypothesis must be false. Often, you will find that a proof by contraposition is easily constructed from the negation of the conclusion. We illustrate this strategy in Examples 7 and 8. In each example, note how straightforward a proof by contraposition is, while there is no clear way to provide a direct proof. Before we present our next example, we need a definition. Definition 2 The real number r is rational if there exist integers p and q with q ≠ 0 such that r = p∕q. A real number that is not rational is called irrational. EXAMPLE 8 Prove that the sum of two rational numbers is rational. (Note that if we include the implicit quantifiers here, the theorem we want to prove is “For every real number r and every real number Extra s, if r and s are rational numbers, then r + s is rational.) Examples Solution: We first attempt a direct proof. To begin, suppose that r and s are rational numbers. From the definition of a rational number, it follows that there are integers p and q, with q ≠ 0, such that r = p∕q, and integers t and u, with u ≠ 0, such that s = t∕u. Can we use this informa- tion to show that r + s is rational? That is, can we find integers v and w such that r + s = v∕w and w ≠ 0? With the goal of finding these integers v and w, we add r = p∕q and s = t∕u, using qu as the common denominator. We find that p t pu + qt r+s= + =. q u qu 90 1 / The Foundations: Logic and Proofs Because q ≠ 0 and u ≠ 0, it follows that qu ≠ 0. Consequently, we have expressed r + s as the ratio of two integers, v = pu + qt and w = qu, where w ≠ 0. This means that r + s is rational. We have proved that the sum of two rational numbers is rational; our attempt to find a direct proof succeeded. ◂ EXAMPLE 9 Prove that if n is an integer and n2 is odd, then n is odd. Solution: We first attempt a direct proof. Suppose that n is an integer and n2 is odd. From the definition of an odd integer, there exists an integer k such that n2 = 2k + 1. Can we use this information to show that n is odd? There seems to be √no obvious approach to show that n is odd because solving for n produces the equation n = ± 2k + 1, which is not terribly useful. Because this attempt to use a direct proof did not bear fruit, we next attempt a proof by contraposition. We take as our hypothesis the statement that n is not odd. Because every integer is odd or even, this means that n is even. This implies that there exists an integer k such that n = 2k. To prove the theorem, we need to show that this hypothesis implies the conclusion that n2 is not odd, that is, that n2 is even. Can we use the equation n = 2k to achieve this? By squaring both sides of this equation, we obtain n2 = 4k2 = 2(2k2 ), which implies that n2 is also even because n2 = 2t, where t = 2k2. We have proved that if n is an integer and n2 is odd, then n is odd. Our attempt to find a proof by contraposition succeeded. ◂ 1.7.7 Proofs by Contradiction Suppose we want to prove that a statement p is true. Furthermore, suppose that we can find a contradiction q such that ¬p → q is true. Because q is false, but ¬p → q is true, we can conclude that ¬p is false, which means that p is true. How can we find a contradiction q that might help us prove that p is true in this way? Because the statement r ∧ ¬r is a contradiction whenever r is a proposition, we can prove that p is true if we can show that ¬p → (r ∧ ¬r) is true for some proposition r. Proofs of this type are called proofs by contradiction. Because a proof by contradiction does not prove a result directly, it is another type of indirect proof. We provide three examples of proof by contradiction. The first is an example of an application of the pigeonhole principle, a combinatorial technique that we will cover in depth in Section 6.2. EXAMPLE 10 Show that at least four of any 22 days must fall on the same day of the week. Extra Solution: Let p be the proposition “At least four of 22 chosen days fall on the same day of the Examples week.” Suppose that ¬p is true. This means that at most three of the 22 days fall on the same day of the week. Because there are seven days of the week, this implies that at most 21 days could have been chosen, as for each of the days of the week, at most three of the chosen days could fall on that day. This contradicts the premise that we have 22 days under consideration. That is, if r is the statement that 22 days are chosen, then we have shown that ¬p → (r ∧ ¬r). Consequently, we know that p is true. We have proved that at least four of 22 chosen days fall on the same day of the week. ◂ √ EXAMPLE 11 Prove that 2 is irrational by giving a proof by contradiction. √ Solution: Let p be the proposition “ 2 is irrational.” To start a proof by√contradiction, we sup- pose that √ ¬p is true. Note that ¬p is the statement “It is not the case that 2 is irrational,” which says that 2 is rational. We will show that assuming that ¬p is true leads to a contradiction.  1.7 Introduction to Proofs 91 √ √ If 2 is rational, there exist integers a and b with 2 = a∕b, where b ≠ 0 and a and b have no common factors (so that the fraction a∕b is in lowest terms). (Here, √ we are using the fact that every rational number can be written in lowest terms.) Because 2 = a∕b, when both sides of this equation are squared, it follows that a2 2=. b2 Hence, 2b2 = a2. By the definition of an even integer it follows that a2 is even. We next use the fact that if a2 is even, a must also be even, which follows by Exercise 18. Furthermore, because a is even, by the definition of an even integer, a = 2c for some integer c. Thus, 2b2 = 4c2. Dividing both sides of this equation by 2 gives b2 = 2c2. By the definition of even, this means that b2 is even. Again using the fact that if the square of an integer is even, then the integer itself must be even, we conclude that b must √ be even as well. We have now shown that the assumption of ¬p leads to the equation 2 = a∕b, where a and b have no common factors, √ but both a and b are even, that is, 2 divides both a and b. Note that the statement that 2 = a∕b, where a and b have no common factors, means, in particular, that 2 does not divide both a and b. Because our assumption of ¬p leads to the contradiction that 2 divides √both a and b and 2 does not divide both a and √ b, ¬p must be false. That is, the statement p, “ 2 is irrational,” is true. We have proved that 2 is irrational. ◂ Proof by contradiction can be used to prove conditional statements. In such proofs, we first assume the negation of the conclusion. We then use the premises of the theorem and the negation of the conclusion to arrive at a contradiction. (The reason that such proofs are valid rests on the logical equivalence of p → q and (p ∧ ¬q) → F. To see that these statements are equivalent, simply note that each is false in exactly one case, namely, when p is true and q is false.) Note that we can rewrite a proof by contraposition of a conditional statement as a proof by contradiction. In a proof of p → q by contraposition, we assume that ¬q is true. We then show that ¬p must also be true. To rewrite a proof by contraposition of p → q as a proof by contradiction, we suppose that both p and ¬q are true. Then, we use the steps from the proof of ¬q → ¬p to show that ¬p is true. This leads to the contradiction p ∧ ¬p, completing the proof. Example 11 illustrates how a proof by contraposition of a conditional statement can be rewritten as a proof by contradiction. EXAMPLE 12 Give a proof by contradiction of the theorem “If 3n + 2 is odd, then n is odd.” Solution: Let p be “3n + 2 is odd” and q be “n is odd.” To construct a proof by contradiction, assume that both p and ¬q are true. That is, assume that 3n + 2 is odd and that n is not odd. Because n is not odd, we know that it is even. Because n is even, there is an integer k such that n = 2k. This implies that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). Because 3n + 2 is 2t, where t = 3k + 1, 3n + 2 is even. Note that the statement “3n + 2 is even” is equivalent to the statement ¬p, because an integer is even if and only if it is not odd. Because both p and ¬p are 92 1 / The Foundations: Logic and Proofs true, we have a contradiction. This completes the proof by contradiction, proving that if 3n + 2 is odd, then n is odd. ◂ Note that we can also prove by contradiction that p → q is true by assuming that p and ¬q are true, and showing that q must be also be true. This implies that ¬q and q are both true, a contradiction. This observation tells us that we can turn a direct proof into a proof by contra- diction. PROOFS OF EQUIVALENCE To prove a theorem that is a biconditional statement, that is, a statement of the form p ↔ q, we show that p → q and q → p are both true. The validity of this approach is based on the tautology (p ↔ q) ↔ (p → q) ∧ (q → p). EXAMPLE 13 Prove the theorem “If n is an integer, then n is odd if and only if n2 is odd.” Extra Examples Solution: This theorem has the form “p if and only if q,” where p is “n is odd” and q is “n2 is odd.” (As usual, we do not explicitly deal with the universal quantification.) To prove this theorem, we need to show that p → q and q → p are true. We have already shown (in Example 1) that p → q is true and (in Example 8) that q → p is true. Because we have shown that both p → q and q → p are true, we have shown that the theorem is true. ◂ Sometimes a theorem states that several propositions are equivalent. Such a theorem states that propositions p1 , p2 , p3 , … , pn are equivalent. This can be written as p1 ↔ p2 ↔ ⋯ ↔ pn , which states that all n propositions have the same truth values, and consequently, that for all i and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n, pi and pj are equivalent. One way to prove these are mutually equivalent is to use the tautology p1 ↔ p2 ↔ ⋯ ↔ pn ↔ (p1 → p2 ) ∧ (p2 → p3 ) ∧ ⋯ ∧ (pn → p1 ). This shows that if the n conditional statements p1 → p2 , p2 → p3 , … , pn → p1 can be shown to be true, then the propositions p1 , p2 , … , pn are all equivalent. This is much more efficient than proving that pi → pj for all i ≠ j with 1 ≤ i ≤ n and 1 ≤ j ≤ n. (Note that there are n2 − n such conditional statements.) When we prove that a group of statements are equivalent, we can establish any chain of conditional statements we choose as long as it is possible to work through the chain to go from any one of these statements to any other statement. For example, we can show that p1 , p2 , and p3 are equivalent by showing that p1 → p3 , p3 → p2 , and p2 → p1. EXAMPLE 14 Show that these statements about the integer n are equivalent: p1 : n is even. p2 : n − 1 is odd. p3 : n2 is even. Solution: We will show that these three statements are equivalent by showing that the condi- tional statements p1 → p2 , p2 → p3 , and p3 → p1 are true.  1.7 Introduction to Proofs 93 We use a direct proof to show that p1 → p2. Suppose that n is even. Then n = 2k for some integer k. Consequently, n − 1 = 2k − 1 = 2(k − 1) + 1. This means that n − 1 is odd because it is of the form 2m + 1, where m is the integer k − 1. We also use a direct proof to show that p2 → p3. Now suppose n − 1 is odd. Then n − 1 = 2k + 1 for some integer k. Hence, n = 2k + 2 so that n2 = (2k + 2)2 = 4k2 + 8k + 4 = 2(2k2 + 4k + 2). This means that n2 is twice the integer 2k2 + 4k + 2, and hence is even. To prove p3 → p1 , we use a proof by contraposition. That is, we prove that if n is not even, then n2 is not even. This is the same as proving that if n is odd, then n2 is odd, which we have already done in Example 1. This completes the proof. ◂ COUNTEREXAMPLES In Section 1.4 we stated that to show that a statement of the form ∀xP(x) is false, we need only find a counterexample, that is, an example x for which P(x) is false. When presented with a statement of the form ∀xP(x), which we believe to be false or which has resisted all proof attempts, we look for a counterexample. We illustrate the use of counterexamples in Example 15. EXAMPLE 15 Show that the statement “Every positive integer is the sum of the squares of two integers” is false. Extra Examples Solution: To show that this statement is false, we look for a counterexample, which is a par- ticular integer that is not the sum of the squares of two integers. It does not take long to find a counterexample, because 3 cannot be written as the sum of the squares of two integers. To show this is the case, note that the only perfect squares not exceeding 3 are 02 = 0 and 12 = 1. Furthermore, there is no way to get 3 as the sum of two terms each of which is 0 or 1. Conse- quently, we have shown that “Every positive integer is the sum of the squares of two integers” is false. ◂ 1.7.8 Mistakes in Proofs There are many common errors made in constructing mathematical proofs. We will briefly de- scribe some of these here. Among the most common errors are mistakes in arithmetic and basic algebra. Even professional mathematicians make such errors, especially when working with complicated formulae. Whenever you use such computations you should check them as care- fully as possible. (You should also review any troublesome aspects of basic algebra, especially before you study Section 5.1.) Links Each step of a mathematical proof needs to be correct and the conclusion needs to follow logically from the steps that precede it. Many mistakes result from the introduction of steps that do not logically follow from those that precede it. This is illustrated in Examples 16–18. EXAMPLE 16 What is wrong with this famous supposed “proof” that 1 = 2? “Proof”: We use these steps, where a and b are two equal positive integers. Step Reason 1. a = b Given 2. a2 = ab Multiply both sides of (1) by a 3. a2 − b2 = ab − b2 Subtract b2 from both sides of (2) 4. (a − b)(a + b) = b(a − b) Factor both sides of (3) 5. a + b = b Divide both sides of (4) by a − b 6. 2b = b Replace a by b in (5) because a = b and simplify 7. 2 = 1 Divide both sides of (6) by b 94 1 / The Foundations: Logic and Proofs Solution: Every step is valid except for step 5, where we divided both sides by a − b. The error is that a − b equals zero; division of both sides of an equation by the same quantity is valid as long as this quantity is not zero. ◂ EXAMPLE 17 What is wrong with this “proof”? “Theorem”: If n2 is positive, then n is positive. “Proof ”: Suppose that n2 is positive. Because the conditional statement “If n is positive, then n2 is positive” is true, we can conclude that n is positive. Solution: Let P(n) be “n is positive” and Q(n) be “n2 is positive.” Then our hypothesis is Q(n). The statement “If n is positive, then n2 is positive” is the statement ∀n(P(n) → Q(n)). From the hypothesis Q(n) and the statement ∀n(P(n) → Q(n)) we cannot conclude P(n), because we are not using a valid rule of inference. Instead, this is an example of the fallacy of affirming the conclusion. A counterexample is supplied by n = −1 for which n2 = 1 is positive, but n is negative. ◂ EXAMPLE 18 What is wrong with this “proof”? “Theorem”: If n is not positive, then n2 is not positive. (This is the contrapositive of the “theorem” in Example 17.) “Proof ”: Suppose that n is not positive. Because the conditional statement “If n is positive, then n2 is positive” is true, we can conclude that n2 is not positive. Solution: Let P(n) and Q(n) be as in the solution of Example 17. Then our hypothesis is ¬P(n) and the statement “If n is positive, then n2 is positive” is the statement ∀n(P(n) → Q(n)). From the hypothesis ¬P(n) and the statement ∀n(P(n) → Q(n)) we cannot conclude ¬Q(n), because we are not using a valid rule of inference. Instead, this is an example of the fallacy of denying the hypothesis. A counterexample is supplied by n = −1, as in Example 17. ◂ Finally, we briefly discuss a particularly nasty type of error. Many incorrect arguments are based on a fallacy called begging the question. This fallacy occurs when one or more steps of a proof are based on the truth of the statement being proved. In other words, this fallacy arises when a statement is proved using itself, or a statement equivalent to it. That is why this fallacy is also called circular reasoning. EXAMPLE 19 Is the following argument correct? It supposedly shows that n is an even integer whenever n2 is an even integer. Suppose that n2 is even. Then n2 = 2k for some integer k. Let n = 2l for some integer l. This shows that n is even. Solution: This argument is incorrect. The statement “let n = 2l for some integer l” occurs in the proof. No argument has been given to show that n can be written as 2l for some integer l. This is circular reasoning because this statement is equivalent to the statement being proved, namely, “n is even.” The result itself is correct; only the method of proof is wrong. ◂  1.7 Introduction to Proofs 95 Making mistakes in proofs is part of the learning process. When you make a mistake that someone else finds, you should carefully analyze where you went wrong and make sure that you do not make the same mistake again. Even professional mathematicians make mistakes in proofs. More than a few incorrect proofs of important results have fooled people for many years before subtle errors in them were found. 1.7.9 Just a Beginning We have now developed a basic arsenal of proof methods. In the next section we will introduce other important proof methods. We will also introduce several important proof techniques in Chapter 5, including mathematical induction, which can be used to prove results that hold for all positive integers. In Chapter 6 we will introduce the notion of combinatorial proofs. In this section we introduced several methods for proving theorems of the form ∀x(P(x) → Q(x)), including direct proofs and proofs by contraposition. There are many theorems of this type whose proofs are easy to construct by directly working through the hypotheses and definitions of the terms of the theorem. However, it is often difficult to prove a theorem without resorting to a clever use of a proof by contraposition or a proof by contradiction, or some other proof technique. In Section 1.8 we will address proof strategy. We will describe various approaches that can be used to find proofs when straightforward approaches do not work. Constructing proofs is an art that can be learned only through experience, including writing proofs, having your proofs critiqued, and reading and analyzing other proofs. Exercises 1. Use a direct proof to show that the sum of two odd inte- 14. Prove that if x is rational and x ≠ 0, then 1∕x is rational. √ gers is even. 15. Prove that if x is an irrational number and x > 0, then x 2. Use a direct proof to show that the sum of two even inte- is also irrational. gers is even. 16. Prove that if x, y, and z are integers and x + y + z is odd, 3. Show that the square of an even number is an even num- then at least one of x, y, and z is odd. ber using a direct proof. 17. Use a proof by contraposition to show that if x + y ≥ 2, 4. Show that the additive inverse, or negative, of an even where x and y are real numbers, then x ≥ 1 or y ≥ 1. number is an even number using a direct proof. 18. Prove that if m and n are integers and mn is even, then m is even or n is even. 5. Prove that if m + n and n + p are even integers, where 19. Show that if n is an integer and n3 + 5 is odd, then n is m, n, and p are integers, then m + p is even. What kind of even using proof did you use? a) a proof by contraposition. 6. Use a direct proof to show that the product of two odd b) a proof by contradiction. numbers is odd. 20. Prove that if n is an integer and 3n + 2 is even, then n is 7. Use a direct proof to show that every odd integer is the even using difference of two squares. [Hint: Find the difference of a) a proof by contraposition. the squares of k + 1 and k where k is a positive integer.] b) a proof by contradiction. 8. Prove that if n is a perfect square, then n + 2 is not a per- 21. Prove the proposition P(0), where P(n) is the proposition fect square. “If n is a positive integer greater than 1, then n2 > n.” 9. Use a proof by contradiction to prove that the sum of an What kind of proof did you use? irrational number and a rational number is irrational. 22. Prove the proposition P(1), where P(n) is the proposi- 10. Use a direct proof to show that the product of two rational tion “If n is a positive integer, then n2 ≥ n.” What kind of numbers is rational. proof did you use? 23. Let P(n) be the proposition “If a and b are positive real 11. Prove or disprove that the product of two irrational num- numbers, then (a + b)n ≥ an + bn.” Prove that P(1) is bers is irrational. true. What kind of proof did you use? 12. Prove or disprove that the product of a nonzero rational 24. Show that if you pick three socks from a drawer contain- number and an irrational number is irrational. ing just blue socks and black socks, you must get either a 13. Prove that if x is irrational, then 1∕x is irrational. pair of blue socks or a pair of black socks. 96 1 / The Foundations: Logic and Proofs 25. Show that at least ten of any 64 days chosen must fall on (3) x2 − 1 = 0, obtained by subtracting x2 from both the same day of the week. sides of (2); (4) (x − 1)(x + 1) = 0, obtained by factor- 26. Show that at least three of any 25 days chosen must fall ing the left-hand side of x2 − 1; (5) x = 1 or x = −1, in the same month of the year. which follows because ab = 0 implies that a = 0 or b = 0. √ 27. Use a proof by contradiction to show that there is no ra- tional number r for which r3 + r + 1 = 0. [Hint: Assume 37. Are these steps for√finding the solutions of x + 3 = that r = a∕b is a root, where a and b are integers and a∕b 3 − x correct? (1) x + 3 = 3 − x is given; (2) x + 3 = is in lowest terms. Obtain an equation involving integers x2 − 6x + 9, obtained by squaring both sides of (1); (3) by multiplying by b3. Then look at whether a and b are 0 = x2 − 7x + 6, obtained by subtracting x + 3 from both each odd or even.] sides of (2); (4) 0 = (x − 1)(x − 6), obtained by factoring 28. Prove that if n is a positive integer, then n is even if and the right-hand side of (3); (5) x = 1 or x = 6, which fol- only if 7n + 4 is even. lows from (4) because ab = 0 implies that a = 0 or b = 0. 29. Prove that if n is a positive integer, then n is odd if and 38. Show that the propositions p1 , p2 , p3 , and p4 can be shown only if 5n + 6 is odd. to be equivalent by showing that p1 ↔ p4 , p2 ↔ p3 , and p1 ↔ p3. 30. Prove that m2 = n2 if and only if m = n or m = −n. 39. Show that the propositions p1 , p2 , p3 , p4 , and p5 can 31. Prove or disprove that if m and n are integers such that be shown to be equivalent by proving that the condi- mn = 1, then either m = 1 and n = 1, or else m = −1 and tional statements p1 → p4 , p3 → p1 , p4 → p2 , p2 → p5 , n = −1. and p5 → p3 are true. 32. Show that these three statements are equivalent, where a 40. Find a counterexample to the statement that every posi- and b are real numbers: (i) a is less than b, (ii) the average tive integer can be written as the sum of the squares of of a and b is greater than a, and (iii) the average of a and three integers. b is less than b. 41. Prove that at least one of the real numbers a1 , a2 , … , an 33. Show that these statements about the integer x are is greater than or equal to the average of these numbers. equivalent: (i) 3x + 2 is even, (ii) x + 5 is odd, (iii) x2 What kind of proof did you use? is even. 42. Use Exercise 41 to show that if the first 10 positive inte- 34. Show that these statements about the real number x are gers are placed around a circle, in any order, there exist equivalent: (i) x is rational, (ii) x∕2 is rational, (iii) 3x − 1 three integers in consecutive locations around the circle is rational. that have a sum greater than or equal to 17. 35. Show that these statements about the real number x are 43. Prove that if n is an integer, these four statements are equivalent: (i) x is irrational, (ii) 3x + 2 is irrational, equivalent: (i) n is even, (ii) n + 1 is odd, (iii) 3n + 1 is (iii) x∕2 is irrational. odd, (iv) 3n is even. 36. Is this √ reasoning for finding the√solutions of the equa- 44. Prove that these four statements about the integer n are tion 2x2 − 1 = x correct? (1) 2x2 − 1 = x is given; equivalent: (i) n2 is odd, (ii) 1 − n is even, (iii) n3 is odd, (2) 2x2 − 1 = x2 , obtained by squaring both sides of (1); (iv) n2 + 1 is even. 1.8 Proof Methods and Strategy 1.8.1 Introduction Assessment In Section 1.7 we introduced many methods of proof and illustrated how each method can be used. In this section we continue this effort. We will introduce several other commonly used proof methods, including the method of proving a theorem by considering different cases separately. We will also discuss proofs where we prove the existence of objects with desired properties. In Section 1.7 we briefly discussed the strategy behind constructing proofs. This strategy includes selecting a proof method and then successfully constructing an argument step by step, based on this method. In this section, after we have developed a versatile arsenal of proof meth- ods, we will study some aspects of the art and science of proofs. We will provide advice on how to find a proof of a theorem. We will describe some tricks of the trade, including how proofs can be found by working backward and by adapting existing proofs.  1.8 Proof Methods and Strategy 97 When mathematicians work, they formulate conjectures and attempt to prove or disprove them. We will briefly describe this process here by proving results about tiling checkerboards with dominoes and other types of pieces. Looking at tilings of this kind, we will be able to quickly formulate conjectures and prove theorems without first developing a theory. We will conclude the section by discussing the role of open questions. In particular, we will discuss some interesting problems either that have been solved after remaining open for hundreds of years or that still remain open. 1.8.2 Exhaustive Proof and Proof by Cases Sometimes we cannot prove a theorem using a single argument that holds for all possible cases. We now introduce a method that can be used to prove a theorem by considering different cases separately. This method is based on a rule of inference that we will now introduce. To prove a conditional statement of the form (p1 ∨ p2 ∨ ⋯ ∨ pn ) → q the tautology [(p1 ∨ p2 ∨ ⋯ ∨ pn ) → q] ↔ [(p1 → q) ∧ (p2 → q) ∧ ⋯ ∧ (pn → q)] can be used as a rule of inference. This shows that the original conditional statement with a hypothesis made up of a disjunction of the propositions p1 , p2 , … , pn can be proved by proving each of the n conditional statements pi → q, i = 1, 2, … , n, individually. Such an argument is called a proof by cases. Sometimes to prove that a conditional statement p → q is true, it is convenient to use a disjunction p1 ∨ p2 ∨ ⋯ ∨ pn instead of p as the hypothesis of the conditional statement, where p and p1 ∨ p2 ∨ ⋯ ∨ pn are equivalent. EXHAUSTIVE PROOF Some theorems can be proved by examining a relatively small num- ber of examples. Such proofs are called exhaustive proofs, or proofs by exhaustion because these proofs proceed by exhausting all possibilities. An exhaustive proof is a special type of proof by cases where each case involves checking a single example. We now provide some illustrations of exhaustive proofs. EXAMPLE 1 Prove that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4. Extra Solution: We use a proof by exhaustion. We only need verify the inequality (n + 1)3 ≥ 3n when Examples n = 1, 2, 3, and 4. For n = 1, we have (n + 1)3 = 23 = 8 and 3n = 31 = 3; for n = 2, we have (n + 1)3 = 33 = 27 and 3n = 32 = 9; for n = 3, we have (n + 1)3 = 43 = 64 and 3n = 33 = 27; and for n = 4, we have (n + 1)3 = 53 = 125 and 3n = 34 = 81. In each of these four cases, we see that (n + 1)3 ≥ 3n. We have used the method of exhaustion to prove that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4. ◂ EXAMPLE 2 Prove that the only consecutive positive integers not exceeding 100 that are perfect powers are 8 and 9. (An integer n is a perfect power if it equals ma , where m is an integer and a is an integer greater than 1.) Solution: We use a proof by exhaustion. In particular, we can prove this fact by examining positive integers n not exceeding 100, first checking whether n is a perfect power, and if it is, checking whether n + 1 is also a perfect power. A quicker way to do this is simply to look at all perfect powers not exceeding 100 and checking whether the next largest integer is also a perfect power. The squares of positive integers not exceeding 100 are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 98 1 / The Foundations: Logic and Proofs 100. The cubes of positive integers not exceeding 100 are 1, 8, 27, and 64. The fourth powers of positive integers not exceeding 100 are 1, 16, and 81. The fifth powers of positive integers not exceeding 100 are 1 and 32. The sixth powers of positive integers not exceeding 100 are 1 and 64. There are no powers of positive integers higher than the sixth power not exceeding 100, other than 1. Looking at this list of perfect powers not exceeding 100, we see that n = 8 is the only perfect power n for which n + 1 is also a perfect power. That is, 23 = 8 and 32 = 9 are the only two consecutive perfect powers not exceeding 100. ◂ Proofs by exhaustion can tire out people and People can carry out exhaustive proofs when it is necessary to check o