- This question is worth 8 marks
Let A = {1, 2, 3, 4, 5}.
(a) Find a function f : A → A so that f ◦ f (2) = 3.
(b) How many functions f : A → A are there so that f ◦ f (2) = 3? Explain.
(c) How many one-to-one functions f : A → A are there so that f ◦ f (2) = 3? Explain.
(d) Is there a function f : A → A so that f ◦ f (2) = 3 and f ◦ f (3) = 2? Prove your answer.
2 - This question is worth 7 marks.
Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9} and T = {2, 4, 6, 8}. Let R be the relation on P (A) defined by
for all X, Y ∈ P (A), XRY if and only if X ∪ T = Y ∪ T.
(a) Prove that R is an equivalence relation on P (A).
(b) How many equivalence classes are there? Explain.
(c) How many elements does [∅], the equivalence class of the empty set, have? Explain.
3 - This question is worth 8 marks.
Let A = {1, 2, 3, 4, 5} and let F be the set of all functions f from A to A. Let R be the relation on F defined by
for all f, g ∈ F, fRg if and only if P
5
i=1
f (i) = P
5
i=1
g (i).
(a) Prove that R is an equivalence relation on F.
(b) How many equivalence classes are there? Explain.
(c) Find two functions f and g in the equivalence class of IA so that f 6= IA 6= g.
(d) Is there an equivalence class that has exactly one element? Prove your answer.
4 - This question is worth 7 marks.
Prove or disprove each of the following using the definition of congruence modulo n, where n is a positive integer; which
is given below:
For all integers x and y, x ≡ y (mod n) if and only if n | (x − y)
(a) For all positive integers n, a and b, if 5a ≡ 5b (mod n) then a ≡ b (mod n).
(b) For all positive integers a, there exists an integer n so that n > 2a and a is invertible modulo n.
(c) Is 271 is invertible modulo 2020? Explain. If 271 is invertible modulo 2020, find an inverse of 271 modulo 2020.
5
Sample Solution