Aditya University

Extend a Hearty Welcome

to
SCHOOL OF ENGINEERING

Discrete Mathematics

Unit-II (Relations)

A.Y. 2024-25
Freshmen Engineering Department
 Definitions

Set:
A set is a well-defined collection of distinct objects.
For example
1. Set of vowels in English alphabet:
𝑨 = {𝒂, 𝒆, 𝒊, 𝒐, 𝒖}
2. Set of natural numbers less than 5:
𝑩 = {𝟏, 𝟐, 𝟑, 𝟒}
3. Set of colours in the rainbow:
C={red, orange, yellow, green, blue, indigo, violet}
 Definitions

Cartesian product:
Let 𝐴 and 𝐵 be any two sets. The Cartesian product of 𝐴 and 𝐵 is denoted as 𝐴 × 𝐵 and is
defined as 𝐴 × 𝐵 = { 𝑎, 𝑏 : 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵}
For example let 𝐴 = {1,2,3,4} and 𝐵 = {2,3,7} then
𝐴 × 𝐵 = { 1,2 , 1,3 , 1,7 , 2,2 , 2,3 , 2,7 , 3,2 , 3,3 , 3,7 , 4,2 , 4,3 , 4,7 }

Note: If 𝐴 has 𝑚 elements and 𝐵 has 𝑛 elements then 𝐴 × 𝐵 will have 𝑚𝑛 ordered pairs.
 Definitions
Relation:
A relation from a set A to a set B is a subset of the Cartesian product A×B
if and only if 𝑅 ⊆ 𝐴 × 𝐵.
It consists of ordered pairs (a, b) where a ∈ A in and b ∈ B, and a is related to b.
Note: If 𝑎 is related to 𝑏 under the relation 𝑅 then we write a𝑅𝑏 or < 𝑎, 𝑏 > ∈ 𝑅.

Relation on a Set:
A relation 𝑅 from a set 𝐴 to the set 𝐴 itself is called a relation on the set 𝐴 i.e., 𝑅 ⊆ 𝐴 × 𝐴
Thus 𝑅 = {< 𝑥, 𝑦 >/ 𝑥𝑅𝑦 𝑎𝑛𝑑 𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑦 ∈ 𝐴}.
 Example

Example1: Let 𝐴 = {2,3,4} and 𝐵 = {2,3,5,7}. Define a relation 𝑅 from 𝐴 to 𝐵 such that
𝑅 = 𝑥, 𝑦 𝑥 < 𝑦}
Solution:
 Example

Example2: Let 𝐴 = {1,2,3,4} . Define a relation 𝑅 from 𝐴 by 𝑅 = 𝑥, 𝑦 ∈ 𝑅 𝑥 − 𝑦 𝑖𝑠 𝑒𝑣𝑒𝑛}

Solution: Let 𝐴 = {1,2,3,4}
The relation is defined as 𝑅 = 𝑥, 𝑦 ∈ 𝑅 𝑥 − 𝑦 𝑖𝑠 𝑒𝑣𝑒𝑛}
 Definitions

Domain & Range of a Relation:

Let 𝑅 be a relation defined on two sets 𝐴 and 𝐵.
The domain of 𝑅 is denoted by "𝑑𝑜𝑚𝑅" is defined as
𝑑𝑜𝑚𝑅 = {𝑥|𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥𝑅𝑦 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑦 ∈ 𝐵}.
The range of 𝑅 is denoted by 𝑟𝑎𝑛𝑅 is defined as
𝑟𝑎𝑛𝑅 = {𝑦|𝑦 ∈ 𝐵 𝑎𝑛𝑑 𝑥𝑅𝑦 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑥 ∈ 𝐴}.
𝑅 = { 𝑥, 𝑦 / 𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑦 ∈ 𝐵}
For example let 𝑅 = { 1,2 , 2,2 , 3,3 , 3,7 }
Then 𝑑𝑜𝑚𝑅 = {1,2,3} and 𝑟𝑎𝑛𝑅 = {2,3,7}
 Example

Example: Let R be the relation from 𝑋 = {2,3,4,5} and 𝑌 = 3,6,7,10 which is defined
by “X divides Y then .
(a) Write R as a set of order pairs
(b) Find range and domain of R
 Definitions

