Practice Problem Final

1. Consider the following statement: For any positive integer n, if n is divisible by 6, then n is divisible by 2. (a) Please use symbolic language to rewrite it. Solution: 8n 2 Z>0 , 6 | n =) 2 | n. (b) Please write down its denial in the affirmative form. Solution: 9n 2 Z>0 , 6 | n ^ 2 6 | n. (c) Is the statement is correct or false? If yes, please prove it. If not, please disprove it. Solution: Yes, it is correct. Proof: Since 6 | n, there is an integer k such that n = 6 · k = 2 · (3k) Then, n is also divisible by 2. (d) Please write down its contrapositive statement. Solution: 8n 2 Z>0 , 2 6 | n =) 6 6 | n. 2. Let A be the set of rational numbers which are greater than 2 and less than 7 and B be the set of all integers divisible by 3. (a) Use the condition and the symbolic language to rewrite A and B. Solution: A = {x 2 Q | 1 < x < 7}, B = {x 2 Z | 3 | x} (b) Please all elements in A \ B and compute |A \ B|. (Hint: Please write down the bijection. ) Solution: A \ B = {3, 6} (c) Prove that if x 2 A \ B, then x2 9x + 18 = 0 Solution: Since A \ B = {3, 6}, we have two cases: x = 3 or x = 6. When x = 3, then x2 9x + 18 = 32 9 · 3 + 18 = 0 When x = 6, then x2 9x + 18 = 62 9 · 3 + 18 = 0 (d) Let C be a finite subset of (30, 1). If |C| = n, please compute |(A \ B) ⇥ C| and |(A \ B) [ C| Solution: We have that |(A \ B) ⇥ C| = |A \ B| ⇥ |C| = 2n Since A \ B = {3, 6}, we have that (A \ B) \ C = ;. |(A \ B) [ C| = |A \ B| + |C| = 2 + n. 3. Let f (x) : R ! R be a function defined as follows: f (x) = ( x + a, when x 1 3 when x  1 (a) Find the constant a so that f is a function from R to R. Solution: When f (x) = x + a for x 2 [1, +1), then f (1) = 1 + a When f (x) = 3 for x 2 ( 1, 1], then f (1) = 3 We have that a + 1 = 3. Then, a = 2. (b) Is f |(3,1) : (3, 1) ! R injection or not ? If yes, please prove it. If not, disprove it. Solution: We have that It is injection. The proof is as follows: f |(3,1) = x + 2 For any x1 and x2 in (3, 1), f (x1 ) = f (x2 ) =) x1 + 2 = x2 + 2 =) x1 = x2 . We can conclude that f is an injection. Page 2 (c) Justify whether f |(0,1) : (0, 1) ! R is an surjection or not. If yes, please prove it. If no, point out the image (you do not need to prove it). Solution: No. Its image is [2, 1) p (d) consider the function g(x) = 3 x : R ! R. Verify whether g is a bijection or not. If yes, please prove it and find out its inverse. If not, please explain the reason. Solution: Yes, it is a bijection Its inverse function is x = y 3 . For injection, let x1 and x2 be any two elements in R3 . We have that g(x1 ) = g(x2 ) =) p 3 x1 = p 3 x2 =) x1 = x2 . We have that g(x) is an injection. For surjection, let y be any element in R. We choose x = y 3 and have that p g(x) = 3 y 3 = y We have that g(x) is a surjection. We can conclude that g : R ! R is a bijection. 4. Let {an } be a sequence of real numbers satisfying that a1 = 1 an = 2an 1 (a) Use the inductive argument to prove that an = 2n Solution: Proof When n = 1, then a1 = 1 = 21 1 . It is done. Suppose that an = 2n 1 is true. Then, we have that an+1 = 2an = 2 ⇥ 2n 1 = 2n = 2(n+1) Page 3 1 1 for n 2 Z>0 (b) Recall that 1 X n=1 k X an = a1 = ak + n=1 k 1 X an n=1 k P Use the inductive argument to prove that an = (2k n=1 Solution: P Proof When k = 1, then 1n=1 an = a1 = 1 = 21 Suppose that Pk n=1 an = 2 k 1) for n 2 Z>0 1. It is done. 1 is true. Then, we have that k+1 X an = ak+1 + n=1 =2 k X an n=1 (k+1) 1 k = 2k+1 +2 1 1 5. Let {fn (x)} be a sequence of functions from R to R and f (x) be a function from R to R. The function f (x) is called the limit of the sequence {fn (x)} as n goes to infinity ( written as lim fn (x) = f (x)), if for any x 2 R and any ✏ > 0, there is a positive integer N such n!1 that for any integer n, we have that when n N , then |fn (x) f (x)|  ✏. (a) Use the symbolic language to rewrite it f (x) = lim fn (x) () n!1 Solution: f (x) = lim fn (x) () 8x 2 R 8✏ > 0, 9N 2 Z>0 , 8n 2 Z>0 , n n!1 Page 4 N =) |f (x) fn (x)|  ✏ (b) Write down its useful denial. f (x) 6= lim fn (x) () n!1 Solution: f (x) 6= lim fn (x) () 9x 2 R 9✏ > 0, 8N 2 Z>0 , 9n 2 Z>0 , n n!1 N ^ |f (x) fn (x)| > ✏ (c) Consider a sequence of functions fn (x) as follows: fn (x) = x . n Please prove that lim fn (x) = 0 n!1 Solution: Proof: For any x 2 R and ✏ > 0, we choose that N = [ |x| ] + 1 and then have that ✏ n N =) n [ |x| ]+1 ✏ n |x| x =) | |  ✏. ✏ n 6. Recall that a relation ⇠ over a set X is called an equivalent relation if it satisfies that for any x, y and z in X, we have that • x⇠x • x⇠y () y⇠x • x ⇠ y ^ y ⇠ z =) x ⇠ z Consider the relation ⇠ on R ⇥ (R {0}) as follows: For any (x1 , y1 ) and (x2 , y2 ) in R ⇥ (R {0}) (x1 , y1 ) ⇠ (x2 , y2 ) () x1 y2 x2 y1 = 0 (a) Prove that ⇠ is an equivalent relation on R ⇥ (R Solution: Proof: Reflexive property: For any (x, y) 2 R ⇥ R x·y {0}, we have that y · x = 0 =) (x, y) ⇠ (x, y) Symmetric property: For any (x1 , y1 ), (x2 , y2 ) in R ⇥ R (x1 , y1 ) ⇠ (x2 , y2 ) =) x1 · y2 {0}). x2 · y1 = 0 =) x2 · y1 Page 5 {0}, we have that x1 · y2 = 0 =) (x2 , y2 ) ⇠ (x1 , y1 ) Symmetric property: For any (x1 , y1 ), (x2 , y2 ), (x3 , y3 ) in R ⇥ R {0}, we have that (x1 , y1 ) ⇠ (x2 , y2 ) ^ (x2 , y2 ) ⇠ (x2 , y2 ) ⇠ (x3 , y3 ) =) x1 · y2 x2 · y1 = 0 ^ x2 · y3 x3 · y2 = 0 x2 x2 x3 x1 =) = ^ = y1 y2 y2 y3 x1 x3 =) = =) x1 y3 x3 y1 = 0 y1 y3 =) (x1 , y1 ) ⇠ (x3 , y3 ) (b) Consider the function f : R ⇥ (R {0}) ! R f : R ⇥ (R {0}) ! R x (x, y) ! y Prove that f is surjection. Solution: Proof. For any element x 2 R, we choose (x, 1) 2 R ⇥ (R f (x, 1) = {0}) and have that x =x 1 (c) For any any (x1 , y1 ) and (x2 , y2 ) in R ⇥ (R {0}), prove that f (x1 , y1 ) = f (x2 , y2 ) if only if (x1 , y1 ) ⇠ (x2 , y2 ) Solution: Proof. f (x1 , y1 ) = f (x2 , y2 ) =) x1 x2 = =) x1 y2 y1 y2 x2 y1 = 0 =) (x1 , y1 ) ⇠ (x2 , y2 ) (d) Use (c) to define the function f¯ from the equivalent class R ⇥ (R follows: f¯ : R ⇥ (R {0})/ ⇠ ! R x [(x, y)] ! y {0})/ ⇠ to R as where [(x, y)] is the equivalent class containing (x, y). Please use (b) and (c) to prove that f¯ is a bijection. (Hint: [(x1 , y1 )] = [(x2 , y2 )] in R ⇥ (R {0})/ ⇠ means that (x1 , y1 ) ⇠ (x2 , y2 ).) Page 6 Solution: Proof. Show that f¯ is well-defined: For any [(x1 , y1 )] = [(x2 , y2 )], we have that (x1 , y1 ) ⇠ (x2 , y2 ). Then, we show that (x1 , y1 ) ⇠ (x2 , y2 ) =) x1 x2 = =) f¯([(x1 , y2 )]) = f¯([(x2 , y2 )]) y1 y2 Hence, the function f¯ is well-defined. For injection For any [(x1 , y1 )], [(x2 , y2 )] in X/ ⇠, we have that f¯([(x1 , x2 )]) = f¯([(x2 , y2 )]) =) f (x1 , y1 ) = f (x2 , y2 ) Use (c) to get that (x1 , y1 ) ⇠ (x2 , y2 ). Namely, [(x1 , y1 )] = [(x2 , y2 )]. We can conclude that f¯ is injection. For surjection: For any element x 2 R, we choose (x, 1) 2 R ⇥ (R {0}) and have that x f¯([(x, 1)]) = f (x, 1) = = x 1 7. Let x, y and z be three positive integers satisfying that 1 1 1 + + =1 x y z In the following, we will find all pairs (x, y, z) 2 Z3 satisfying the above equation. (a) Prove by contradiction that min{x, y, z}  3 Solution: Proof. Suppose that min{x, y, z} > 3. Then x > 3, y > 3 and z > 3. We have that 1 1 1 1 1 1 1 1 1 < , < and < =) + + <1 x 3 y 3 z 3 x y z However, 1 x + 1 y + 1 z = 1, which leads to a contradiction. In the following, we assume that 1 < x  y  z. Use (a) to have that 1 < x  3. That is, we have two cases: (1) x = 2 and (2). x = 3. Page 7 (b) If x = 2, prove that (z 2)(y 2) = 4 Solution: Proof. When x = 2, we have that 1 1 1 + + =1 2 y z That’s, yz = 2y + 2z. We can get that (y 2)(z 2) = 4. (c) Use (b) to prove that if x = 2, then (y, z) = (4, 4) or (y, z) = (3, 6). Solution: From (b), we have that (y 2)(z 2) = 4 Since y and z are positive integers and z y, then we have two cases: When y 2 = 1 and z 2 = 4, then y = 3 and z = 6. When y 2 = 2 and z 2 = 2, then y = 4 and z = 6 (d) If x = 3, prove that (2y 3)(2y 3) = 9 Solution: Proof. When x = 3, we have that 1 1 1 + + =1 3 y z That’s, 2yz = 3y + 3z. We can get that (2yz = 3y + 3z =) 4yz = 6y + 6z =) 4yz 6y + 6z + 9 = 9 =) (2y (e) Use (c) to prove that if x = 3, then (y, z) = (3, 3). (Hint: z y Solution: From (c), we have that (2y 3)(2z 3) = 9 Since y and z are positive integers and z y, then we have two cases: When 2y 3 = 3 and 2z 3 = 3, then y = 3 and z = 3. Page 8 x) 3)(2z 3) = 9. When 2y 3 = 1 and 2z 3 = 9, then y = 2 and z = 6. However, it is impossible ,because 3=xyz We can conclude that (y, z) = (3, 3) (f) Find out all pairs (x, y, z) 2 Z3 satisfying that 1 1 1 + + =1 x y z Solution: From (c) and (e), we assume that x  y  y  z and get three solutions as follows: (x, y, z) = (2, 4, 4), (2, 3, 6), (3, 3, 3) Page 9