MODULE - III

FUNCTIONS
1. Define a i) function ii) 1 to 1 function iii) onto function. Give an example for each. (Dec 2013)
2. If A and B are finite sets with |A| = m, |B| = n i) find how many functions are possible from A to B?
ii) if there are 2187 functions from A to B and |B| = 3 then determine |A|
3. If f is a real valued function defined by 𝑓(𝑥) = 𝑥 2 + 1 ∀𝑥 ∈ 𝑅. Find the images of the following:
i) 𝐴1 = {2, 3} ii) 𝐴2 = {−2, 0, 3} iii) 𝐴3 = {0, 1} iv) 𝐴4 = {−6, 3}. (Jan 2017, Dec 2015)
4. If 𝑓 ∶ 𝐴 → 𝐵 and 𝐵1 , 𝐵2 ⊆ 𝐵, then prove the following: i) 𝑓 −1 (𝐵1 ∩ 𝐵2 ) = 𝑓 −1 (𝐵1 ) ∩ 𝑓 −1 (𝐵2 )

̅̅̅1 ) = ̅̅̅̅̅̅̅̅̅̅̅
ii) 𝑓 −1 (𝐵1 ∪ 𝐵2 ) = 𝑓 −1 (𝐵1 ) ∪ 𝑓 −1 (𝐵2 ) iii) 𝑓 −1 (𝐵 𝑓 −1 (𝐵1 ) . iii) f 1
( B1 )  f 1 ( B1 ) (June 2017)
3x − 5 if x > 0
5. Let f: R → R be defined by, f(x) = { . Find f −1 (0), f −1 (1), f −1 (−1), f −1 (3), f −1 (6),
1 − 3x if x ≤ 0
f −1 ([−6, 5]) and f −1 ([−5, 5]) (Dec 2015, 2014)
6. Let f: Z → Z be defined by 𝑓(𝑎) = 𝑎 + 1 for all 𝑎 ∈ 𝑍. Show that f is a Bijection. (June 2013)
7. In each of the following cases sets A and B and a function f from A to B are given. Determine whether f is one to one
or onto or both or neither. i) A = {a, b, c}, B = {1, 2, 3, 4}, f = {(a, 1), (b, 1), (c, 3)}
ii) A = {1, 2, 3}, B = {1, 2, 3, 4, 5}, f = {(1, 1), (2, 3), (3, 4)}
iii) A = {1, 2, 3, 4}, B = {1, 2, 3, 4} f = {(1, 1), (2, 3), (3, 4), (4, 2)}
8. Let A = R, B ={𝑥|𝑥 𝑖𝑠 𝑟𝑒𝑎𝑙 𝑎𝑛𝑑 𝑥 ≥ 0}. Is the function 𝑓: 𝐴 → 𝐵 defined by 𝑓(𝑎) = 𝑎2 an onto function? Is it a one
to one function? (June 2016)
9. Let f, g : Z+ → Z+ , where ∀𝑥 ∈ Z + , f(x) = x + 1 and 𝑔(𝑥) = max(1, 𝑥 − 1)
i) What is range of f? ii) Is f onto function? iii) Is f one to one function?
iv) What is range of g? v) Is g onto function? vi) Is g one to one function? (June 2017)
10. For each of the following functions, determine whether it is 1 – 1 and determine its range.
i) f: Z → Z, f(x) = 2x + 1 ii) f: Z → Z, f(x) = x 3 − x (Dec 2011)
11. Let A= {a, b, c, d} and B = {1, 2, 3, 4, 5, 6} i) How many functions are there from A to B? How many of these are
one to one? How many are onto? ii) How many functions are there from B to A? How many of these are onto?
How many are one to one? (June 2017)
12. Define Stirling’s number of 2nd kind. If |A| = 7, |B| = 4 find the number of onto functions from A to B. Hence find
S(7, 4).
13. Define Stirling’s number of 2nd kind and evaluate S (8, 6). (Dec 2012)
14. Define Stirling’s number of 2nd kind. Find the number of ways of distributing 6 objects among 4 identical containers
with some container(s) possibly empty. (Dec 2014, June 2014, 2013)
15. Let : 𝑅 → 𝑅 , 𝑔: 𝑅 → 𝑅 be defined by 𝑓(𝑥) = 𝑥 2 and 𝑔(𝑥) = 𝑥 + 5. Determine f ∘ 𝑔 and g ∘ 𝑓. Show that the
composition of two functions is not commutative. (Dec 2013)
0, 𝑖𝑓 𝑥 𝑖𝑠 𝑒𝑣𝑒𝑛
16. Let f, g, h be functions from Z to Z defined by 𝑓(𝑥) = 𝑥 − 1, 𝑔(𝑥) = 3𝑥, ℎ(𝑥) = { .
1, 𝑖𝑓 𝑥 𝑖𝑠 𝑜𝑑𝑑

1
Show that f ∘ (g ∘ h) = (f ∘ g) ∘ h. (Jan 2017, Dec 2012)
17. If 𝑓: 𝐴 → 𝐵, 𝑔: 𝐵 → 𝐶, ℎ: 𝐶 → 𝐷 are three functions, then Prove that h∘ (g ∘ f) = (h ∘ g) ∘ f. (June 2014, 2013)
18. Let 𝐴 = {1, 2, 3, 4} f and g be functions from A to A given by: 𝑓 = {(1, 4)(2, 1)(3, 2)(4, 3)}
𝑔 = {(1, 2)(2, 3)(3, 4)(4, 1)}. Prove that 𝑓 and 𝑔 are inverses of each other. (June 2016)
19. Let A = B = R be the set of the real numbers. The functions 𝑓 ∶ 𝐴 → 𝐵 and 𝑔 ∶ 𝐵 → 𝐴 be defined by 𝑓(𝑥) = 2𝑥 3 − 1,
1 1⁄
∀𝑥 ∈ 𝐴; 𝑔(𝑦) = {2 (𝑦 + 1)} 3 ∀𝑦 ∈ 𝐵. Show that each of 𝑓 and 𝑔 is the inverse of the other. (Jan 2017)

20. Define a function. Prove that the function f: A → B is invertible iff it is one to one and onto. (June 2015, Dec 2012)
21. Let A = B = C = R, 𝑓: 𝐴 → 𝐵, 𝑓(𝑎) = 2𝑎 + 1; 𝑔: 𝐵 → 𝐶, 𝑔(𝑏) = 𝑏⁄2 . Compute g ∘ 𝑓 and show that it is invertible.
(Dec 2011)
22. What is Invertible function? If f: A → B, g: B → C are invertible functions, then prove that g ∘ f: A → C is an invertible
function and (g ∘ f)−1 = f −1 ∘ g −1 . (June 2017, Dec 2015)
23. Let f and g be two functions from R to R defined by 𝑓(𝑥) = 2𝑥 + 5 and 𝑔(𝑥) = (𝑥 − 5)/2. Show that f and g are
invertible.
24. State the pigeonhole principle. Let ABC be an equilateral triangle with AB = 1. Show that if we select five points in
the interior of this triangle, there must be at least two whose distance apart is less than 1⁄2. (Jan 2017)
25. State the pigeonhole principle. Let ABC be an equilateral triangle with AB = 1. Show that if we select ten points in
the interior of this triangle, there must be at least two whose distance apart is less than 1⁄3. (Dec 2011)
26. Prove that if 151 integers are selected from {1, 2, 3, . . . . .300}, then the selection must include two integers x, y such
that xy or yx.
27. Show that if n+1 numbers are chosen from 1 to 2n then at least one pair add to 2n+1. (Dec 2012)
28. Show that if any 14 integers are selected from the set 𝑆 = {1 ,2 ,3 , … … . , 25} there are atleast two integers whose sum
is 26.
29. State Pigeon hole principle. An office employs 13 clerks. Show that at least 2 of them will have birthdays during the
same month of the year. (Dec 2013)
30. State Pigeon hole principle. Prove that in any set of 29 persons; at least 5 persons have been born on the same day of
the week. (Dec 2015)
31. Prove that if 30 dictionaries in a library contain a total of 61,327 pages, then at least one of the dictionaries must have
at least 2045 pages. (Dec 2014)
32. State Pigeon hole principle. Show that if seven numbers from 1 to 13 are chosen then two of them add to 13.
33. Shirts numbered consecutively from 1 to 20 are worn by 20 students of a class. When any 3 of these students are
chosen to be a debating team from the class, the sum of their shirt numbers is used as the code number of the team.
Show that if any eight of the 20 are selected, then from these eight, we may form at least two different teams having
the same code number. (June 2015)

*********************************************************

2
RELATIONS
1. Find A × B, A × (B ∪ C), (A ∩ B) × C for A = {1, 2, 3, 4}, B = {3, 4, 5, 6}, C = {2, 4, 6}.
2. For any sets A and B prove that, i). A × (B∩C) = (A×B) ∩ (A×C). ii). A × (B ∪ C) = (A × B) ∪ (A × C).
(Dec 2013, 2011)
3. Define Cartesian product of two sets. For A, B, C ⊆ U, prove that i) A × (B – C) = (A×B) – (A×C).
ii) (A ∩ B) × C = (A × C) ∩ (B × C) (June 2016, 2013)
4. Suppose 𝐴, 𝐵, 𝐶 ⊆ 𝑍 × 𝑍 with 𝐴 = {(𝑥, 𝑦)|𝑦 = 5𝑥 − 1}; 𝐵 = {(𝑥, 𝑦)|𝑦 = 6𝑥}; 𝐶 = {(𝑥, 𝑦)|3𝑥 − 𝑦 = −7}. Find
i) 𝐴 ∩ 𝐵, ii) 𝐵 ∩ 𝐶, iii) ̅̅̅̅̅̅̅
𝐴̅ ∪ 𝐶̅ , iv) 𝐵̅ ∪ 𝐶̅ . (June 2014)
5. Let A= {1, 2, 3} and B= {2, 4, 5}. Determine the following: i) |𝐴 × 𝐵|
ii) Number of relations from A to B
iii) Number of binary relations on A iv) Number of relations from A to B that contain (1, 2) and (1, 5)
v) Number of relations from A to B that contain exactly 5 ordered pairs
vi) Number of binary relations on A that contains at least 7 ordered pairs. (Jan 2017, June 2015)
6. Define a matrix of a relation and digraph of a relation with example.
7. Let A = {1, 2, 3, 4} and let R be the relation on A defined by “xRy iff x divides y”, written xy.
i) Write down R as a set of ordered pairs. ii) Write down the relation matrix M(R) and draw the digraph of R
iii) Determine the in-degrees and out -degrees of the vertices in the digraph.
8. Let A = {1, 2, 3, 4, 6} and R be a relation on A defined by aRb if and only if a is a multiple of b. i) Write R as a set of
ordered pairs ii) Represent R as a matrix iii) Draw the digraph of R. iv) Determine the in-degrees and out-degrees of
the vertices in the digraph. (Dec 2015, June 2015, 2013)
9. Let A = {1, 2, 3, 4}. Let R be a relation on A defined by 𝑥𝑅𝑦 iff 𝑥𝑦 and 𝑦 = 2𝑥. Write i) R as a set of ordered pairs
ii) Draw the digraph of R iii) Determine in – degree and out – degree of every vertex of digraph.
10. Let R = {(1, 2), (1, 3), (2, 4), (3, 2)} be a relation on A = {1, 2, 3, 4}. Find M(R) and [M(R)]2 . Hence find 𝑅 2.
11. If A = {1, 2, 3, 4} and R is a relation on A defined by R = {(1, 2), (1, 3), (2, 4), (3, 2), (3,3), (3, 4)}. Find R2, R3
Draw their digraphs. (June 2016)
12. Let R = {(1, 1), (1, 2), (2, 3), (3, 3), (3, 4)} be a relation on A = {1, 2, 3, 4}. i) Draw the digraph of R.
ii) Obtain R2, R3 and draw the digraph of R2, R3 iii) Find M(R2), M(R3) (Dec 2011)
13. For A = {1, 2, 3, 4}, let R and S be the relations on A defined by R={(1, 2), (1, 3), (2, 4), (4, 4)} and
S = {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4)}. Find R ∘ S, S ∘ R, R2 , S 2 and R3.
14. Let A = {1, 2, 3, 4}, B = {w, x, y, z} and C = {p, q, r, s}. consider 𝑅1 = {(1, 𝑥), (2, 𝑤), (3, 𝑧)], a relation from A to
B, 𝑅2 = {(𝑤, 𝑝), (𝑧, 𝑞), (𝑦, 𝑠), (𝑥, 𝑝)}, a relation from B to C.
i) What is the composite relation R1 ∘ R 2 from A to C
ii) Write the relation matrices M(𝑅1 ), M(𝑅2 ) 𝑎𝑛𝑑 𝑀(R1 ∘ R 2 )
iii) Verify M(𝑅1 ) ∙ M(𝑅2 ) = 𝑀(R1 ∘ R 2 ) (June 2012)
3
15. Let A = {1, 2, 3, 4}, B = {w, x, y, z} and C = {5, 6, 7}. Let 𝑅1 be a relation from A to B defined by
𝑅1 = {(1, 𝑥), (2, 𝑥), (3, 𝑦), (3, 𝑧)} and 𝑅2 𝑎𝑛𝑑 𝑅3 be relations from B to C defined by 𝑅2 = {(𝑤, 5), (𝑥, 6)},
𝑅3 = {(𝑤, 5), (𝑤, 6)}. Find R1 ∘ R 2 and R1 ∘ R 3 . (June 2014, Dec 2012)
16. Let R = {(1, 2), (3, 4), (2, 2)} and S = {(4, 2), (2, 5), (3, 1), (1, 3)} be relations on the set A = {1, 2, 3, 4, 5}. Find the
following: i) R ∘ (R ∘ S) ii) R ∘ (S ∘ R) iii) S ∘ (R ∘ S) iv) S ∘ (S ∘ R) .
17. Define the following with an example each: i) Reflexive ii) Irreflexive iii) Antisymmetric
iv) Transitive v) Partition set.
18. Given a set A with |𝐴| = 𝑛 and a relation R on A, let M denote the relation matrix for R, then Prove that:
i) R is symmetric if and only if 𝑀 = 𝑀1 . ii) R is transitive if and only if 𝑀. 𝑀 = 𝑀2 ≤ 𝑀. (Dec 2014)
19. Define equivalence relation and equivalence class with one example. (Dec 2015)
20. Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. On this set define the relation R by (𝑥, 𝑦) ∈ 𝑅 if and only if (𝑥 − 𝑦) is a
multiple of 5. Verify that R is an equivalence relation. (Dec 2012)
21. For each of the following relations, determine if the relation R is reflexive, symmetric, anti-symmetric or transitive:
i) On the set of all lines in the plane 𝑙1 𝑅𝑙2 if line 𝑙1 is perpendicular to line 𝑙2
ii) On Z, 𝑥𝑅𝑦 if 𝑥 − 𝑦 is even. (Dec 2011)
22. Find the number of equivalence relations that can be defined on a finite set A with |𝐴| = 6. (June 2016, 2014)
23. Let A= {1, 2, 3, 4}, R= {(1, 3), (1, 1), (3, 1), (1, 2), (3, 3), (4, 4)} be the relation on A. Determine whether the
relation R is reflexive, irreflexive, symmetric, antisymmetric or transitive. (June 2017)
24. Let A= {1, 2, 3, 4}, and let R be the relation defined by 𝑅 = {(𝑥, 𝑦)|𝑥, 𝑦 ∈ 𝐴, 𝑥 ≤ 𝑦}. Determine whether R is
reflexive, symmetric, antisymmetric or transitive. (Dec 2013)
25. Define equivalence relation R on a set A. For a fixed integer 𝑛 > 1, prove that the relation “Congruent modulo 𝑛” is
an equivalence relation on the set of all integers Z. (June 2015)
26. Define partition set. List all partitions of P = {1, 2, 3}.
27. For 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑥, 𝑦, 𝑧}. Define equivalence relation. Hence find equivalence class. Also find partition of A.
28. Define a partition of a set. Prove that the relation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (3, 3), (4, 4)}is an
equivalence relation on set A = {1, 2, 3, 4}. Also determine the partition induced by R on A. (Dec 2013)
29. Let A = {a, b, c, d, e}. Consider partition P = {{a, b}, {c, d}, {e}} of A. Find the equivalence relation inducing this
partition.
30. Let A = {1, 2, 3, 4, 5, 6, 7} and R be the equivalence relation on A that induces the partition
A = {1, 2} ∪ {3} ∪ {4, 5, 7} ∪ {6}. Find R. (June 2016)
31. Let A = {1, 2, 3, 4, 5} and define a relation R on A×A by (x1, y1) R (x2, y2) iff x1 + y1 = x2 + y2.
i) Verify that R is an equivalence relation on A.
ii) Determine the equivalence classes [(1, 3)], [(2, 4)] and [(1, 1)].
iii) Determine the partition of A × A induced by R. (Jan 2017, Dec 2015, Dec 2014, June 2012)
32. Define an equivalence relation. Let N be the set of all natural numbers. On 𝑁 × 𝑁, the relation R is defined as

