University:
Amherst College
Course:
MATH 220 | Mathematical Reasoning and Proof
Academic year:

2024
Views:

366

Pages:

6
Author:

Cierra Dawson

Math 220, Solutions to Practice Problems 1 1. Let A = {1, 2, 3, 4, 5}, B = {2, 5, 1, 7}, C = {3, 4, 4, 4, 7}. Compute each of the following sets: Answers. Before starting, it will help to rewrite B = {1, 2, 5, 7} and C = {3, 4, 7}. So: a. A ∩ B = {1, 2, 5}. b. A ∩ C = {3, 4}. c. B ∩ C = {7}. d. A ∩ B ∩ C = ∅. e. A ∪ B = {1, 2, 3, 4, 5, 7}. f. (A ∪ C) ∩ B = {1, 2, 3, 4, 5, 7} ∩ {1, 2, 5, 7} = {1, 2, 5, 7}. g. A r C = {1, 2, 5}. h. [(B∪C)∩A]∪(CrB) = [{1, 2, 3, 4, 5, 7}∩A]∪{3, 4} = {1, 2, 3, 4, 5}∪{3, 4} = {1, 2, 3, 4, 5}. i. C × C = {(3, 3), (3, 4), (3, 7), (4, 3), (4, 4), (4, 7), (7, 3), (7, 4), (7, 7)}. j. (A ∩ C) × (B ∩ C) = {3, 4} × {7} = {(3, 7), (4, 7)}. 2. Let A, B, C be sets. If A ⊆ B, prove that (C r B) ⊆ (C r A). Proof. Given x ∈ C r B. Then x ∈ C, but x 6∈ B. If we had x ∈ A, then x ∈ B, a contradiction. Thus, x 6∈ A. Since x ∈ C and x 6∈ A, we have x ∈ C r A. QED 3. Show that the converse of problem 2 fails; that is, give examples of set A, B, C such that (C r B) ⊆ (C r A), but A 6⊆ B. Answer/Proof. Choose A = {1}, B = {2}, and C = {3}. Then (C r B) = {3} ⊆ {3} = (C r A), but A 6⊆ B, since 1 ∈ A but 1 6∈ B. QED [There are many ways to do this; just choose your sets so that A is not a subset of C.] 4. For each of the following sets, write out all the elements in the form {blah, blah, . . . , blah}. Answers. a. ∅ = {}. b. P(∅) = {∅}. c. P P(∅) = ∅, {∅} . 5. Let A, B, C, D be sets. Prove that (A × C) ∩ (B × D) = (A ∩ B) × (C ∩ D). Proof. (⊆): Given (x, y) ∈ (A × C) ∩ (B × D), we have (x, y) ∈ A × C, and hence x ∈ A and y ∈ C; we also have (x, y) ∈ B × D, and hence x ∈ B and y ∈ D. Thus, x ∈ A ∩ B, and y ∈ C ∩ D. That is, (x, y) ∈ (A ∩ B) × (C ∩ D). QED (⊆) (⊇): Given (x, y) ∈ (A ∩ B) × (C ∩ D), we have x ∈ A ∩ B and y ∈ C ∩ D. Thus, x ∈ A and y ∈ C, so that (x, y) ∈ A × C. Similarly, x ∈ B and y ∈ D, so that (x, y) ∈ B × D. That is, (x, y) ∈ (A × C) ∩ (B × D). QED (⊇) 6. Let A, B, C, D be sets. Prove that (A × C) ∪ (B × D) ⊆ (A ∪ B) × (C ∪ D). Proof. Given (x, y) ∈ (A × C) ∪ (B × D), we have two cases. Case 1: (x, y) ∈ A × C. Then x ∈ A ⊆ A ∪ B, and y ∈ C ⊆ C ∪ D. Hence, (x, y) ∈ (A ∪ B) × (C ∪ D). Case 2: (x, y) ∈ B × D. Then x ∈ B ⊆ A ∪ B, and y ∈ D ⊆ C ∪ D. Hence, (x, y) ∈ (A ∪ B) × (C ∪ D). QED 7. Give examples of sets A, B, C, D such that (A × C) ∪ (B × D) 6= (A ∪ B) × (C ∪ D). Answer/Proof. Choose A = {1}, B = {2}, C = {3}, and D = {4}. Then (A × C) ∪ (B × D) = {(1, 3)} ∪ {(2, 4)} = {(1, 3), (2, 4)}, but (A ∪ B) × (C ∪ D) = {1, 2} × {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4)}. The two sets are not equal because, for example, (1, 4) belongs to the second one but not the first. QED [Again, there are many ways to do this.] \h [h 1 1i 1i 1 1 + ,3 + and , where [a, b] denotes the usual closed 1 + ,3 + n n n n n∈N n∈N interval [a, b] = {x ∈ R | a ≤ x ≤ b}. Don’t forget to prove your claimed set equalities. [h \h 1 1i 1 1i Answers. We claim that 1 + ,3 + = (1, 4], and 1 + ,3 + = [2, 3]. n n n n n∈N n∈N Proof of first claim: (⊆): Given x ∈ LHS, there is some n ∈ N such that x ∈ [1 + 1/n, 3 + 1/n]. Thus, 8. Find 1<1+ 1 1 ≤ x ≤ 3 + ≤ 4, n n and hence x ∈ (1, 4]. (⊇): Given x ∈ (1, 4], first suppose x ≥ 3. Then h 1 1i x ∈ [3, 4] ⊆ [2, 4] = 1 + , 3 + ⊆ LHS. 1 1 Otherwise, we have 1 < x < 3. Since x − 1 > 0, we can pick n ∈ N with n > 1/(x − 1). Then 1/n < x − 1, so that 1+ 1 1 3, then since x − 3 > 0, we can pick n ∈ N with n > 1/(x − 3). Then 1/n < x − 3, so that h 1 1 1i 3 + < x, and hence x 6∈ 1 + , 3 + , n n n contradicting the fact that x ∈ LHS. Thus, x ≤ 3. Since 2 ≤ x ≤ 3, we have x ∈ [2, 3]. (⊇): Given x ∈ [2, 3], then for any n ∈ N, we have 1+ 1 1 ≤2≤x≤3<3+ , n n Thus, x ∈ LHS. \ 9. Find (−t, ∞) and t∈(0,∞) Answers. We claim that h 1 1i and hence x ∈ 1 + , 3 + . n n QED (second claim). [ (−t, ∞). t∈(0,∞) \ [ (−t, ∞) = [0, ∞), and t∈(0,∞) (−t, ∞) = R. t∈(0,∞) Proof of first claim: (⊆): Given x ∈ LHS, we have x ∈ (−1, ∞) ⊆ R. [It remains to show that x ≥ 0.] Suppose, by way of contradiction, that x < 0. Let t = −x > 0. Then x = −t 6∈ (−t, ∞), and hence x 6∈ LHS, a contradiction. Thus, x 6< 0; since x ∈ R, we must have x ≥ 0. That is, x ∈ [0, ∞). (⊇): Given x ∈ [0, ∞), and given t ∈ (0, ∞), we have x ≥ 0 > −t, so that x ∈ (−t, ∞). Since this is true for all t ∈ (0, ∞), we have x ∈ LHS. QED (first claim) Proof of second claim: (⊆): Given x ∈ LHS, there is some t ∈ (0, ∞) such that x ∈ (−t, ∞) ⊆ R, and hence x ∈ R. (⊇): Given x ∈ R, we consider two cases. Case 1. If x ≥ 0, then x ∈ (−1, ∞) ⊆ LHS Case 2. If x 6≥ 0, then x < 0. Let t = 1 − x ∈ (0, ∞). Then x = 1 − t > −t. Thus, x ∈ (−t, ∞) ⊆ LHS. QED (second claim) \ [ 10. Find (t, ∞) and (t, ∞). t∈(0,∞) t∈(0,∞) Answers. We claim that \ (t, ∞) = ∅, and t∈(0,∞) [ (t, ∞) = (0, ∞). t∈(0,∞) Proof of first claim: To show LHS is empty, we proceed by contradiction. Suppose there were an element x ∈ LHS. Then in particular, x ∈ (1, ∞), so x > 0. Choosing t = x ∈ (0, ∞), then we have x 6∈ (t, ∞), and hence x 6∈ LHS, a contradiction. Thus, the set on the LHS must be empty. QED (first claim) Proof of second claim: (⊆): Given x ∈ LHS, there is some t ∈ (0, ∞) such that x ∈ (t, ∞). Thus, x > t > 0, and hence x ∈ (0, ∞). (⊇): Given x ∈ (0, ∞), let t = x/2 ∈ (0, ∞). Then x > t, and hence x ∈ (t, ∞) ⊆ LHS. QED (second claim) 11. For each positive integer k ∈ N, define Sk = {n ∈ N | k divides n}. For any integers k, m ∈ N, prove that k|m ⇐⇒ Sm ⊆ Sk . Proof. (=⇒): Given k, m ∈ N such that k|m, and given n ∈ Sm , we have m|n. That is, there are integers i, j ∈ N such that m = ki and n = mj. Thus, n = (ki)j = k(ij). Since ij ∈ N, we have k|n, and hence n ∈ Sk . (⇐=): Given k, m ∈ N such that Sm ⊆ Sk , we have m = m · 1, and hence m|m. Thus, m ∈ Sm ⊆ Sk , meaning that k divides m, i.e., k|m. QED 12. With notation as in problem 11 above, let T = N r (S7 ∪ S13 ). Let A = {S7 , S13 , T }. Decide whether or not A is a partition of N; prove your answer. Answer/Proof. No, A is not a partition, because S7 and S13 are different (since 7 ∈ S7 rS13 , for example), but 7 · 13 ∈ S7 ∩ S13 , and hence S7 ∩ S13 6= ∅. QED 13. For each r ∈ [0, ∞), let Cr = {(x, y) ∈ R2 | x2 + y 2 = r2 }. Let C = {Cr | r ∈ [0, ∞)}. Decide whether or not C is a partition of R2 ; prove your answer. Answer/Proof. Yes, C is a partition of R2 . Each Cr is a subset of R2 by definition, and for each r ∈ [0, ∞), we have (r, 0) ∈ Cr , since r2 + 02 = r2 . Thus, Cr 6= ∅ for all r ∈ [0, ∞). In addition, if r, s ∈ [0, ∞) have Cr ∩ Cs 6= ∅, pick (x, y) ∈ Cr ∩ Cs . Then r 2 = x2 + y 2 = s 2 , and hence r = ±s. However, since r, s ≥ 0, in fact we have r = s. Thus, the sets Cr are mutually disjoint. p 2 2 2 2 2 Finally, given (x, y) ∈ R , we S have x +y ≥2 0, and hence we may set r = x + y ∈ [0, ∞). Then (x, y) ∈ Cr . That is, r∈[0,∞) Cr = R . QED 14. Demonstrate, using a truth table, that (P ∧ (∼ Q)) ∨ ((∼ P ) ∨ Q) is a tautology, i.e., that it is always true, regardless of whether P and Q are true or false. Answer/Proof : P Q ∼ P ∼ Q P ∧ (∼ Q) (∼ P ) ∨ Q (P ∧ (∼ Q)) ∨ ((∼ P ) ∨ Q) T T F F F T T T F F T T F T F T T F F T T F F T T F T T 15. Prove the following statement: ∀a ∈ N, ∃b, c ∈ N s.t. ab = c3 . Proof. Given a ∈ N, let b = a2 ∈ N, and let c = a ∈ N. Then ab = a · a2 = a3 = c3 . [There are many other ways to do this, but this is probably the easiest.] QED 16. Give the negation of the following statement: ∀a ∈ N, ∃b, c ∈ N s.t. a = bc3 and c 6= 1. Answer. ∃a ∈ N s.t. ∀b, c ∈ N, either a 6= bc3 or c = 1. 17. Prove the statement you gave as the answer to problem 16 above. Proof. Let a = 1 ∈ N. Given b, c ∈ N, if c = 1, we are done. Thus, we may assume that c ≥ 2. Since b ≥ 1, we have bc3 ≥ 1 · 23 = 8 > 1 = a, and hence a 6= bc3 . QED 18. Consider the statement “Everybody loves a lover.” Let’s assume that this statement is true, where a “lover” means anybody who loves somebody. Under that assumption, together with the assumption that Fred loves Jane, prove that everybody loves everybody. Proof. Let S be the set of all people. Given x, y ∈ S, then because Fred is a lover, y must love Fred. Thus, y is a lover, and therefore x loves y. QED 19. Find the contrapositive, the converse, and the negation of the following implication statement: (S ⊆ T ) ∨ (a = b) ⇒ (a, b) ∈ S × T. Answer. Contrapositive: (a, b) 6∈ S × T ⇒ (S 6⊆ T ) ∧ (a 6= b) . Converse: (a, b) ∈ S × T ⇒ (S ⊆ T ) ∨ (a = b) . Negation: (S ⊆ T ) ∨ (a = b) ∧ (a, b) 6∈ S × T . 20. Let n ∈ Z. Prove the following are equivalent: a. 5|(n + 2) b. 5|(2n − 1) c. 5|(6n + 7) Proof. (a ⇒ b): There is some m ∈ Z such that n + 2 = 5m. Thus, 2n − 1 = 2(n + 2) − 4 − 1 = 2(5m) − 5 = 5(2m − 1). Since 2m − 1 ∈ Z, we have 5|(2n − 1). (b ⇒ c): There is some m ∈ Z such that 2n − 1 = 5m. Thus, 6n + 7 = 3(2n − 1) + 10 = 3(5m) + 10 = 5(3m + 2). Since 3m + 2 ∈ Z, we have 5|(6n + 7). (c ⇒ a): There is some m ∈ Z such that 6n + 7 = 5m. Thus, n + 2 = 6n + 7 − 5n − 5 = 5m − 5n − 5 = 5(m − n − 1). Since m − n − 1 ∈ Z, we have 5|(n + 2). QED 21. Prove that there is no quadratic polynomial f (x) = ax2 + bx + c with the properties that f (0) = 3, f (1) = f (−1) = 2, and f (2) = 5. Proof. We proceed by contradiction. Suppose there were such a polynomial f (x) = ax2 + bx + c. Then 3 = f (0) = c. In addition 2 = f (1) = a+b+c = a+b+3, so that a+b = −1. Moreover, 2 = f (−1) = a−b+c = a−b+3, so that a − b = −1. Adding these two equations, we have 2a = −2, and hence a = −1; then b = 0. Thus, 5 = f (2) = 4a + 2b + c = −4 + 0 + 3 = −1, a contradiction. QED 22. For any x ∈ R, prove that there exists a unique y ∈ R such that 5x + 3y = 7. Proof. (Existence): Given x ∈ R, let y = (7 − 5x)/3 ∈ R. Then 5x + 3y = 5x + (7 − 5x) = 7. (Uniqueness): Given x ∈ R and y1 , y2 ∈ R such that 5x + 3y1 = 7 = 5x + 3y2 . Then 3y1 = 3y2 , and hence y1 = y2 . QED 23. Prove, for every n ∈ N, that 1 + 3 + 5 + · · · + (2n − 1) = n2 . Proof. By induction on n. Base Case: For n = 1, LHS = 1 = 12 , as desired. Inductive Step: Given that the claim holds for n = k ∈ N, we have 1 + 3 + · · · + 2(k + 1) − 1 = 1 + 3 + · · · + (2k − 1) + (2k + 1) = k 2 + 2k + 1 = (k + 1)2 , where the second equality is by the inductive hypothesis. QED 24. Define a sequence a1 , a2 , a3 , . . . of real numbers by a1 = 1, and for n ≥ 1, an+1 = 3 − 1 . an Prove that for every n ∈ N r {1, 2}, we have an ∈ (2, 3), and an > an−1 . Proof. By induction on n ≥ 3. Base Case: We compute a2 = 3 − 1/1 = 2, and a3 = 3 − 1/2 = 5/2. Since 5/2 ∈ (2, 3), and 5/2 > 2 = a2 , the base case holds. Inductive Step: Given that the claim holds for n = k ∈ N, we have ak+1 = 3 − 1 < 3, ak ak+1 = 3 − since ak > 2 > 0, and 1 1 >3− = ak > 2. ak ak−1 Thus, we have both ak+1 > ak , and ak+1 ∈ (ak , 3) ⊆ (2, 3). QED 25. Prove, for all n ∈ N, that the integer 1 + 32n−1 is divisible by 4. Proof. By induction on n. Base Case: For n = 1, we have 1 + 32−1 = 1 + 3 = 4, which is divisible by 4. Inductive Step: Given that the claim holds for n = k ∈ N, there is some m ∈ N such that 1 + 32n−1 = 4m. Therefore, 1 + 32(k+1)−1 = 1 + 32k−1 − 32k−1 + 32k+1 = 4m + 32k−1 (9 − 1) = 4(m + 2 · 32k−1 ). Since m + 2 · 32k−1 ∈ N, the integer 1 + 32(k+1)−1 is divisible by 4. QED

Math 220 Solutions to Practice Problems 1

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock