Hi,
Please help me to check is the given relation is transitive or not ? Please explain why.
R={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)}
Regards
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 ?
Please help me on this. Is there any wrong in my understanding in transitive relation ?
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.
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?
@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