MATH2448: Discrete Mathematics

1
Lecturer: Dr Nguyen Hieu Thao
Email: [Link]@[Link]

Tutorial Solutions: Functions

(2024C, Week 4)1

1. Determine whether each of the sets is a function from X = {1, 2, 3, 4} to Y = {a, b, c, d}.
If it is a function, find its domain and range, draw its arrow diagram, and determine if it
is one-to-one, onto, or both.

(a) {(1, a), (2, a), (3, c), (4, b)} is a function.

(i) It is not injective since two distin-

guished elements 1 and 2 in X have
the same value a in Y .

(ii) It is not surjective since d does not

belong to its range.

(iii) The diagram of this function is beside.

(b) {(1, c), (2, a), (3, b), (4, c), (2, d)} is not a function since there are two correspondences
for the input 2 (a and d).

2. Draw the graph of the function f (x) = x − bxc, whose domain and codomain are the set
of real numbers.

Solution. Note that the function f (x) = x − bxc is periodic with period 1. Consider, for
example, the interval [0, 1), we have f (x) = x. Duplicating the graph of f on [0, 1) to all
the periodic intervals, we obtain the graph of f as below.

1 Most of the content of this document is taken from the book [1].
2

3. Determine whether each function is one-to-one, onto, or both. The domain and codomain
are the set of integers. Justify your answers.

(a) The function f (n) = dn/2e is surjective, but not injective.

(i) It is surjective because for any integer n, we have f (2n) = d2n/2e = n. That is,
the range of f contains all integers.
(ii) It is not injective because 1 6= 2, but f (1) = d1/2e = 1 = d1e = f (2).
(b) The function f (n) = 2n is injective, but not surjective.
(i) It is injective because whenever n 6= m, we have f (n) = 2n 6= 2m = f (m).
(ii) It is not surjective because odd integers do not belong to the range of f which
contains only even integers (2n, n ∈ Z).

4. The function f (x) = 3 log2 x is one-to-one on its domain X - the set of positive real
numbers. By letting Y = range(f ), we obtain a bijection from X to Y . Find its inverse.

Solution. The inverse function is f −1 (y) = 2y/3 . Justify the result for yourself.

5. Given g = {(1, b), (2, c), (3, a)}, a function from X = {1, 2, 3} to Y = {a, b, c, d}, and
f = {(a, x), (b, x), (c, z), (d, w)}, a function from Y to Z = {w, x, y, z}, write f ◦ g as a set
of ordered pairs and draw the arrow diagram of f ◦ g.

Solution. The composition function f ◦ g as a set of

ordered pairs is

f ◦ g = {(1, x), (2, z), (3, x)} .

The arrow diagram of f ◦ g is beside.

6. Let f (n) = 2n + 1 and g(n) = 3n − 1 be functions from the set of positive integers to itself.
Find the compositions f ◦ f , g ◦ g, f ◦ g, and g ◦ f .
Solution. The composition functions are below.

(i) f ◦ f (n) = 2(2n + 1) + 1 = 4n + 3 (iii) f ◦ g(n) = 2(3n − 1) + 1 = 6n − 1

(ii) g ◦ g(n) = 3(3n − 1) − 1 = 9n − 4 (iv) g ◦ f (n) = 3(2n + 1) − 1 = 6n + 2

7. Decompose the function f (x) = log2 (x2 + 2) into simpler functions.

Solution. It can be decomposed as f = f1 ◦ f2 ◦ f3 , where

f3 (x) = x2 , f2 (y) = y + 2, and f1 (z) = log2 (z).

Justify the result for yourself.

 3

8. Consider the function f (x) = 4x( mod 5) from X = {0, 1, 2, 3, 4} to X. Write f as a set
of ordered pairs and draw the arrow diagram of f . Is f one-to-one? Is f onto? Explain
your answers.

Solution.

(i) As a set of ordered pairs:

f = {(0, 0), (1, 4), (2, 3), (3, 2), (4, 1)} .

(ii) The arrow diagram of f is beside.

(iii) f is both one-to-one and onto. Explain the

answers to yourself.

9. For the following hash function, show how the data would be inserted in initially empty
cells in the given order. Use the collision resolution policy mentioned in Notes Week 4.

h(x) = x mod 11; cells indexed 0 to 10; data: 53, 13, 281, 743, 377, 20, 10, 796.

Solution. Recall that the collision resolution policy is to look for the next unoccupied cell.
The hash values are below.

53 13 281 743 377 20 10 796

9 2 6 7 3 10 0 4

10. Let g be a function from X to Y and let f be a function from Y to Z. For each statement,
if the statement is true, prove it; otherwise, give a counterexample.

(a) If f and g are onto, then f ◦ g is onto. The statement is True.

Proof. Take any z ∈ Z. Since f is onto, there is y ∈ Y such that f (y) = z. Since g is
onto and y ∈ Y , there is x ∈ X such that g(x) = y. That is, f ◦ g(x) = z. Thus, for
every z ∈ Z, there is x ∈ X such that f ◦ g(x) = z. That is, f ◦ y is onto.

