RELATIONS

&
DIGRAPHS
 Dr. A. Dhanalakshmi
Assistant Professor of Mathematics,
Sri Chandrasekharendra Saraswathi Viswa
Mahavidyalaya, Kanchipuram.
Aims and Objectives:

• It aims to develop the concept of relations, digraphs, types

of relations.
• To state the definitions of binary relation, reflexive,
symmetric, transitive, equivalence relation,
equivalence class and partition.
• To Show that a binary relation on a set is an equivalence
relation, or give a counterexample to show that it is not an
equivalence relation.
• Given an equivalence relation on a set, find the
equivalence classes of the relation and show that they
form a partition of the set. And their uses in database
Descriptions:
1. Pre – Test- MCQ
2. Topic Description
(i) Ordered Pair
(ii) Product Set
(iii) Partition
(iv) Relation
(v) Matrix of Relation
(vi) Digraph of Relation
(v) Properties of Relation
(vi) Equivalence Relation
3. Post Test – MCQ
4. References
5. Assignment
PRE-TEST
1. A __________ is an ordered collection of objects.
a) Relation
b) Function
c) Set
d) Proposition
Answer : c

2. Power set of empty set has exactly _________ subset.

a) One
b) Two
c) Zero
d) Three
Answer: a

3. What is the Cartesian product of A = {1, 2} and B = {a, b}?

a) {(1, a), (1, b), (2, a), (b, b)}
b) {(1, 1), (2, 2), (a, a), (b, b)}
c) {(1, a), (2, a), (1, b), (2, b)}
d) {(1, 1), (a, a), (2, a), (1, b)}
Answer: c
.
4. The Cartesian Product B x A is equal to the Cartesian product A x B.
a) True
b) False
Answer: b

5. Which of the following sets are null sets ?

a. {0}
b. ø
c.{ }
d.Both (b) & (c)
Answer: D

6. The number of elements in the Power set P(S) of the set S = [ [ Φ] , 1, [ 2, 3 ]] is

A.2
B.4
C.8
D.None of these
Answer: C
7. If A and B are sets and A B= A ∩ B, then
a.A = Φ
b.B = Φ
c.A = B
d. none of these
Answer: c
8. The number of elements in the power set of the set {{a, b}, c} is
a.8
b.4
c.3
d.7
Answer:b
9.Let n(A) denotes the number of elements in set A. If n(A) =p and n(B) = q, then how
many ordered pairs (a, b) are there with a A and b B ?
a.p2
b. p x q
c. p + q
d.2 pq
Answer: b
10.What is the cardinality of the set of odd positive integers less than 10?
a) 10
b) 5
c) 3
d) 20
Answer: b

11. Which of the following two sets are equal?

a) A = {1, 2} and B = {1}
b) A = {1, 2} and B = {1, 2, 3}
c) A = {1, 2, 3} and B = {2, 1, 3}
d) A = {1, 2, 4} and B = {1, 2, 3}
Answer: c

12. The set of positive integers is _____________

a) Infinite
b) Finite
c) Subset
d) Empty
Answer: a
13. What is the Cardinality of the Power set of the set {0, 1, 2}?
a) 8
b) 6
c) 7
d) 9
Answer: a

14. The members of the set S = {x | x is the square of an integer and x < 100} is
________________
a) {0, 2, 4, 5, 9, 58, 49, 56, 99, 12}
b) {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}
c) {1, 4, 9, 16, 25, 36, 64, 81, 85, 99}
d) {0, 1, 4, 9, 16, 25, 36, 49, 64, 121}

Answer: b
Basics:
Set theory:
A set is a collection of objects which are called the
members or elements of that set.
Examples:
1. W := {0, 1, 2, . . .}, the set of whole numbers
2. N := {1, 2, . . .}, the set of Natural numbers
3. Set of all vowels. A={a, e, i, o, u}
Notation: A, B, C, … for sets;
a, b, c, … or x, y, z, … for members.
b A if b belongs to A (B A if both A and B are
sets and B is a member of A)
and c A, if c doesn’t belong to A.
Subsets :
A set A is a subset of a set B iff every element of A is
also an element of B.
Such a relation between sets is denoted by A B.
If A B and A ≠ B we call A a proper subset of B and write A
B.

Examples: {a,b} {d,a,b,e} and {a,b} {d,a,b,e}, {a,b}

{a,b}, but {a,b} {a,b}
Power sets:
The set of all subsets of a set A is called the power set
of A and denoted as ℘(A) .
For example, if A = {a,b}, ℘(A) = { , {a}, {b}, {a,b}}.

From the example above: a A; {a} A; {a} ℘(A)

