VIT Bhopal University

Winter Semester 2024 - 25

1. (a) Let R be the relation R = {(a, b) : a divides b} on the set of positive integer. Find (i) R−1 , (ii)
R′ .
(b) Let P = {(1, 2), (2, 4), (3, 3)} and Q = {(1, 3), (2, 4), (4, 2)}. Find P ∪ Q, P ∩ Q, dom(P ),
dom(Q), dom(P ∪ Q), ran(P ), ran(Q) and ran(P ∩ Q).

2. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric,
and / or transitive, where (x, y) ∈ R if and only if x = y 2 .

3. Give example of a relation on the set of positive integers which is

(a) symmetric and reflexive but not transitive;

4. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric,
and / or transitive, where (x, y) ∈ R if and only if x is a multiple of y.

5. If R is a relation on the set of positive integers such that ordered pair (a, b) ∈ R if and only if ab
is a perfect square. Prove that R is an equivalence relation.

6. If R is a relation on the set of integers such that (a, b) ∈ R if and only if 3a + 4b = 7n where n is
some integers. Prove that R is an equivalence relation.

7. Let A be the set of non-zero integers and let R be the relation on A × A defined by

(a, b)R(c, d) ⇔ ad = bc

(a) Show that R is an equivalence relation (b) Find [(1, 2)], i.e., equivalence class of (1, 2).

8. Define ρ on the set R × R of ordered pairs of real numbers as follows. For all (a, b), (c, d) ∈ R × R.

(a, b)ρ(c, d) ⇔ a = c

(a) Show that ρ is an equivalence relation. (b) Describe the distinct equivalence class of ρ. Inter-
preting R × R as the co-ordinate plane, give a geometrical description of the equivalence classes.

9. (a) Let A = {2, 3, 6, 8, 9, 11} and B = {1, 4, 5, 10, 15}. Let R be a relation on A × B defined by
(a, b)R(c, d) if and only if 3ad − 7bc is an even integer. What properties of an equivalence
relation is satisfied by R?
(b) Define a relation R on the interval [0, π2 ) by xRy if and only if sec2 x − tan2 y = 1. Is R an
equivalence relation? If yes, find the equivalence classes of 0, π4 , π3 ? Can we find equivalence
classes of π2 ?

10. (a) Determine whether the relation with the directed graph shown is an equivalence relation.

1
 (b) Determine whether the relation represented by the zero–one matrix A is an equivalence relation.
 
1 1 1 0
1 1 1 0
A= 1 1 1 0


0 0 0 1

11. Let A = {1, 2, 3} and let R and S be the relations on A such that
   
1 0 1 0 1 1
MR =  0 1 0  and MS =  1 1 0 
0 0 0 0 0 1

Find (i) MR′ (ii) MR−1 (iii) MR∪S (iv) MR∩S

12. Let A = {2, 3, 4, 5}. The relation R and S on A defined by

R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}

Find the matrices of the above relations. Use the matrices to find the following composition of the
relation R and S . (i) RoS (ii) RoR (iii) SoR.

13. (a) Suppose R is the relation on the set of strings of english alphabet where aRb iff l(a) = l(b),
where l(x) is the length of the string x. Is R an equivalence relation?
(b) Suppose R is the relation on the set on integers where aRb iff a ≡ b (mod 4). Is R an equivalence
relation, if yes then find the equivalence class of integers formed by congruence mod 4.

14. Consider A = {1, 2, 3, 4}, B = {a, b, c, d} and D = {x, y, z}. Let R = {(1, a), (2, d), (3, a), (3, b), (3, d)}
and S = {b, x), (b, z), (c, y), (d, z)}. Draw the diagram to represent the relation R and S and also
construct the matrix to represent the relations.

15. Which of the following are partial order?

(a) The relation R = {(a, b) ∈ Z × Z : |a − b| ≤ 1} on Z

16. What can be said about a relation R that is both a partial ordering and an equivalence relation?
Give an example of such a relation on the set {1, 2, 3}.

2
17. Define a relation R on the set Z of all integers as follows :
mRn ⇔ m + n is even for all m, n ∈ Z
Is R a partial order relation? Prove or give a counter example.
18. (a) Which of the following pairs of elements are comparable in the POSET (Z+ , |) ?
(a) 2, 4 (b) 4, 6 (c) 5, 5
(b) Find two incomparable elements in the following POSETs
(a) (P({0, 1, 2}), ⊆) (b) ({1, 2, 4, 6, 8}, |)
19. Let A = {1, 2, 3, 4} and consider the relation
R = {(1, 1), (1, 2), (1, 3), (2, 2), (3, 2), (3, 3), (4, 2), (4, 3), (4, 4)}
Show that R is a partial ordering, and draw its Hasse diagram.
20. Let Dm denote the positive divisors of m ordered by divisibility. Draw the Hasse diagrams of
(a) D12 (b) D15 (c) D16 (d) D17
21. Let D24 (set of all divisors of 24) and the relation divides “|” be the partial ordering on D24 . Draw
the Hasse diagram: illustrate step by step from the digraph of the given POSET.
22. Let A = {1, 2, 3, 4, 5, 6, 7, 8}; nRm if and only if n = 2k m for some k ∈ Z. Determine whether the
given relation is a partial order relation on A.
23. Show that P({a, b, c, d}) is a partially ordered set with respect to the subset relation ⊆. Draw the
Hasse Diagram of the POSET and find a chain of length 4 in P({a, b, c, d}).
24. Let S = {1, 2, 3, 4, 5, 6} be ordered as in figure given below. Find
(a) All minimal and maximal elements of S.
(b) Greatest and least element.
(c) All linearly ordered subsets with three or more elements.

25. Draw Hasse-diagram and answer the following questions concerning the POSET
({1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, ⊆)
(a) Find the maximal elements.
(b) Find the minimal elements.
(c) Find all the upper bounds of {{2}, {4}} and the least upper bound, if it exists.
(d) Find all the lower bounds of {1, 3, 4} and the greatest lower bound of {1, 3, 4}.
26. Give an example of POSET that has
(a) Only one minimal element and only one maximal element.
(b) A minimal element but no maximal element.
(c) A maximal element but no minimal element.
(d) Neither a maximal nor a minimal element.