UNIT-III

 Cartesian Products and Relations

 Matrix and Digraph representation of relation
 Properties of Relations
 Equivalence Relations and Partitions
 Operations on Relations
 Transitive closure
 Partial order relation and Posets
 Hasse diagram

Cartesian Product of two sets

Let 𝐴 and 𝐵 be two sets . Then the set of all ordered pairs (𝑎, 𝑏) , where 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 ,

is called Cartesian product or cross product of A and B and is denoted by 𝐴 × 𝐵.

Thus 𝐴 × 𝐵 = {(𝑎, 𝑏)/ 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵 }

Note: 1) 𝐴 × 𝐵 ≠ 𝐵 × 𝐴, since (𝑎, 𝑏) ≠ (𝑏, 𝑎)

2.If A and B are finite sets with |𝐴| = 𝑚, |𝐵| = 𝑛, then

|𝐴 × 𝐵| = No. of elements of 𝐴 × 𝐵 = 𝑚𝑛

3. |𝑃(𝐴 × 𝐵)| = no. of elements of power set of (𝐴 × 𝐵 ) = 2𝑚𝑛

If A has 4 elements ,B has 5 elements then 𝐴 × 𝐵 has 2𝑚𝑛 = 24.5 = 220

Subsets.

Example: If A = { 2,3,4}, B= {4,5} then

(1) 𝐴 × 𝐵 = { 2,3,4} × {4,5} = {(2,4), (2,5), (3,4), (3,5), (4,4), (4,5)}

(2) 𝐵 × 𝐴 = {4,5} × { 2,3,4} = {(4,2), (4,3), (4,4), }(5,2), (5,3), (5,4)}

MVS Page 1
 (3) 𝐴 × 𝐴 = { 2,3,4} × { 2,3,4} =

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

4) 𝐵 × 𝐵 = {4,5} × {4,5} = {(4,4), (4,5), (5,4), (5,5)}

Binary Relation
Let 𝑨 and B be two non- empty sets. If 𝑹 ⊆ 𝑨 × 𝑩 , then 𝑹 is said to be a binary
relation from 𝑨 to 𝑩.

Therefore , any subset of 𝑨 × 𝑩 is a relation from 𝑨 to 𝑩.

If (𝒂, 𝒃) 𝝐 𝑹, then 𝒂 is related to 𝒃 and is written as 𝒂𝑹𝒃.

𝑨×𝑩
R
𝑹 ⊆ 𝑨×𝑩

Domain of R : The set {𝑎 ∈ 𝐴: (𝑎, 𝑏)𝜖 𝑅 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑏𝜖𝐵 } is called the domain of R
and is denoted by 𝐷𝑅 or dom(R )

(OR)

The set of all first elements of the ordered pairs in a relation R from a set A to a set
B is called domain of R.

Range of R : The set {𝑏 ∈ 𝐴: (𝑎, 𝑏)𝜖 𝑅 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑎 𝜖 𝐴 } is called the range of R

The set of all second elements in a relation R from a set A to a set B is called range
of R.
MVS Page 2
 If R is a relation from a set A to itself, we say that is a relation on A .
i.e 𝑹 ⊆ 𝑨 × 𝑨

A binary relation from A to itself is said to be a relation on A

(OR)

If 𝐑 ⊆ 𝐀 × 𝐀 then R is said to be a binary relation from A to A

or simply a relation on A .

In other words, a binary relation from A to B is a set R of ordered pairs where the first
element of each ordered pair comes from A and the second element comes from B. We
use the notation 𝑎 𝑅 𝑏 to denote that (𝑎, 𝑏) ∈ 𝑅 and 𝑎 𝑅 𝑏 to denote that (𝑎, 𝑏) ∉ 𝑅.
Moreover, when (𝑎, 𝑏) ∈ 𝑅, 𝑎 is said to be related to 𝑏 by 𝑅. Binary relations represent
relationships between the elements of two sets.

Example-1

Let = {2,3,5} , and B={2,3,4,6,7}. Define a relation R from A to B as

𝑅 = {(𝑎, 𝑏)⁄𝑎 𝑖𝑠 a factor of b}

Then 𝑅 = {(2,2), (2,4), (2,6), (3,3), (3,6)}

on it self
Dom ( R )={2,3} and range (R) ={2,3,4,6}

Example-2
Let A = {a, b, c} B = {r, s, t}
Then R = {(a, r), (b, r), (b, t), (c, s)} is a relation from A to B.

MVS Page 3
ii) Let A = {1, 2, 3} and B = A
R = {(1, 1), (2, 2), (3, 3)}
is a relation (equal) on A.

Example-3

Let A = {5, 6, 7, 8, 9, 10} and B = {7, 8, 9, 10, 11, 13}.

Define a relation R from A to B by

R = {(x, y): y = x + 2}. Write down the domain and range of R.

Answer : Here, R = {(5, 7), (6, 8), (7, 9), (8, 10), (9, 11)}.

Domain of R = {5, 6, 7, 8, 9}

Range of R = {7, 8, 9, 10, 11}

MVS Page 4
Example-4
Let 𝐴 ={3,6,9 } , 𝐵 = {4,8,12 }

Then 𝑅 ={(3,4 ), (3,8) , (3,12) } is a relation from A to B

Example-5

Define a relation R from A = {chicken, dog, cat} to B = {fish, rice, cotton} by

R = {(a, b)| a eats b}.

Then R = {(chicken, fish), (chicken, rice), (dog, fish), (dog, rice), (cat, fish), (cat,
rice)}. Its adjacency matrix is

Adjacency Matrix of a Relation: (Relation as a Matrix )

𝑀𝑅 is the adjacency matrix of the relation R.

Example-1
Define a relation R from A = {chicken, dog, cat} to B = {fish, rice, cotton} by

R = {(a, b)| a eats b}.

Then R = {(chicken, fish), (chicken, rice), (dog, fish), (dog, rice), (cat, fish), (cat, rice)}. Its
adjacency matrix is

MVS Page 5
Example -2

(OR)
0 1 1
𝑀𝑅 = [0 0 1]
0 0 0
MVS Page 6
Example-2

Solution:

