Amity School of Engineering & Technology (CSE)

Discrete Mathematics
Module II
Lecture-1
Relation
Anant Kr Jayswal
ASET(CSE)
1
 Amity School of Engineering & Technology (CSE)

Module I:
q Relation and properties of relation

2
 Amity School of Engineering & Technology (CSE)

OBJECTIVES
After completing this section, you will be able to

1.1 Explain Cross production

1.2 Differentiate between Relation and functions

1.3 Various properties of relation

3
 Amity School of Engineering & Technology (CSE)

Relation
Introduction

We start by considering a simple example.

Let S denote the set of all students at AMITY University, Noida and
Let T denote the set of all teaching staff there.
For every student sS and every teaching staff tT, exactly one of the
following is true:

v s has attended a lecture given by t, or

v s has not attended a lecture given by t.

We now define a relation R as follows.

Let sS and tT.
We say that sRt if s has attended a lecture given by t. If we now look at
all possible pairs (s,t) of students and teaching staff, then some of these
pairs will satisfy the relation while other pairs may not.
4
 Amity School of Engineering & Technology (CSE)

Relation
Introduction
Formally, we define a relation in terms of these “ordered pairs”.
Relations, as noted above, will be defined in terms of ordered pairs (a, b)
of elements, where a is designated as the first element and b as the
second element.

Some definitions required to define relation

Ordered Pair:
Let A and B are two sets and let aA and bB then a set of two elements
whose elements have been listed in a specific order is called an ordered
pair. It is denoted by (a,b).
Particularly:
For different a and b: (a,b)(b,a) and
If (a1,b1)=(a2,b2)  a1=a2 and b1=b2
Thus in case of relation (a,b)(b,a) unless a=b, whereas in case of Sets,
the order of elements is irrelevant; for example {2,3}={3,2}.
5
 Amity School of Engineering & Technology (CSE)

Relation
Some definitions required to define relation

Definition2: (Cartesian product of two sets):

Let A and B be two nonempty sets. The set AB = {(a,b) : aA and bB} is
called the Cartesian product of the sets A and B. In other words, AB is
the set of all ordered pairs (a,b), where aA and bB. In short this product
AB is read as “A cross B”.
Example1
Let A = {1, 2} and B= {a, b, c}. Then
AB = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}
BXA = {(a, 1), (a, 2) (b, 1) (b, 2), (c, 1), (c, 2)}
And AXA = {(1, 1), (1,2),(2,1),(2,2)}
Clearly, from this example, we can note down the following points:
ABBA
If A has n elements and B has m elements than AB has m.n elements.
If A= and (or) B= then AB=
If AB=BA  A=B
6
 Amity School of Engineering & Technology (CSE)

Relation
RELATION

Let A and B are two nonempty sets. A binary relation or, simply, relation
from A to B is a subset of A X B i.e.
R is a relation from A to B  R (AB)

Example1
Let A = {1, 2,3} and B= {a, b, c}
Then AB={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)}
R1={(1,a),(1,c)}
R2={(1,a),(2,a),(2,c)}
R3={(3,c)} are all examples of relations from A to B.

Suppose R is a relation from A to B (i.e. R (AB)).

That is, for each pair aA and bB, exactly one of the following is true:
v (a,b)R, we then say “a is R-related to b”. We write aRb.
v (a, b)R, we then say “a is not R-related to b”. 7
 Amity School of Engineering & Technology (CSE)

Relation
Domain and Range of a Relation
If R (AB) is a relation from AB, then
v Domain(R)={a: (a,b)R} and
v Range(R)={b: (a,b)R}.
The domain of a relation R is the set of all first elements of the ordered
pairs which belong to R, and the range of R is the set of second
elements.

Example
Let A = {1, 2,3} and B= {a, b, c}
Then AB={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)}
R={(1,a),(2,a),(2,c)}

v Domain(R)={1,2}
v Range(R)={a,c}.

8
 Amity School of Engineering & Technology (CSE)