Operations on a Relation:
Let 𝑅 and 𝑆 be relations from 𝐴 to 𝐵
𝑖) 𝑅 ∩ 𝑆 = {(𝑥, 𝑦) ∈ 𝐴 × 𝐵 | (𝑥, 𝑦) ∈ 𝑅 𝑎𝑛𝑑 (𝑥, 𝑦) ∈ 𝑆 }
is the intersection of the relations 𝑅 and 𝑆

𝑖𝑖) 𝑅 ∪ 𝑆 = {(𝑥, 𝑦) ∈ 𝐴 × 𝐵 | (𝑥, 𝑦) ∈ 𝑅 𝑜𝑟 (𝑥, 𝑦) ∈ 𝑆 }

is the union of the relations 𝑅 & 𝑆

𝑖𝑖𝑖) 𝑅 − 𝑆 = {(𝑥, 𝑦) ∈ 𝐴 × 𝐵|(𝑥, 𝑦) ∈ 𝑅 𝑎𝑛𝑑 (𝑥, 𝑦) ∉ 𝑆 }

is the difference of the relations 𝑅 and 𝑆
 Example

Example-1: Let 𝑹 = { 𝟏, 𝟐 , 𝟐, 𝟒 , 𝟑, 𝟑 } and 𝑺 = { 𝟏, 𝟑 , 𝟐, 𝟒 , 𝟒, 𝟐 } then

find 𝑹 ∪ 𝑺, 𝑹 ∩ 𝑺, 𝑹 − 𝑺 ,D(𝑹 ∪ 𝑺) and R(𝑹 ∩ 𝑺)
 Example

Example-2: What is the range of the relation S= { 𝒙, 𝒙𝟐 | 𝒙 ∈ 𝑵} and 𝑻 = 𝒙, 𝟐𝒙 | 𝒙 ∈ 𝑵 .

Find S ∪ 𝑻, 𝑺 ∩ 𝑻
 Definitions

Properties of Relations:
Reflexive
Symmetric
Transitive
Irreflexive
Anti-symmetric
Asymmetric
 Definitions

Reflexive:
Let R be a relation on set 𝐴 𝑡ℎ𝑒𝑛 𝑅 𝑖𝑠 reflexive if order pair 𝑎, 𝑎 ∈ 𝑅 ∀𝑎 ∈ 𝐴
For example let 𝐴 = 1,2,3,4 then the relation
𝑅 = { 1,1 , 1,3 , 2,2 , 3,3 , 4,1 , 4,4 } is Reflexive

Note: If (𝑥, 𝑥) ∉ 𝑅 for at least one 𝑥 ∈ 𝐴 then 𝑅 is not reflexive

Irreflexive:
A relation 𝑅 in a set 𝐴 is Irreflexive if for every 𝑎 ∈ 𝐴, (𝑎, 𝑎) ∉ 𝑅
For example let 𝐴 = 1,2,3,4 then the relation 𝑅 = { 3,2 , 3,4 , 4,3 } is irreflexive

Note: If (𝑥, 𝑥) ∈ 𝑅 for at least one 𝑥 ∈ 𝐴 then 𝑅 is not irreflexive

Note: Any relation which is not reflexive is not necessarily irreflexive.

The relation 𝑆 = { 1,1 , 1,2 , 3,2 , 2,3 , 3,3 } in the set 𝐴 = 1,2,3 is not reflexive not
irreflexive.
 Definitions

Symmetric:
Let R be a relation on set 𝐴 𝑡ℎ𝑒𝑛 𝑅 𝑖𝑠 Symmetry if order pair 𝑎, 𝑏 ∈ 𝑅 ⇒ 𝑏, 𝑎 ∈ 𝑅 ∀𝑎, 𝑏 ∈ 𝐴
i.e., if (𝑎, 𝑏) ∈ 𝑅 then (𝑏, 𝑎) ∈ 𝑅.
For example let 𝐴 = 1,2,3,4 then the relation 𝑅 = { 1,1 , 1,3 , 3,1 , 3,4 , 4,3 } is symmetric

Note : If (𝑥, 𝑦) ∈ 𝑅, but (𝑦, 𝑥) ∉ 𝑅 for at least on pair (𝑥, 𝑦) ∈ 𝐴 × 𝐴 then 𝑅 is not symmetric

Anti-Symmetric:
A relation 𝑅 in a set 𝐴 is anti-symmetric if for every 𝑎 and 𝑏 in 𝐴 whenever
𝑎, 𝑏 ∈ 𝑅 𝑎𝑛𝑑 (𝑏, 𝑎) ∈ R then a= 𝑏.
For example let 𝐴 = 1,2,3 then the relation 𝑅 = { 1,1 , 2, 2 , 3,1 } is symmetric