Relation as an Arrow Diagram

If A and B are finite sets and R is a relation from A to B. Relation R can be represented as
an arrow diagram as follows.

Draw two ellipses for the sets A and B. Write down the elements of A and elements of B
column-wise in these ellipses. If (𝑎, 𝑏) ∈ 𝑅 where 𝑎 ∈ A and 𝑏 ∈ B, then we draw an
arrow from an element 𝑎 in A to an element 𝑏 in B .

Example

Let A = {5, 6, 7, 8, 9, 10} and B = {7, 8, 9, 10, 11, 13}.

Define a relation R from A to B by

R = {(x, y): y = x + 2}. Write down the domain and range of R.

Answer : Here, R = {(5, 7), (6, 8), (7, 9), (8, 10), (9, 11)}.

MVS Page 7
Relation as a Directed Graph:

There is another way of picturing a relation R when R is a relation from a finite set
to itself. Let R be a relation on the set A

We denote every element of 𝐴 by a point, called a vertex or node, and each ordered pair
(𝒂, 𝒃) in R by a directed arc or a directed line segment, called an edge , from 𝒂 to b. The
resulting diagram is a directed graph or simply a digraph. If an edge (𝒂, 𝒃) exists,we say
that vertex 𝒃 is adjacent to vertex 𝒂.

An edge of the form (𝒂, 𝒂) is represented using an arc from the vertex 𝒂 back to
itself. Such an edge is called a loop.

Example-1

The directed graph of the relation

R = {(1, 1),(1, 3),(2, 1),(2, 3),(2, 4),(3, 1),(3, 2),(4, 1)} on the set {1, 2, 3, 4}

Digraph of the relation R

MVS Page 8
Example-2

What are the ordered pairs in the relation R represented by the directed graph
shown in Figure

Solution:

Ans: R = {(1, 3),(1, 4),(2, 1),(2, 2),(2, 3),(3, 1),(3, 3),(4, 1),(4, 3)}.

Example-3

Let A = {1, 2, 3, 4}
R = {(1, 2) (2, 2) (2, 4) (3, 2) (3, 4) (4, 1) (4, 3)} is a relation on A

Example-4

Let A={2,3,4,6} and R={(a ,b)/ a is a factor of b}

Represent the relation R by directed graph.

Solution: Given

R = {(a , b)/ a is a factor of b}

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

MVS Page 9
 Example-5:
Consider the relation R whose digraph is given below.

The graph tells us that R is a relation on A={1,2,3} and

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

MVS Page 10
Properties of Relations
Relations can have several properties which help to classify them.

1.
A relation R on a set A is said to be reflexive if

(𝑎, 𝑎) ∈ 𝑅 ,for all 𝑎 ∈ 𝐴

i,e 𝑎 𝑅 𝑎 for all 𝑎 ∈ 𝐴.

Example-2

If A = {1, 2, 3, 4} then R = {(1, 1) (2, 2), (1, 3), (2, 4), (3, 3), (3, 4), (4, 4)}.

Is R a relation reflexive?

Solution: The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2),
(3, 3), (4, 4) ∈ R.

H.W

Which of the following relations on A = {x, y, z} are reflexive?

𝑅1 = {(𝑥, 𝑥), (𝑥, 𝑦), (𝑦, 𝑦), (𝑧, 𝑧)}

𝑅2 = {(𝑥, 𝑥 ), (𝑦, 𝑦), (𝑦, 𝑧), (𝑧, 𝑦)}

𝑅3 = {(𝑥, 𝑥), (𝑦, 𝑦), (𝑧, 𝑧)}

MVS Page 11
A relation R on set A is said to be irreflexive if (a, a) ∉ R for every a ∈ A.

Example-1

Let A = {1, 2, 3} and R = {(1, 2), (2,3 ), (3, 1), (1, 3)}

The relation R is irreflexive. Since (𝑎, 𝑎) ∉ 𝑅 for any element of set A.

Example-2

Let A = {1, 2, 3} and R = {(1, 2), (2, 2), (3, 1), (1, 3)}. Is the relation R reflexive or irreflexive?

Solution: The relation R is not reflexive as (2, 2) ∈ R.

A relation R on set A is said to be symmetric

whenever (a, b) ∈ R then (b, a) ∈ R for all a,b ∈ R

R is Symmetric: If any one element is related to any other element, then the second
is related to the first

Example-1

Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}. Is a relation R symmetric or not?

Solution: The relation is symmetric as for every (a, b) ∈ R, we have (b, a) ∈ R,

i.e., (1, 2), (2, 1), (2, 3), (3, 2) ∈ R but not reflexive because (3, 3) ∉ R.

Example-2

Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3)}

The relation R is not symmetric , as (2, 3) ∈ R but (3, 2) ∉ R

MVS Page 12
Example-3

Let A= set of all male persons and define R={ (a,b)/ a is a brother of b}

Then R is symmetric relation on A.

Example-4

Let A = {1, 2, 3,4,5,6,7,8,9,10,11}

define R={ (a,b)/ a – b is divisible by 3}

here, the relation R is symmetric as a – b is divisible by 3 the b-a is also divisible by 3

Note: 1.Relation ⊥r is symmetric since a line a is ⊥r to b, then b is ⊥r to a.

2. Parallel is symmetric, since if a line a is ∥ to b then b is also ∥ to a.

A relation R on a set A is antisymmetric whenever (a, b) ∈ R and (b, a) ∈ R

then a = b. (OR)

A relation R defined on a set A is said to be antisymmetric

if (𝑎, 𝑏) ∈ 𝑅 and 𝑎 ≠ 𝑏,then (𝑏, 𝑎) ∉ 𝑅 for all 𝑎, 𝑏, ∈ 𝐴

Example1: Let A = {1, 2, 3} and R = {(1, 1), (2, 2)}. Is the relation R antisymmetric?

Solution: The relation R is antisymmetric as a = b when (a, b) and (b, a) both belong to R.

Example2: Let A = {4, 5, 6} and R = {(4, 4), (4, 5), (5, 4), (5, 6), (4, 6)}. Is the relation R
antisymmetric?

