The University of Hong Kong, Faculty of Engineering
COMP 2121C Discrete Mathematics. Assignment 2
Ravi
(Dated: February 20, 2024)
This Assignment 2 tests understanding of the concepts of Sets, Relations and Functions.
Students are expected to work on the assignment for a period of up to two weeks and submit their
solutions through Moodle. Typically, the solution sheet will be formatted in LaTeX but any clear,
legible solution sheet will be accepted. Answers will be judged on correctness, as well as evidence
of detailed understanding, so please show working and explain the steps leading to the final solution.
Assignment 2 Due Date: Mar 5, 2024, 23:59.
1. Set Theory [19 Marks]
(a) (5 marks) Find all sets X,Y,Z that satisfy the following condition: X =
{
1, |Y|, |Z|}, Y = {2, |X|, |Z|},
and Z =
{
1, 2, |X|, |Y|}.
(b) (6 marks) For arbitrary finite sets A, B and C, prove that (A \ C) \ (B \ C) ⊆ (A \ B).
(c) (8 marks) Suppose that A, B1, B2, . . . , Bn are finite sets where n is a positive integer. Prove that
A ∪
(
n⋂
i=1
Bi
)
=
n⋂
i=1
(A ∪ Bi) .
2. Properties of Relations [18 Marks]
(a) (6 marks) List all the symmetric, antisymmetric and asymmetric relations on the set A =
{
Φ, {Φ}}.
Conjecture a formula for the numbers of antisymmetric and asymmetric relations on a set of m elements.
Substantiate your conjecture with brief (informal) reasoning.
(b) (6 marks) Consider the homogeneous relation R on set A = {3, 4, 5, 8, 10, 24, 25, 27, 48, 50, 81, 100, 125, 128}
defined by aRb if and only if a and b have exactly the same prime factors. Determine whether it is (i)
reflexive, (ii) symmetric, (iii) transitive, (iv) antisymmetric. Then state whether it is (a) an equivalence
relation and (b) a partial order. If it is an equivalence relation, determine its equivalence classes.
(c) (6 marks) Let A := {a, b, c, d}. Find the smallest relation S on A that includes the relation R =
{(a, b), (b, a), (b, c), (c, d), (d, a)} as a subset and is both reflexive and transitive.
3. Representing Relations [10 Marks]
Given the directed graphs representing two relations, how can the directed graph of the union, intersection,
difference and composition of these relations be found? Illustrate this with the relations R1 and R2 on a set A
represented by the matrices
MR1 =
0 1 01 0 0
0 1 1
 and MR2 =
1 1 00 1 0
1 0 1

4. Functions [18 Marks]
(a) (6 marks) Let f , g : R → R be two functions defined as follows. For all x ∈ R, f (x) := x + |x| and
g(x) = |x| − x where | · | denotes the absolute value function. Find the functions f ◦ g and g ◦ f .
(b) (6 marks) Let R be a homogeneous relation on a finite set A. Suppose R is an Equivalence Relation as well
as a Function, is it necessarily the case that R is the Identity Relation defined by I(a) = a for all a ∈ A?
Prove your answer.
(c) (6 marks) Identify whether the function f : R → R defined as f (x) = xx2+1 for all x ∈ R is (a) Injective
and (b) Surjective. Explain your answer.
5. Special Functions [19 Marks]
(a) (6 marks) Solve for x ∈ R the equation d7x+ 3bxce = 17.
(b) (6 marks) Solve for x ∈ R the equation (6 log5 x)2 + log5 x11 − 35 = 0.
(c) (7 marks) Compute ∑0≤k√
kc (give a closed form expression for the sum). Check your answer for the
case n = 10.
6. Growth of Functions and Relations [16 Marks]
(a) (9 marks) Arrange the following functions on integers in increasing order of their growth rate. If f (n) is
O (g(n)) but g(n) is not O ( f (n)) then f (n) must be below g(n). If they are each big-O of each other, then
they must be on the same level. All logs below have base 2.
f1(n) = log log log n f2(n) = log n · log log n, f3(n) = log n3, f4(n) = n2 + n3/100,
f5(n) = n!, f6(n) = 2n + 3log n, f7(n) =
(
n log n+ n4
)
(n3 + 1). (1)
(b) (7 marks) Let R be the relation on the set of functions from Z+ to Z+ such that ( f , g) belongs to R if
and only if f is Θ(g). Show that R is an equivalence relation. Describe the equivalence class containing
f (n) = 2n3 for this equivalence relation.