Asymmetric:
A relation 𝑅 on a set 𝑋 is asymmetric if (𝑥, 𝑦) ∈ 𝑅 then (𝑦, 𝑥) ∉ 𝑅
For example let 𝐴 = 1,2,3,4 then the relation 𝑅 = { 1,2 , 3,1 , 2,4 , 4,3 } is asymmetric
 Definitions

Transitive:
Let R be a relation on set 𝐴 𝑡ℎ𝑒𝑛 𝑅 𝑖𝑠 Transitive if order pair 𝑎, 𝑏 ∈ 𝑅, 𝑏, 𝑐 ∈ 𝑅 ⇒
𝑎, 𝑐 ∈ 𝑅 ∀𝑎, 𝑏, 𝑐 ∈ 𝐴
For example let 𝐴 = 1,2,3,4 then the relation
𝑅 = {(1,1), (1,3), (3,1), (3,4), (4,3), (3,3), (1,4), (4,1), (4,4)}is transitive
 Definitions

Equivalence Relation:
Let R be a relation on a set A. Then R is called an equivalence relation if it satisfies
the following three properties for all 𝑎, 𝑏, 𝑐 ∈ 𝐴:
1. Reflexive:
Every element is related to itself. That is, 𝑎𝑅𝑎
2. Symmetric:
If a is related to b, then b is related to a.
If 𝑎𝑅𝑏, then 𝑏𝑅𝑎
3. Transitive:
If a is related to b and b is related to c, then a is related to c.
If 𝑎𝑅𝑏 and 𝑏𝑅𝑐, then 𝑎𝑅𝑐
 Example

Example 1: Determine whether the relation R={(1,1),(2,2),(3,3),(1,2),(2,1)} is an equivalence relation.

1. Reflexive
A relation on set A is reflexive if (a,a)∈R all a∈A .
Here, the elements involved in R are A={1,2,3}.
(1,1)∈R(1,1) in R(1,1)∈R
(2,2)∈R(2,2) in R(2,2)∈R
(3,3)∈R(3,3) in R(3,3)∈R
∴ Relation is Reflexive
2. Symmetric
A relation is symmetric if whenever (a,b)∈ R then (b,a)∈ R too.
Checking:
(1,2)∈ R ⇒ (2,1)∈R
(2,1)∈R ⇒ (1,2)∈R
All other pairs like (1,1),(2,2),(3,3) already satisfy symmetry trivially.
∴ Relation is Symmetric
 Example
3. Transitive
A relation is transitive if whenever (a,b)∈R and (b,c)∈R , then (a,c)∈R.
Check cases:
Given R={(1,1),(2,2),(3,3),(1,2),(2,1)}

All chains satisfy transitivity.

∴ Relation is Transitive
∴ 𝑹 𝒊𝒔 𝒂𝒏 𝒆𝒒𝒖𝒊𝒗𝒂𝒍𝒆𝒏𝒄𝒆 𝒓𝒆𝒍𝒂𝒕𝒊𝒐𝒏
 Definitions

Example-2: Let 𝑿 = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟔, 𝟕} and 𝑹 = 𝒙, 𝒚 𝒙 − 𝒚 𝒊𝒔 𝒅𝒊𝒗𝒊𝒔𝒊𝒃𝒍𝒆 𝒃𝒚 𝟑} in 𝑿. Show that 𝑹 is an equivalence

relation.
Solution:
To prove 𝑅 is an equivalence relation we need to prove 𝑅 is reflexive, symmetric and Transitive
𝑖) For any 𝑥 ∈ 𝑋 we have 𝑥 − 𝑥 is divisible by 3 hence 𝑥𝑅𝑥 for all 𝑥 ∈ 𝑋
Thus 𝑅 is reflexive
𝑖𝑖) For any 𝑥, 𝑦 ∈ 𝑋 if 𝑥 − 𝑦 is divisible by 3 then − 𝑥 − 𝑦 is also divisible by 3
i.e., 𝑦 − 𝑥 is divisible by 3
Hence 𝑥𝑅𝑦 ⇒ 𝑦𝑅𝑥. Thus 𝑅 is symmetric
𝑖𝑖𝑖) For any 𝑥, 𝑦, 𝑧 ∈ 𝑋 if 𝑥 − 𝑦 is divisible by 3 and 𝑦 − 𝑧 is divisible by 3 then
𝑥 − 𝑦 + 𝑦 − 𝑧 is also divisible by 3
i.e., 𝑥 − 𝑧 is divisible by 3
Hence 𝑥𝑅𝑦, 𝑦𝑅𝑧 ⇒ 𝑥𝑅𝑧. Thus 𝑅 is transitive
Hence 𝑅 is an equivalence relation in 𝑋
 Definitions