Ans: It is not antisymmetric since (4, 5) ∈ R and (5, 4) ∈ R, but 4 ≠ 5

MVS Page 13
 :

A relation R on a set A is called an Asymmetric Relation if for every (a, b) ∈ R

implies that (b, a) does not belong to R.

Example: Let A = {4, 5, 6} and R = { (4, 5), (5, 6), (4, 6)}.

Here, the relation R asymmetric.

A Relation R on set A is said to be transitive

if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R, for all a,b,c ∈ R

R is Transitive: If any one element is related to a second and that second element is
related to a third, then the first element is related to the third.

R is not transitive: If there are elements 𝑥, 𝑦 and 𝑧 in 𝐴 such that (𝑥, 𝑦) ∈ 𝑅 and
(𝑦, 𝑧) ∈ 𝑅 but (𝑦, 𝑧) ∉ 𝑅

MVS Page 14
Example-1

Example 2: Let A = {1, 2, 3} and R = {(1, 2), (2, 1), (1, 1), (2, 2)}. Is the relation transitive?

Solution: The relation R is transitive as for every (a, b) (b, c) belong to R, we have (a, c) ∈ R i.e, (1,
2) (2, 1) ∈ R ⇒ (1, 1) ∈ R.

Note1: The Relation ≤ ( Less than or equal to) , ⊆ (sub set)

and / (divides) are always transitive relations.
(i) If a ≤ b, b ≤ c then a ≤
(ii) If A ⊆ B, B ⊆ C then A ⊆ C
(iii) If a/b and b/c then a/c.

Example:

Consider the following relations on {1, 2, 3, 4}:

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

𝑅2 = {(1, 1),(1, 2),(2, 1)},

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

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

𝑅5 = {(1, 1),(1, 2),(1, 3),(1, 4),(2, 2),(2, 3),(2, 4),(3, 3),(3, 4),(4, 4)},
MVS Page 15
 𝑅6 = {(3, 4)}.

1 Which of these relations are reflexive?

2 Which of the relations are symmetric and which are antisymmetric?

3 Which of the relations are transitive?

MVS Page 16
 Let R be a relation on the set A .
1.Reflexive : (𝒂, 𝒂) ∈ 𝑹, ∀ 𝒂 ∈ 𝑨
2.Symmetric: If (𝒂, 𝒃) ∈ 𝑹 and (𝒃, 𝒂) ∈ 𝑹 ∀ 𝒂 , 𝒃 ∈ 𝑨
3.Transitive: If (𝒂, 𝒃) ∈ 𝑹 and (𝒃, 𝒄) ∈ 𝑹 then (𝒂, 𝒄) ∈ 𝑹, ∀ 𝒂 , 𝒃, 𝒄 ∈ 𝑨
4.Antisymmetric : If (𝒂, 𝒃) ∈ 𝑹 and (𝒃, 𝒂) ∈ 𝑹 then 𝒂 = 𝒃 ∀ 𝒂 , 𝒃 ∈ 𝑨
5.Irreflexive: (𝒂, 𝒂) ∉ 𝑹, ∀𝒂 ∈ 𝑨
6.Asymmetric: If (𝒂, 𝒃) ∈ 𝑹 then (𝒃, 𝒂) ∉ 𝑹, ∀ 𝒂 , 𝒃 ∈ 𝑨

Give an example of a nonempty set and a relation on the set that satisfies each of the
following combinations of properties; draw a digraph of the relation.

(a) symmetric and transitive, but not reflexive.

(b) symmetric and reflexive, but not transitive.

(c) transitive and reflexive,but not symmetric

(d) transitive and reflexive, but not antisymmetric.

(e) transitive and antisymmetric, but not reflexive.

(f) antisymmetric and reflexive, but not transitive.

MVS Page 17
Ans:

EQUIVALENCE RELATION
A relation R on a set A is called an equivalence relation if it satisfies following three properties:

1. Relation R is Reflexive : (𝒂, 𝒂) ∈ 𝑹, ∀ 𝒂 ∈ 𝑨

2. Relation R is Symmetric : If (𝒂, 𝒃) ∈ 𝑹 then (𝒃, 𝒂) ∈ 𝑹 ∀ 𝒂 , 𝒃 ∈ 𝑨
3. Relation R is transitive :If (𝒂, 𝒃) ∈ 𝑹 and (𝒃, 𝒄) ∈ 𝑹 then (𝒂, 𝒄) ∈ 𝑹,
∀ 𝒂 , 𝒃, 𝒄 ∈ 𝑨

A binary relation on a non-empty set A is said to be an equivalence

relation if and only if the relation is
 reflexive
 symmetric, and
 transitive.

MVS Page 18
Example-1 Let A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}.

Show that R is an Equivalence Relation.

Solution:

Reflexive: Relation R is reflexive as (1, 1), (2, 2), (3, 3) and (4, 4) ∈ R.

Symmetric: Relation R is symmetric because whenever (a, b) ∈ R, (b, a) also belongs to R.

here, (2, 4) ∈ R ⟹ (4, 2) ∈ R.

Transitive: Relation R is transitive because whenever (a, b) and (b, c) belongs to R, (a, c) also
belongs to R.

here,(3, 1) ∈ R and (1, 3) ∈ R ⟹ (3, 3) ∈ R.

So, as R is reflexive, symmetric and transitive, hence, R is an Equivalence Relation.

Example-2

Note: If 𝑅1 and 𝑅2 are equivalence relations then 𝑅1 ∩ 𝑅2 is also an equivalence

relation.

Example: A = {1, 2, 3}
R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
R1∩ R2 = {(1, 1), (2, 2), (3, 3)}

MVS Page 19
Example-3:

Let 𝐴 = {1,2,3,4,5,6,7} and 𝑅 = {(𝑎, 𝑏)⁄𝑎 − 𝑏 𝑖𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3}

Then 𝑅 is equivalence on 𝐴

Solution:

(i)Reflexive: 𝑎 − 𝑎 = 0, is divisible by (𝑎, 𝑎) ∈ 𝑅 ∀𝑎 ∈ 𝐴

∴ R is reflexive

