Discrete Math

1. 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
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
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
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

The post Discrete Math appeared first on homework handlers.