Relation Matrix: If 𝐴 = {𝑎1 , 𝑎2 , … , 𝑎𝑚 } and 𝐵 = {𝑏1 , 𝑏2 , … , 𝑏𝑛 } are finite sets

containing 𝑚 and 𝑛 elements respectively and 𝑅 is a relation from 𝐴 to 𝐵, then we
can represent the relation 𝑅 by an 𝑚 × 𝑛, called Relation matrix, denoted by
𝑀𝑅 = 𝑚𝑖𝑗 where
𝑚×𝑛

1, 𝑖𝑓 𝑎𝑖 , 𝑏𝑗 ∈ 𝑅
𝑚𝑖𝑗 = ቐ
0, 𝑖𝑓 𝑎𝑖 , 𝑏𝑗 ∉ 𝑅
 Example

Example-1: Let 𝑨 = {𝒂𝟏 , 𝒂𝟐 , 𝒂𝟑 } and 𝑩 = {𝒃𝟏 , 𝒃𝟐 , 𝒃𝟑 , 𝒃𝟒 }, the relation 𝑹 from 𝑨 to 𝑩 is given by

𝑹 = { 𝒂𝟏 , 𝒃𝟏 , 𝒂𝟏 , 𝒃𝟒 , 𝒂𝟐 , 𝒃𝟐 , 𝒂𝟐 , 𝒃𝟑 , 𝒂𝟑 , 𝒃𝟏 , 𝒂𝟑 , 𝒃𝟑 }.Find the relation matrix 𝑴𝑹
Solution: given relation is
𝑅 = { 𝑎1 , 𝑏1 , 𝑎1 , 𝑏4 , 𝑎2 , 𝑏2 , 𝑎2 , 𝑏3 , 𝑎3 , 𝑏1 , 𝑎3 , 𝑏3 }
Now the relation matrix is
𝑏1 𝑏2 𝑏3 𝑏4
𝑎1 1 0 0 1
𝑀𝑅 = 𝑎
2 0 1 1 0
𝑎3 1 0 1 0

1 0 0 1
𝑀𝑅 = 0 1 1 0 is the required Relation matrix
1 0 1 0
 Example

Example-2: Let 𝑨 = {𝟏, 𝟐, 𝟑} and 𝑩 = {𝟏, 𝟐, 𝟑, 𝟒} then obtain the relation from
𝟏 𝟎 𝟏 𝟏
the matrix 𝑴𝑹 = 𝟎 𝟏 𝟏 𝟎
𝟏 𝟎 𝟎 𝟎
 Example

Example-3: If R is the relation on A={1,2,3} such that (a, b)R, iff a+b=even,
find the relational matrix MR.
Solution:
Relation R is defined as aRb iff a+b=even
𝐴𝑋𝐴 ={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

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

1 0 1
 
M R = 0 1 0 
1 0 1
 Properties

Properties of Relation matrix:

The matrix of a relation on a set, which is square matrix, can be used to determine
whether the relation has certain properties
𝑖) 𝑅 is reflexive if all the elements on the principal diagonal of 𝑀𝑅 are equal to 1
𝑖𝑖) 𝑅 is symmetric if the relation matrix is symmetric. i.e., 𝑀𝑅 = 𝑀𝑅 𝑇
𝑖𝑖𝑖) 𝑅 is anti-symmetric if 𝑚𝑖𝑗 = 1 for 𝑖 ≠ 𝑗, then 𝑚𝑗𝑖 = 0 .
 Examples
Example: Suppose that the relation 𝑹 on a set is represented by the matrix
𝟏 𝟏 𝟎
𝑴𝑹 = 𝟏 𝟏 𝟏 . Is 𝑹 reflexive, symmetric or anti-symmetric?
𝟎 𝟏 𝟏
 Definitions

Partition of a set:
Let A be a non empty set and A1,A2,…,An are the subsets of A.
A partition set of A is denoted by P or П and defined as

(i ) Ai  
(ii ) Ai  A j = 
n
(iii )  Ai = A
i =1