(ii)Symmetric: Let (𝑎, 𝑏) ∈ 𝑅 ⇒ 𝑎 − 𝑏 is divisible by 3

⇒ 𝑏 − 𝑎 is also divisible by 3

∴(𝑎, 𝑏) ∈ 𝑅 ⇒ (𝑏, 𝑎) ∈ 𝑅 ∴ R is symmetric.

(iii) Transitive: Let 𝑎𝑅𝑏 and 𝑏𝑅𝑐

𝑎 − 𝑏 is divisible by 3 and 𝑏 − 𝑐 is divisible by 3

𝑎 − 𝑏 = 3𝑘, and 𝑏 − 𝑐 = 3𝑙 where 𝑘, 𝑙 are integers

⇒ 𝑎 − 𝑐 = (𝑎 − 𝑏) + (𝑏 − 𝑐 ) = 3𝑘 + 3𝑙 = 3(𝑘 + 𝑙) = 3𝑚 where, 𝑘 + 𝑙 = 𝑚

⇒ 𝑎 − 𝑐 is divisible by 3

i.𝑒 𝑎𝑅𝑐 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑐 ⇒ 𝑎𝑅𝑐

∴𝑅 is transitive

Hence the relation R is equivalence relation.

Example-4

Let Z denote the set of integers and the relation R in Z be defined by 𝑎𝑅𝑏 iff

𝑎 − 𝑏 is an even integer.Then show that 𝑅 is an equivalence relation

Solution:

(i)Reflexive: 𝑎 − 𝑎 = 0 which is an even integer 𝑎 𝑅𝑎 ∀𝑎 ∈ 𝑧 ∴ R is reflexive

(ii)Symmetric: Let 𝑎𝑅𝑏 ⇒ 𝑎 − 𝑏 is a even integer ⇒ −(𝑎 − 𝑏) is an even integer

MVS Page 20
 ⇒ 𝑏 − 𝑎 is an even integer

∴𝑏𝑅𝑎 𝑖. 𝑒, , 𝑎𝑅𝑏 ⇒ 𝑏𝑅𝑎 ∴ R is symmetric.

(iii) Transitive: Let 𝑎𝑅𝑏 and 𝑏𝑅𝑐 .

𝑎𝑅𝑏 ⇒ 𝑎 − 𝑏 is an even integer

𝑏𝑅𝑐 ⇒ 𝑏 − 𝑐 is an even integer.

𝑎 − 𝑐 = (𝑎 − 𝑏) + (𝑏 − 𝑐)

∴ (𝑎 − 𝑐) is an even integer.

i.𝑒 𝑎𝑅𝑐 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑐 ⇒ 𝑎𝑅𝑐

∴R is transitive

R is reflexive symmetric and transitive. Thus R is an equivalence relation.

Example-5

Show that the ”divides” relation is the set of positive integers in not an equivalence
relation.

Solution: We show that the ”divides” relation is reflexive and transitive and is not
symmetric. We conclude that the ”divides” relation on the set of positive integers is not an
equivalence relation.
𝑎
(i)Reflexive: i.e 𝑎 divides 𝑎 ,
𝑎

𝑎 𝑅𝑎 ∀𝑎 ∈ 𝑁 ∴ R is reflexive

(ii)Symmetric: R is not symmetric 2 divides 4 but 4 does not divide 2

∴ 𝑖. 𝑒, , (𝑎, 𝑏) ∈ 𝑅 but (𝑏, 𝑎) need not be a member of 𝑅

(iii) Transitive: Let 𝑎𝑅𝑏 and 𝑏𝑅𝑐

a divides b and b divides c

⇒ a divides c

i.𝑒 𝑎𝑅𝑐 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑐 ⇒ 𝑎𝑅𝑐

MVS Page 21
∴𝑅 is transitive

As R is not symmetric, we conclude that 𝑅 is not an equivalence relation.

Example-6

Let 𝑅 denotes a relation on the set 𝑃 = 𝑁 × 𝑁, where N is set of natural numbers,

defined as (𝑥, 𝑦)𝑅 (𝑢, 𝑣 ) if and only if 𝑥𝑣 = 𝑦𝑢. Then show that 𝑅 is an equivalence
relation on 𝑃.

Solution.

Given 𝑃 = {(𝑥, 𝑦) 𝑥 𝑎𝑛𝑑 𝑦 𝑎𝑟𝑒 𝑛𝑎𝑡𝑢𝑟𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟𝑠}

and 𝑅 is a relation defined as

(𝑥, 𝑦)𝑅 (𝑢, 𝑣 ) if and only if 𝑥𝑣 = 𝑦𝑢

⇒ 𝑥𝑣 = 𝑦𝑢 ---(1) and 𝑢𝑛 = 𝑣𝑚 -----(2)Type equation here.

𝑥𝑣
From (1) 𝑢 = , substituting 𝑢 in (2)
𝑦

MVS Page 22
 𝑥𝑣
We have ( ) 𝑛 = 𝑣𝑚
𝑦

⇒ 𝑥𝑛 = 𝑦𝑚

∴ 〈𝑢, 𝑣〉𝑅〈𝑚, 𝑛〉

Therefore R is reflexive, symmetric , and transitive.

Hence R is an equivalence relation.

Example-7

If R and S are equivalence relations on X, show that

a) 𝑅 ∩ 𝑆 also equivalent
b) 𝑅 ∪ 𝑆 need not be an equivalence relation.

Solution:

MVS Page 23
 ⇒ 〈𝑥, 𝑧〉 ∈ 𝑅 ∵R is transitive

⇒ 〈𝑥, 𝑧〉 ∈ 𝑆 ∵S is transitive

∴ 〈𝑥, 𝑧〉 ∈ 𝑅 ∩ 𝑆

Thus, 𝑅 ∩ 𝑆 is transitive .

As, 𝑅 ∩ 𝑆 satisfies all properties,

𝑅 ∩ 𝑆 is an equivalence relation.

(b) 𝑅 ∪ 𝑆 need not be an equivalence relation.

Example: A = {1, 2, 3}
R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
R1∪ R2 = {(1, 1), (2, 2), (3, 3) (1,2),(2,1),(2,3),(3,2)}