A; A; ℘(A); ℘(A)
Operations on sets:
Union
Let A and B be arbitrary sets. The union of A and B, written A
B, is the set whose elements are just the elements of A or B
or of both.
In the predicate notation the definition is
A B =def { x/ x A or x B}
Examples.:
Let K = {a,b}, L = {c,d} and M = {b,d},
then K L = {a,b,c,d} K M = {a,b,d} L M = {b,c,d}
(K L) M = K (L M) = {a,b,c,d}
K K=K
K = K = K = {a,b}
Intersection
The intersection of A and B, written A ∩ B, is the set whose
elements are just the elements of both A and B.
In the predicate notation the definition is
A ∩ B =def { x/ x A and x B}
Examples: K ∩ L =
K ∩ M = {b}
L ∩ M = {d}
(K ∩ L) ∩ M = K ∩ (L ∩ M) =
K∩K=K
K∩ = ∩K=
RELATIONS
ORDERED PAIR:

An ordered pair (a , b) is a listing of the object ‘a’ & ‘b’ in

prescribed order in which ‘a’ appearing first and ‘b’ appearing
next.
Equivalence Relation Definition
A relation R on a set A is said to be an equivalence relation if
and only if the relation R is reflexive, symmetric and transitive.

Reflexive: A relation is said to be reflexive, if (a, a) R, for every a A.

Symmetric: A relation is said to be symmetric, if (a, b) R, then (b, a)
R.
Transitive: A relation is said to be transitive if (a, b) R and (b, c) R,
then (a, c) R.

Examples:
•For a given set of triangles, the relation of ‘is similar to’ and ‘is
congruent to’.
•For a given set of integers, the relation of ‘is congruent to, modulo n’
shows equivalence.
•For a set of all angles, ‘has the same cosine’.
•For a set of all real numbers,’ has the same absolute value’.
Problems:
1. Let us assume that R be a relation on the set of ordered pairs of positive
integers such that ((a, b), (c, d)) R if and only if ad=bc. Is R an
equivalence relation?
In order to prove that R is an equivalence relation, we must show that R is
reflexive, symmetric and transitive.

Reflexive Property
According to the reflexive property, if (a, a) R, for every a A
For all pairs of positive integers,
((a, b),(a, b)) R.
Clearly, we can say
ab = ab for all positive integers.
Hence, the reflexive property is proved.
Symmetric Property
From the symmetric property,
if (a, b) R, then we can say (b, a) R
For the given condition,
if ((a, b),(c, d)) R, then ((c, d),(a, b)) R.
If ((a, b),(c, d)) R, then ad = bc and cb = da
since multiplication is commutative.
Therefore ((c, d),(a, b)) R
Hence symmetric property is proved.

