April 1999
MA214: DISCRETE MATHEMATICS

QUESTION 5

Total Marks: 20 Marks

 Click here to access other questions

GRADE A
Student's solutions are indicated in green.
Return to Question 5

 
(a) (i) How many functions are there from a set with three elements to a set with four elements? Explain your answer. [2]
(ii) How many functions are there from a set with four elements to a set with three elements? Explain your answer. [2]
(i) The 1st element can map to one of the elements in 2nd group.
The 2nd element can also map to one of the elements in 2nd group (as the 2nd element can have same range as the 1st element).
Same for the 3rd element.
\ no. of functions = 4 * 4 * 4
                              = 64

(ii) The 1st element have a selection of 3 elements in 2nd group, so as the 2nd, 3rd, and 4th elements.
\ no. of functions = 3 * 3 * 3 * 3
                              = 81

 
(b) (i) How many one-to-one functions are there from a set with three elements to a set with four elements? Explain your answer. [2]
(ii) How many one-to-one functions are there from a set with four elements to a set with three elements? Explain your answer. [2]
(i) The 1st element has a selection of 4 elements.
The 2nd element has a selection of 3 elements.
The 3rd element has a selection of 2 elements.
\ no. of one-to-one functions = 4 * 3 * 2
                                                = 24


(ii) No one-to-one functions is able to form as the numbers of elements in the 1st group is more than the numbers of elements in the 2nd group.

 
(c) (i) How many onto functions are there from a set with three elements to a set with four elements? Explain your answer. [2]
(ii) How many onto functions are there from a set with four elements to a set with three elements? Explain your answer. [2]
(i) No onto functions as the number of elements in the first group is less than the numbers of elements in the 2nd group.

(ii) (3 * 1 * 2 * 1) + (3 * 2 * 2 * 1) + (3 * 2 * 1* 3) = 6 + 12 + 18 = 36
The first element in the domain can map onto any of the three elements in the range. If the 2nd element maps onto that same element, then the 3rd and fourth elements must map onto the other two elements.
Otherwise, if the 3rd elements map onto either of the elements which the first or second mapped onto then the fourth element must map onto the remaining element. Otherwise, the fourth element can map onto any element.

 
(d) (i) How many invertible functions are there from a set with three elements to a set with four elements? [1]
(ii) How many invertible functions are there from a set with four elements to a set with three elements? [1]
(i) No invertible functions. In order to have invertible functions, it must be one-to-one and onto. In this case, since the number of elements in the 1st group is less the 2nd group. It is no onto function and therefore no invertible functions.

(ii) No invertible functions. As it has no one-to-one function (refer to b(ii)), therefore no invertible functions.

 
(e) Construct a function from three elements to two elements which is neither one-to-one nor onto. [2]
All three elements in the domain must map onto one element in the range.

 

 
(f) The relation R, "is a factor of " is defined on pic7.gif (99 bytes). Decide whether or not R is reflexive, symmetric or transitive. [4]
R is reflexive as every number is a factor of itself.
R is not symmetric as 3 is a factor of 6 but 6 is not a factor of 3.
R is transitive as if a is a factor of b, and b is a factor of c, then a must also be a factor of c.