Results 1 to 9 of 9
Like Tree4Thanks
  • 1 Post By romsek
  • 2 Post By SlipEternal
  • 1 Post By Plato

Math Help - Is this relation transitive ?

  1. #1
    Newbie
    Joined
    Feb 2014
    From
    India
    Posts
    4

    Is this relation transitive ?

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,241
    Thanks
    854

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Is this relation transitive ?

    Quote Originally Posted by Sujith View Post
    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)}
    What is $R\circ R~?$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2014
    From
    India
    Posts
    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 ?

    Please help me on this. Is there any wrong in my understanding in transitive relation ?Is this relation transitive ?-digraph.jpg
    Last edited by Sujith; February 27th 2014 at 08:03 PM. Reason: Forgot to attach image
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,241
    Thanks
    854

    Re: Is this relation transitive ?

    Quote Originally Posted by Sujith View Post
    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 ?Click image for larger version. 

Name:	digraph.jpg 
Views:	1 
Size:	11.4 KB 
ID:	30262
    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 from Sujith
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2014
    From
    India
    Posts
    4

    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,841
    Thanks
    709

    Re: Is this relation transitive ?

    Quote Originally Posted by Sujith View Post
    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?
    romsek made a minor typo. The second line should read

    (1,1)(1,2) ? (1,2) yes
    Thanks from romsek and Sujith
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    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~.$
    Thanks from Sujith
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Feb 2014
    From
    India
    Posts
    4

    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.
    Is this relation transitive ?-matrix.jpg
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relation symmetric or transitive?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 13th 2013, 05:28 AM
  2. Transitive Relation
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 13th 2011, 01:40 PM
  3. [SOLVED] Transitive relation help please?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 23rd 2010, 12:39 AM
  4. Transitive relation help
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 3rd 2009, 03:40 PM
  5. Transitive relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 19th 2009, 03:02 AM

Search Tags


/mathhelpforum @mathhelpforum