The sets A1,A2,…,An are called the blocks of the partition.

 Example

Example : Let A={1,2,3,4,5,6} then the collection of sets A1={1,2,3}, A2={4,5},

A3={6} then P={A1,A2,A3} forms a partition of A since these sets are

(i)not empty
(ii)Disjoint
i.e., A1  A2 =  , A2  A3 =  and A1  A3 = 
also A1  A2  A3 = A
(iii) And their union is A
 Defination

Covering of a set:
Let S be a given set and A={A1,A2,…,An}where each
Ai,i=1,2,…,n is a subset of S.

If (i ) Ai  
n
(ii )  Ai = S
i =1

Then A is called a Covering of S.

The sets A1,A2,…,An are said to cover S.
Remark:
Every Partition is also a Covering of a Set, but the converse
need not be true.
Example

and Partition ?
 Definitions

Composite Relation:
Let 𝑅 be a relation from a set 𝐴 to a set 𝐵 and 𝑆 a relation from 𝐵 to a set 𝐶. The composite of
𝑆 and 𝑅 is the relation consisting of ordered pairs (𝑎, 𝑐), where 𝑎 ∈ 𝐴, 𝑐 ∈ 𝐶, and for which
there exists an element 𝑏 ∈ 𝐵 such that (𝑎, 𝑏) ∈ 𝑅 and (𝑏, 𝑐) ∈ 𝑆.
We denote the composite of 𝑅 and 𝑆 by𝑹𝜊𝑺.
𝑺 𝜊 𝑹 = {(𝒂, 𝒄) / 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩, 𝒄 ∈ 𝑪, (𝒂, 𝒃) ∈ 𝑹 𝒂𝒏𝒅 (𝒃, 𝒄) ∈ 𝑺}

Note: 𝐼𝑡 𝑖𝑠 𝑡𝑜 𝑏𝑒 𝑛𝑜𝑡𝑒𝑑 𝑡ℎ𝑎𝑡 𝑆 𝑜 𝑅 ≠ 𝑅 𝑜 𝑆

 Definitions
Example : Let R = {(1, 2), (3, 4), (2, 2)} and S = {(4, 2), (2, 5), (3, 1),(1,3)}
Then find R o S and S o R
 Definitions

Power of a Relation:
Let 𝑅 be a relation on the set 𝐴. The powers 𝑅𝑛 , 𝑛 = 1, 2, 3,−− −are defined
by 𝑹𝟏 = 𝑹 and 𝑹𝒏+𝟏 = 𝑹𝒏 𝜊 𝑹

Transitive Closure of a Relation:

The transitive closure of a relation 𝑅 is the smallest transitive relation containing 𝑅.
We denote transitive closure of 𝑅 by 𝑅+ . Let 𝑋 be any set containing 𝑛 elements and
𝑅 be the relation in 𝑋. The relation 𝑅+ = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ ⋯ ∪ 𝑅𝑛 in 𝑋 is called the
transitive closure of 𝑅 in 𝑋.
 Examples

Example 1: Let 𝑿 = {𝟏, 𝟐, 𝟑, 𝟒} and 𝑹 = { 𝟏, 𝟐 , 𝟐, 𝟑 , 𝟑, 𝟒 } be the relation on 𝑿 find 𝑹+ .

Solution: Given 𝑅 = { 1,2 , 2,3 , 3,4 }
Now 𝑅2 = 𝑅𝜊𝑅 = 1,2 , 2,3 , 3,4 𝜊 1,2 , 2,3 , 3,4
= { 1,3 , 2,4 }
𝑅3 = 𝑅 2 𝜊𝑅 = 1,3 , 2,4 𝜊 1,2 , 2,3 , 3,4 = { 1,4 }
𝑅4 = 𝑅 3 𝜊𝑅 = { 1,4 }𝜊 1,2 , 2,3 , 3,4 = 𝜙
∴ 𝑅+ = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ 𝑅4 = { 1,2 , 1,3 , 1,4 , 2,3 , 2,4 , 3,4 }
This is the transitive closure of the relation 𝑅 in 𝑋
 Example

Example 2: Find the transitive closure of R if R={(a, b),(b, c),(c, d),(d, e)}.
Solution: Given 𝑅 = {(a, b),(b, c),(c, d),(d, e)}.
Now,
 Warshall’s Algorithm

Given: Let R be a relation which is not transitive

