Transitive relation

TRANSITIVE RELATION

Let P be a set on which the relation R is defined.

R is said to be transitive, if

(p, q) ∈ R and (q, r) ∈ R ⇒ (p, r) ∈ R,

That is pRq and qRr ⇒ pRr where p, q, r ∈ P.

The relation is said to be non-transitive, if

(p, q) ∈ R and (q, r) ∈ R do not imply (p, r ) ∈ R.

For example, in the set P of whole numbers if the relation R be defined by ‘x less than y’ then

p < q and q < r imply p < r, that is, pRq and qRr ⇒ pRr.

Hence this  is a transitive relation.

Solved examples of transitive relation on given set:

1. Let L be given positive integer.

Let R = {(p, q) : p, q  ∈ Z and (p – q) is divisible by L}.

Show that R is transitive relation.

Solution:

Given R = {(p, q) : p, q ∈ Z, and (p – q) is divisible by L}.

Let p, q, r ∈ R such that (p, q) ∈ R and (q, r) ∈ R. Then

   ⇒ (p – q) is divisible by L,and (q – r) is divisible by L.

   ⇒ {(p – q) + (q – r)} is divisible by L.

   ⇒ (p – r) is divisible by L.

   ⇒ (p, r) ∈ R.

Therefore, (p, q) ∈ R and (q, r) ∈ R   ⇒ (p, r) ∈ R.

So, R is a transitive relation.

2. A relation ρ on the set N is given by “ρ = {(x, y) ∈ N × N : x is divisor of y}”. Examine whether ρ is transitive or not transitive relation on set N.

Solution:

Given ρ = {(x, y) ∈ N × N : x is divisor of y}.

Let p, q, r ∈ N and (p, q) ∈ ρ and  (q, r ) ∈ ρ. Then

  (p, q) ∈ ρ and  (q, r ) ∈ ρ  ⇒ p is divisor of q and q is divisor of r.

⇒ p is divisor of r.

 ⇒ (p, r) ∈ ρ

Therefore, (p, q) ∈ ρ and q, r) ∈ ρ ⇒ (p, r) ∈ ρ.

Hence, R is a transitive relation.