4
(a,b) R (c,d) if and only if a + d = b + c. Show that R is an equivalence relation. Find the equivalence class of the
element (2, 5). (June 2013)
33. Let A = {1, 2, 3, 4} and R = {(1, 1), (1, 2), (2, 2), (2, 4), (1, 3), (3, 3), (3, 4), (1, 4), (4, 4)}. Draw the Hasse diagram
for the Poset (A, R).
34. Define Partial Order. If R is a relation on A = {1, 2, 3, 4} defined by xRy iff 𝑥|𝑦. Prove that (A, R) is a Poset.
Draw its Hasse diagram. (Dec 2013)
35. Let A = {1, 2, 3, 4, 6, 12, 18}. On A, define the relation R by xRy iff 𝑥|𝑦. Prove that R is a partial order on A. Draw
the Hasse diagram for this relation.
36. Let A = {1, 2, 3, 6, 9, 12, 18}. On A, define the relation R by aRb iff a divides b. Prove that R is a partial order on A.
Draw the Hasse diagram for this relation. (June 2012)
37. Let A = {1, 2, 3, 4, 6, 8, 12} and R be the partial ordering on A defined by aRb iff a divides b, then
i) Draw the Hasse diagram of the Poset (A, R) ii) Determine the relation matrix for R. (Dec 2014)
38. Draw the digraph and Hasse diagram representing the positive divisors of 36. (June 2016)
39. Draw the digraph and Hasse diagram representing the positive divisors of 72. (June 2015, Dec 2011)
40. Determine the matrix of the partial order whose Hasse diagram is as shown in fig(i).
41. For A = {a, b, c, d, e}, the Hasse diagram for the Poset (A, R) is as shown in fig (ii). Determine the relation matrix for
R and construct the digraph for R. (Jan 2017, June 2014)
42. Let (A,R) be a Poset with BA. Define i) lower bound of B ii) upper bound of B iii) least upper bound of B
iv) greatest lower bound of B.
43. Let (A,R) be a Poset. Define i) maximal element ii) minimal element iii) greatest element iv) least element.
44. Let A = {2, 3, 4, 6, 8, 12, 24} and let ≤ denotes the partial order of divisibility that is 𝑥 ≤ 𝑦 means 𝑥|𝑦 . Let
B = {4, 6, 12}. Determine i) All upper bounds of B ii) All lower bounds of B iii) Least upper bound of B
iv) Greatest lower bound of B. (Dec 2013)
45. For the Hasse diagram given in fig (iii), write i) maximal ii) minimal iii) greatest and iv) least element (s).
(June 2017)
46. Consider the Hasse diagram of a Poset (A, R) given in fig (iv). If B = {c, d, e}, find i) all upper bounds of B
ii) all lower bounds of B iii) the least upper bound of B iv) the greatest lower bound of B.
(Jan 2017, Dec 2015, 2012)

***************************************************