Discrete Mathematical Structures by Pearson

Relations and Digraphs 2-11

THEOREM 2.1 The following theorem can also be used to find the transitive closure R* of a

relation R.

Proof: Let R be a relation on a set A with n elements,

then

R* = R ∪ R

2

∪ R

3

∪,… ∪ R

n

where R

2

= ROR, R

3

= R

2

OR, … R

n

= R

n-1

O R.

For a set with infinite number of elements, R*

=

=

∞

∑

i

i

R

1

Example: Find the transitive closure R* of the relation R = {(1, 2), (2, 3), (3, 3)} defined on the

set A = {1, 2, 3}.

Solution: The transitive closure R* of the relation R is given by R* = R ∪ R

2

∪ R

3

as A contains

three elements.

Now,

R

2

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

R

3

= ROR = {(1, 3), (2, 3), (3, 3)} o {(1, 3), (2, 3), (3, 3)}

 = {(1, ...