Transitive Property
From the transitive property,
if (a, b) R and (b, c) R, then (a, c) also belongs to R
For the given set of ordered pairs of positive integers,
((a, b), (c, d)) R and ((c, d), (e, f)) R,
then ((a, b),(e, f) R.
Now, assume that ((a, b), (c, d)) R and ((c, d), (e, f)) R.
Then we get, ad = cb and cf = de.
The above relation implies that a/b = c/d and that c/d = e/f,
so a/b = e/f we get af = be.
Therefore ((a, b),(e, f)) R.
Hence transitive property is proved.
Equivalence Relation Examples

1. Let assume that F is a relation on the set R real numbers defined by xFy if
and only if x-y is an integer. Prove that F is an equivalence relation on R.
Solution:
Reflexive: Consider x belongs to R, then x – x = 0 which is an integer.
Therefore xFx.
Symmetric: Consider x and y belongs to R and xFy. Then x – y is an integer.
Thus, y – x = – ( x – y), y – x is also an integer. Therefore yFx.
Transitive: Consider x and y belongs to R, xFy and yFz. Therefore x-y and
y-z are integers. According to the transitive property, ( x – y ) + ( y – z ) = x –
z is also an integer. So that xFz.
Thus, R is an equivalence relation on R.
2. Show that the relation R is an equivalence relation in the set A = { 1, 2, 3, 4, 5 }
given by the relation R = { (a, b):|a-b| is even }.
Solution:
R = { (a, b):|a-b| is even }. Where a, b belongs to A
Reflexive Property :
From the given relation,
|a – a| = | 0 |=0
And 0 is always even.
Thus, |a-a| is even
Therefore, (a, a) belongs to R
Hence R is Reflexive
Symmetric Property :
From the given relation,
|a – b| = |b – a|
We know that |a – b| = |-(b – a)|= |b – a|
Hence |a – b| is even,
Then |b – a| is also even.
Therefore, if (a, b) R, then (b, a) belongs to R
Hence R is symmetric.
Transitive Property :
If |a-b| is even, then (a-b) is even.
Similarly, if |b-c| is even, then (b-c) is also even.
Sum of even number is also even
So, we can write it as a-b+ b-c is even
Then, a – c is also even
So,
|a – b| and |b – c| is even , then |a-c| is even.
Therefore, if (a, b) R and (b, c) R, then (a, c) also belongs to R
Hence R is transitive.
Post Test:
The binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is
__________
a) reflective, symmetric and transitive
b) irreflexive, symmetric and transitive
c) neither reflective, nor irreflexive but transitive
d) irreflexive and antisymmetric
Answer: c
Explanation: Not reflexive -> (3,3) not present; not irreflexive -> (1, 1) is present; not
symmetric -> (2, 1) is present but not (1, 2); not antisymmetric – (2, 3) and (3, 2) are
present; not asymmetric -> asymmetry requires both antisymmetry and irreflexivity.
So, it is transitive closure of relation.
2. Consider the relation: R’ (x, y) if and only if x, y>0 over the set of non-zero rational
numbers, then R’ is _________
a) not equivalence relation
b) an equivalence relation
c) transitive and asymmetry relation
d) reflexive and antisymmetric relation
Answer: b
Explanation: Reflexive: a, a>0
Symmetric: if a, b>0 then both must be +ve or -ve, which means b, a > 0 also exists
Transitive: if a, b>0 and b, c>0 then to have b as same number, both pairs must be +ve
or -ve which implies a, c>0. Hence, R’ is an equivalence relation.
3. Let S be a set of n>0 elements. Let be the number Br of binary relations on S and let
Bf be the number of functions from S to S. The expression for Br and Bf, in terms of n
should be ____________
a) n2 and 2(n+1)2
b) n3 and n(n+1)
c) n and n(n+6)
d) 2(n*n) and nn
Answer: d
Explanation: For a set with n elements the number of binary relations should be
2(n*n) and the number of functions should be nn. Hence Br = 2(n*n) and Bf = nn.
4. Let A be a set of k (k>0) elements. Which is larger between the number of binary
relations (say, Nr) on A and the number of functions (say, Nf) from A to A?
a) number of relations
b) number of functions
c) the element set
d) number of subsets of the relation
Answer: a
Explanation: For a set with k elements the number of binary relations should be
2(n*n) and the number of functions should be nn. Now, 2(n*n) => n2log (2) [taking log] and
nn => nlog (n) [taking log]. It is known that n2log (2) > nlog (n). Hence, the number of
binary relations > the number of functions i.e, Nr > Nf.

5. Consider the binary relation, A = {(a,b) | b = a – 1 and a, b belong to {1, 2, 3}}. The
reflexive transitive closure of A is?
a) {(a,b) | a >= b and a, b belong to {1, 2, 3}}
b) {(a,b) | a > b and a, b belong to {1, 2, 3}}
c) {(a,b) | a <= b and a, b belong to {1, 2, 3}}
d) {(a,b) | a = b and a, b belong to {1, 2, 3}}
Answer: a
Explanation: By definition of Transitive closure we have that a is related to all smaller
b (as every a is related to b – 1) and from the reflexive property a is related to a.
6. Let R1 be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 be another
relation from B to C = {1, 2, 3, 4} as defined below:
i. An element a in A is related to an element b in B (under R1) if a * b is divisible by 3.
ii. An element a in B is related to an element b in C (under R2) if a * b is even but not
divisible by 3. Which is the composite relation R1R2 from A to C?
a) R1R2 = {(1, 2), (1, 4), (3, 3), (5, 4), (5,6), (7, 3)}
b) Φ
c) R1R2 = {(1, 2), (1,6), (3, 2), (3, 4), (5, 4), (7, 2)}
d) R1R2 = {(2,2), (3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}
Answer: b
Explanation: By definition, i) R1 = {(1,6), (3,2), (3,4), (3,6), (3,8), (5,6), (7,6)} and ii)
R2 = {(1,2), (1,4), (1,8), (5,2), (5,4), (5,8), (7,2), (7,4), (7,8)}. So, R1R2 = Φ.
7. How many binary relations are there on a set S with 9 distinct elements?
a) 290
b) 2100
c) 281
d) 260
Answer: c
Explanation: S is the set with 9 elements. A relation on S is defined as S x S. There are
92 number of ordered pairs in relation. So, the number of binary relations is 2(9*9) = 281.
8. Relations may exist between?
a. objects of the same set
b. between objects of two or more sets.
c. Both A and B
d. None of the above
Ans : C
Explanation: Relations may exist between objects of the same set or between objects of
two or more sets.
9. A binary relation R on a single set A is a subset of?
A. A X A
B. A U A
C. A ^ A
D. A ∩ A
Ans : A
Explanation: A binary relation R on a single set A is a subset of A×A.
10. A relation R on set A is called _________ if xRy implies yRx.
A. Irreflexive
B. Reflexive
C. Anti-Symmetric
D. Symmetric
Ans : D