here, R1∪ R2 is not equivalence. Why?

Congruence Modulo n

Let 𝑛 be a non-zero integer. The numbers 𝑎, 𝑏 ∈ 𝑍 are said to be congruent modulo 𝑛 if

𝑎 − 𝑏 is divisible by 𝑛. (or) 𝑛 / (𝑎 − 𝑏),that is 𝑛 divides (𝑎 − 𝑏)

This is written as

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛)

For example,

3 = 7 (𝑚𝑜𝑑4) etc

MVS Page 24
where k ,ℓ are some integers.

By adding these together, we have

i.e (𝑎 − 𝑐) is divisible by 𝑛.

It follows from here that 𝑎 ≡ 𝑏 (mod 𝑛). This proves the transitivity of R

Some Other Examples

The following relations are equivalence relations:
 "a and b live in the same city" on the set of all people;
 "a and b are the same age" on the set of all people;
 "a and b were born in the same month" on the set of all people;
 "a and b have the same remainder when divided by 3" on the set of integers;
 "a and b have the same last digit" on the set of integers;
 Any relation that can be defined using expressions like “have the same” or “are
the same” is an equivalence relation.

MVS Page 25
Equivalence Class
Let R be an equivalence relation on a set A and let a ∈ A. The equivalence class of a,
denoted by [𝑎] or [𝑎] 𝑅 is defined as [𝒂] = {𝒙 ∈ 𝑨 |𝒙 𝑹 𝒂}. It consists of all elements in A
that are linked to 𝑎 by the relation R. If 𝑥 ∈ [𝑎], then 𝑥 is a representative of the class [𝑎].

Example: Let R be an equivalence relations on the set A = {4, 5, 6, 7} defined by

R = {(4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4)}.

Determine its equivalence classes.

Solution: we have equivalence class of the element ‘ 𝑎’ is

[𝑎] = {𝑥 ∈ 𝐴 |𝑥 𝑅 𝑎}.

[4] = {𝑥 ∈ 𝐴 |𝑥 𝑅 4} = {4,6}

[5] = {𝑥 ∈ 𝐴 |𝑥 𝑅 5} = {5}

[7] = {𝑥 ∈ 𝐴 |𝑥 𝑅 7} = {7}

[6] = {𝑥 ∈ 𝐴 |𝑥 𝑅6} = {4,6}

The equivalence classes are as follows:

{4} = {6} = {4, 6}
{5} = {5}
{7} = {7}.

Example:

Let R be an equivalence relations on the set A = {1,2,3,4, 5, 6, 7,8,9,10,11,12} defined by

R = {(a,b)/ a-b is a multiple of 5}.

Determine its equivalence classes.

MVS Page 26
Solution: Given A = {1,2,3,4, 5, 6, 7,8,9,10,11,12}

and R = {(a,b)/ a-b is a multiple of 5}= { (1,1), (2,2)…….(1,6) ,……(12,12)}

we have equivalence class of the element ‘ 𝑎’ is

[𝑎] = {𝑥 ∈ 𝐴 |𝑥 𝑅 𝑎}.

[1] = {𝑥 ∈ 𝐴 |𝑥 𝑅 1} = {1,6,11} = [6] = [11]

[2] = {𝑥 ∈ 𝐴 |𝑥 𝑅 2} = {2,7,12} = [7] = [12]

[3] = {𝑥 ∈ 𝐴 |𝑥 𝑅 3} = {3,8} = [8]

[4] = {𝑥 ∈ 𝐴 |𝑥 𝑅 4} = {4,9}=[9]

[5] = {𝑥 ∈ 𝐴 |𝑥 𝑅 5} = {5,10} = [10]

Example:

If A= 𝐴1 ∪ 𝐴2 ∪ 𝐴3, where 𝐴1 = {1,2}, 𝐴2 = {2,3,4} and

𝐴3 = {5}. Define the relation R on A by 𝑥𝑅𝑦 iff 𝑥 and 𝑦 are in the same

set 𝐴𝑖 , 𝑖 = 1,2,3. Is R an equivalence relation?.

Solution: Given A= 𝐴1 ∪ 𝐴2 ∪ 𝐴3 = {1,2,3,4,5}

𝑅 = {(𝑥, 𝑦)/𝑥, 𝑦 𝑎𝑟𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑠𝑎𝑚𝑒 𝑠𝑒𝑡 }

𝑅 = {(1,1), (1,2), (2,1), (2,2), (2,4), (3,2), (3,3), (3,4), (4,2), (4,3), (4,4), (5,5)}

i) R is reflexive ∵ (𝑎, 𝑎) ∈ 𝑅, ∀ 𝑎𝜖𝐴

ii) R is symmetric, ∵ 𝑎𝑅𝑏 ⇒ 𝑏𝑅𝑎 ∀ 𝑎, 𝑏 𝜖𝐴
iii) R is not transitive , ∵ (1,2) ∈ 𝑅 and (2,3) ∈ 𝑅 but
(1,3)∉ 𝑅
∴ R is not an equivalence relation.

MVS Page 27
A partition of a set S is a sub-division of the set into subsets that are disjoint and
exhaustive,i.e every element of S belong to one and only one element of the subsets

Def: Let S be a non -empty set and 𝐴 = {𝐴1, 𝐴2, … … 𝐴𝑛 } where, 𝐴𝑖 ⊆ 𝑆for all 𝑖 = 1,2, . . 𝑛

(i) Then set A is said to be a partition of S if

𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴𝑛 = 𝑆 and 𝐴𝑖 ∩ 𝐴𝑗 = ∅ for 𝑖 ≠ 𝑗

(OR)

Let S be a non empty set .Then the collection of nonempty subsets of S , say
𝐴1, 𝐴2, … … 𝐴𝑛 is said to be a partition of a set S

if, and only if,

1. 𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴𝑛 = 𝑆 and
2. 𝐴1, 𝐴2, … … 𝐴𝑛 are mutually disjoint.

i,e 𝐴𝑖 ∩ 𝐴𝑗 = ∅ for 𝑖 ≠ 𝑗