Aim: The transitive closure R* has to be constructed.
Step 1: R is a relation defined on a set A with n elements.
Step 2: Write the n x n matrix 𝑀𝑅 representing the relation 𝑅
Step 3: Take 𝑀𝑅 = 𝑊0
Step 4: Empty the zero values of 𝑊0 and keep it blank.
Step 5:Count the no. of 1’s in column1 and the [Link] 1’s in row 1. Write the positions of 1’s in
col1 and [Link] the Cartesian product of these positions .This will create new pairs,
which should be represented by ‘1’ in matrix 𝑊1
Step6: Count the no. of 1’s in column2 and the [Link] 1’s in row 2. Write the positions of 1’s in
col2 and [Link] the Cartesian product of these positions .This will create new pairs,
which should be represented by ‘1’ in matrix 𝑊2
Step7:Repeat this procedure up to nth column and nth row to construct the matrix 𝑊𝑛
Step8: Write the matrix 𝑊1 into the relation R* which is the transitive closure of the relation R.
 Definitions

Find the transitive closure of the relation R={(1,4),(2,1),(2,3),(3,1),(3,4),(4,3)} using Warshall’s Algorithm
Solution:
Here R is not transitive relation since (1,4), (4,3) in R but (1,3) not in R.
To find the transitive closure R*,
Step1: The relation R is defined on the set A={1,2,3,4} n(A)=4
Step2: Write the 4 x 4 matrix 𝑀𝑅 representing the relation.
1 2 3 4
1 0 0 0 1
2 1 0 1 0
MR =
3 1 0 0 1
 
4 0 0 1 0

Step3: Take MR=W0

1 2 3 4
1 0 0 0 1
2 1 0 1 0
W0 =
3 1 0 0 1
 
4 0 0 1 0
 Example
Step4: Empty the 0’s in W0.
1 2 3 4
1 − − − 1
2  1 − 1 − 
W0 =
3 1 − − 1
 
4 − − 1 −

Step5: Count the 1’s in column 𝐶1 ,there are two 1’s in {2,3} positions and
only 1’s in row 𝑅1 at {4} position.
Find the cartesian product of 𝐶1 𝑋𝑅1 = {2,3}x{4}={(2,4),(3,4)}

Step6: Write 𝑊1 matrix by including these new pairs

1 2 3 4
1 − − − 1
2  1 − 1 1 
W1 =
3 1 − − 1
 
4 − − 1 −
 Step7: Count the 1’s in col 𝐶2 ,there are no 1’s .Therefore the position set is ∅ .
Three 1’s in row 𝑅2 at {1,3,4} positions.
Find the Cartesian product of 𝐶2 𝑋𝑅2 = ∅ x{1,3,4}= ∅
Therefore W2=W1
Step8: Write 𝑊2 matrix
1 2 3 4
1 − − − 1

2 1 − 1 
1
W2 =
3 1 − − 1
 
4 − − 1 −
Step8: Count the 1’s in col 𝐶3 ,there are two1’s at {2,4} positions.
Two 1’s in row 𝑅3 at {1,4} positions.
Find the cartesian product of 𝐶1 𝑋𝑅1 ={2,4}x{1,4}={(2,1),(4,1),(2,4),(4,4)}
Step9: Write 𝑊3 matrix including the new pairs
1 2 3 4
1 − − − 1
2  1 − 1 1
W3 =
3 1 − − 1
 
4 1 − 1 1 Discrete Mathematics
Step10: Count the 1’s in col 𝐶4 ,there are four 1’s at {1,2,3,4}positions.
Three 1’s in row 𝑅4 at {1,3,4} positions.
Find the cartesian product of
𝐶4 𝑋𝑅4 ={1,2,3,4}x{1,3,4}={(1,1),(2,1),(3,1),(4,1),(1,3),(2,3),(3,3),(4,3),(1,4),(2,4),(3,4),(4,4)}

Step11: Write 𝑊4 matrix including the new pairs 1 2 3 4

1 1 − 1 1
2 1 − 1 1
W4 =
3 1 − 1 1
 
4 1 − 1 1

1 2 3 4
Step12: Write the relation matrix from 𝑊4 .
1 1 0 1 1
2 1 0 1 1
M R* =
3 1 0 1 1
 
4 1 0 1 1

Step13: Write the transitive closure R*

R*={(1,1),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4)}
Discrete Mathematics
 Definitions

