BookOfProof bomba, Provas de Matemática

Baixe BookOfProof bomba e outras Provas em PDF para Matemática, somente na Docsity! Book of Proof Richard Hammack Virginia Commonwealth University Richard Hammack (publisher) Department of Mathematics & Applied Mathematics P.O. Box 842014 Virginia Commonwealth University Richmond, Virginia, 23284 Book of Proof Edition 2.2 © 2013 by Richard Hammack This work is licensed under the Creative Commons Attribution-No Derivative Works 3.0 License Typeset in 11pt TEX Gyre Schola using PDFLATEX v II How to Prove Conditional Statements 4. Direct Proof 87 4.1. Theorems 87 4.2. Definitions 89 4.3. Direct Proof 92 4.4. Using Cases 98 4.5. Treating Similar Cases 99 5. Contrapositive Proof 102 5.1. Contrapositive Proof 102 5.2. Congruence of Integers 105 5.3. Mathematical Writing 107 6. Proof by Contradiction 111 6.1. Proving Statements with Contradiction 112 6.2. Proving Conditional Statements by Contradiction 115 6.3. Combining Techniques 116 6.4. Some Words of Advice 117 III More on Proof 7. Proving Non-Conditional Statements 121 7.1. If-and-Only-If Proof 121 7.2. Equivalent Statements 123 7.3. Existence Proofs; Existence and Uniqueness Proofs 124 7.4. Constructive Versus Non-Constructive Proofs 128 8. Proofs Involving Sets 131 8.1. How to Prove a ∈ A 131 8.2. How to Prove A ⊆ B 133 8.3. How to Prove A = B 136 8.4. Examples: Perfect Numbers 139 9. Disproof 146 9.1. Counterexamples 148 9.2. Disproving Existence Statements 150 9.3. Disproof by Contradiction 152 10. Mathematical Induction 154 10.1. Proof by Strong Induction 161 10.2. Proof by Smallest Counterexample 165 10.3. Fibonacci Numbers 167 vi IV Relations, Functions and Cardinality 11. Relations 175 11.1. Properties of Relations 179 11.2. Equivalence Relations 184 11.3. Equivalence Classes and Partitions 188 11.4. The Integers Modulo n 191 11.5. Relations Between Sets 194 12. Functions 196 12.1. Functions 196 12.2. Injective and Surjective Functions 201 12.3. The Pigeonhole Principle 205 12.4. Composition 208 12.5. Inverse Functions 211 12.6. Image and Preimage 214 13. Cardinality of Sets 217 13.1. Sets with Equal Cardinalities 217 13.2. Countable and Uncountable Sets 223 13.3. Comparing Cardinalities 228 13.4. The Cantor-Bernstein-Schröeder Theorem 232 Conclusion 239 Solutions 240 Index 301 Preface In writing this book I have been motivated by the desire to create ahigh-quality textbook that costs almost nothing. The book is available on my web page for free, and the paperback version (produced through an on-demand press) costs considerably less than comparable traditional textbooks. Any revisions or new editions will be issued solely for the purpose of correcting mistakes and clarifying exposition. New exercises may be added, but the existing ones will not be unnecessarily changed or renumbered. This text is an expansion and refinement of lecture notes I developed while teaching proofs courses over the past fourteen years at Virginia Commonwealth University (a large state university) and Randolph-Macon College (a small liberal arts college). I found the needs of these two audiences to be nearly identical, and I wrote this book for them. But I am mindful of a larger audience. I believe this book is suitable for almost any undergraduate mathematics program. This second edition incorporates many minor corrections and additions that were suggested by readers around the world. In addition, several new examples and exercises have been added, and a section on the Cantor- Bernstein-Schröeder theorem has been added to Chapter 13. Richard Hammack Richmond, Virginia May 25, 2013 x Introduction To the instructor. The book is designed for a three credit course. Here is a possible timetable for a fourteen-week semester. Week Monday Wednesday Friday 1 Section 1.1 Section 1.2 Sections 1.3, 1.4 2 Sections 1.5, 1.6, 1.7 Section 1.8 Sections 1.9∗, 2.1 3 Section 2.2 Sections 2.3, 2.4 Sections 2.5, 2.6 4 Section 2.7 Sections 2.8∗, 2.9 Sections 2.10, 2.11∗, 2.12∗ 5 Sections 3.1, 3.2 Section 3.3 Sections 3.4, 3.5∗ 6 EXAM Sections 4.1, 4.2, 4.3 Sections 4.3, 4.4, 4.5∗ 7 Sections 5.1, 5.2, 5.3∗ Section 6.1 Sections 6.2 6.3∗ 8 Sections 7.1, 7.2∗, 7.3 Sections 8.1, 8.2 Section 8.3 9 Section 8.4 Sections 9.1, 9.2, 9.3∗ Section 10.0 10 Sections 10.0, 10.3∗ Sections 10.1, 10.2 EXAM 11 Sections 11.0, 11.1 Sections 11.2, 11.3 Sections 11.4, 11.5 12 Section 12.1 Section 12.2 Section 12.2 13 Sections 12.3, 12.4∗ Section 12.5 Sections 12.5, 12.6∗ 14 Section 13.1 Section 13.2 Sections 13.3, 13.4∗ Sections marked with ∗ may require only the briefest mention in class, or may be best left for the students to digest on their own. Some instructors may prefer to omit Chapter 3. Acknowledgments. I thank my students in VCU’s MATH 300 courses for offering feedback as they read the first edition of this book. Thanks especially to Cory Colbert and Lauren Pace for rooting out typographical mistakes and inconsistencies. I am especially indebted to Cory for reading early drafts of each chapter and catching numerous mistakes before I posted the final draft on my web page. Cory also created the index, suggested some interesting exercises, and wrote some solutions. Thanks to Andy Lewis and Sean Cox for suggesting many improvements while teaching from the book. I am indebted to Lon Mitchell, whose expertise with typesetting and on-demand publishing made the print version of this book a reality. And thanks to countless readers all over the world who contacted me concerning errors and omissions. Because of you, this is a better book. Part I Fundamentals Introduction to Sets 5 This box analogy can help us think about sets. The set F = {;,{;},{{;}}} may look strange but it is really very simple. Think of it as a box containing three things: an empty box, a box containing an empty box, and a box containing a box containing an empty box. Thus |F| = 3. The set G = {N,Z} is a box containing two boxes, the box of natural numbers and the box of integers. Thus |G| = 2. A special notation called set-builder notation is used to describe sets that are too big or complex to list between braces. Consider the infinite set of even integers E = { . . . ,−6,−4,−2,0,2,4,6, . . .}. In set-builder notation this set is written as E = {2n : n ∈Z}. We read the first brace as “the set of all things of form,” and the colon as “such that.” So the expression E = {2n : n ∈Z} is read as “E equals the set of all things of form 2n, such that n is an element of Z.” The idea is that E consists of all possible values of 2n, where n takes on all values in Z. In general, a set X written with set-builder notation has the syntax X = {expression : rule}, where the elements of X are understood to be all values of “expression” that are specified by “rule.” For example, the set E above is the set of all values the expression 2n that satisfy the rule n ∈ Z. There can be many ways to express the same set. For example, E = {2n : n ∈ Z} ={ n : n is an even integer } = {n : n = 2k,k ∈ Z}. Another common way of writing it is E = {n ∈Z : n is even}, read “E is the set of all n in Z such that n is even.” Some writers use a bar instead of a colon; for example, E = {n ∈Z | n is even}. We use the colon. Example 1.1 Here are some further illustrations of set-builder notation. 1. { n : n is a prime number }= {2,3,5,7,11,13,17, . . .} 2. { n ∈N : n is prime}= {2,3,5,7,11,13,17, . . .} 3. { n2 : n ∈Z}= {0,1,4,9,16,25, . . .} 4. { x ∈R : x2 −2= 0}= {p2,−p2} 5. { x ∈Z : x2 −2= 0}=; 6. { x ∈Z : |x| < 4}= {−3,−2,−1,0,1,2,3} 7. { 2x : x ∈Z, |x| < 4}= {−6,−4,−2,0,2,4,6} 8. { x ∈Z : |2x| < 4}= {−1,0,1} 6 Sets These last three examples highlight a conflict of notation that we must always be alert to. The expression |X |means absolute value if X is a number and cardinality if X is a set. The distinction should always be clear from context. Consider { x ∈Z : |x| < 4} in Example 1.1 (6) above. Here x ∈Z, so x is a number (not a set), and thus the bars in |x| must mean absolute value, not cardinality. On the other hand, suppose A = {{1,2},{3,4,5,6},{7}} and B = {X ∈ A : |X | < 3}. The elements of A are sets (not numbers), so the |X | in the expression for B must mean cardinality. Therefore B = {{1,2},{7}}. We close this section with a summary of special sets. These are sets or types of sets that come up so often that they are given special names and symbols. • The empty set: ;= {} • The natural numbers: N= {1,2,3,4,5, . . .} • The integers: Z= { . . . ,−3,−2,−1,0,1,2,3,4,5, . . .} • The rational numbers: Q= {x : x = m n , where m,n ∈Z and n 6= 0} • The real numbers: R (the set of all real numbers on the number line) Notice that Q is the set of all numbers that can be expressed as a fraction of two integers. You are surely aware that Q 6=R, as p2 ∉Q but p2 ∈R. Following are some other special sets that you will recall from your study of calculus. Given two numbers a,b ∈ R with a < b, we can form various intervals on the number line. • Closed interval: [a,b]= {x ∈R : a ≤ x ≤ b} • Half open interval: (a,b]= {x ∈R : a < x ≤ b} • Half open interval: [a,b)= {x ∈R : a ≤ x < b} • Open interval: (a,b)= {x ∈R : a < x < b} • Infinite interval: (a,∞)= {x ∈R : a < x} • Infinite interval: [a,∞)= {x ∈R : a ≤ x} • Infinite interval: (−∞,b)= {x ∈R : x < b} • Infinite interval: (−∞,b]= {x ∈R : x ≤ b} Remember that these are intervals on the number line, so they have in- finitely many elements. The set (0.1,0.2) contains infinitely many numbers, even though the end points may be close together. It is an unfortunate notational accident that (a,b) can denote both an interval on the line and a point on the plane. The difference is usually clear from context. In the next section we will see still another meaning of (a,b). Introduction to Sets 7 Exercises for Section 1.1 A. Write each of the following sets by listing their elements between braces. 1. { 5x−1 : x ∈Z} 2. { 3x+2 : x ∈Z} 3. { x ∈Z :−2≤ x < 7} 4. { x ∈N :−2< x ≤ 7} 5. { x ∈R : x2 = 3} 6. { x ∈R : x2 = 9} 7. { x ∈R : x2 +5x =−6} 8. { x ∈R : x3 +5x2 =−6x} 9. { x ∈R : sinπx = 0} 10. { x ∈R : cos x = 1} 11. { x ∈Z : |x| < 5} 12. { x ∈Z : |2x| < 5} 13. { x ∈Z : |6x| < 5} 14. { 5x : x ∈Z, |2x| ≤ 8} 15. { 5a+2b : a,b ∈Z} 16. { 6a+2b : a,b ∈Z} B. Write each of the following sets in set-builder notation. 17. { 2,4,8,16,32,64 . . . } 18. { 0,4,16,36,64,100, . . . } 19. { . . . ,−6,−3,0,3,6,9,12,15, . . .} 20. { . . . ,−8,−3,2,7,12,17, . . .} 21. { 0,1,4,9,16,25,36, . . . } 22. { 3,6,11,18,27,38, . . . } 23. { 3,4,5,6,7,8 } 24. {−4,−3,−2,−1,0,1,2} 25. { . . . , 18 , 1 4 , 1 2 ,1,2,4,8, . . . } 26. { . . . , 127 , 1 9 , 1 3 ,1,3,9,27, . . . } 27. { . . . ,−π,−π2 ,0, π2 ,π, 3π2 ,2π, 5π2 , . . . } 28. { . . . ,− 32 ,− 34 ,0, 34 , 32 , 94 ,3, 154 , 92 , . . . } C. Find the following cardinalities. 29. ∣∣{{1},{2,{3,4}},;}∣∣ 30. ∣∣{{1,4},a,b,{{3,4}},{;}}∣∣ 31. ∣∣{{{1},{2,{3,4}},;}}∣∣ 32. ∣∣{{{1,4},a,b,{{3,4}},{;}}}∣∣ 33. ∣∣{x ∈Z : |x| < 10}∣∣ 34. ∣∣{x ∈N : |x| < 10}∣∣ 35. ∣∣{x ∈Z : x2 < 10}∣∣ 36. ∣∣{x ∈N : x2 < 10}∣∣ 37. ∣∣{x ∈N : x2 < 0}∣∣ 38. ∣∣{x ∈N : 5x ≤ 20}∣∣ D. Sketch the following sets of points in the x-y plane. 39. { (x, y) : x ∈ [1,2], y ∈ [1,2]} 40. { (x, y) : x ∈ [0,1], y ∈ [1,2]} 41. { (x, y) : x ∈ [−1,1], y= 1} 42. { (x, y) : x = 2, y ∈ [0,1]} 43. { (x, y) : |x| = 2, y ∈ [0,1]} 44. { (x, x2) : x ∈R} 45. { (x, y) : x, y ∈R, x2 + y2 = 1} 46. { (x, y) : x, y ∈R, x2 + y2 ≤ 1} 47. { (x, y) : x, y ∈R, y≥ x2 −1} 48. { (x, y) : x, y ∈R, x > 1} 49. { (x, x+ y) : x ∈R, y ∈Z} 50. { (x, x 2 y ) : x ∈R, y ∈N } 51. { (x, y) ∈R2 : (y− x)(y+ x)= 0} 52. { (x, y) ∈R2 : (y− x2)(y+ x2)= 0} 10 Sets We can also take Cartesian powers of sets. For any set A and positive integer n, the power An is the Cartesian product of A with itself n times: An = A× A×·· ·× A = {(x1, x2, . . . , xn) : x1, x2, . . . , xn ∈ A}. In this way, R2 is the familiar Cartesian plane and R3 is three-dimensional space. You can visualize how, if R2 is the plane, then Z2 = {(m,n) : m,n ∈Z} is a grid of points on the plane. Likewise, as R3 is 3-dimensional space, Z3 = {(m,n, p) : m,n, p ∈Z} is a grid of points in space. In other courses you may encounter sets that are very similar to Rn, but yet have slightly different shades of meaning. Consider, for example, the set of all two-by-three matrices with entries from R: M = {[u v wx y z ] : u,v,w, x, y, z ∈R} . This is not really all that different from the set R6 = {(u,v,w, x, y, z) : u,v,w, x, y, z ∈R}. The elements of these sets are merely certain arrangements of six real numbers. Despite their similarity, we maintain that M 6= R6, for two-by- three matrices are not the same things as sequences of six numbers. Exercises for Section 1.2 A. Write out the indicated sets by listing their elements between braces. 1. Suppose A = {1,2,3,4} and B = {a, c}. (a) A×B (b) B× A (c) A× A (d) B×B (e) ;×B (f) (A×B)×B (g) A× (B×B) (h) B3 2. Suppose A = {π, e,0} and B = {0,1}. (a) A×B (b) B× A (c) A× A (d) B×B (e) A×; (f) (A×B)×B (g) A× (B×B) (h) A×B×B 3. { x ∈R : x2 = 2}×{a, c, e} 4. { n ∈Z : 2< n < 5}×{n ∈Z : |n| = 5} 5. { x ∈R : x2 = 2}×{x ∈R : |x| = 2} 6. { x ∈R : x2 = x}×{x ∈N : x2 = x} 7. {;}×{0,;}×{0,1} 8. { 0,1 }4 B. Sketch these Cartesian products on the x-y plane R2 (or R3 for the last two). 9. { 1,2,3 }×{−1,0,1} 10. {−1,0,1}×{1,2,3} 11. [0,1]× [0,1] 12. [−1,1]× [1,2] 13. { 1,1.5,2 }× [1,2] 14. [1,2]×{1,1.5,2} 15. { 1 }× [0,1] 16. [0,1]×{1} 17. N×Z 18. Z×Z 19. [0,1]× [0,1]× [0,1] 20. { (x, y) ∈R2 : x2 + y2 ≤ 1}× [0,1] Subsets 11 1.3 Subsets It can happen that every element of some set A is also an element of another set B. For example, each element of A = {0,2,4} is also an element of B = {0,1,2,3,4}. When A and B are related this way we say that A is a subset of B. Definition 1.3 Suppose A and B are sets. If every element of A is also an element of B, then we say A is a subset of B, and we denote this as A ⊆ B. We write A 6⊆ B if A is not a subset of B, that is, if it is not true that every element of A is also an element of B. Thus A 6⊆ B means that there is at least one element of A that is not an element of B. Example 1.2 Be sure you understand why each of the following is true. 1. { 2,3,7 }⊆ {2,3,4,5,6,7} 2. { 2,3,7 } 6⊆ {2,4,5,6,7} 3. { 2,3,7 }⊆ {2,3,7} 4. { 2n : n ∈Z}⊆Z 5. { (x,sin(x)) : x ∈R}⊆R2 6. { 2,3,5,7,11,13,17, . . . }⊆N 7. N⊆Z⊆Q⊆R 8. R×N⊆R×R This brings us to a significant fact: If B is any set whatsoever, then ;⊆ B. To see why this is true, look at the last sentence of Definition 1.3. It says that ; 6⊆ B would mean that there is at least one element of ; that is not an element of B. But this cannot be so because ; contains no elements! Thus it is not the case that ; 6⊆ B, so it must be that ;⊆ B. Fact 1.2 The empty set is a subset of every set, that is, ;⊆ B for any set B. Here is another way to look at it. Imagine a subset of B as a thing you make by starting with braces {} , then filling them with selections from B. For example, to make one particular subset of B = {a,b, c}, start with {}, select b and c from B and insert them into {} to form the subset { b, c } . Alternatively, you could have chosen just a to make { a } , and so on. But one option is to simply select nothing from B. This leaves you with the subset {} . Thus {}⊆ B. More often we write it as ;⊆ B. 12 Sets This idea of “making” a subset can help us list out all the subsets of a given set B. As an example, let B = {a,b, c}. Let’s list all of its subsets. One way of approaching this is to make a tree-like structure. Begin with the subset {} , which is shown on the left of Figure 1.3. Considering the element a of B, we have a choice: insert it or not. The lines from {} point to what we get depending whether or not we insert a, either {} or { a } . Now move on to the element b of B. For each of the sets just formed we can either insert or not insert b, and the lines on the diagram point to the resulting sets {} , { b } , { a } , or { a,b } . Finally, to each of these sets, we can either insert c or not insert it, and this gives us, on the far right-hand column, the sets {} , { c } , { b } , { b, c } , { a } , { a, c } , { a,b } and { a,b, c } . These are the eight subsets of B = {a,b, c}. Insert a? Insert b? Insert c? No Yes Yes Yes Yes Yes Yes Yes No No No No No No {} {} {} {}{ c } { b } { b, c } { a } { a, c } { a,b } { a,b, c } { b } { a } { a,b } { a } Figure 1.3. A “tree” for listing subsets We can see from the way this tree branches out that if it happened that B = {a}, then B would have just two subsets, those in the second column of the diagram. If it happened that B = {a,b}, then B would have four subsets, those listed in the third column, and so on. At each branching of the tree, the number of subsets doubles. Thus in general, if |B| = n, then B must have 2n subsets. Fact 1.3 If a finite set has n elements, then it has 2n subsets. Power Sets 15 Fact 1.4 If A is a finite set, then |P(A)| = 2|A|. Example 1.4 You should examine the following statements and make sure you understand how the answers were obtained. In particular, notice that in each instance the equation |P(A)| = 2|A| is true. 1. P ({ 0,1,3 })= {;, {0}, {1}, {3}, {0,1}, {0,3}, {1,3}, {0,1,3} } 2. P ({ 1,2 })= {;, {1}, {2}, {1,2} } 3. P ({ 1 })= {;, {1} } 4. P (;)= {; } 5. P ({ a })= {;, {a} } 6. P ({;})= {;, {;} } 7. P ({ a })×P ({;})= { (;,;), (;,{;}) , ({a},;) , ({a},{;}) } 8. P ( P ({;}))= {;, {;}, {{;}}, {;,{;}} } 9. P ({ 1, { 1,2 }})= {;, {1}, {{1,2}}, {1,{1,2}} } 10. P ({ Z,N })= {;, {Z}, {N}, {Z,N} } Next are some that are wrong. See if you can determine why they are wrong and make sure you understand the explanation on the right. 11. P(1)= {;, {1} } . . . . . . . . . . . . . . . . . . . . . . . . . . . meaningless because 1 is not a set 12. P ({ 1, { 1,2 }})= {;,{1},{1,2},{1,{1,2}}} . . . . . . . . wrong because {1,2} 6⊆ {1,{1,2}} 13. P ({ 1, { 1,2 }})= {;,{{1}},{{1,2}},{;,{1,2}}} . . . . .wrong because {{1}} 6⊆ {1,{1,2}} If A is finite, it is possible (though maybe not practical) to list out P(A) between braces as was done in the above example. That is not possible if A is infinite. For example, consider P(N). If you start listing its elements you quickly discover that N has infinitely many subsets, and it’s not clear how (or if) they could be arranged as a list with a definite pattern: P(N)= {;,{1},{2}, . . . ,{1,2},{1,3}, . . . ,{39,47}, . . . , { 3,87,131 } , . . . , { 2,4,6,8, . . . } , . . . ? . . . } . The set P(R2) is mind boggling. Think of R2 = {(x, y) : x, y ∈R} as the set of all points on the Cartesian plane. A subset of R2 (that is, an element of P(R2)) is a set of points in the plane. Let’s look at some of these sets. Since { (0,0), (1,1) } ⊆ R2, we know that {(0,0), (1,1)} ∈ P(R2). We can even draw a picture of this subset, as in Figure 1.4(a). For another example, the graph of the equation y= x2 is the set of points G = {(x, x2) : x ∈R} and this is a subset of R2, so G ∈P(R2). Figure 1.4(b) is a picture of G. Because this can be done for any function, the graph of any imaginable function f :R→R is an element of P(R2). 16 Sets x x x y y y (a) (b) (c) Figure 1.4. Three of the many, many sets in P(R2) In fact, any black-and-white image on the plane can be thought of as a subset of R2, where the black points belong to the subset and the white points do not. So the text “INFINITE” in Figure 1.4(c) is a subset of R2 and therefore an element of P(R2). By that token, P(R2) contains a copy of the page you are reading now. Thus in addition to containing every imaginable function and every imaginable black-and-white image, P(R2) also contains the full text of every book that was ever written, those that are yet to be written and those that will never be written. Inside of P(R2) is a detailed biography of your life, from beginning to end, as well as the biographies of all of your unborn descendants. It is startling that the five symbols used to write P(R2) can express such an incomprehensibly large set. Homework: Think about P(P(R2)). Exercises for Section 1.4 A. Find the indicated sets. 1. P ({{ a,b } , { c }}) 2. P ({ 1,2,3,4 }) 3. P ({{;},5}) 4. P ({ R,Q }) 5. P ( P ({ 2 })) 6. P ({ 1,2 })×P ({3}) 7. P ({ a,b })×P ({0,1}) 8. P ({ 1,2 }×{3}) 9. P ({ a,b }×{0}) 10. { X ∈P ({1,2,3}) : |X | ≤ 1} 11. { X ⊆P ({1,2,3}) : |X | ≤ 1} 12. { X ∈P ({1,2,3}) : 2 ∈ X} B. Suppose that |A| = m and |B| = n. Find the following cardinalities. 13. |P(P(P(A)))| 14. |P(P(A))| 15. |P(A×B)| 16. |P(A)×P(B)| 17. ∣∣{X ∈P(A) : |X | ≤ 1}∣∣ 18. |P(A×P(B))| 19. |P(P(P(A×;)))| 20. ∣∣{X ⊆P(A) : |X | ≤ 1}∣∣ Union, Intersection, Difference 17 1.5 Union, Intersection, Difference Just as numbers are combined with operations such as addition, subtrac- tion and multiplication, there are various operations that can be applied to sets. The Cartesian product (defined in Section 1.2) is one such operation; given sets A and B, we can combine them with × to get a new set A×B. Here are three new operations called union, intersection and difference. Definition 1.5 Suppose A and B are sets. The union of A and B is the set A∪B = {x : x ∈ A or x ∈ B}. The intersection of A and B is the set A∩B = {x : x ∈ A and x ∈ B}. The difference of A and B is the set A−B = {x : x ∈ A and x ∉ B}. In words, the union A∪B is the set of all things that are in A or in B (or in both). The intersection A∩B is the set of all things in both A and B. The difference A−B is the set of all things that are in A but not in B. Example 1.5 Suppose A = {a,b, c,d, e}, B = {d, e, f } and C = {1,2,3}. 1. A∪B = {a,b, c,d, e, f } 2. A∩B = {d, e} 3. A−B = {a,b, c} 4. B− A = { f } 5. (A−B)∪ (B− A)= {a,b, c, f } 6. A∪C = {a,b, c,d, e,1,2,3} 7. A∩C =; 8. A−C = {a,b, c,d, e} 9. (A∩C)∪ (A−C)= {a,b, c,d, e} 10. (A∩B)×B = {(d,d), (d, e), (d, f ), (e,d), (e, e), (e, f )} 11. (A×C)∩ (B×C)= {(d,1), (d,2), (d,3), (e,1), (e,2), (e,3)} Observe that for any sets X and Y it is always true that X ∪Y =Y ∪ X and X ∩Y =Y ∩ X , but in general X −Y 6=Y − X . Continuing the example, parts 12–15 below use the interval notation discussed in Section 1.1, so [2,5] = {x ∈ R : 2 ≤ x ≤ 5}, etc. Sketching these examples on the number line may help you understand them. 12. [2,5]∪ [3,6]= [2,6] 13. [2,5]∩ [3,6]= [3,5] 14. [2,5]− [3,6]= [2,3) 15. [0,3]− [1,2]= [0,1)∪ (2,3] 20 Sets Example 1.7 If P is the set of prime numbers, then P =N−P = {1,4,6,8,9,10,12, . . .}. Thus P is the set of composite numbers and 1. Example 1.8 Let A = {(x, x2) : x ∈ R} be the graph of the equation y = x2. Figure 1.6(a) shows A in its universal set R2. The complement of A is A = R2 − A = {(x, y) ∈R2 : y 6= x2}, illustrated by the shaded area in Figure 1.6(b). A A (a) (b) Figure 1.6. A set and its complement Exercises for Section 1.6 1. Let A = {4,3,6,7,1,9} and B = {5,6,8,4} have universal set U = {0,1,2, . . . ,10}. Find: (a) A (b) B (c) A∩ A (d) A∪ A (e) A− A (f) A−B (g) A−B (h) A∩B (i) A∩B 2. Let A = {0,2,4,6,8} and B = {1,3,5,7} have universal set U = {0,1,2, . . . ,8}. Find: (a) A (b) B (c) A∩ A (d) A∪ A (e) A− A (f) A∪B (g) A∩B (h) A∩B (i) A×B 3. Sketch the set X = [1,3]× [1,2] on the plane R2. On separate drawings, shade in the sets X and X ∩ ([0,2]× [0,3]). 4. Sketch the set X = [−1,3]× [0,2] on the plane R2. On separate drawings, shade in the sets X and X ∩ ([−2,4]× [−1,3]). 5. Sketch the set X = {(x, y) ∈ R2 : 1 ≤ x2 + y2 ≤ 4} on the plane R2. On a separate drawing, shade in the set X . 6. Sketch the set X = {(x, y) ∈R2 : y< x2} on R2. Shade in the set X . Venn Diagrams 21 1.7 Venn Diagrams In thinking about sets, it is sometimes helpful to draw informal, schematic diagrams of them. In doing this we often represent a set with a circle (or oval), which we regard as enclosing all the elements of the set. Such diagrams can illustrate how sets combine using various operations. For example, Figures 1.7(a–c) show two sets A and B that overlap in a middle region. The sets A ∪B, A ∩B and A −B are shaded. Such graphical representations of sets are called Venn diagrams, after their inventor, British logician John Venn, 1834–1923. A A AB B B A∪B A∩B A−B (a) (b) (c) Figure 1.7. Venn diagrams for two sets Though you are unlikely to draw Venn diagrams as a part of a proof of any theorem, you will probably find them to be useful “scratch work” devices that help you to understand how sets combine, and to develop strategies for proving certain theorems or solving certain problems. The remainder of this section uses Venn diagrams to explore how three sets can be combined using ∪ and ∩. Let’s begin with the set A∪B∪C. Our definitions suggest this should consist of all elements which are in one or more of the sets A, B and C. Figure 1.8(a) shows a Venn diagram for this. Similarly, we think of A∩B∩C as all elements common to each of A, B and C, so in Figure 1.8(b) the region belonging to all three sets is shaded. A AB B C C A∪B∪C A∩B∩C (a) (b) Figure 1.8. Venn diagrams for three sets 22 Sets We can also think of A∩B∩C as the two-step operation (A∩B)∩C. In this expression the set A∩B is represented by the region common to both A and B, and when we intersect this with C we get Figure 1.8(b). This is a visual representation of the fact that A∩B∩C = (A∩B)∩C. Similarly, we have A∩B∩C = A∩ (B∩C). Likewise, A∪B∪C = (A∪B)∪C = A∪ (B∪C). Notice that in these examples, where the expression either contains only the symbol ∪ or only the symbol ∩, the placement of the parentheses is irrelevant, so we are free to drop them. It is analogous to the situations in algebra involving expressions (a+b)+ c = a+ (b+ c) or (a ·b) · c = a · (b · c). We tend to drop the parentheses and write simply a+b+ c or a ·b · c. By contrast, in an expression like (a+ b) · c the parentheses are absolutely essential because (a+b) · c and a+ (b · c) are generally not equal. Now let’s use Venn diagrams to help us understand the expressions (A∪B)∩C and A∪ (B∩C), which use a mix of ∪ and ∩. Figure 1.9 shows how to draw a Venn diagram for (A∪B)∩C. In the drawing on the left, the set A∪B is shaded with horizontal lines, while C is shaded with vertical lines. Thus the set (A∪B)∩C is represented by the cross-hatched region where A∪B and C overlap. The superfluous shadings are omitted in the drawing on the right showing the set (A∪B)∩C. A AB B C C Figure 1.9. How to make a Venn diagram for (A∪B)∩C Now think about A∪ (B∩C). In Figure 1.10 the set A is shaded with horizontal lines, and B∩C is shaded with vertical lines. The union A∪(B∩C) is represented by the totality of all shaded regions, as shown on the right. A AB B C C Figure 1.10. How to make a Venn diagram for A∪ (B∩C) Indexed Sets 25 This notation is also used when the list of sets A1, A2, A3, . . . is infinite: ∞⋃ i=1 A i = A1 ∪ A2 ∪ A3 ∪·· · = { x : x ∈ A i for at least one set A i with 1≤ i } . ∞⋂ i=1 A i = A1 ∩ A2 ∩ A3 ∩·· · = { x : x ∈ A i for every set A i with 1≤ i } . Example 1.10 This example involves the following infinite list of sets. A1 = {−1,0,1}, A2 = {−2,0,2}, A3 = {−3,0,3}, · · · , A i = {− i,0, i}, · · · Observe that ∞⋃ i=1 A i =Z, and ∞⋂ i=1 A i = { 0 } . Here is a useful twist on our new notation. We can write 3⋃ i=1 A i = ⋃ i∈{1,2,3} A i, as this takes the union of the sets A i for i = 1,2,3. Likewise: 3⋂ i=1 A i = ⋂ i∈{1,2,3} A i ∞⋃ i=1 A i = ⋃ i∈N A i ∞⋂ i=1 A i = ⋂ i∈N A i Here we are taking the union or intersection of a collection of sets A i where i is an element of some set, be it { 1,2,3 } or N. In general, the way this works is that we will have a collection of sets A i for i ∈ I, where I is the set of possible subscripts. The set I is called an index set. It is important to realize that the set I need not even consist of integers. (We could subscript with letters or real numbers, etc.) Since we are programmed to think of i as an integer, let’s make a slight notational change: We use α, not i, to stand for an element of I. Thus we are dealing with a collection of sets Aα for α ∈ I. This leads to the following definition. Definition 1.8 If we have a set Aα for every α in some index set I, then⋃ α∈I Aα = { x : x ∈ Aα for at least one set Aα with α ∈ I } ⋂ α∈I Aα = { x : x ∈ Aα for every set Aα with α ∈ I } . 26 Sets Example 1.11 Here the sets Aα will be subsets of R2. Let I = [0,2] ={ x ∈R : 0≤ x ≤ 2}. For each number α ∈ I, let Aα = {(x,α) : x ∈R,1≤ x ≤ 2}. For instance, given α= 1 ∈ I the set A1 = { (x,1) : x ∈ R,1 ≤ x ≤ 2} is a horizontal line segment one unit above the x-axis and stretching between x = 1 and x = 2, as shown in Figure 1.11(a). Likewise Ap2 = { (x, p 2) : x ∈R,1≤ x ≤ 2} is a horizontal line segment p 2 units above the x-axis and stretching between x = 1 and x = 2. A few other of the Aα are shown in Figure 1.11(a), but they can’t all be drawn because there is one Aα for each of the infinitely many numbers α ∈ [0,2]. The totality of them covers the shaded region in Figure 1.11(b), so this region is the union of all the Aα. Since the shaded region is the set { (x, y) ∈R2 : 1≤ x ≤ 2,0≤ y≤ 2} = [1,2]× [0,2], it follows that⋃ α∈[0,2] Aα = [1,2]× [0,2]. Likewise, since there is no point (x, y) that is in every set Aα, we have⋂ α∈[0,2] Aα =;. x x y y 1 1 2 2 1 1 2 2 A0.25 A0.5 A1 A2 Ap2 ⋃ α∈[0,2] Aα (a) (b) Figure 1.11. The union of an indexed collection of sets One final comment. Observe that Aα = [1,2]× { α } , so the above expres- sions can be written as⋃ α∈[0,2] [1,2]×{α}= [1,2]× [0,2] and ⋂ α∈[0,2] [1,2]×{α}=;. Indexed Sets 27 Example 1.12 In this example our sets are indexed by R2. For any (a,b) ∈R2, let P(a,b) be the following subset of R3: P(a,b) = { (x, y, z) ∈R3 : ax+by= 0} . In words, given a point (a,b) ∈R2, the corresponding set P(a,b) consists of all points (x, y, z) in R3 that satisfy the equation ax+by= 0. From previous math courses you will recognize this as a plane in R3, that is, P(a,b) is a plane in R3. Moreover, since any point (0,0, z) on the z-axis automatically satisfies ax+by= 0, each P(a,b) contains the z-axis. Figure 1.12 (left) shows the set P(1,2) = { (x, y, z) ∈R3 : x+2y= 0}. It is the vertical plane that intersects the xy-plane at the line x+2y= 0. x y z (−2,1,0) P(1,2) Figure 1.12. The sets P(a,b) are vertical planes containing the z-axis. For any point (a,b) ∈R2 with (a,b) 6= (0,0), we can visualize P(a,b) as the vertical plane that cuts the xy-plane at the line ax+ by = 0. Figure 1.12 (right) shows a few of the P(a,b). Since any two such planes intersect along the z-axis, and because the z-axis is a subset of every P(a,b), it is immediately clear that⋂ (a,b)∈R2 P(a,b) = { (0,0, z) : z ∈R} = “the z-axis”. For the union, note that any given point (a,b, c) ∈R3 belongs to the set P(−b,a) because (x, y, z)= (a,b, c) satisfies the equation −bx+ay= 0. (In fact, any (a,b, c) belongs to the special set P(0,0) =R3, which is the only P(a,b) that is not a plane.) Since any point in R3 belongs to some P(a,b) we have⋃ (a,b)∈R2 P(a,b) =R3. 30 Sets Although there is no harm in accepting the division algorithm without proof, note that it does follow from the well-ordering principle. Here’s how: Given integers a,b with b > 0, form the set A = {a− xb : x ∈Z, 0≤ a− xb}⊆ {0,1,2,3, . . .}. (For example, if a = 17 and b = 3 then A = {2,5,8,11,14,17,20, . . .} is the set of positive integers obtained by adding multiples of 3 to 17. Notice that the remainder r = 2 of 17÷3 is the smallest element of this set.) In general, let r be the smallest element of the set A = {a− xb : x ∈Z, 0≤ a− xb}. Then r = a− qb for some x = q ∈ Z, so a = qb+ r. Moreover, 0 ≤ r < b, as follows. The fact that r ∈ A ⊆ {0,1,2,3 . . .} implies 0 ≤ r. In addition, it cannot happen that r ≥ b: If this were the case, then the non-negative number r−b = (a−qb)−b = a−(q+1)b having form a−xb would be a smaller element of A than r, and r was explicitly chosen as the smallest element of A. Since it is not the case that r ≥ b, it must be that r < b. Therefore 0≤ r < b. We’ve now produced a q and an r for which a = qb+ r and 0≤ r < b. Moving on, it is time to clarify a small issue. This chapter asserted that all of mathematics can be described with sets. But at the same time we maintained that some mathematical entities are not sets. (For instance, our approach was to say that an individual number, such as 5, is not itself a set, though it may be an element of a set.) We have made this distinction because we need a place to stand as we explore sets: After all, it would appear suspiciously circular to declare that every mathematical entity is a set, and then go on to define a set as a collection whose members are sets! But to most mathematicians, saying “The number 5 is not a set,” is like saying “The number 5 is not a number.” The truth is that any number can itself be understood as a set. One way to do this is to begin with the identification 0=;. Then 1= {;}= {0}, and 2 = {;, {;}} = {0,1}, and 3 = {;, {;}, {;, {;}}} = {0,1,2}. In general the natural number n is the set n = {0,1,2, . . . ,n−1} of the n numbers (which are themselves sets) that come before it. We will not undertake such a study here, but the elements of the number systems Z, Q and R can all be defined in terms of sets. (Even the operations of addition, multiplication, etc., can be defined in set-theoretic terms.) In fact, mathematics itself can be regarded as the study of things that can be described as sets. Any mathematical entity is a set, whether or not we choose to think of it that way. Russell’s Paradox 31 1.10 Russell’s Paradox This section contains some background information that may be interesting, but is not used in the remainder of the book. The philosopher and mathematician Bertrand Russell (1872–1970) did groundbreaking work on the theory of sets and the foundations of mathematics. He was probably among the first to understand how the misuse of sets can lead to bizarre and paradoxical situations. He is famous for an idea that has come to be known as Russell’s paradox. Russell’s paradox involves the following set of sets: A = { X : X is a set and X ∉ X }. (1.1) In words, A is the set of all sets that do not include themselves as elements. Most sets we can think of are in A. The set Z of integers is not an integer (i.e., Z ∉Z) and therefore Z ∈ A. Also ;∈ A because ; is a set and ;∉;. Is there a set that is not in A? Consider B = {{{{ . . .}}}}. Think of B as a box containing a box, containing a box, containing a box, and so on, forever. Or a set of Russian dolls, nested one inside the other, endlessly. The curious thing about B is that it has just one element, namely B itself: B = { {{{ . . .}}}︸ ︷︷ ︸ B } . Thus B ∈ B. As B does not satisfy B ∉ B, Equation (1.1) says B ∉ A. Russell’s paradox arises from the question “Is A an element of A?” For a set X , Equation (1.1) says X ∈ A means the same thing as X ∉ X . So for X = A, the previous line says A ∈ A means the same thing as A ∉ A. Conclusion: if A ∈ A is true, then it is false; if A ∈ A is false, then it is true. This is Russell’s paradox. Initially Russell’s paradox sparked a crisis among mathematicians. How could a mathematical statement be both true and false? This seemed to be in opposition to the very essence of mathematics. The paradox instigated a very careful examination of set theory and an evaluation of what can and cannot be regarded as a set. Eventually mathematicians settled upon a collection of axioms for set theory—the so-called Zermelo-Fraenkel axioms. One of these axioms is the well- ordering principle of the previous section. Another, the axiom of foundation, states that no non-empty set X is allowed to have the property X ∩ x 6= ; for all its elements x. This rules out such circularly defined “sets” as X = {X} introduced above. If we adhere to these axioms, then situations 32 Sets like Russell’s paradox disappear. Most mathematicians accept all this on faith and happily ignore the Zermelo-Fraenkel axioms. Paradoxes like Russell’s do not tend to come up in everyday mathematics—you have to go out of your way to construct them. Still, Russell’s paradox reminds us that precision of thought and lan- guage is an important part of doing mathematics. The next chapter deals with the topic of logic, a codification of thought and language. Additional Reading on Sets. For a lively account of Bertrand Russell’s life and work (including his paradox), see the graphic novel Logicomix: An Epic Search For Truth, by Apostolos Doxiadis and Christos Papadimitriou. Also see cartoonist Jessica Hagy’s online strip Indexed—it is based largely on Venn diagrams. Statements 35 Example 2.4 We will often use the letters P, Q, R and S to stand for specific statements. When more letters are needed we can use subscripts. Here are more statements, designated with letters. You decide which of them are true and which are false. P : For every integer n > 1, the number 2n −1 is prime. Q : Every polynomial of degree n has at most n roots. R : The function f (x)= x2 is continuous. S1 :Z⊆; S2 : {0,−1,−2}∩N=; Designating statements with letters (as was done above) is a very useful shorthand. In discussing a particular statement, such as “The function f (x) = x2 is continuous,” it is convenient to just refer to it as R to avoid having to write or say it many times. Statements can contain variables. Here is an example. P : If an integer x is a multiple of 6, then x is even. This is a sentence that is true. (All multiples of 6 are even, so no matter which multiple of 6 the integer x happens to be, it is even.) Since the sentence P is definitely true, it is a statement. When a sentence or statement P contains a variable such as x, we sometimes denote it as P(x) to indicate that it is saying something about x. Thus the above statement can be denoted as P(x) : If an integer x is a multiple of 6, then x is even. A statement or sentence involving two variables might be denoted P(x, y), and so on. It is quite possible for a sentence containing variables to not be a statement. Consider the following example. Q(x) : The integer x is even. Is this a statement? Whether it is true or false depends on just which integer x is. It is true if x = 4 and false if x = 7, etc. But without any stipulations on the value of x it is impossible to say whether Q(x) is true or false. Since it is neither definitely true nor definitely false, Q(x) cannot be a statement. A sentence such as this, whose truth depends on the value of one or more variables, is called an open sentence. The variables in an open sentence (or statement) can represent any type of entity, not just numbers. Here is an open sentence where the variables are functions: 36 Logic R( f , g) : The function f is the derivative of the function g. This open sentence is true if f (x)= 2x and g(x)= x2. It is false if f (x)= x3 and g(x) = x2, etc. We point out that a sentence such as R( f , g) (that involves variables) can be denoted either as R( f , g) or just R. We use the expression R( f , g) when we want to emphasize that the sentence involves variables. We will have more to say about open sentences later, but for now let’s return to statements. Statements are everywhere in mathematics. Any result or theorem that has been proved true is a statement. The quadratic formula and the Pythagorean theorem are both statements: P : The solutions of the equation ax2 +bx+ c = 0 are x = −b± p b2 −4ac 2a . Q : If a right triangle has legs of lengths a and b and hypotenuse of length c, then a2 +b2 = c2. Here is a very famous statement, so famous, in fact, that it has a name. It is called Fermat’s last theorem after Pierre Fermat, a seventeenth- century French mathematician who scribbled it in the margin of a notebook. R : For all numbers a,b, c,n ∈N with n > 2, it is the case that an+bn 6= cn. Fermat believed this statement was true. He noted that he could prove it was true, except his notebook’s margin was too narrow to contain his proof. It is doubtful that he really had a correct proof in mind, for after his death generations of brilliant mathematicians tried unsuccessfully to prove that his statement was true (or false). Finally, in 1993, Andrew Wiles of Princeton University announced that he had devised a proof. Wiles had worked on the problem for over seven years, and his proof runs through hundreds of pages. The moral of this story is that some true statements are not obviously true. Here is another statement famous enough to be named. It was first posed in the eighteenth century by the German mathematician Christian Goldbach, and thus is called the Goldbach conjecture: S : Every even integer greater than 2 is a sum of two prime numbers. You must agree that S is either true or false. It appears to be true, because when you examine even numbers that are bigger than 2, they seem to be sums of two primes: 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 5+5, 12 = 5+7, Statements 37 100= 17+83 and so on. But that’s not to say there isn’t some large even number that’s not the sum of two primes. If such a number exists, then S is false. The thing is, in the over 260 years since Goldbach first posed this problem, no one has been able to determine whether it’s true or false. But since it is clearly either true or false, S is a statement. This book is about the methods that can be used to prove that S (or any other statement) is true or false. To prove that a statement is true, we start with obvious statements (or other statements that have been proven true) and use logic to deduce more and more complex statements until finally we obtain a statement such as S. Of course some statements are more difficult to prove than others, and S appears to be notoriously difficult; we will concentrate on statements that are easier to prove. But the point is this: In proving that statements are true, we use logic to help us understand statements and to combine pieces of information to produce new pieces of information. In the next several sections we explore some standard ways that statements can be combined to form new statements, or broken down into simpler statements. Exercises for Section 2.1 Decide whether or not the following are statements. In the case of a statement, say if it is true or false, if possible. 1. Every real number is an even integer. 2. Every even integer is a real number. 3. If x and y are real numbers and 5x = 5y, then x = y. 4. Sets Z and N. 5. Sets Z and N are infinite. 6. Some sets are finite. 7. The derivative of any polynomial of degree 5 is a polynomial of degree 6. 8. N ∉P(N). 9. cos(x)=−1 10. (R×N)∩ (N×R)=N×N 11. The integer x is a multiple of 7. 12. If the integer x is a multiple of 7, then it is divisible by 7. 13. Either x is a multiple of 7, or it is not. 14. Call me Ishmael. 15. In the beginning, God created the heaven and the earth. 40 Logic To conclude this section, we mention another way of obtaining new statements from old ones. Given any statement P, we can form the new statement “It is not true that P.” For example, consider the following statement. The number 2 is even. This statement is true. Now change it by inserting the words “It is not true that” at the beginning: It is not true that the number 2 is even. This new statement is false. For another example, starting with the false statement “2 ∈;,” we get the true statement “It is not true that 2 ∈;.” We use the symbol ∼ to stand for the words “It’s not true that,” so ∼ P means “It’s not true that P.” We often read ∼ P simply as “not P.” Unlike ∧ and ∨, which combine two statements, the symbol ∼ just alters a single statement. Thus its truth table has just two lines, one for each possible truth value of P. P ∼ P T F F T The statement ∼ P is called the negation of P. The negation of a specific statement can be expressed in numerous ways. Consider P : The number 2 is even. Here are several ways of expressing its negation. ∼ P : It’s not true that the number 2 is even. ∼ P : It is false that the number 2 is even. ∼ P : The number 2 is not even. In this section we’ve learned how to combine or modify statements with the operations ∧, ∨ and ∼. Of course we can also apply these operations to open sentences or a mixture of open sentences and statements. For example, (x is an even integer)∧ (3 is an odd integer) is an open sentence that is a combination of an open sentence and a statement. Conditional Statements 41 Exercises for Section 2.2 Express each statement or open sentence in one of the forms P ∧Q, P ∨Q, or ∼ P. Be sure to also state exactly what statements P and Q stand for. 1. The number 8 is both even and a power of 2. 2. The matrix A is not invertible. 3. x 6= y 4. x < y 5. y≥ x 6. There is a quiz scheduled for Wednesday or Friday. 7. The number x equals zero, but the number y does not. 8. At least one of the numbers x and y equals 0. 9. x ∈ A−B 10. x ∈ A∪B 11. A ∈ {X ∈P(N) : |X | <∞} 12. Happy families are all alike, but each unhappy family is unhappy in its own way. (Leo Tolstoy, Anna Karenina) 13. Human beings want to be good, but not too good, and not all the time. (George Orwell) 14. A man should look for what is, and not for what he thinks should be. (Albert Einstein) 2.3 Conditional Statements There is yet another way to combine two statements. Suppose we have in mind a specific integer a. Consider the following statement about a. R : If the integer a is a multiple of 6, then a is divisible by 2. We immediately spot this as a true statement based on our knowledge of integers and the meanings of the words “if” and “then.” If integer a is a multiple of 6, then a is even, so therefore a is divisible by 2. Notice that R is built up from two simpler statements: P : The integer a is a multiple of 6. Q : The integer a is divisible by 2. R : If P, then Q. In general, given any two statements P and Q whatsoever, we can form the new statement “If P, then Q.” This is written symbolically as P ⇒Q which we read as “If P, then Q,” or “P implies Q.” Like ∧ and ∨, the symbol ⇒ has a very specific meaning. When we assert that the statement P ⇒Q is true, we mean that if P is true then Q must also be true. (In other words we mean that the condition P being true forces Q to be true.) A statement of form P ⇒Q is called a conditional statement because it means Q will be true under the condition that P is true. 42 Logic You can think of P ⇒Q as being a promise that whenever P is true, Q will be true also. There is only one way this promise can be broken (i.e. be false) and that is if P is true but Q is false. Thus the truth table for the promise P ⇒Q is as follows: P Q P ⇒Q T T T T F F F T T F F T Perhaps you are bothered by the fact that P ⇒Q is true in the last two lines of this table. Here’s an example to convince you that the table is correct. Suppose your professor makes the following promise: If you pass the final exam, then you will pass the course. Your professor is making the promise (You pass the exam) ⇒ (You pass the course). Under what circumstances did she lie? There are four possible scenarios, depending on whether or not you passed the exam and whether or not you passed the course. These scenarios are tallied in the following table. You pass exam You pass course (You pass exam)⇒ (You pass course) T T T T F F F T T F F T The first line describes the scenario where you pass the exam and you pass the course. Clearly the professor kept her promise, so we put a T in the third column to indicate that she told the truth. In the second line, you passed the exam, but your professor gave you a failing grade in the course. In this case she broke her promise, and the F in the third column indicates that what she said was untrue. Now consider the third row. In this scenario you failed the exam but still passed the course. How could that happen? Maybe your professor felt sorry for you. But that doesn’t make her a liar. Her only promise was that if you passed the exam then you would pass the course. She did not say Biconditional Statements 45 But sometimes, if P and Q are just the right statements, it can happen that P ⇒ Q and Q ⇒ P are both necessarily true. For example, consider the statements (a is even) ⇒ (a is divisible by 2), (a is divisible by 2) ⇒ (a is even). No matter what value a has, both of these statements are true. Since both P ⇒Q and Q ⇒ P are true, it follows that (P ⇒Q)∧ (Q ⇒ P) is true. We now introduce a new symbol ⇔ to express the meaning of the statement (P ⇒Q)∧ (Q ⇒ P). The expression P ⇔Q is understood to have exactly the same meaning as (P ⇒Q)∧ (Q ⇒ P). According to the previous section, Q ⇒ P is read as “P if Q,” and P ⇒Q can be read as “P only if Q.” Therefore we pronounce P ⇔Q as “P if and only if Q.” For example, given an integer a, we have the true statement (a is even)⇔ (a is divisible by 2), which we can read as “Integer a is even if and only if a is divisible by 2.” The truth table for ⇔ is shown below. Notice that in the first and last rows, both P ⇒Q and Q ⇒ P are true (according to the truth table for ⇒), so (P ⇒ Q)∧ (Q ⇒ P) is true, and hence P ⇔ Q is true. However, in the middle two rows one of P ⇒Q or Q ⇒ P is false, so (P ⇒Q)∧(Q ⇒ P) is false, making P ⇔Q false. P Q P ⇔Q T T T T F F F T F F F T Compare the statement R : (a is even)⇔ (a is divisible by 2) with this truth table. If a is even then the two statements on either side of ⇔ are true, so according to the table R is true. If a is odd then the two statements on either side of ⇔ are false, and again according to the table R is true. Thus R is true no matter what value a has. In general, P ⇔Q being true means P and Q are both true or both false. Not surprisingly, there are many ways of saying P ⇔Q in English. The following constructions all mean P ⇔Q: 46 Logic P if and only if Q. P is a necessary and sufficient condition for Q. For P it is necessary and sufficient that Q. If P, then Q, and conversely.  P ⇔Q The first three of these just combine constructions from the previous section to express that P ⇒Q and Q ⇒ P. In the last one, the words “...and conversely” mean that in addition to “If P, then Q” being true, the converse statement “If Q, then P” is also true. Exercises for Section 2.4 Without changing their meanings, convert each of the following sentences into a sentence having the form “P if and only if Q.” 1. For matrix A to be invertible, it is necessary and sufficient that det(A) 6= 0. 2. If a function has a constant derivative then it is linear, and conversely. 3. If xy= 0 then x = 0 or y= 0, and conversely. 4. If a ∈Q then 5a ∈Q, and if 5a ∈Q then a ∈Q. 5. For an occurrence to become an adventure, it is necessary and sufficient for one to recount it. (Jean-Paul Sartre) 2.5 Truth Tables for Statements You should now know the truth tables for ∧, ∨, ∼, ⇒ and ⇔. They should be internalized as well as memorized. You must understand the symbols thoroughly, for we now combine them to form more complex statements. For example, suppose we want to convey that one or the other of P and Q is true but they are not both true. No single symbol expresses this, but we could combine them as (P ∨Q)∧∼ (P ∧Q), which literally means: P or Q is true, and it is not the case that both P and Q are true. This statement will be true or false depending on the truth values of P and Q. In fact we can make a truth table for the entire statement. Begin as usual by listing the possible true/false combinations of P and Q on four lines. The statement (P ∨Q)∧∼ (P ∧Q) contains the individual statements (P ∨Q) and (P ∧Q), so we next tally their truth values in the third and fourth columns. The fifth column lists values for ∼ (P ∧Q), and these Truth Tables for Statements 47 are just the opposites of the corresponding entries in the fourth column. Finally, combining the third and fifth columns with ∧, we get the values for (P ∨Q)∧∼ (P ∧Q) in the sixth column. P Q (P ∨Q) (P ∧Q) ∼ (P ∧Q) (P ∨Q)∧∼ (P ∧Q) T T T T F F T F T F T T F T T F T T F F F F T F This truth table tells us that (P ∨Q)∧ ∼ (P ∧Q) is true precisely when one but not both of P and Q are true, so it has the meaning we intended. (Notice that the middle three columns of our truth table are just “helper columns” and are not necessary parts of the table. In writing truth tables, you may choose to omit such columns if you are confident about your work.) For another example, consider the following familiar statement con- cerning two real numbers x and y: The product xy equals zero if and only if x = 0 or y= 0. This can be modeled as (xy = 0) ⇔ (x = 0 ∨ y = 0). If we introduce letters P,Q and R for the statements xy= 0, x = 0 and y= 0, it becomes P ⇔ (Q∨R). Notice that the parentheses are necessary here, for without them we wouldn’t know whether to read the statement as P ⇔ (Q∨R) or (P ⇔Q)∨R. Making a truth table for P ⇔ (Q∨R) entails a line for each T/F combina- tion for the three statements P, Q and R. The eight possible combinations are tallied in the first three columns of the following table. P Q R Q∨R P ⇔ (Q∨R) T T T T T T T F T T T F T T T T F F F F F T T T F F T F T F F F T T F F F F F T We fill in the fourth column using our knowledge of the truth table for ∨. Finally the fifth column is filled in by combining the first and fourth columns with our understanding of the truth table for ⇔. The resulting table gives the true/false values of P ⇔ (Q∨R) for all values of P,Q and R. 50 Logic There are two pairs of logically equivalent statements that come up again and again throughout this book and beyond. They are prevalent enough to be dignified by a special name: DeMorgan’s laws. Fact 2.1 (DeMorgan’s Laws) 1. ∼ (P ∧Q) = (∼ P)∨ (∼Q) 2. ∼ (P ∨Q) = (∼ P)∧ (∼Q) The first of DeMorgan’s laws is verified by the following table. You are asked to verify the second in one of the exercises. P Q ∼ P ∼Q P ∧Q ∼ (P ∧Q) (∼ P)∨ (∼Q) T T F F T F F T F F T F T T F T T F F T T F F T T F T T DeMorgan’s laws are actually very natural and intuitive. Consider the statement ∼ (P ∧Q), which we can interpret as meaning that it is not the case that both P and Q are true. If it is not the case that both P and Q are true, then at least one of P or Q is false, in which case (∼ P)∨ (∼Q) is true. Thus ∼ (P ∧Q) means the same thing as (∼ P)∨ (∼Q). DeMorgan’s laws can be very useful. Suppose we happen to know that some statement having form ∼ (P ∨Q) is true. The second of DeMorgan’s laws tells us that (∼Q)∧(∼ P) is also true, hence ∼ P and ∼Q are both true as well. Being able to quickly obtain such additional pieces of information can be extremely useful. Here is a summary of some significant logical equivalences. Those that are not immediately obvious can be verified with a truth table. P ⇒Q = (∼Q)⇒ (∼ P) Contrapositive law (2.1) ∼ (P ∧Q) = ∼ P∨∼Q ∼ (P ∨Q) = ∼ P∧∼Q } DeMorgan’s laws (2.2) P ∧Q = Q∧P P ∨Q = Q∨P } Commutative laws (2.3) P ∧ (Q∨R) = (P ∧Q)∨ (P ∧R) P ∨ (Q∧R) = (P ∨Q)∧ (P ∨R) } Distributive laws (2.4) P ∧ (Q∧R) = (P ∧Q)∧R P ∨ (Q∨R) = (P ∨Q)∨R } Associative laws (2.5) Notice how the distributive law P ∧ (Q ∨R) = (P ∧Q)∨ (P ∧R) has the same structure as the distributive law p · (q+ r)= p · q+ p · r from algebra. Quantifiers 51 Concerning the associative laws, the fact that P∧(Q∧R)= (P∧Q)∧R means that the position of the parentheses is irrelevant, and we can write this as P ∧Q∧R without ambiguity. Similarly, we may drop the parentheses in an expression such as P ∨ (Q∨R). But parentheses are essential when there is a mix of ∧ and ∨, as in P ∨ (Q∧R). Indeed, P ∨ (Q∧R) and (P ∨Q)∧R are not logically equivalent. (See Exercise 13 for Section 2.6, below.) Exercises for Section 2.6 A. Use truth tables to show that the following statements are logically equivalent. 1. P ∧ (Q∨R)= (P ∧Q)∨ (P ∧R) 2. P ∨ (Q∧R)= (P ∨Q)∧ (P ∨R) 3. P ⇒Q = (∼ P)∨Q 4. ∼ (P ∨Q) = (∼ P)∧ (∼Q) 5. ∼ (P ∨Q∨R) = (∼ P)∧ (∼Q)∧ (∼ R) 6. ∼ (P ∧Q∧R) = (∼ P)∨ (∼Q)∨ (∼ R) 7. P ⇒Q = (P∧∼Q)⇒ (Q∧∼Q) 8. ∼ P ⇔Q = (P ⇒∼Q)∧ (∼Q ⇒ P) B. Decide whether or not the following pairs of statements are logically equivalent. 9. P ∧Q and ∼ (∼ P∨∼Q) 10. (P ⇒Q)∨R and ∼ ((P∧∼Q)∧∼ R) 11. (∼ P)∧ (P ⇒Q) and ∼ (Q ⇒ P) 12. ∼ (P ⇒Q) and P∧∼Q 13. P ∨ (Q∧R) and (P ∨Q)∧R 14. P ∧ (Q∨∼Q) and (∼ P)⇒ (Q∧∼Q) 2.7 Quantifiers Using symbols ∧, ∨, ∼, ⇒ and ⇔, we can deconstruct many English sentences into a symbolic form. As we have seen, this symbolic form can help us understand the logical structure of sentences and how different sentences may actually have the same meaning (as in logical equivalence). But these symbols alone are not powerful enough to capture the full meaning of every statement. To help overcome this defect, we introduce two new symbols that correspond to common mathematical phrases. The symbol “∀” stands for the phrase “For all” or “For every.” The symbol “∃” stands for the phrase “There exists a” or “There is a.” Thus the statement For every n ∈Z, 2n is even, can be expressed in either of the following ways: ∀n ∈Z, 2n is even, ∀n ∈Z, E(2n). 52 Logic Likewise, a statement such as There exists a subset X of N for which |X | = 5. can be translated as ∃X , (X ⊆N)∧ (|X | = 5) or ∃X ⊆N, |X | = 5 or ∃X ∈P(N), |X | = 5. The symbols ∀ and ∃ are called quantifiers because they refer in some sense to the quantity (i.e., all or some) of the variable that follows them. Symbol ∀ is called the universal quantifier and ∃ is called the existen- tial quantifier. Statements which contain them are called quantified statements. A statement beginning with ∀ is called a universally quan- tified statement, and one beginning with ∃ is called an existentially quantified statement. Example 2.5 The following English statements are paired with their translations into symbolic form. Every integer that is not odd is even. ∀n ∈Z,∼ (n is odd )⇒ (n is even), or ∀n ∈Z,∼O(n)⇒ E(n). There is an integer that is not even. ∃n ∈Z,∼ E(n). For every real number x, there is a real number y for which y3 = x. ∀x ∈R,∃ y ∈R, y3 = x. Given any two rational numbers a and b, it follows that ab is rational. ∀a,b ∈Q,ab ∈Q. Given a set S (such as, but not limited to, N, Z, Q etc.), a quantified statement of form ∀x ∈ S,P(x) is understood to be true if P(x) is true for every x ∈ S. If there is at least one x ∈ S for which P(x) is false, then ∀x ∈ S,P(x) is a false statement. Similarly, ∃x ∈ S,P(x) is true provided that P(x) is true for at least one element x ∈ S; otherwise it is false. Thus each statement in Example 2.5 is true. Here are some examples of quantified statements that are false: Example 2.6 The following false quantified statements are paired with their translations. Every integer is even. ∀n ∈Z,E(n). Translating English to Symbolic Logic 55 Likewise, the next sentence is a false statement (as it is not true for all x). If x is even, then x is a multiple of 6. This leads to the following significant interpretation of a conditional statement, which is more general than (but consistent with) the interpre- tation from Section 2.3. Definition 2.1 If P and Q are statements or open sentences, then “If P, then Q,” is a statement. This statement is true if it’s impossible for P to be true while Q is false. It is false if there is at least one instance in which P is true but Q is false. Thus the following are true statements: If x ∈R, then x2 +1> 0. If a function f is differentiable on R, then f is continuous on R. Likewise, the following are false statements: If p is a prime number, then p is odd. (2 is prime.) If f is a rational function, then f has an asymptote. (x2 is rational.) 2.9 Translating English to Symbolic Logic In writing (and reading) proofs of theorems, we must always be alert to the logical structure and meanings of the sentences. Sometimes it is necessary or helpful to parse them into expressions involving logic symbols. This may be done mentally or on scratch paper, or occasionally even explicitly within the body of a proof. The purpose of this section is to give you sufficient practice in translating English sentences into symbolic form so that you can better understand their logical structure. Here are some examples: Example 2.8 Consider the Mean Value Theorem from Calculus: If f is continuous on the interval [a,b] and differentiable on (a,b), then there is a number c ∈ (a,b) for which f ′(c)= f (b)− f (a)b−a . Here is a translation to symbolic form:(( f cont. on [a,b] )∧ ( f is diff. on (a,b)))⇒ (∃ c ∈ (a,b), f ′(c)= f (b)− f (a)b−a ). 56 Logic Example 2.9 Consider Goldbach’s conjecture, from Section 2.1: Every even integer greater than 2 is the sum of two primes. This can be translated in the following ways, where P is the set of prime numbers and S = {4,6,8,10, . . .} is the set of even integers greater than 2.( n ∈ S)⇒ (∃ p, q ∈ P, n = p+ q) ∀ n ∈ S, ∃ p, q ∈ P, n = p+ q These translations of Goldbach’s conjecture illustrate an important point. The first has the basic structure (n ∈ S)⇒Q(n) and the second has structure ∀ n ∈ S, Q(n), yet they have exactly the same meaning. This is significant. Every universally quantified statement can be expressed as a conditional statement. Fact 2.2 Suppose S is a set and Q(x) is a statement about x for each x ∈ S. The following statements mean the same thing: ∀ x ∈ S, Q(x) (x ∈ S)⇒Q(x). This fact is significant because so many theorems have the form of a conditional statement. (The Mean Value Theorem is an example!) In proving a theorem we have to think carefully about what it says. Sometimes a theorem will be expressed as a universally quantified statement but it will be more convenient to think of it as a conditional statement. Understanding the above fact allows us to switch between the two forms. We close this section with some final points. In translating a state- ment, be attentive to its intended meaning. Don’t jump into, for example, automatically replacing every “and” with ∧ and “or” with ∨. An example: At least one of the integers x and y is even. Don’t be led astray by the presence of the word “and.” The meaning of the statement is that one or both of the numbers is even, so it should be translated with “or,” not “and”: (x is even) ∨ (y is even). Finally, the logical meaning of “but” can be captured by “and.” The sentence “The integer x is even, but the integer y is odd,” is translated as (x is even) ∧ (y is odd). Negating Statements 57 Exercises for Section 2.9 Translate each of the following sentences into symbolic logic. 1. If f is a polynomial and its degree is greater than 2, then f ′ is not constant. 2. The number x is positive but the number y is not positive. 3. If x is prime then px is not a rational number. 4. For every prime number p there is another prime number q with q > p. 5. For every positive number ε, there is a positive number δ for which |x−a| < δ implies | f (x)− f (a)| < ε. 6. For every positive number ε there is a positive number M for which | f (x)−b| < ε, whenever x > M. 7. There exists a real number a for which a+ x = x for every real number x. 8. I don’t eat anything that has a face. 9. If x is a rational number and x 6= 0, then tan(x) is not a rational number. 10. If sin(x)< 0, then it is not the case that 0≤ x ≤π. 11. There is a Providence that protects idiots, drunkards, children and the United States of America. (Otto von Bismarck) 12. You can fool some of the people all of the time, and you can fool all of the people some of the time, but you can’t fool all of the people all of the time. (Abraham Lincoln) 13. Everything is funny as long as it is happening to somebody else. (Will Rogers) 2.10 Negating Statements Given a statement R, the statement ∼ R is called the negation of R. If R is a complex statement, then it is often the case that its negation ∼ R can be written in a simpler or more useful form. The process of finding this form is called negating R. In proving theorems it is often necessary to negate certain statements. We now investigate how to do this. We have already examined part of this topic. DeMorgan’s laws ∼ (P ∧Q) = (∼ P)∨ (∼Q) (2.6) ∼ (P ∨Q) = (∼ P)∧ (∼Q) (2.7) (from Section 2.6) can be viewed as rules that tell us how to negate the statements P ∧Q and P ∨Q. Here are some examples that illustrate how DeMorgan’s laws are used to negate statements involving “and” or “or.” 60 Logic Example 2.13 Negate the following statement about a particular (i.e., constant) number a. R : If a is odd then a2 is odd. Using Equation (2.10), we get the following negation. ∼ R : a is odd and a2 is not odd. Example 2.14 This example is like the previous one, but the constant a is replaced by a variable x. We will negate the following statement. R : If x is odd then x2 is odd. As discussed in Section 2.8, we interpret this as the universally quantified statement R : ∀x ∈Z, (x odd)⇒ (x2 odd). By Equations (2.8) and (2.10), we get the following negation for R. ∼ (∀x ∈Z, (x odd)⇒ (x2 odd)) = ∃x ∈Z,∼ ((x odd)⇒ (x2 odd)) = ∃x ∈Z, (x odd)∧∼ (x2 odd). Translating back into words, we have ∼ R : There is an odd integer x whose square is not odd. Notice that R is true and ∼ R is false. The above Example 2.14 showed how to negate a conditional statement P(x) ⇒ Q(x). This type of problem can sometimes be embedded in more complex negation. See Exercise 5 below (and its solution). Exercises for Section 2.10 Negate the following sentences. 1. The number x is positive, but the number y is not positive. 2. If x is prime, then px is not a rational number. 3. For every prime number p, there is another prime number q with q > p. 4. For every positive number ε, there is a positive number δ such that |x−a| < δ implies | f (x)− f (a)| < ε. 5. For every positive number ε, there is a positive number M for which | f (x)−b| < ε whenever x > M. 6. There exists a real number a for which a+ x = x for every real number x. Logical Inference 61 7. I don’t eat anything that has a face. 8. If x is a rational number and x 6= 0, then tan(x) is not a rational number. 9. If sin(x)< 0, then it is not the case that 0≤ x ≤π. 10. If f is a polynomial and its degree is greater than 2, then f ′ is not constant. 11. You can fool all of the people all of the time. 12. Whenever I have to choose between two evils, I choose the one I haven’t tried yet. (Mae West) 2.11 Logical Inference Suppose we know that a statement of form P ⇒ Q is true. This tells us that whenever P is true, Q will also be true. By itself, P ⇒Q being true does not tell us that either P or Q is true (they could both be false, or P could be false and Q true). However if in addition we happen to know that P is true then it must be that Q is true. This is called a logical inference: Given two true statements we can infer that a third statement is true. In this instance true statements P ⇒Q and P are “added together” to get Q. This is described below with P ⇒Q and P stacked one atop the other with a line separating them from Q. The intended meaning is that P ⇒Q combined with P produces Q. P ⇒Q P Q P ⇒Q ∼Q ∼ P P ∨Q ∼ P Q Two other logical inferences are listed above. In each case you should convince yourself (based on your knowledge of the relevant truth tables) that the truth of the statements above the line forces the statement below the line to be true. Following are some additional useful logical inferences. The first expresses the obvious fact that if P and Q are both true then the statement P ∧Q will be true. On the other hand, P ∧Q being true forces P (also Q) to be true. Finally, if P is true, then P ∨Q must be true, no matter what statement Q is. P Q P ∧Q P ∧Q P P P ∨Q These inferences are so intuitively obvious that they scarcely need to be mentioned. However, they represent certain patterns of reasoning that we will frequently apply to sentences in proofs, so we should be cognizant of the fact that we are using them. 62 Logic 2.12 An Important Note It is important to be aware of the reasons that we study logic. There are three very significant reasons. First, the truth tables we studied tell us the exact meanings of the words such as “and,” “or,” “not” and so on. For instance, whenever we use or read the “If..., then” construction in a mathematical context, logic tells us exactly what is meant. Second, the rules of inference provide a system in which we can produce new information (statements) from known information. Finally, logical rules such as DeMorgan’s laws help us correctly change certain statements into (potentially more useful) statements with the same meaning. Thus logic helps us understand the meanings of statements and it also produces new meaningful statements. Logic is the glue that holds strings of statements together and pins down the exact meaning of certain key phrases such as the “If..., then” or “For all” constructions. Logic is the common language that all mathematicians use, so we must have a firm grip on it in order to write and understand mathematics. But despite its fundamental role, logic’s place is in the background of what we do, not the forefront. From here on, the beautiful symbols ∧, ∨, ⇒, ⇔, ∼, ∀ and ∃ are rarely written. But we are aware of their meanings constantly. When reading or writing a sentence involving mathematics we parse it with these symbols, either mentally or on scratch paper, so as to understand the true and unambiguous meaning. Counting Lists 65 for the choice for the third entry, which is either a or x. Thus, in the diagram there are 3 ·2 ·2= 12 paths from left to right, each corresponding to a particular choice for each entry in the list. The corresponding lists are tallied at the far-right end of each path. So, to answer our original question, there are 12 possible lists with the stated properties. first choice second choice third choice Resulting list a b c 5 7 5 7 5 7 a x a x a x x a x a x a (a,5,a) (a,5, x) (a,7,a) (a,7, x) (b,5,a) (b,5, x) (b,7,a) (b,7, x) (c,5,a) (c,5, x) (c,7,a) (c,7, x) Figure 3.1. Constructing lists of length 3 We summarize the type of reasoning used above in an important fact called the multiplication principle. Fact 3.1 (Multiplication Principle) Suppose in making a list of length n there are a1 possible choices for the first entry, a2 possible choices for the second entry, a3 possible choices for the third entry and so on. Then the total number of different lists that can be made this way is the product a1 ·a2 ·a3 · · · · ·an. So, for instance, in the above example we had a1 = 3,a2 = 2 and a3 = 2, so the total number of lists was a1 ·a2 ·a3 = 3 ·2 ·2 = 12. Now let’s look at some additional examples of how the multiplication principle can be used. Example 3.1 A standard license plate consists of three letters followed by four numbers. For example, JRB-4412 and MMX-8901 are two standard license plates. (Vanity plates such as LV2COUNT are not included among the standard plates.) How many different standard license plates are possible? 66 Counting To answer this question, note that any standard license plate such as JRB-4412 corresponds to a length-7 list (J,R,B,4,4,1,2), so the question can be answered by counting how many such lists are possible. We use the multiplication principle. There are a1 = 26 possibilities (one for each letter of the alphabet) for the first entry of the list. Similarly, there are a2 = 26 possibilities for the second entry and a3 = 26 possibilities for the third entry. There are a4 = 10 possibilities for the fourth entry, and likewise a5 = a6 = a7 = 10. Therefore there are a total of a1 ·a2 ·a3 ·a4 ·a5 ·a6 ·a7 = 26 ·26 ·26 ·10 ·10 ·10 ·10= 175,760,000 possible standard license plates. There are two types of list-counting problems. On one hand, there are situations in which the same symbol or symbols may appear multiple times in different entries of the list. For example, license plates or telephone numbers can have repeated symbols. The sequence CCX-4144 is a perfectly valid license plate in which the symbols C and 4 appear more than once. On the other hand, for some lists repeated symbols do not make sense or are not allowed. For instance, imagine drawing 5 cards from a standard 52-card deck and laying them in a row. Since no 2 cards in the deck are identical, this list has no repeated entries. We say that repetition is allowed in the first type of list and repetition is not allowed in the second kind of list. (Often we call a list in which repetition is not allowed a non-repetitive list.) The following example illustrates the difference. Example 3.2 Consider making lists from symbols A, B, C, D, E, F, G. (a) How many length-4 lists are possible if repetition is allowed? (b) How many length-4 lists are possible if repetition is not allowed? (c) How many length-4 lists are possible if repetition is not allowed and the list must contain an E? (d) How many length-4 lists are possible if repetition is allowed and the list must contain an E? Solutions: (a) Imagine the list as containing four boxes that we fill with selections from the letters A,B,C,D,E,F and G, as illustrated below. , , ,( ) 7 choices 7 choices 7 choices 7 choices There are seven possibilities for the contents of each box, so the total number of lists that can be made this way is 7 ·7 ·7 ·7= 2401. Counting Lists 67 (b) This problem is the same as the previous one except that repetition is not allowed. We have seven choices for the first box, but once it is filled we can no longer use the symbol that was placed in it. Hence there are only six possibilities for the second box. Once the second box has been filled we have used up two of our letters, and there are only five left to choose from in filling the third box. Finally, when the third box is filled we have only four possible letters for the last box. , , ,( ) 7 choices 6 choices 5 choices 4 choices Thus the answer to our question is that there are 7 ·6 ·5 ·4= 840 lists in which repetition does not occur. (c) We are asked to count the length-4 lists in which repetition is not allowed and the symbol E must appear somewhere in the list. Thus E occurs once and only once in each such list. Let us divide these lists into four categories depending on whether the E occurs as the first, second, third or fourth entry. These four types of lists are illustrated below. , , , , , , , , , , , ,E E E E Type 1 Type 2 Type 3 Type 4 ( ( ( () ) ) ) 6 choices 6 choices 6 choices 6 choices 5 choices 5 choices 5 choices 5 choices 4 choices 4 choices 4 choices 4 choices Consider lists of the first type, in which the E appears in the first entry. We have six remaining choices (A,B,C,D,F or G) for the second entry, five choices for the third entry and four choices for the fourth entry. Hence there are 6 ·5 ·4= 120 lists having an E in the first entry. As indicated in the above diagram, there are also 6 ·5 ·4= 120 lists having an E in the second, third or fourth entry. Thus there are 120+120+120+120= 480 such lists all together. (d) Now we must find the number of length-four lists where repetition is allowed and the list must contain an E. Our strategy is as follows. By Part (a) of this exercise there are 7 ·7 ·7 ·7 = 74 = 2401 lists where repetition is allowed. Obviously this is not the answer to our current question, for many of these lists contain no E. We will subtract from 2401 the number of lists that do not contain an E. In making a list that does not contain an E, we have six choices for each list entry (because 70 Counting 3.2 Factorials In working the examples from Section 3.1, you may have noticed that often we need to count the number of non-repetitive lists of length n that are made from n symbols. In fact, this particular problem occurs with such frequency that a special idea, called a factorial, is introduced to handle it. The table below motivates this idea. The first column lists successive integer values n (beginning with 0) and the second column contains a set { A,B, · · ·} of n symbols. The third column contains all the possible non-repetitive lists of length n which can be made from these symbols. Finally, the last column tallies up how many lists there are of that type. Notice that when n = 0 there is only one list of length 0 that can be made from 0 symbols, namely the empty list ( ). Thus the value 1 is entered in the last column of that row. n Symbols Non-repetitive lists of length n made from the symbols n! 0 {} ( ) 1 1 { A } (A) 1 2 { A,B } (A,B), (B, A) 2 3 { A,B,C } (A,B,C), (A,C,B), (B,C, A), (B, A,C), (C, A,B), (C,B, A) 6 4 { A,B,C,D } (A,B,C,D), (A,B,D,C), (A,C,B,D), (A,C,D,B), (A,D,B,C), (A,D,C,B)(B,A,C,D), (B,A,D,C), (B,C,A,D), (B,C,D,A), (B,D, A,C), (B,D,C,A) (C,A,B,D), (C,A,D,B), (C,B,A,D), (C,B,D,A), (C,D,A,B), (C,D,B,A) (D,A,B,C), (D,A,C,B), (D,B,A,C), (D,B,C,A), (D,C,A,B), (D,C,B,A) 24 ... ... ... ... For n > 0, the number that appears in the last column can be computed using the multiplication principle. The number of non-repetitive lists of length n that can be made from n symbols is n(n−1)(n−2) · · ·3·2·1. Thus, for instance, the number in the last column of the row for n = 4 is 4 ·3 ·2 ·1= 24. The number that appears in the last column of Row n is called the factorial of n. It is denoted as n! (read “n factorial”). Here is the definition: Definition 3.1 If n is a non-negative integer, then the factorial of n, denoted n!, is the number of non-repetitive lists of length n that can be made from n symbols. Thus 0! = 1 and 1! = 1. If n > 1, then n! = n(n−1)(n−2) · · ·3 ·2 ·1. Factorials 71 It follows that 0! = 1 1! = 1 2! = 2 ·1= 2 3! = 3 ·2 ·1= 6 4! = 4 ·3 ·2 ·1= 24 5! = 5 ·4 ·3 ·2 ·1= 120 6! = 6 ·5 ·4 ·3 ·2 ·1= 720, and so on. Students are often tempted to say 0!= 0, but this is wrong. The correct value is 0!= 1, as the above definition and table tell us. Here is another way to see that 0! must equal 1: Notice that 5!= 5 ·4 ·3 ·2 ·1= 5 · (4 ·3 ·2 ·1)= 5 ·4!. Also 4!= 4 ·3 ·2 ·1= 4 · (3 ·2 ·1)= 4 ·3!. Generalizing this reasoning, we have the following formula. n!= n · (n−1)! (3.1) Plugging in n = 1 gives 1!= 1·(1−1)!= 1·0!, that is, 1!= 1·0!. If we mistakenly thought 0! were 0, this would give the incorrect result 1!= 0. We round out our discussion of factorials with an example. Example 3.3 This problem involves making lists of length seven from the symbols 0,1,2,3,4,5 and 6. (a) How many such lists are there if repetition is not allowed? (b) How many such lists are there if repetition is not allowed and the first three entries must be odd? (c) How many such lists are there in which repetition is allowed, and the list must contain at least one repeated number? To answer the first question, note that there are seven symbols, so the number of lists is 7! = 5040. To answer the second question, notice that the set { 0,1,2,3,4,5,6 } contains three odd numbers and four even numbers. Thus in making the list the first three entries must be filled by odd numbers and the final four must be filled with even numbers. By the multiplication principle, the number of such lists is 3 ·2 ·1 ·4 ·3 ·2 ·1= 3!4!= 144. To answer the third question, notice that there are 77 = 823,543 lists in which repetition is allowed. The set of all such lists includes lists that are non-repetitive (e.g., (0,6,1,2,4,3,5)) as well as lists that have some repetition (e.g., (6,3,6,2,0,0,0)). We want to compute the number of lists that have at least one repeated number. To find the answer we can subtract the number of non-repetitive lists of length seven from the total number of possible lists of length seven. Therefore the answer is 77 −7!= 823,543−5040= 818,503. 72 Counting We close this section with a formula that combines the ideas of the first and second sections of the present chapter. One of the main problems of Section 3.1 was as follows: Given n symbols, how many non-repetitive lists of length k can be made from the n symbols? We learned how to apply the multiplication principle to obtain the answer n(n−1)(n−2) · · · (n−k+1). Notice that by cancellation this value can also be written as n(n−1)(n−2) · · · (n−k+1)(n−k)(n−k−1) · · ·3 ·2 ·1 (n−k)(n−k−1) · · ·3 ·2 ·1 = n! (n−k)! . We summarize this as follows: Fact 3.2 The number of non-repetitive lists of length k whose entries are chosen from a set of n possible entries is n!(n−k)! . For example, consider finding the number of non-repetitive lists of length five that can be made from the symbols 1,2,3,4,5,6,7,8. We will do this two ways. By the multiplication principle, the answer is 8 ·7 ·6 ·5 ·4= 6720. Using the formula from Fact 3.2, the answer is 8!(8−5)! = 8!3! = 40,3206 = 6720. The new formula isn’t really necessary, but it is a nice repackaging of an old idea and will prove convenient in the next section. Exercises for Section 3.2 1. What is the smallest n for which n! has more than 10 digits? 2. For which values of n does n! have n or fewer digits? 3. How many 5-digit positive integers are there in which there are no repeated digits and all digits are odd? 4. Using only pencil and paper, find the value of 100!95! . 5. Using only pencil and paper, find the value of 120!118! . 6. There are two 0’s at the end of 10! = 3,628,800. Using only pencil and paper, determine how many 0’s are at the end of the number 100!. 7. Compute howmany 9-digit numbers can be made from the digits 1,2,3,4,5,6,7,8,9 if repetition is not allowed and all the odd digits occur first (on the left) followed by all the even digits (i.e. as in 137598264, but not 123456789). 8. Compute how many 7-digit numbers can be made from the digits 1,2,3,4,5,6,7 if there is no repetition and the odd digits must appear in an unbroken sequence. (Examples: 3571264 or 2413576 or 2467531, etc., but not 7234615.) Counting Subsets 75 To begin, note that (5 3 ) is the number of 3-element subsets of { a,b, c,d, e } . These are listed in the following table. We see that in fact (5 3 )= 10. { a,b,c }{ a,b,d }{ a,b,e } { a,c,d } { a,c,e } { a,d,e }{ b,c,d } { b,c,e } { b,d,e } { c,d,e } (5 3 ) 3! The formula will emerge when we expand this table as follows. Taking any one of the ten 3-element sets above, we can make 3! different non- repetitive lists from its elements. For example, consider the first set { a,b, c } . The first column of the following table tallies the 3!= 6 different lists that can be the letters { a,b, c } . The second column tallies the lists that can be made from { a,b,d } , and so on. abc abd abe acd ace ade bcd bce bde cde acb adb aeb adc aec aed bdc bec bed ced bac bad bae cad cae dae cbd cbe dbe dce bca bda bea cda cea dea cdb ceb deb dec cba dba eba dca eca eda dcb ecb edb edc cab dab eab dac eac ead dbc ebc ebd ecd 3! (5 3 ) This table has (5 3 ) columns and 3! rows, so it has a total of 3! (5 3 ) lists. But notice also that the table consists of every non-repetitive length-3 list that can be made from the symbols { a,b, c,d, e } . We know from Fact 3.2 that there are 5!(5−3)! such lists. Thus the total number of lists in the table is 3! (5 3 )= 5!(5−3)! . Dividing both sides of this equation by 3!, we get( 5 3 ) = 5! 3!(5−3)! . Working this out, you will find that it does give the correct value of 10. But there was nothing special about the values 5 and 3. We could do the above analysis for any (n k ) instead of (5 3 ) . The table would have (n k ) columns and k! rows. We would get( n k ) = n! k!(n−k)! . We summarize this as follows: 76 Counting Fact 3.3 If n,k ∈Z and 0≤ k ≤ n, then ( n k ) = n! k!(n−k)! . Otherwise ( n k ) = 0. Let’s now use our new knowledge to work some exercises. Example 3.4 How many 4-element subsets does { 1,2,3,4,5,6,7,8,9 } have? The answer is (9 4 )= 9!4!(9−4)! = 9!4!5! = 9·8·7·6·5!4!5! = 9·8·7·64! = 9·8·7·624 = 126. Example 3.5 A single 5-card hand is dealt off of a standard 52-card deck. How many different 5-card hands are possible? To answer this, think of the deck as being a set D of 52 cards. Then a 5-card hand is just a 5-element subset of D. For example, here is one of many different 5-card hands that might be dealt from the deck.{ 7 ♣ , 2 ♣ , 3 ♥ , A ♠ , 5 ♦ } The total number of possible hands equals the number of 5-element subsets of D, that is( 52 5 ) = 52! 5! ·47! = 52 ·51 ·50 ·49 ·48 ·47! 5! ·47! = 52 ·51 ·50 ·49 ·48 5! = 2,598,960. Thus the answer to our question is that there are 2,598,960 different five-card hands that can be dealt from a deck of 52 cards. Example 3.6 This problem concerns 5-card hands that can be dealt off of a 52-card deck. How many such hands are there in which two of the cards are clubs and three are hearts? Solution: Think of such a hand as being described by a list of length two of the form ( { ∗ ♣ , ∗ ♣ } , { ∗ ♥ , ∗ ♥ , ∗ ♥ } ) , where the first entry is a 2-element subset of the set of 13 club cards, and the second entry is a 3-element subset of the set of 13 heart cards. There are (13 2 ) choices for the first entry and (13 3 ) choices for the second entry, so by the multiplication principle there are (13 2 )(13 3 )= 13!2!11! 13!3!10! = 22,308 such lists. Answer: There are 22,308 possible 5-card hands with two clubs and three hearts. Example 3.7 Imagine a lottery that works as follows. A bucket contains 36 balls numbered 1,2,3,4, ...,36. Six of these balls will be drawn randomly. For $1 you buy a ticket that has six blanks: ääääää . You fill in the blanks with six different numbers between 1 and 36. You win $1,000,000 Counting Subsets 77 if you chose the same numbers that are drawn, regardless of order. What are your chances of winning? Solution: In filling out the ticket you are choosing six numbers from a set of 36 numbers. Thus there are (36 6 ) = 36!6!(36−6)! = 1,947,792 different combinations of numbers you might write. Only one of these will be a winner. Your chances of winning are one in 1,947,792. Exercises for Section 3.3 1. Suppose a set A has 37 elements. How many subsets of A have 10 elements? How many subsets have 30 elements? How many have 0 elements? 2. Suppose A is a set for which |A| = 100. How many subsets of A have 5 elements? How many subsets have 10 elements? How many have 99 elements? 3. A set X has exactly 56 subsets with 3 elements. What is the cardinality of X? 4. Suppose a set B has the property that ∣∣{X : X ∈P(B), |X | = 6}∣∣= 28. Find |B|. 5. How many 16-digit binary strings contain exactly seven 1’s? (Examples of such strings include 0111000011110000 and 0011001100110010, etc.) 6. ∣∣{X ∈P({0,1,2,3,4,5,6,7,8,9}) : |X | = 4}∣∣= 7. ∣∣{X ∈P({0,1,2,3,4,5,6,7,8,9}) : |X | < 4}∣∣= 8. This problem concerns lists made from the symbols A,B,C,D,E,F,G,H,I. (a) How many length-5 lists can be made if repetition is not allowed and the list is in alphabetical order? (Example: BDEFI or ABCGH, but not BACGH.) (b) How many length-5 lists can be made if repetition is not allowed and the list is not in alphabetical order? 9. This problem concerns lists of length 6 made from the letters A,B,C,D,E,F, without repetition. How many such lists have the property that the D occurs before the A? 10. A department consists of 5 men and 7 women. From this department you select a committee with 3 men and 2 women. In how many ways can you do this? 11. How many positive 10-digit integers contain no 0’s and exactly three 6’s? 12. Twenty-one people are to be divided into two teams, the Red Team and the Blue Team. There will be 10 people on Red Team and 11 people on Blue Team. In how many ways can this be done? 13. Suppose n and k are integers for which 0≤ k ≤ n. Use the formula (nk)= n!k!(n−k)! to show that (n k )= ( nn−k). 14. Suppose n,k ∈Z, and 0≤ k ≤ n. Use Definition 3.2 alone (without using Fact 3.3) to show that (n k )= ( nn−k). 80 Counting In fact this turns out to be true for every n. This result is known as the binomial theorem, and it is worth mentioning here. It tells how to raise a binomial x+ y to a non-negative integer power n. Theorem 3.1 (Binomial Theorem) If n is a non-negative integer, then (x+ y)n = (n0)xn + (n1)xn−1 y+ (n2)xn−2 y2 + (n3)xn−3 y3 +·· ·+ ( nn−1)xyn−1 + (nn)yn. For now we will be content to accept the binomial theorem without proof. (You will be asked to prove it in an exercise in Chapter 10.) You may find it useful from time to time. For instance, you can apply it if you ever need to expand an expression such as (x+ y)7. To do this, look at Row 7 of Pascal’s triangle in Figure 3.2 and apply the binomial theorem to get (x+ y)7 = x7 +7x6 y+21x5 y2 +35x4 y3 +35x3 y4 +21x2 y5 +7xy6 + y7. For another example, (2a−b)4 = ((2a)+ (−b))4 = (2a)4 +4(2a)3(−b)+6(2a)2(−b)2 +4(2a)(−b)3 + (−b)4 = 16a4 −32a3b+24a2b2 −8ab3 +b4. Exercises for Section 3.4 1. Write out Row 11 of Pascal’s triangle. 2. Use the binomial theorem to find the coefficient of x8 y5 in (x+ y)13. 3. Use the binomial theorem to find the coefficient of x8 in (x+2)13. 4. Use the binomial theorem to find the coefficient of x6 y3 in (3x−2y)9. 5. Use the binomial theorem to show ∑nk=0(nk)= 2n. 6. Use Definition 3.2 (page 74) and Fact 1.3 (page 12) to show ∑nk=0(nk)= 2n. 7. Use the binomial theorem to show ∑nk=0 3k(nk)= 4n. 8. Use Fact 3.3 (page 76) to derive Equation 3.2 (page 78). 9. Use the binomial theorem to show (n 0 )− (n1)+ (n2)− (n3)+ (n4)−·· ·+ (−1)n(nn)= 0. 10. Show that the formula k (n k )= n(n−1k−1) is true for all integers n,k with 0≤ k ≤ n. 11. Use the binomial theorem to show 9n =∑nk=0(−1)k(nk)10n−k. 12. Show that (n k )( k m )= (nm)(n−mk−m). 13. Show that (n 3 )= (22)+ (32)+ (42)+ (52)+·· ·+ (n−12 ). 14. The first five rows of Pascal’s triangle appear in the digits of powers of 11: 110 = 1, 111 = 11, 112 = 121, 113 = 1331 and 114 = 14641. Why is this so? Why does the pattern not continue with 115? Inclusion-Exclusion 81 3.5 Inclusion-Exclusion Many counting problems involve computing the cardinality of a union A∪B of two finite sets. We examine this kind of problem now. First we develop a formula for |A∪B|. It is tempting to say that |A∪B| must equal |A|+ |B|, but that is not quite right. If we count the elements of A and then count the elements of B and add the two figures together, we get |A|+ |B|. But if A and B have some elements in common, then we have counted each element in A∩B twice. A B Therefore |A| + |B| exceeds |A ∪B| by |A ∩B|, and consequently |A ∪B| = |A|+ |B|− |A∩B|. This can be a useful equation. |A∪B| = |A|+ |B|− |A∩B| (3.3) Notice that the sets A, B and A∩B are all generally smaller than A∪B, so Equation (3.3) has the potential of reducing the problem of determining |A ∪B| to three simpler counting problems. It is sometimes called an inclusion-exclusion formula because elements in A∩B are included (twice) in |A|+|B|, then excluded when |A∩B| is subtracted. Notice that if A∩B =;, then we do in fact get |A∪B| = |A|+ |B|; conversely if |A∪B| = |A|+ |B|, then it must be that A∩B =;. Example 3.8 A 3-card hand is dealt off of a standard 52-card deck. How many different such hands are there for which all 3 cards are red or all three cards are face cards? Solution: Let A be the set of 3-card hands where all three cards are red (i.e., either ♥ or ♦). Let B be the set of 3-card hands in which all three cards are face cards (i.e., J,K or Q of any suit). These sets are illustrated below. A = {{ 5 ♥ , K ♦ , 2 ♥ } , { K ♥ , J ♥ , Q ♥ } , { A ♦ , 6 ♦ , 6 ♥ } , . . . } (Red cards) B = {{ K ♠ , K ♦ , J ♣ } , { K ♥ , J ♥ , Q ♥ } , { Q ♦ , Q ♣ , Q ♥ } , . . . } (Face cards) 82 Counting We seek the number of 3-card hands that are all red or all face cards, and this number is |A ∪B|. By Formula (3.3), |A ∪B| = |A| + |B| − |A ∩B|. Let’s examine |A|, |B| and |A ∩B| separately. Any hand in A is formed by selecting three cards from the 26 red cards in the deck, so |A| = (263 ). Similarly, any hand in B is formed by selecting three cards from the 12 face cards in the deck, so |B| = (123 ). Now think about A∩B. It contains all the 3-card hands made up of cards that are red face cards. A∩B = {{ K ♥ , K ♦ , J ♥ } , { K ♥ , J ♥ , Q ♥ } , { , Q ♦ , J ♦ , Q ♥ } , . . . } (Red face cards) The deck has only 6 red face cards, so |A∩B| = (63). Now we can answer our question. The number of 3-card hands that are all red or all face cards is |A∪B| = |A|+ |B|− |A∩B| = (263 )+ (123 )− (63) = 2600+220−20= 2800. There is an analogue to Equation (3.3) that involves three sets. Consider three sets A, B and C, as represented in the following Venn Diagram. A B C Using the same kind of reasoning that resulted in Equation (3.3), you can convince yourself that |A∪B∪C| = |A|+ |B|+ |C|− |A∩B|− |A∩C|− |B∩C|+ |A∩B∩C|. (3.4) There’s probably not much harm in ignoring this one for now, but if you find this kind of thing intriguing you should definitely take a course in combinatorics. (Ask your instructor!) As we’ve noted, Equation (3.3) becomes |A∪B| = |A|+ |B| if it happens that A∩B =;. Also, in Equation (3.4), note that if A∩B =;, A∩C =; and B∩C =;, we get the simple formula |A∪B∪C| = |A|+ |B|+ |C|. In general, we have the following formula for n sets, none of which overlap. It is sometimes called the addition principle. Fact 3.4 (Addition Principle) If A1, A2, . . . , An are sets with A i∩A j =; whenever i 6= j, then |A1 ∪ A2 ∪·· ·∪ An| = |A1|+ |A2|+ · · ·+ |An|. Part II How to Prove Conditional Statements CHAPTER 4 Direct Proof It is time to prove some theorems. There are various strategies for doingthis; we now examine the most straightforward approach, a technique called direct proof. As we begin, it is important to keep in mind the meanings of three key terms: Theorem, proof and definition. A theorem is a mathematical statement that is true and can be (and has been) verified as true. A proof of a theorem is a written verification that shows that the theorem is definitely and unequivocally true. A proof should be understandable and convincing to anyone who has the requisite background and knowledge. This knowledge includes an understanding of the meanings of the mathematical words, phrases and symbols that occur in the theorem and its proof. It is crucial that both the writer of the proof and the readers of the proof agree on the exact meanings of all the words, for otherwise there is an intolerable level of ambiguity. A definition is an exact, unambiguous explanation of the meaning of a mathematical word or phrase. We will elaborate on the terms theorem and definition in the next two sections, and then finally we will be ready to begin writing proofs. 4.1 Theorems A theorem is a statement that is true and has been proved to be true. You have encountered many theorems in your mathematical education. Here are some theorems taken from an undergraduate calculus text. They will be familiar to you, though you may not have read all the proofs. Theorem: Let f be differentiable on an open interval I and let c ∈ I. If f (c) is the maximum or minimum value of f on I, then f ′(c)= 0. Theorem: If ∑∞k=1 ak converges, then limk→∞ ak = 0. Theorem: Suppose f is continuous on the interval [a,b]. Then f is integrable on [a,b]. Theorem: Every absolutely convergent series converges.