Relation
Some Examples
Example1: Let A={1,2,3,4}. Define a relation R on A by writing (x,y)R if x
< y. Then
R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}.

Example2: Let A={1,2,3}. Define a relation R on A as

R={(a,b): a is divisible by b. We have R = {(1,1),(2,1),(3,1),(2,2),(3,3)}.

Example3:Let A be the power set of the set {1,2} in other words, A =

{,{1},{2},{1,2}} is the set of subsets of the set {1,2}. Write a relation on A,
where (P,Q)R, if PQ.
In this case we have:
R = {(,{1}), (,{2}), (,{1,2}), ({1},{1,2}), ({2},{1,2})}.

9
 Amity School of Engineering & Technology (CSE)

Summary

Ø Let A and B be two nonempty sets. The Cartesian product AB

= {(a,b) : aA and bB}. In other words, AB is the set of all
ordered pairs (a,b), where aA and bB.
Ø A binary relation or, simply, relation from A to B is a subset of
A X B i.e. R is a relation from A to B  R (AB)
Ø If R (AB) is a relation from AB, then
Domain(R)={a: (a,b)R} and
Range(R)={b: (a,b)R}.

10
Amity School of Engineering & Technology (CSE)

11
 Amity School of Engineering & Technology (CSE)

Discrete Mathematics
Module II
Lecture-2
Types of Relation
Anant Kr Jayswal
ASET(CSE)
12
 Amity School of Engineering & Technology (CSE)

Module I:
q Types of Relation

13
 Amity School of Engineering & Technology (CSE)

OBJECTIVES
After completing this section, you will be able to

Ø Differentiate between various types of Relations

Ø Relate types of relation with Directed graphs

14
 Amity School of Engineering & Technology (CSE)

Types of Relations

15
 Amity School of Engineering & Technology (CSE)

Types of Relations
Let A be a given non empty set then a relation RAA is called a
binary relation on A.
Binary relations that satisfy certain special properties can be very
useful in solving computation problems. So let’s discuss some of
these properties:

We have following types of properties in a (Binary) relation on a

given set A.
1. Reflexive
2. Irreflexive
3. Symmetric
4. Asymmetric
5. Anti-symmetric
6. Transitive
16
Amity School of Engineering & Technology (CSE)

17
 Amity School of Engineering & Technology (CSE)

Types of Relation
Reflexive
A relation R on a set A is reflexive if for every aA, aRa. that is, a relation
R in a set A is said to be reflexive if every element of A is related to itself
i.e. aRa is true for every aA.

Definition2: (In terms of directed graph): R is reflexive if there must be a

loop at each node aA.

Example:
Example1: Let A be the set of all straight lines in a plane. The relation R
“x is parallel to y” is reflexive since every straight line is parallel to itself.
Example2: Let A be the set of numbers and relation R in A is defined by
“x is equal to y” is reflexive” since each number is equal to itself.
Example3: Let A={1,2,3} and the relation R in A is defined by
R={(1,1),(2,2),(2,3)} is not reflexive because (3,3) does not belongs to R.
The given relation R will be reflexive, if every ordered pair (a,a)R for all
aA. 18
 Amity School of Engineering & Technology (CSE)

Types of Relation..
Irreflexive Relations

A relations R on a set is irreflexive if (a, a)R for every a є A. Thus R is not

irreflexive if there exist at least one aA such that (a, a)R.
Definition2: (In terms of directed graph): R is Irreflexive if there is no loop
at any node aA.
Note: No self loop allowed

Example:
Example1: Let A= {1,2,3} and let R= {(1, 1),(3,2)}.
Here R is not reflexive since (2,2) or (3,3)R. Also R is not irreflexive,
since (1, 1)R.
Example2: Let A={a,b,c}be a non empty set. Let R={(a,b),(b,c),(c,a)}
Here R is irreflexive since (a,a) )R for every aA. Also note that there is no
loop at any node.

19
 Amity School of Engineering & Technology (CSE)

Types of Relation
Symmetric Relation

A relation R on a set A is symmetric if a,b in A, if aRb, then bRa. In other

words a relation R is symmetric if in R whenever (a, b)R then (b, a)R.
Thus R is not symmetric if there exists a, bA such that (a, b)R but (b, a)R.

Example
Example1: Let A={set of all straight lines in a plane}. The Relation R on A
is defined by “ a is perpendicular to be” is a symmetric relation because
ab  ba.
Example2: Let N={set of Natural numbers}. The Relation R on N is
defined by “ a is equal to b” is symmetric since aRbbRa.

20
 Amity School of Engineering & Technology (CSE)

Types of Relation
Asymmetric Relation

A relation R on a set A is symmetric if a,b in A, if aRb, then bRa in not

allowed. In other words a relation R is Asymmetric if in R whenever (a,
b)R then (b, a)R.
Thus R is not symmetric if there exists a, bA such that (a, b)R but (b, a)R.
Note: No bidirectional arrow.

Example
Example1: Let A={set of all straight lines in a plane}. The Relation R on A
is defined by “ a is perpendicular to be” is a symmetric relation because
ab  ba.
Example2: Let N={set of Natural numbers}. The Relation R on N is
defined by “ a is equal to b” is symmetric since aRbbRa.

21
 Amity School of Engineering & Technology (CSE)

Types of Relation
Anti-Symmetric Relation

A relation R on a set A is anti-symmetric if whenever aRb and bRa then a

= b. That is if (a,b),(b,a)R then there must be the case that a=b. Thus R
is not antisymmetric if there exists a, bA such that (a, b) and (b, a) belong
to R, but
a≠b
Note: No Bi-directional arrow except self loop.

Example

Let A be a set of positive integers and R be a relation on A such that

R={(a,b): a,bA and ab}. This relation R is an anti-symmetric relation
because if (a,b),(b,a)R a=b

22
Amity School of Engineering & Technology (CSE)

23
 Amity School of Engineering & Technology (CSE)

Types of Relation
Transitive Relation

A relation R on a set A is said to be transitive if (a,b)R and (b,c)R (a,c)R,

for all a,b,cA.
In other words relation R is transitive if aRb and bRc implies that aRc, for
all a,b,cA
Thus R is not transitive if there exist a, b, c A such that (a, b), (b, c)R but
(a, c)R.

Example
Consider the following five relations on the set A = {1, 2, 3, 4, 5}:

R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

This relation is Transitive

24
Amity School of Engineering & Technology (CSE)

25
 Amity School of Engineering & Technology (CSE)

Summary

Ø A relation R on a set A is called reflexive if there is a self loop

at each node in directed graph of a relation.

Ø A relation R on a set A is called symmetric if there is an arrow

from then there is a return arrow from .

Ø A relation R on a set A is said to be transitive if there is an

arrow from then there is an arrow from .

26
Amity School of Engineering & Technology (CSE)

27
 Amity School of Engineering & Technology (CSE)

Discrete Mathematics
Module II
Lecture-2
Digraph Representation
of Relation
Anant Kr Jayswal
ASET(CSE) 28
 Amity School of Engineering & Technology (CSE)

Module II:
q Digraph Representation of
Relation

29
 Amity School of Engineering & Technology (CSE)

OBJECTIVES
After completing this section, you will be able to

Ø Explain Digraph (directed graph)

Ø Understand how to make a digraph of a given relation

30
 Amity School of Engineering & Technology (CSE)

Representing Relation using Digraph

Pictorial representation is an another way of representing
a relation (also known as Directed graph or simply
Digraph).

Digraph representation of binary relations:

� A binary relation on a set can be represented by a digraph.� Let R be a
binary relation on a set A, that is R is a subset of .
Then the digraph, call it G, representing R can be constructed as follows:�
1. The vertices of the digraph G are the elements of A, and� 2. <x, y> is
an arc of G from vertex x to vertex y if and only if <x, y> is
in R.

31
 Amity School of Engineering & Technology (CSE)

Example
The less than relation R on the set of integers A ={1,2,3,4} is
the set {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
and it can be represented by the following digraph:

32
 Amity School of Engineering & Technology (CSE)

Digraph representation: Reflexive, Symmetric & Transitive

Relation:

33
 Amity School of Engineering & Technology (CSE)

Example

34
 Amity School of Engineering & Technology (CSE)

Check your progress1

35
 Amity School of Engineering & Technology (CSE)

Summary
Ø A relation R on a set A is called reflexive if there is a self loop
at each node in directed graph of a relation.

Ø A relation R on a set A is called symmetric if there is an arrow

from then there is a return arrow from .

Ø A relation R on a set A is said to be transitive if there is an

arrow from then there is an arrow from .

36
Amity School of Engineering & Technology (CSE)

37
 Amity School of Engineering & Technology (CSE)

Discrete Mathematics
Module II
Lecture-3
Equivalence and Partial
order relation
Anant Kr Jayswal
ASET(CSE)
38
 Amity School of Engineering & Technology (CSE)

Module I:
q Equivalence and Partial Order
Relation

39
 Amity School of Engineering & Technology (CSE)

OBJECTIVES
After completing this section, you will be able to

Ø Define Equivalence Relation

Ø Define Partial Order Relation

Ø Differentiate Between Equivalence Relation and Partial

Order Relation

40
 Amity School of Engineering & Technology (CSE)

Equivalence Relation
A relation R in a set A is said to be an equivalence relation if

1) R is Reflexive i.e. aRa aA.

2) R is Symmetric i.e. aRabRa, a,bA.
3) R is Transitive i.e. If aRb and bRc aRc a,b,cA.

Example1: Relation R on a set A defined by “a is equal to b” is an

equivalence relation, since it is reflexive (a = a for every aA), symmetric
(If a = b, then b = a , a,bA) and transitive (If a = b and b = c, then a = c,
a,b,cA).

41
 Amity School of Engineering & Technology (CSE)

Partial Order Relation

A relation R on a set A is called a Partial ordering or a partial order
relation, if it is:
Reflexive, i.e. aRa aA.
Anti-symmetric, i.e. If aRb and bRa a=b a,bA.
Transitive i.e. If aRb and bRc aRc a,b,cA.

The set over which a partial order is defined is called a partially ordered
set (or POSET). It is denoted by (A,R) where A is a given set and R is a
relation which satisfy the above three conditions.

Example: The relation ≤ (less than or equal to) on the set R of real
numbers is a partial order relation.
Since the relation () is:
1. Reflexive i.e. aa, aR
2. Anti-symmetric i.e. a b and b aa=b, a,bR
3. Transitive i.e ab and bc, ac a,b,cR

42
 Amity School of Engineering & Technology (CSE)

OBJECTIVES
Summary

Ø A relation R on a set A is said to be an equivalence relation

if R is Reflexive, Symmetric and Transitive

Ø A relation R on a set A is said to be an Partial-Order relation

if R is Reflexive, Anti-symmetric and Transitive.

43
Amity School of Engineering & Technology (CSE)

44
 Amity School of Engineering Technology

Warshall Algorithm
• Input: Adjacency matrix A of relation R on a set of n elements
• Output: Adjacency matrix T of the transitive closure of R.
Algorithm
• Body:
• T := A [initialize T to A]
for j := 1 to n
for i := 1 to n
if Ti, j = 1 then
ai := ai ∨ aj [form the Boolean OR of row i and row j, store
it in i a ]
next i
next j
end Algorithm
45
 Amity School of Engineering Technology

Example
•

• Let A =

• apply the Warshall algorithm to find the

transitive closure.

46
 Amity School of Engineering Technology

j = 1 i = 1, Ti, j = 0 no action
i = 2 Ti, j = 0 no action
i = 3 Ti, j = 0 no action

Therefore W = T [1] = A

47
 Amity School of Engineering Technology