Graph of a Relation:
1.A relation graph is a graphical representation of a relation on a set. The resulting graph is
called digraph or a directed graph.
[Link] R be a relation in a set 𝑋 = {𝑥1 , 𝑥2 ,−− −, 𝑥𝑛 } then the elements of 𝑋 are represented by
points or circles called nodes or vertices.
[Link] 𝑥𝑖 , 𝑥𝑗 ∈ 𝑅 then we connect 𝑥𝑖 & 𝑥𝑗 by an arc and put an arrow on the arc in the direction
from 𝑥𝑖 to 𝑥𝑗 this directed arc is called an edge. If 𝑥𝑖 , 𝑥𝑖 ∈ 𝑅 we get an arc which starts
from node 𝑥𝑖 and returns to node 𝑥𝑖 , such an arc is called a loop
 Properties

Properties of Relations through Graph of a Relation:

From the graph of a relation it is possible to observe some of its properties
[Link] a relation is reflexive then there must be a loop at each node.
[Link] a relation is Irreflexive then there is no loop at any node.
3. If the relation is symmetric if one node is connected to another then there must be a
return arc from the second node to the first.
[Link] the relation is anti-symmetric no such directed return path as in symmetric case.
5.A relation is transitive if and only if whenever there is an edge form a vertex 𝑥 to a
vertex 𝑦 and a vertex 𝑦 to a vertex 𝑧, there is an edge from 𝑥 to 𝑧
 Examples

Example-1: Draw the graph of the relation

𝑹 = { 𝟏, 𝟏 , 𝟏, 𝟑 , 𝟐, 𝟏 , 𝟐, 𝟑 , 𝟐, 𝟒 , 𝟑, 𝟏 , 𝟑, 𝟐 , 𝟒, 𝟏 , 4,3 } on the set {𝟏, 𝟐, 𝟑, 𝟒}
Solution: Given that 𝑅 = { 1,1 , 1,3 , 2,1 , 2,3 , 2,4 , 3,1 , 3,2 , 4,1 , 4,3 }
Then the graph of the relation is
 Examples
Example-2: Determine whether the relation with the directed graph shown is an equivalence relation

Solution:
Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}
From the given graph we have the relation
𝑅 = { 𝑎, 𝑎 , 𝑎, 𝑏 , 𝑎, 𝑑 , 𝑏, 𝑎 , 𝑏, 𝑏 , 𝑏, 𝑐 , 𝑐, 𝑏 , 𝑐, 𝑐 , 𝑐, 𝑑 , 𝑑, 𝑎 , 𝑑, 𝑐 , 𝑑, 𝑑 }
Clearly 𝑥, 𝑥 ∈ 𝑅 ∀𝑥 ∈ 𝐴 hence 𝑅 is reflexive
The relation 𝑅 is symmetric
Since 𝑎, 𝑏 ∈ 𝑅 ⇒ 𝑏, 𝑎 ∈ 𝑅
𝑎, 𝑑 ∈ 𝑅 ⇒ 𝑑, 𝑎 ∈ 𝑅
𝑏, 𝑐 ∈ 𝑅 ⇒ 𝑐, 𝑏 ∈ 𝑅
and 𝑐, 𝑑 ∈ 𝑅 ⇒ 𝑑, 𝑐 ∈ 𝑅
The given relation 𝑅 is not transitive
Because 𝑎, 𝑏 ∈ 𝑅, 𝑏, 𝑐 ∈ 𝑅 but 𝑎, 𝑐 ∉ 𝑅
Hence the given relation is not equivalence.
 Examples

OR

𝑅 is reflexive since there is a loop at every vertex of the directed graph of 𝑅

𝑅 is symmetric since for every edge between distinct vertices in the directed
graph there is an edge in the opposite direction.
𝑅 is not transitive since there is an edge between the vertices 𝑎, 𝑏 and
between the vertices 𝑏, 𝑐 but 𝑎, 𝑐 are not connected by an edge
From the above we conclude that 𝑅 is not equivalence relation.
 Definitions

Partial Order Relation:

A binary relation R in a set P is called a partial order relation or a partial ordering in P if and only if R is
reflexive, anti-symmetric and transitive.
Partial Ordered Set (OR) Poset:
If ≤ is a partial ordering on P, then the ordered pair 𝑃, ≤ is called a partially ordered set or a POSET.
Note: here ≤ is the symbol used to represent a relation

Hasse Diagram:
A Hasse diagram is a graphical representation of a partial order relation in which the arrows are omitted
but are understood to point upward.
Procedure for drawing Hasse diagram:
Step I : Draw diagraph of relation
Step 2: Remove all self loops.
Step 3: Remove transitive edge.
Step 4: Arrange all edges pointing from upward.
 Examples