(b) If f ◦ g is one-to-one, then f is one-to-one. The statement is False.

Counterexample. Consider the function g : {1} → {a, b} given by g(1) = a and the
function f : {a, b} → {α} given by f (a) = f (b) = α. Then the composition function
f ◦ g : {1} → {α} with f ◦ g(1) = α is one-to-one, but f is not one-to-one.
4

11. In asynchronous transfer mode (ATM) (a communication protocol used on backbone net-
works), data are organized into cells of 53 bytes. How many ATM cells can be transmitted
in 1 minute over a connection that transmits data at the rate of 500 kilobits per second?
Solution.

(i) 53 bytes/cell = 53 · 8 = 424 bits/cell.

(ii) In 60 seconds, 60 · 500, 000 = 30, 000, 000 bits can be transmitted.

(iii) Thus, b30, 000, 000/424c = b70, 754.717c = 70, 754 cells can be transmitted.

12. A JPEG file stores image data in blocks of 8 × 8 pixels. How many blocks are needed to
store a JPEG image whose dimensions are 4753 × 3747 pixels?
Solution.

(i) Horizontally, it requires ceiling(4, 753/8) = ceiling(594.125) = 595 blocks.

(ii) Vertically, it requires ceiling(3, 747/8) = ceiling(468.375) = 469 blocks.

(iii) Total number of blocks required is 595 · 469 = 279, 055 blocks.

13. Consider the set X = {1, 2, . . . , 10}. Define the function f from the power set of X to the
set of positive integers. For each subset A of X, the function f returns the cardinality of
A. Justify yours answers.

(a) f is not injective. For example, {A} = {1} 6= {B} = {2}, but f (A) = f (B) = 1.

(b) f is not surjective since 11 ∈

/ range(f ) which ranges from 0 to 10.

(c) X is a proper subset of range(f ) since X ⊂ range(f ) and 0 ∈ range(f ) \ X.

14. Define the function f : R2 → R2 by f (x) = Ax for every x ∈ R2 , where

 
1 2
A= .
2 4

(a) Calculate f (x), where x = (−3, −6)T (column vector).

Solution. f (x) = Ax = (−15, −30)T .

(b) Is f an injective, surjective, bijective function? Explain/prove your answers.

Solution. f is not injective since f ((2, 1)T ) = f ((0, 2)T ) while (2, 1)T 6= (0, 2)T . f is
not surjective since f −1 ((1, 1)T ) = ∅. As a consequence, f is not bijective.
 5

15. Define the function f : R3 → R3 by f (a) = Aa (matrix-vector multiplication) for every

a ∈ R3 , where 
1 2 3


A = 0 −1 1 .
0 0 1
(a) Calculate f (a) and f −1 (a), where a = (1, 1, 1)T (column vector).
    
1 2 3 1 6
f (a) = Aa = 0 −1 1 1 = 0 .
0 0 1 1 1
To compute f −1 (a), we solve the equation f (x) = a for the unknown x. Indeed,
    
1 2 3 x1 1
f (x) = Ax = a ⇐⇒ 0 −1 1 x2  = 1
0 0 1 x3 1
 
x1 + 2x2 +3x3 = 1 x1 = −2
⇐⇒ −x2 +x3 = 1 ⇐⇒ x2 = 0 .
x3 = 1 x3 = 1
 

Hence, f −1 (a) = (−2, 0, 1)T .

(b) f is injective. Indeed, suppose that f (x) = f (y) for some x, y ∈ R3 . Then
    
1 2 3 x1 − y1 0
Ax = Ay ⇐⇒ A(x − y) = 0 ⇐⇒ 0 −1 1 x2 − y2  = 0
0 0 1 x3 − y3 0
 
(x1 − y1 ) + 2(x2 − y2 ) +3(x3 − y3 ) = 0 x1 = y1
⇐⇒ −(x2 − y2 ) +(x3 − y3 ) = 0 ⇐⇒ x2 = y2 .
x3 − y3 = 0 x3 = y3
 

Hence x = y and f is injective.

(c) f is surjective. Indeed, consider any a ∈ R3 . We show that the equation f (x) = a has
a solution x. Indeed,
    
1 2 3 x1 a1
f (x) = Ax = a ⇐⇒ 0 −1 1 x2  = a2 
0 0 1 x3 a3
 
x1 + 2x2 +3x3 = a1 x1 = a1 + 2a2 − 5a3
⇐⇒ −x2 +x3 = a2 ⇐⇒ x2 = −a2 + a3 .
x3 = a3 x3 = a3
 

This means that for every given a ∈ R3 , the equation f (x) = a has a solution x, and
hence f is surjective.

References
1. Johnsonbaugh, R.: Discrete Mathematics - Eighth Edition. Pearson Education, New York
(2018).