# Thread: Is this relation transitive ?

1. ## Is this relation transitive ?

Hi,

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

Regards
Sujith

2. ## Re: Is this relation transitive ?

why don't you post what you think the answers are and we can check them.

Do you know what transitive means?

3. ## Re: Is this relation transitive ?

Originally Posted by Sujith
Hi,

R={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)}
What is $R\circ R~?$

4. ## Re: Is this relation transitive ?

I am newbie to Discrete Maths. As per my understanding the transitive relation is, if a path of length 2 exists between vertices a to b, there should be a path of length 1 exists from a to b. Please correct me if I am wrong. When I refer the answer of this question in text book, it is said that the relation is transitive. But I am confused how it could be ?

I tried to draw the digraph of the relation R={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)} and attached here with. From the figure you can see that there is no such path exists having length 2. Then how can we state this digraph is a transitive ?

5. ## Re: Is this relation transitive ?

Originally Posted by Sujith
I am newbie to Discrete Maths. As per my understanding the transitive relation is, if a path of length 2 exists between vertices a to b, there should be a path of length 1 exists from a to b. Please correct me if I am wrong. When I refer the answer of this question in text book, it is said that the relation is transitive. But I am confused how it could be ?

I tried to draw the digraph of the relation R={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)} and attached here with. From the figure you can see that there is no such path exists having length 2. Then how can we state this digraph is a transitive ?

your definition of transitive is so different from what mine is I hesitate to say anything.

To me a transitive relation R is one such that $(a R b) \wedge (b R c) \Rightarrow (a R c)$

you can make a table to check this

(1,1) (1,1) ? (1,1) yes
(1,1) (1,2) ? (2,1) yes
(1,2) (2,1) ? (1,1) yes
(1,2) (2,2) ? (1,2) yes
(2,1) (1,1) ? (1,1) yes
(2,1) (1,2) ? (2,2) yes
(2,2) (2,1) ? (2,1) yes
(2,2) (2,2) ? (2,2) yes
(3,3) (3,3) ? (3,3) yes
(3,3) (3,4) ? (3,4) yes
(3,4) (4,3) ? (3,3) yes
(3,4) (4,4) ? (3,4) yes
(4,3) (3,3) ? (4,3) yes
(4,3) (3,4) ? (4,4) yes
(4,4) (4,4) ? (4,4) yes

so this relation does appear to be transitive.

If I had to put this in terms of a graph I guess it would be that if there is a path of length 1 between a and b, and a path of length 1 between b and c, then there must be a path of length 1 between a and c. Your diagram shows that this is so.

6. ## Re: Is this relation transitive ?

Thanks for making me clear about the transitive relation that is (aRb)∧(bRc)⇒(aRc)

If so, some results confusing me again looking at the table you given

--------------------
aRb bRc ? aRc
--------------------
(1,1) (1,1) ? (1,1) - here a is 1 and c is 1. so (a,c) means (1,1) - ok
(1,1) (1,2) ? (2,1) - here a is 1 and c is 2. so (a,c) means (1,2) - but the value given is (2,1). please clarify

Is that I am wrong again?

7. ## Re: Is this relation transitive ?

Originally Posted by Sujith
Thanks for making me clear about the transitive relation that is (aRb)∧(bRc)⇒(aRc)

If so, some results confusing me again looking at the table you given

--------------------
aRb bRc ? aRc
--------------------
(1,1) (1,1) ? (1,1) - here a is 1 and c is 1. so (a,c) means (1,1) - ok
(1,1) (1,2) ? (2,1) - here a is 1 and c is 2. so (a,c) means (1,2) - but the value given is (2,1). please clarify

Is that I am wrong again?

(1,1)(1,2) ? (1,2) yes

8. ## Re: Is this relation transitive ?

@Sujith, In my reply above, I was hoping that you would find one of the most used theorems about transitive relations:
$\text{The relation }R \text{ is transitive if and only if }~~R\circ R\subseteq R~.$

9. ## Re: Is this relation transitive ?

@Plato, Thanks for clarifying me the need for RoR on your first reply based on the theorem R∘R⊆R.

Based on this, I try to re-write the relation in matrix form as given below.

From the above figure, I understood that R∘R is same as R, which is ⊆ R. Hope my understanding is correct here.

From Plato's and Romsek's reply, I am summarizing my understanding. Please correct me If I am wrong here.

1. If we need to check a relation is transitive or not, the basic steps are
1.1 Check all possible combination ( from cartision product R x R) as given by Romsek's table which should satisfy (aRb)∧(bRc)⇒(aRc)

OR

1.2 Find R o R in the form of matrix(I hope matrix is easy method) and check RoR is ⊆ R