MVS Page 28
Let S be a non empty set . A collection of nonempty sets 𝑨𝟏, 𝑨𝟐, … … 𝑨𝒏 is said to be a
covering of a set S if 𝑨𝟏 ∪ 𝑨𝟐 ∪ … ∪ 𝑨𝒏 = 𝑺

Example:

Consider the following collections of subsets of

S = {1,2,3,4,5,6,7,8,9}

(i) {{1,3,5}, {2,6}, {4,8,9}} , Neither partition nor a cover of set S(since 7 in S does
not belong to any of the subsets)
(ii) {{1,3,5}, {2,4,6,8}, {5,7,9}}, only cover of set S
(iii) {{1,3,5}, {2,4,6,8}, {7,9}} ,Partition of set S.
(iv) {{1,3, {2,5}, {4,6,8}, {7,9} Partition of set S.

Note : If R is an equivalence relation on the set A, its equivalence classes form a partition
of A. In each equivalence class, all the elements are related and every element in A
belongs to one and only one equivalence class.

Example:

Let R be an equivalence relations on the set A = {4, 5, 6, 7} defined by

R = {(4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4)}.

Determine its equivalence classes and find the partition of A.

MVS Page 29
Solution: we have equivalence class of the element ‘ 𝑎’ is

[𝑎] = {𝑥 ∈ 𝐴 |𝑥 𝑅 𝑎}.

[4] = {𝑥 ∈ 𝐴 |𝑥 𝑅 4} = {4,6}

[5] = {𝑥 ∈ 𝐴 |𝑥 𝑅 5} = {5}

[7] = {𝑥 ∈ 𝐴 |𝑥 𝑅 7} = {7}

[6] = {𝑥 ∈ 𝐴 |𝑥 𝑅6} = {4,6}

The equivalence classes are as follows:

{4} = {6} = {4, 6}
{5} = {5}
{7} = {7}.

Partition of set A is {[4], [5], [7]}

Example-2

Let R be an equivalence relations on the set A = {1,2,3,4, 5, 6, 7,8,9,10,11,12} defined by

R = {(a , b)/ a-b is a multiple of 5}.

Determine its equivalence classes and partition of A

Solution: Given A = {1,2,3,4, 5, 6, 7,8,9,10,11,12}

and R = {(a,b)/ a-b is a multiple of 5}= { (1,1), (2,2)…….(1,6) ,……(12,12)}

we have equivalence class of the element ‘ 𝑎’ is

[𝑎] = {𝑥 ∈ 𝐴 |𝑥 𝑅 𝑎}.

[1] = {𝑥 ∈ 𝐴 |𝑥 𝑅 1} = {1,6,11} = [6] = [11]

[2] = {𝑥 ∈ 𝐴 |𝑥 𝑅 2} = {2,7,12} = [7] = [12]

[3] = {𝑥 ∈ 𝐴 |𝑥 𝑅 3} = {3,8} = [8]

[4] = {𝑥 ∈ 𝐴 |𝑥 𝑅 4} = {4,9} =[9]

MVS Page 30
[5] = {𝑥 ∈ 𝐴 |𝑥 𝑅 5} = {5,10} = [10]

The partition of set A is {[1], [2], [3], [4][5], }

Let 𝑅1 be a relation from 𝐴 𝑡𝑜 𝐵 and 𝑅2 be a relation from 𝐵 𝑡𝑜 𝐶. The composition of 𝑅1

and 𝑅2 denoted by 𝑅1 o 𝑅2 is the relation from A to C defined as

𝑅1 o 𝑅2 = {(𝑎, 𝑐 )⁄(𝑎, 𝑏) ∈ 𝑅1 𝑎𝑛𝑑 (𝑏, 𝑐 ) ∈ 𝑅2 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑏 ∈ 𝐵 }

Example 1:

𝑅1 o 𝑅2 = {(1, 𝑥 ), (1, 𝑧), (2, 𝑦), (3, 𝑦), (3, 𝑧), (3, 𝑥 )}

Let R be a relation from A to B. The inverse of R is denoted by R -1 , and it is a

relation from B to A defined by

Example:

MVS Page 31
Partial Order Set (POSET):
A relation 𝑹 on a set 𝑨 is called a partial ordering or partial order if it satisfies the
following three properties:

1. Relation 𝑹 𝒊s Reflexive, i.e. (𝒂, 𝒂) ∈ 𝑹 ∀ 𝒂 ∈ 𝑨.

2. Relation R is Antisymmetric, i.e., (𝒂, 𝒃) ∈ 𝑹 and (𝒃, 𝒂) ∈ 𝑹 then 𝒂 = 𝒃 ∀ 𝒂, 𝒃 ∈ 𝑨
3. Relation R is transitive, i.e., ., (𝒂, 𝒃) ∈ 𝑹 and (𝒃, 𝒄) ∈ 𝑹 then (𝒂, 𝒄) ∈ 𝑹 ∀ 𝒂, 𝒃,c ∈ 𝑨

A set 𝐴 together with a partial ordering 𝑅 is called a partially ordered set, or poset, and
is denoted by (𝐴, 𝑅). Members of 𝐴 are called elements of the poset.

Example: The relation ≤ on the set of all integers is a partial order.

∴ (𝑍, ≤) is a Poset. The relation ≥ on the set of all integers is a parial

order.

∴ (𝑍, ≥) is a Poset

Example-2
Consider set
R = {(1, 1), (1, 3), (1, 4), (2, 2), (2, 1), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4), (4, 3)}
(i)Pairs (1, 1), (2, 2), (3, 3), (4, 4) exist:
⇒ This satisfies the reflexive condition.
(ii) The transitive condition is also satisfied.
(iii) For the pairs (4, 3):
⇒ The relation (3, 4) exists
⇒ This does not satisfy the anti-symmetric condition.
So the relation is not anti-symmetric.
Hence the relation R is not a partial order relation.

MVS Page 32
Example3:

Show whether the relation (x, y) ∈ R, if, x ≥ y defined on the set of +ve integers is a
partial order relation.

Solution: Consider the set A = {1, 2, 3, 4} containing four +ve integers. Find the
relation for this set such as

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

Reflexive: The relation is reflexive as for every a ∈ A.

(a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3), (4, 4) ∈ R.

Antisymmetric: The relation is antisymmetric as whenever (a, b) and (b, a) ∈ R, we have a = b.

Transitive: The relation is transitive as whenever (a, b) and (b, c) ∈ R, we have (a, c) ∈ R.

Example: (4, 2) ∈ R and (2, 1) ∈ R, implies (4, 1) ∈ R.

As the relation is reflexive, antisymmetric and transitive. Hence, it is a partial order relation.

Example4:

Show that the relation 'Divides' defined on N is a partial order relation.

Reflexive: We have a divides a, ∀ a∈N. Therefore, relation 'Divides' is reflexive.

Antisymmetric: Let a, b, c ∈N, such that a divides b. It implies b divides a iff a = b. So, the
relation is antisymmetric.

Transitive: Let a, b, c ∈N, such that a divides b and b divides c.

Then a divides c. Hence the relation is transitive. Thus, the relation being reflexive,
antisymmetric and transitive, the relation 'divides' is a partial order relation.

MVS Page 33
Example-5:

(a) The relation ⊆ of a set of inclusion is a partial ordering or any collection of sets since
set inclusion has three desired properties:

1. A ⊆ A for any set A.

2. If A ⊆ B and B ⊆ A then B = A.
3. If A ⊆ B and B ⊆ C then A ⊆ C

(b) The relation ≤ on the set R of real no that is Reflexive, Antisymmetric and transitive.

∴ Relation ≤ is a Partial Order Relation.

Note: Relations Divides , ⊆ (subset) and ≤ (less than or equal to) are partial ordering
relations on N (natural number)

Example: Show that the relation '<' (less than) defined on N, the set of +ve
integers is neither an equivalence relation nor partially ordered relation but is a
total order relation

Reflexive: Let a ∈ N, then a < a

⟹ '<' is not reflexive.

As, the relation '<' (less than) is not reflexive, it is neither an equivalence relation nor the
partial order relation.

But, as ∀ a, b ∈ N, we have either a < b or b < a or a = b. So, the relation is a total order
relat

MVS Page 34
 Procedure for constructing Hasse diagram
• To represent a finite poset (𝑷, ≤ ) using a Hasse diagram, start with the
directed graph of the relation:

1. Remove all self-loops

2. Remove all edges that must be present because of transitivity.

3. Also remove the arrows, as all arrows point upward

Totally Ordered Sets

 If (𝑃, ≤) is a poset and every two elements of P are

comparable ,then P is called a totally ordered set .
 It is also called a chain.
 The Poset (𝑍, ≤) is a chain.
 The poset (𝑍 + ,/) is not a chain

MVS Page 35
Example -2 Draw the Hasse diagram of the Poset (𝐷12, ∕), where

𝐷12 = Divisors of 12, and a /b means a divides b

Solution: Given poset is (𝐷12 , ∕)

𝐷12 = Divisors of 12= {1,2,3,4,6,12}

𝑅 =/ ={(𝑎, 𝑏) / 𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏} =

{(1,1), (2,2), (3,3), (4,4), (6,6), (12,12), (1,2), (1,3), … … … . . }

Hasse diagram of (𝐷12 , ∕)

Example -3 Draw the Hasse diagram of the Poset (𝐷24 , ∕), where

𝐷24 = Divisors of 24, and a /b means a divides b

Solution: Given poset is (𝐷24 , ∕)

𝐷24 = Divisors of 24 = {1,2,3,4,6,8,12,24}

𝑅 =/ ={(𝑎, 𝑏) / 𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏}

MVS Page 36
Hasse diagram of Poset (𝐷24 , ∕)

Hasse diagrams of different posets

MVS Page 37
MVS Page 38
Example -4 Draw the Hasse diagram of the Poset (𝐷30 , ∕), where

𝐷30 = Divisors of 30, and a /b means a divides b

Solution: Given poset is (𝐷30 , ∕)

𝐷24 = Divisors of 30= {1,2,3,5,6,10,15,30}

𝑅 =/ ={(𝑎, 𝑏) / 𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏}

MVS Page 39
Example
The Hasse diagram for divisibility on the set
{1,2,4,8,16,32,64}

The Hasse diagram (P,/). It is a chain.

In this poset every pair of elements are comparable .

Example

Consider the poset ( { 1, 2, 3, 4 },  ) where  is less than or equal to

MVS Page 40
Here every two elements are comparable. Therefore it is a total ordering or chain

Example:

MVS Page 41
Draw Hasse diagram for ({3, 4, 12, 24, 48, 72}, /)

MVS Page 42
Solution:

Hasse diagram of the poset (𝑃, ⊆) is

Example:

Let R be a relation defined on the set 𝐴 = {1,2,3,4,5,6,7,8,9,10}

𝑎, 𝑏 ∈ 𝐴 , 𝑎𝑅𝑏 ⇔ 𝑎/𝑏

(i) Show that R is a partial ordering on A

(ii) Decide whether R is total ordering on A . Why?
(iii) Draw the Hasse diagram representing the partial ordering relation R on the set
A.

Totally Ordered Sets • If (S, ) is a poset and every two elements of S are comparable, S is
called a totally ordered set or linearly ordered set. • It is also called a chain. • The
Poset(Z,≤) is a chain. • The Poset (Z+,|) is not a chain.

MVS Page 43
Example: Hasse diagram of the poset ({𝑎, 𝑏, 𝑐, 𝑑, 𝑒}, 𝑅 )is shown below :

(1) Determine the relation matrix (ii) Construct the digraph for R

Solution:

(𝑎, 𝑎), (𝑏, 𝑏), (𝑐, 𝑐 ), (𝑑, 𝑑 ), (𝑒, 𝑒), (𝑎, 𝑏), (𝑎, 𝑐 ). (𝑎, 𝑑 ), (𝑎, 𝑒)(𝑏, 𝑑 ),
𝑅={ }
(𝑏, 𝑒), (𝑐, 𝑑 ), (𝑐, 𝑒), (𝑑, 𝑒)

1 1 1 1 1
0 1 0 1 1
𝑀𝑅 = 0 0 1 1 1
0 0 0 1 1
[0 0 0 0 1]

MVS Page 44
Consider a relation R on a set A. The transitive closure of a relation R is the smallest
transitive relation containing R and it is denoted by 𝑅 +

The transitive closure of R is denoted by 𝑅 +

Transitive Closure of R is obtained by using the formula

𝑅+ = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ … … ∪ 𝑅𝑛

here R2 = R◦ R and Rn = Rn-1 ◦ R.

𝑅+ = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ … … ∪ 𝑅𝑛

Procedure for finding Transitive closure using 𝑅, 𝑅 2, 𝑅 3 𝑒𝑡𝑐

Let R be a given relation .

Step-1: Find 𝑹𝟐 using the formula 𝑹𝟐 = 𝑹 ∘ 𝑹

Step-2: Find 𝑹𝟑 using the formula 𝑹𝟑 = 𝑹𝟐 ∘ 𝑹 = 𝑹 ∘ 𝑹𝟐

Step-3: Find 𝑹𝟒 using the formula 𝑹𝟒 = 𝑹𝟑 ∘ 𝑹

Continue like this, till 𝑹𝒏 = 𝑹𝒏−𝟏 or 𝑹𝒏 =∅

Step-4: Use the formula

𝑹+ = 𝑹 ∪ 𝑹𝟐 ∪ 𝑹𝟑 ∪ … … ∪ 𝑹𝒏

Note: If R is a relation on the set A and |𝐴| = 𝑛 then find up to 𝑅 𝑛 .

MVS Page 45
Example1:

Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then find the transitive
closure of R .

Solution:
R2 = R◦ R = {(1, 3), (2, 3), (3, 3)} and

R3 = R2 ◦ R = {(1, 3), (2, 3), (3, 3)} = R2

Transitive of R =𝑅 + = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3 ∪ … … ∪ 𝑅 𝑛 = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3 =

𝑅 + = {(1, 2), (2, 3), (3, 3), (1, 3)}

Note: If R is a relation on the set A and |𝐴| = 3 then find up to 𝑅 3

Example-2

Let A=(1,2,3,4} and R={(1,2),(2,3) (2,4)} be a relation defined on A. Compute transitive

closure of R.

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

𝑅 2 = 𝑅 ∘ 𝑅 ={(1,2),(2,3) (2,4)}∘{(1,2),(2,3) (2,4)} = {(1,3), (1,4)}

𝑅3 = 𝑅2 ∘ 𝑅 = ∅

Transitive of R =𝑅 + = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3 ∪ … … ∪ 𝑅 𝑛 = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3

= {(1,2), (2,3) (2,4)} ∪ {( 1,3) , (1,4)} ∪ ∅

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

Example-3

Let the relation R be defined on the set A={1,2,3} as R={(1,2), (2,3), (3,3),(3,2)}.

Compute transitive closure of R.

Transitive of R =𝑅 + = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3 ∪ … … ∪ 𝑅 𝑛 = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3

MVS Page 46
Example-4

If 𝑅 = {(0,1), (1,2), (2,3)} is a relation on set 𝐴 = {0,1,2,3} then find the transitive closure
of the relation R.

Solution: Transitive of R =𝑅 + = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3 ∪ … … ∪ 𝑅 𝑛

𝑹+ = {(𝟎, 𝟏), (𝟎, 𝟐), (𝟎, 𝟑), (𝟏, 𝟐), (𝟏, 𝟑), (𝟐, 𝟑)}

Example-5

Find the transitive closure of the relation R whose digraph is given below.

Solution

Example-

Let the relation R be defined on the set 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒} 𝑎𝑠