Example-1: Draw the Hasse diagram for the partial ordering 𝑅 = {(𝒙, 𝒚)\𝒙 divides 𝒚} where 𝑿 = 𝟏, 𝟐, 𝟑, 𝟔
Solution: Given that 𝑋 = 𝟏, 𝟐, 𝟑, 𝟔 and the relation i𝑠 𝑥 divides 𝑦.
Then 𝑋, ≤ = { 1, 1 , 1, 2 , 1, 3 , 1,6 , 2, 2 , 2, 6 , 3, 3 , 3, 6 , (6, 6)}
The Hasse diagram is
 Examples

Example-2: Let A={1,2,4,8} Relation R={(a, b)∣a divides b} then Draw the Hasse diagram
Solution: Given that 𝑋 = 𝟏, 𝟐, 𝟒, 𝟖 and the relation i𝑠 𝑥 divides 𝑦.
Then 𝑋, ≤ = { 1, 1 , 1, 2 , 1, 4 , 1,8 , 2, 2 , 2, 4 , 2, 8 , 4, 4 , 4, 8 , (8, 8)}
The Hasse diagram is
 Examples
Example-3: Let 𝑿 = {𝟐, 𝟑, 𝟔, 𝟏𝟐, 𝟐𝟒, 𝟑𝟔} and the relation ≤ be such that 𝒙 ≤ 𝒚 if 𝒙 divides 𝒚.
Solution: Given that 𝑋 = {2,3,6,12,24,36} and the relation ≤ be such that 𝑥 ≤ 𝑦 if 𝑥 divides 𝑦.
Then 𝑋, ≤ = { 2, 2 2,6 , 2,12 , 2,24 , (2, 36) 3, 3 3,6 , 3,12 , 3,24 , 3,36 ,
6, 6 6,12 , 6,24 , 6,36 , 12, 12 , 12,24 , 12,36 , 24, 24 , (36,36)}
The Hasse diagram is
 Examples

Example-4: Let 𝑨 be the set of factors of the positive integer 12 and let ≤ be the relation divides. Draw the Hasse
diagram for 𝑨, ≤
Solution: The factors of the positive integer 12 are 1,2,3,4,6,12
Hence 𝐴 = {1,2,3,4,6,12}
If 𝑥 divides 𝑦 then 𝑥, 𝑦 ∈ 𝐴, ≤
Then the poset is given by
𝐴, ≤
= { 1, 1 , 1,2 , 1,3 , 1,4 , 1,6 , 1,12 , 2, 2 2,4 , 2,6 , 2,12 , 3, 3 3,6 , 3,12 , 4, 4 , 4,12 , 6, 6 6,12 , (12,12)}
 Examples

Example-5: Let 𝑨 = {𝒂, 𝒃, 𝒄} be a given finite set and 𝑷 𝑨 its power set. Let ⊆ be the inclusion relation on the elements
of 𝑷 𝑨 .Draw Hasse diagram of 𝑷 𝑨 , ⊆ .
Solution: Given that 𝐴 = {𝑎, 𝑏, 𝑐}
The power set 𝐴 is given by 𝑃 𝐴 = {𝜙, 𝑎 , 𝑏 , 𝑐 , 𝑎, 𝑏 , 𝑏, 𝑐 , 𝑐, 𝑎 , 𝐴}
Then the poset 𝑃 𝐴 , ⊆ =
{ 𝜙, 𝑎 , 𝜙, 𝑏 , 𝜙, 𝑐 , 𝜙, 𝑎, 𝑏 , 𝜙, 𝑏, 𝑐 , 𝜙, 𝑐, 𝑎 , 𝜙, 𝐴 , 𝑎 , 𝑎, 𝑏 , 𝑎 , 𝑎, 𝑐 , 𝑎 , 𝐴 ,
𝑏 , {𝑎, 𝑏} , 𝑏 , {𝑏, 𝑐} , 𝑏 , 𝐴 , 𝑐 , {𝑎, 𝑏} , 𝑐 , {𝑏, 𝑐} , 𝑐 , 𝐴 , 𝑎, 𝑏 , 𝐴 , 𝑏, 𝑐 , 𝐴 , 𝑐, 𝑎 , 𝐴 }

The Hasse diagram for the given poset 𝑃 𝐴 , ⊆ is