j = 2 i = 1 Ti, j = 1
(0 1 0) OR (0 1 1) = (0 ∨ 0,1∨1,0 ∨1) =
(0 1 1) row 1 of T becomes (0 1 1)
i = 2 Ti, j = 1 row 2 OR row 2 is
computed and put into row 2 however, row
2 OR row 2 = row 2
i = 3 Ti, j = 0 no action

48
 Amity School of Engineering Technology

j = 3 i = 1 Ti, j = 0 no action
i = 2 Ti, j = 1 (0 1 1) OR (0 0 0)
= ( 0 ∨ 0,1∨ 0,1∨ 0) = (0 1 1) result is put into
row 2, which is unchanged
i = 3 Ti, j = 0 no action.
At this stage T = [3] W = [2] W above. We
now have the transitive closure.

49
 Amity School of Engineering Technology

Poset
A relation R on a set S is called a partial order if it is
• Reflexive
• Antisymmetric
• Transitive

Notation:
a b, when (a,b) R

50
 Amity School of Engineering Technology

Example
• Let R ={1,2,3} identify the relation RxR is
poset or not.
• RxR
={(1,1),(1,2)(1,3),(2,1),(2,2),(2,3),(3,1),(3,
2),(3,3)}
• The 3 condition for poset are:
– Reflexive : {(a,a) should belongs to R for
Every element of set}
– In our case it is true hence it is refelxive
51
 Amity School of Engineering Technology

– Anitsymmetric: if(a,b)ϵ R then (b,a) not

belongs to R unless a=b.
– In our case antisymmetric property doesnot
hold good. As Cartesian product always
results in all possible element.
– Therefore the RxR is not a poset.

52
 Amity School of Engineering Technology

Hasse Diagrams
• Patrial order set have conventional
graphical representation called Hasse
diagram.
• Hasse diagram can be drawn from
digraph of the relation
• Remove all self loops
• Remove all transitive edges
• Remove directions on edges assuming
that they are oriented upwards 53
 Amity School of Engineering Technology

Example
• Convert the following Digraph to Hasse
Diagram.

54
 Amity School of Engineering Technology

Hasse Diagram

55
 Amity School of Engineering Technology

• Draw Hasse diagram for ({3, 4, 12, 24,

48, 72}, /)

In the diagram, 3 and 4 are at same

level because they are not related to
each other and they are smaller than
other elements in the set. The next
succeeding element for 3 and 4 is 12
i.e, 12 is divisible by both 3 and 4.
Then 24 is divisible by 3, 4 and 12.
Hence, it is placed above 12. 24
divides both 48 and 72 but 48 does
not divide 72. Hence 48 and 72 are 56
not joined.
 Amity School of Engineering Technology

Maximal and Minimal Element

• A maximal element of a subset S of
some partially ordered set (poset) is
an element of S that is not smaller than
any other element in S.
• A minimal element of a subset S of
some partially ordered set is defined
dually as an element of S that is not
greater than any other
57
 Amity School of Engineering Technology

Maximum and minimum

Element
• Maximum element: if it is maximal and
every element is related to it.
• Minimum element: If it is minimal and it
is every element of poset.

58
 Amity School of Engineering Technology

Example
In the figure, we have 3 minimal
elements (2,3,5)
And 3 maximal elements (10,15,24)

No Minimum element
No maximum element

59
 Amity School of Engineering Technology

Least upper bound (LUB)

• It is also called as supremum.
• It is also called as join.
• It is denoted (a v b)

60
 Amity School of Engineering Technology

Upper bound and lower bound

• Upper bound:Let B be a subset of a set
A. An element xϵ A is in upper bound of
B if (y,x) ϵ poset forevery yϵB.
• Lower Bound:An element xϵ A is in
upper bound of B if (x,y) ϵ poset
forevery yϵB.

61
 Amity School of Engineering Technology

Least upper bound and

Greatest lower bound

If a is an upper bound for S which is

related to all other upper bounds then it is
the least upper bound, denoted lub(S).
Similarly for the greatest lower bound,
glb(S).

62
 Amity School of Engineering Technology

Example
In the poset above {a, b, c} is the greatest
element.
Ø is the least element.

63