4 CSE 191 Fall 2016 Due: Friday 10/28/2016 This assignment will touch on different properties and concepts of functions. We have numerous ways to define a function. The most familiar representation of a function is of the form f (x) = . . ., but, fundamentally, a function is nothing more than a set of pairs representing a relation between an input and an output. As a reminder: You may not use outside references when completing the homework. You must complete all your work on your own. By submitting your homework you are stating that it is your original work (not your friend's work or found from somewhere on the internet). When collaborating with other students in the class, you should not write anything while discussing homework problems. If you do not write solutions in front of one another, then you will have no issues completing problems in your own words and will avoid using the words of someone else. Academic integrity violations will result in an F in the course. If you have questions regarding this, please feel free to ask prior to any incidents and prior to submission. There are a total of 100 points on the assignment. (1) The drawing below shows the arrow diagram for a function f1 . (4 points each for 12 points total) b c d e a w x y z Answer each question below by describing each set in set notation. (1a) What is domain(f1 )? (1b) What is codomain(f1 )? (1c) What is range(f1 )? (2) Consider the sets X2 = {1, 2, 3, 4, 5} and Y2 = {0, 1, 2, 3, 4} and the function f2 : X2 Y2 defined by f2 (x) = |x 2|. (8+2 points for 10 points total) (2a) Draw the arrow diagram for f2 . (2b) What is the range of f2 ? (describe the set representing range(f2 )) (3) Let X3 = {1, 2, 3, 4} and Y3 = {1, 2, 3, 4, 5}. Using the formal definition of a function, determine which of the following subsets of X3 Y3 correspond to functions of X3 Y3 . Justify your answer by providing reasons why each is or is not a function. (6 points each for 18 points total) (3a) f = {(1, 4), (2, 3), (1, 2), (3, 1), (4, 1)} (3b) f = {(1, 0), (2, 1), (3, 1)} (3c) f = {(1, 0), (2, 1), (3, 1), (4, 2), (1, 0)} (4) Consider the mapping f4 : R R where f4 (x) = (6 points) 1 . (x2 4) Prove that f4 is not a function. (5) Suppose g : A B is a function. Let A1 , A2 A. Prove that g(A1 A2 ) = g(A1 ) g(A2 ). Hint: show set equality by taking an element in the left set and showing it belongs to the right set, then complete the other direction. (12 points) (6) Consider the following functions from Z Z Z. Which functions are onto? Justify your answer (modified from zyBooks exercise 4.3.1). (6 points each for 18 points total) (6a) f (x, y) = 2x 4y (6b) f (x, y) = |x| |y| c (6c) f (x, y) = b x+y 3 (7) Consider the following functions. For each function, determine if it is 1-1, onto, and invertible. If a function is invertible, provide the inverse function. Justify each of your answers (modified from zyBooks exercise 4.3.4). (12 points each for 24 points total) (7a) Let A5 = {1, 2, 3, 4, 5, 6, 7, 8}. Let f5 : P(A) {0, 1, 2, 3, 4, 5, 6, 7, 8} be the function defined by f5 (X) = |X| (note that X A). (7b) Let f6 : {a, b}3 {a, b}3 defined by f6 (x, y, z) = (z, y, x). (note: A3 is shorthand for A A A) (8) (Bonus) Consider the following function from N N N defined by 1 f7 (x, y) = (x2 + 2xy + y 2 + 3x + y). 2 Prove this function is 1-1 and onto (taken from Homer Selman \"Computability and Complexity Theory\"). Hint: Use the fact that x + y = k is the equation for the kth line in the figure below, together with the identity that 1 1 + 2 + + k = k(k + 1). 2 y (0, 2) (0, 1) (1, 1) x (0, 0) (1, 0) (2, 0) x+y =0 x+y =1 x+y =2 This function is known as a pairing function. It is useful since we can use a single number z to represent a pair of numbers (x, y) by computing z = f7 (x, y), while still begin able to recover the original pair of numbers from z by inverting f7 (and thus can treat a function taking a pair of inputs as a function with only one variable as input). (8 points each for 16 points total)