𝑅 = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑐), (𝑐, 𝑑), (𝑐, 𝑒), (𝑑, 𝑒)}.

MVS Page 47
Compute transitive closure of R

Here, 𝑹𝟒 = 𝑹𝟓

Transitive of R = 𝑹+ = 𝑹 ∪ 𝑹𝟐 ∪ 𝑹𝟑 ∪ 𝑹𝟒

Procedure for finding transitive closure of a relation using Matrix

method.
Let R be a given relation .

Step-1: Find matrix relation𝑀𝑅 of a relation R

Step-2: Find 𝑀𝑅2 using the formula 𝑀𝑅2 = 𝑀𝑅 ∘ 𝑀𝑅

Step-3: Find 𝑀𝑅3 using the formula 𝑀𝑅3 = 𝑀𝑅2 ∘ 𝑀𝑅

Continue like this, till 𝑀𝑅𝑛 = 𝑀𝑅𝑛−1 or 𝑀𝑅𝑛 = 0 = Zero Matrix

Step-4: Use the formula

𝑀𝑅+ = 𝑀𝑅 ∨ 𝑀𝑅2 ∨ … .∨ 𝑀𝑅𝑛

MVS Page 48
 Example-1

Let A = {4, 6, 8, 10} and R = {(4, 4), (4, 10), (6, 6), (6, 8), (8, 10)} is a relation on
set A. Determine transitive closure of R.

Now, find the powers of MR as in fig:

𝑀𝑅4 = 𝑀𝑅3

Hence, the transitive closure of MR is 𝑀𝑅+

MVS Page 49
 𝑀𝑅+ = 𝑀𝑅 ∨ 𝑀𝑅2 ∨ 𝑀𝑅3

Thus, 𝑅 + = {(4, 4), (4, 10), (6, 8), (6, 6), (6, 10), (8, 10)}.

Note: To find transitive closure of a relation , prefer relation composition

method instead of matrix method

i,e use the formula 𝑅 + = 𝑅 ∪ 𝑅 2 ∪ 𝑅 3 ∪ … … ∪ 𝑅 𝑛

Note: Boolean addition and Boolean product of matrices

How to find 𝑴𝑹 ∨ 𝑴𝑹𝟐 ∨ 𝑴𝑹𝟑 ?

Boolean Operations and , or

1∨1= 1 1∧1 =1

0∨1=1∨0 =1 0∧1= 1∧0 = 0

0∨0= 0 0∧0 =0

MVS Page 50
Boolean Product

MVS Page 51
Boolean Power of a Matrix

MVS Page 52