Explanation: A relation R on set A is called Symmetric if xRy implies yRx.

11. The relation R={(a,b),(b,a)} on set X={a,b} is?

A. Irreflexive
B. Reflexive
C. Anti-Symmetric
D. Symmetric
Ans : A
Explanation: The relation R={(a,b),(b,a)} on set X={a,b} is irreflexive.
12. The binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is
__________
A. reflective, symmetric and transitive
B. irreflexive, symmetric and transitive
C. neither reflective, nor irreflexive but transitive
D. irreflexive and antisymmetric
Ans : C
Explanation: Not reflexive -> (3,3) not present; not irreflexive -> (1, 1) is present; not
symmetric -> (2, 1) is present but not (1, 2); not antisymmetric – (2, 3) and (3, 2) are
present; not asymmetric -> asymmetry requires both antisymmetry and irreflexivity. So,
it is transitive closure of relation.

13. Consider the binary relation, A = {(a,b) | b = a – 1 and a, b belong to {1, 2, 3}}. The
reflexive transitive closure of A is?

A. {(a,b) | a >= b and a, b belong to {1, 2, 3}}

B. {(a,b) | a > b and a, b belong to {1, 2, 3}}
C. {(a,b) | a <= b and a, b belong to {1, 2, 3}}
D. {(a,b) | a = b and a, b belong to {1, 2, 3}}
Ans : A
Explanation: By definition of Transitive closure we have that a is related to all smaller b
(as every a is related to b – 1) and from the reflexive property a is related to a.
14. . The ______ Relation between sets X and Y is the set X×Y

A. Empty
B. Full
C. Identity
D. Inverse
Answer : B

Explanation: The Full Relation between sets X and Y is the set X×Y.
REFERENCES
1. Susanna S. Epp. Discrete Mathematics with applications , Brooks /Cole
publishing co. 1995, 4th Edition 2010
2. J.P. Trembly and Manohar , DISCRETE MATHEMATICAL STRUCTURE
WITH APPLICATIONS TO COMPUTER SCIENCE Tata Mcgrow hill .1997
3. S.Lipschutz , M.lipson , DISCRETE MATHEMATICS , Schaum’s outline
series

Useful Links
1. https://www.youtube.com/watch?v=9a39kWlFg-s
2. https://www.youtube.com/watch?v=A08P9ZJsLOs
3. https://www.slideshare.net/muhammadzawawi1/relations-
digraphs
Assignment Questions:
1. Define Partition of a set.
2. Define relation on a set.
3. Define Inverse of a relation.
4. Let A  {a, b, c, d , e, f , g , h} Consider the following subsets of A
A1  {a, b, c, d }, A 2  {a, c, e, f , g , h}, A3  {a, c, e, g}, A4  {b, d }, A5  { f , h} . Then find the partition of A.

5. Let A  B  {1, 2,3} Define a relation R on A where aRb if and only if a  b .

6. Define matrix of a relation.
7. Define digraph of a relation.
8. Let A  {1, 2,3,4} and R  {(1,1)(1,2 )( 2,1)( 2, 2 )( 2,3)( 2 ,4)(3,4)(4,1)} is a relation on A. Draw the digraph of R.
9. Let A  {1,4,5} and R be given by the digraph shown below.Find the relation determined by the
following digraph

1 4

10. How do you characterize digraph of a reflexive relation

11. Let A  {a, b, c, d , e} and R  {( a, a ), (a, b), (b, c), (c, e), (c, d ), (d , e)}.

Then compute i) R 2 , ii) R ,

12 Let A  1,2,3,4,6 and aRb if and only if a is multiple of b. Find i) Domain,
ii) Range, iii) Matrix of arelation, iv) Digraph of the relation R.
13. Suppose that R and S are relations from A to B .
(i) If R  S , then Prove that R1  S 1
(ii) If R  S , then Prove that S  R
(iii) Prove that  R  S   R1  S 1 and  R  S   R1  S 1
1 1

(iv) Prove that  R  S   R  S and  R  S   R  S

14. If R is a relation on A  {a1 , a2 ,..., an } then Prove that M

R2
 M R M R

15. For n2 and R be a relation on a finite set A, then Prove that
M  M R M R ...M R (n factors)
Rn
THANK YOU