Practice Problem Midterm 3

1. Let A be the set of all integers which are divisible by 3 and B be the set of real numbers which is less than 7 and greater than 3. (a) Use the symbolic language to rewrite A. Solution: A = {x 2 Z | 3 | x} (b) Use the condition to rewrite B Solution: B = {x 2 R | 3 < x < 7} (c) List all elements in A \ B Solution: A \ B = {0, 3, 6} (d) Please the definition of the cardinality to compute |A \ B| (i.e. you should give a bijection). Solution: Consider the function f : N3 ! A \ B as follows: x 1 2 3 f(x) 0 3 6 It is a bijection. Then |A \ B| = 3 (e) Let C be a set of all positive divisors of 9. Please write down C Solution: C = {1, 3, 9} (f) Compute |C| and |C ⇥ (A \ B)|. Solution: Consider the function h : N3 ! C as follows: x 1 2 3 h(x) 1 3 9 It is a bijection. Then |C| = 3. We use the formula for the Cartesian product to get that |C ⇥ (A \ B)| = |C| ⇥ |A \ B| = 3⇥3=9 2. Let A be a set of rational numbers which is greater than 0 and less than 8 and f be function defined as follows: ( 8 when x  0 f (x) = 1 when x > 0. x (a) Give a symbolic form of the set A Solution: A = {x 2 Q | 0 < x < 8} (b) Let B be the pre-image f Solution: 1 ({8}). Please write down the set B in symbolic language. 1 B = {x | f (x) = 8} = { } [ ( 1, 0] 8 (c) List all elements in A \ B Solution: 1 A\B ={ } 8 (d) Let C be the set of all positive divisor of 20. Please write down C and A \ C. Solution: C = {1, 2, 4, 5, 10, 20} A \ C = {1, 2, 4, 5} (e) Use the definition of the cardinality to compute |C| and use the formula to compute |C ⇥ (A \ C)|. Solution: Consider the function f : N6 ! C as follows: x 1 2 3 4 5 6 f(x) 1 2 4 5 10 20 It is a bijection. Then |C| = 6 Consider the function h : N4 ! A \ C as follows: x 1 2 3 4 h(x) 1 2 4 5 It is a bijection. Then |C \ A| = 4 We use the formula for the Cartesian product to get that |C ⇥ (C \ A)| = 6 ⇥ 4 = 24 (f) Compute min A \ Z and max A \ C and find the greatest common divisor of these two integers. Solution: We have that A \ Z = {1, 2, 3, 4, 5, 6, 7}. Then min A \ Z = 2. We have that max A \ C = 5. Then, we have that gcd(1, 5) = 1 Page 2 3. Let f : R ! R be a function defined as follows: ( 1 + a when x  1 f (x) = x + 3 when x 1 where a is a constant (a) Please find the constant a such that f is a well-defined function. Solution: When x  1, then f (x) = a + 1. Hence, f (1) = a + 1. When x 1, then f (x) = x + 3, Hence, f (1) = 1 + 3 = 4. We get that f (1) = a + 1 = 4. We can conclude that a = 3. (b) Find out the set of the pre-image f Solution: f 1 1 (( 1, 9)) (( 1, 9)) = {x 2 R | f (x) 2 ( 1, 9)} = ( 1, 5) (c) Is f | (2, 1) an injection? If yes, please prove it. If not, please give the reason. Solution: Yes, f |(2,+1) = x + 3 is injection. Proof. For any x1 and x2 in (2, +1), f (x1 ) = f (x2 ) =) x1 + 3 = x2 + 3 =) x1 = x2 . We can conclude that f |(2,1) is injection. (d) Is f a surjection ? If yes, please prove it. If not, please give the reason and point out Im(f ). Solution: No, f is not surjection. Because f (x) 0 for x 2 R. The image Im(f ) = [4, 1) For any y 2 [4, 1), we choose x = y 3 1 and get that f (x) = x + 3 = y 3+3=y 4. Consider two functions f and g as follows: f :Z!Z g:Z!Z Page 3 (a) Consider a new function f ⇥ g : Z ⇥ Z ! Z ⇥ Z as follows: f ⇥g : Z⇥Z !Z⇥Z (x, y) ! (f (x), g(y)) Prove that if f and g are injection, then f ⇥ g is also injection. Solution: Idea: It is sufficient to show that for any (x1 , y1 ), (x2 , y2 ) in Z ⇥ Z (f ⇥ g)(x1 , y1 ) = (f ⇥ g)(x2 , y2 ) =) (x1 , y1 ) = (x2 , y2 ) Proof. For any (x1 , y1 ) and (x2 , y2 ) in Z ⇥ Z, assume that (f ⇥ g)(x1 , y1 ) = (f ⇥ g)(x2 , y2 ). Then (f (x1 ), gy1 ) = (f ⇥ g)(x1 , y1 ) = (f ⇥ g)(x2 , y2 ) = (f (x2 ), g(y2 )). That is, f (x1 ) = f (x2 ) and g(x1 ) = g(x2 ). Since f and g are injection, then x1 = x2 and y1 = y2 . That is, (x1 , y1 ) = (x2 , y2 ). We can conclude that f ⇥ g is injection. (b) Prove that if f and g are surjection, then f ⇥ g are also surjection. Solution: Proof. For any (x, y) 2 Z ⇥ Z, since f and g are surjection, then there are x0 2 Z and y 0 2 Z such that f (x0 ) = x g(y 0 ) = y That is, (f ⇥ g)(x0 , y 0 ) = (x, y). We can conclude that f ⇥ g is surjection. (c) Let h : Z ! Z be a function. Consider the function F : Z⇥Z !Z⇥Z . (x, y) ! (f (x), h(x) + g(y)) If f (x) and g(x) are injection, please justify whether F is also injection. If yes, please prove it. If not, please use an example to explain it. Solution: Yes, it is injection. Proof. For any (x1 , y1 ) and (x2 , y2 ) in Z ⇥ Z, assume that F (x1 , y1 ) = F (x2 , y2 ). That is, f (x1 ) = f (x2 ) (1) h(x1 ) + g(y1 ) = h(x2 ) + g(y2 ) (2) Since f is injection, from Equation (1), we have that x1 = x2 . Then, Equation (2) implies g(y1 ) = g(y2 ). Since g is injection, then y1 = y2 . We can conclude that (x1 , y1 ) = (x2 , y2 ). Page 4 5. It is well-known that |X [ Y | = |X| + |Y | (3) |X \ Y |. (a) There are 40 students in a classroom. Each student can swim or ski. 20 students can swim and 30 students can ski. Use the formula (3) to find how many student can both swim and ski ? (Hint: X is the set of students who can swim and Y is the set of students who can ski. Please explain the mean of X \ Y . ) Solution: • X = { students who can swim } • Y = { students who can ski} • X \ Y = { students who can both swim and ski } • X [ Y = { all students in the class} We have that |X| = 20, |Y | = 30, |X [ Y | = 40. Use Equation (3) to get that |X \ Y | = |X| + |Y | |X [ Y | = 20 + 30 40 = 10. We can conclude that ten student can both swim and ski. (b) Recall that (A [ B) \ C = (A \ C) [ (B \ C) Use Formula (3) to prove that |(A [ B) \ C| = |A \ C| + |B \ C| |A \ B \ C| Solution: Proof. We choose X = A \ C and Y = B \ C and then use Equation (3) to get that |(A \ C) [ (B \ C)| = |A \ C| + |B \ C| |(A \ C) \ (B \ C)| Since (A [ B) \ C = (A \ C) [ (B \ C) and (A \ C) \ (B \ C) = A \ B \ C, then we have that |(A [ B) \ C| = |A \ C| + |B \ C| Page 5 |A \ B \ C| (c) There are some children in the school. Ten children can both swim and sing. Nine children can both ski and swim. Three children can swim, sing and ski. Use (b) to find out how many children (1) could ski or sing and (2) could swim. (Hint: Please point out three sets, A, B , C and which set is the required one. ) Solution: • A = { students who can sing } • B = { students who can ski} • C = { students who can swin} • A \ C = { students who can both swim and ski } and |A \ C| = 10 • B \ C = { students who can both sing and swim} and |B \ C| = 9 • A \ B \ C = { students who can sing, ski and swim} and |A \ B \ C| = 3 • (A [ B) \ C = { students who (1) could sing or ski and (2) could swim } We use (b) to get that |(A [ B) \ C| = |A \ C| + |B \ C| |A \ B \ C| = 10 + 9 3 = 16. 6. Let A and B be two finite sets. Consider the set of functions from A to B Fun(A, B) = {f | f : A ! B} (a) Let A = {x} and B = {y1 , y2 , · · · yn }. For yi 2 B, there is a map fi : A ! B with fi (x) = yi . Please construct a bijection between Nn and Fun(A, B) and prove |Fun(A, B)| = n Solution: Let G be function form Nn ! Fun(A, B) as follows: G(i) = fi for i 2 Nn In the following, we should prove it is a bijection. Part for the Injection: For any i and j in Nn , assume that G(i) = G(j). Then fi (x) = fj (x). That is, yi = fi (x) = fj (x) = yj =) i = j We get that G is injection. Page 6 Part for the Surjection: For any map g 2 Fun(A, B), we assume that Im(g) = {yi } for some i 2 Nn (since A just have a unique element).We have that g(x) = yi = fi (x) That is, g = fi = G(i). We can conclude that G is surjection. Since G : Nn ! Fun(A, B) is a bijection, then |F(A, B)| = n (b) Let A be non-empty set and x 2 A. Consider the map as follows F : Fun(A, B) ! F(A {x}, B) ⇥ B f ! (f |A {x} , f (x)) Prove that F is a bijection. Solution: Proof. Part for the Injection: For any f and g in Fun(A, B), assume that F (f ) = F (g). Then (f |A {x} , f (x) = (g |A {x} , g(x)). That is, f |A {x} = g |A {x} and f (x) = g(x) That is, f = g : A ! B. We could say that F is injection. Part for the Surjection: For any (h, y) 2 Fun(A {x}, B) ⇥ B, consider a new function ĥ : A ! B as follows: ( h(a) when a 2 A {x} ĥ(a) = y when a = x That is, F (ĥ) = (h, y). We can conclude that G is surjection. We can conclude that F is bijection. (c) Prove that |Fun(A, B)| = |F(A Solution: {x}, B)| ⇥ |B| Proof. We use (b) to get a bijection F : Fun(A, B) ! Fun(A Therefore, |Fun(A, B)| = |Fun(A {x}|, B) ⇥ B. {x}|, B) ⇥ B| = |Fun(A {x}, B)| ⇥ |B|. (d) Use (c) and the inductive argument on |A| to prove that |Fun(A, B)| = |B||A| Page 7 Solution: Proof. When |A| = 1, we use (a) to get that |Fun(A, B)| = |B| = |B||A| . Assume that it is true that for any finite sets X and Y , if |X| = n, then Fun(X, Y ) = |Y ||X| . When |A| = n + 1, choose an element x 2 A. Then |A inductive hypothesis to get that |Fun(A {x}, B)| = |B||A We use (c) to get that |Fun(A, B)| = Fun(A {n}| {x}| = n + 1 = |B||A| 1 . {x}, B) ⇥ |B| = |B||A| Page 8 1 = n. Use the 1 ⇥ |B| = |B||A| .