MATH1004_Discrete Math_2012 Semester 2_tut03s.pdf

The University of Sydney MATH 1004 Second Semester Discrete Mathematics 2012 Tutorial 3 Week 4 1. Define f : N → N by f(x) = x+ 1. Determine whether or not f is (a) one-to-one; (b) onto. Solution. (a) If x 6= y, then clearly x + 1 6= y + 1 so that f(x) 6= f(y). Hence f is one-to-one. (b) Since x + 1 ≥ 1 for all x ∈ N, we see that there is no x ∈ N such that f(x) = x+ 1 = 0 and hence f is not onto. 2. Each of the following sets of pairs may or may not represent a function from {1, 2, 3} to {a, b, c, d}. {(1, d), (2, b), (3, d)}, {(1, c), (2, a), (3, b)}, {(1, a), (3, b)} {(1, a), (1, c), (3, d)}, {(2, b), (3, c), (1, d)} (i) Identify the sets which represent functions and determine which of these are one-to-one. (ii) Explain clearly why each of the sets does or does not represent a function. (iii) Explain clearly why each of the sets does or does not represent a one-to- one function. Solution. (a) The set {(1, d), (2, b), (3, d)} represents a function since each of the ele- ments 1,2,3 appears exactly once as the first term of an ordered pair. It is not one-to-one since d appears more than once as the second term of an ordered pair. (b) The set {(1, c), (2, a), (3, b)} represents a function since each of the ele- ments 1,2,3 appears exactly once as the first term of an ordered pair. It is one-to-one since none of the elements a,b,c,d appear more than once as second terms of ordered pairs. (c) The set {(1, a), (3, b)} does not represent a function on the set 1,2,3 since 2 does not appear as the first term of an ordered pair. (d) The set {(1, a), (1, c), (3, d)} does not represent a function since 1 appears more than once as the first term of an ordered pair. (Also, 2 does not appear as the first term of an ordered pair). 2(e) The set {(2, b), (3, c), (1, d)} represents a function since each of 1,2,3 ap- pears exactly once as the first term of an ordered pair. It is one-to-one since none of a,b,c,d appear more than once as the second term of an ordered pair. 3. (i) Let