6.042/18.] Mathematics for Computer Science March 29, 2005 Srini devadas and Eric Lehman Problem set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties injective surjective lective Determine the properties of the functions below, and briefly explain your reasoning (a) The function f: R-R defined by f(r)=er Solution. This function is injective, since ef takes on each nonnegative real value for exactly one r. However, the function is not surjective, because e never takes on negative values. Therefore the function is not bijective either (b)The function f: R-R+t defined by f(a)=er Solution. The function et takes on every nonnegative value for exactly one so it is injective, surjective, and bijective (c) The function f: R- R defined by f(ar)=(+1)a(a-1 Solution. This function is surjective, since it is continuous, it tends to +oo for large itive z, and tends to -oo for large negative r. Thus, the function takes on each real value for at least one However, this function is not injective, since it takes on the value 0 at a =-l, =0, and a= 1. Therefore, the function is not bijective either (d) Let S be the set of all 20-bit sequences. Let T be the set of all 10-bit sequences. Let f: S-T map each 20-bit sequence to its first 10 bits. For exampl ∫(11101010101010010)=11101010 Solution. This function is surjective since the sequence b1b2... b10 is mapped to by b1b2 .b1000.0, for example. However, the function is not injective, because this sequence is also mapped to by b1b2.boll.1. Consequently, the function is not bijective either. Problem 2. There are 20 books arranged in a row on a shelf6.042/18.062J Mathematics for Computer Science March 29, 2005 Srini Devadas and Eric Lehman Problem Set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties: injective surjective bijective Determine the properties of the functions below, and briefly explain your reasoning. x (a) The function f : R R → defined by f(x) = e . Solution. This function is injective, since ex takes on each nonnegative real value for exactly one x. However, the function is not surjective, because ex never takes on negative values. Therefore, the function is not bijective either. x (b) The function f : R R+ → defined by f(x) = e . Solution. The function ex takes on every nonnegative value for exactly one x, so it is injective, surjective, and bijective. (c) The function f : R → R defined by f(x) = (x + 1)x(x − 1). Solution. This function is surjective, since it is continuous, it tends to +∞ for large positive x, and tends to −∞ for large negative x. Thus, the function takes on each real value for at least one x. However, this function is not injective, since it takes on the value 0 at x = −1, x = 0, and x = 1. Therefore, the function is not bijective either. (d) Let S be the set of all 20­bit sequences. Let T be the set of all 10­bit sequences. Let f : S T → map each 20­bit sequence to its first 10 bits. For example: f(11110110101101010010) = 1111011010 Solution. This function is surjective since the sequence b1b2 . . . b10 is mapped to by b1b2 . . . b1000 . . . 0, for example. However, the function is not injective, because this sequence is also mapped to by b1b2 . . . b1011 . . . 1. Consequently, the function is not bijective either. Problem 2. There are 20 books arranged in a row on a shelf