Results 1 to 2 of 2

Thread: Prove or disprove that R^4 is a transitive relation

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Prove or disprove that R^4 is a transitive relation

    Let $\displaystyle R$ be a transitive relation defined on a set $\displaystyle B$. Prove or disprove that $\displaystyle R^4$ is a transitive relation.

    I'm inclined to believe that it's true, but I can't be sure. I at least know this: A relation $\displaystyle R$ is transitive on a set $\displaystyle A$ if whenever $\displaystyle (a,b)\in R$ and $\displaystyle (b,c)\in R$, then $\displaystyle (a,c)\in R$, $\displaystyle \forall a,b,c\in R$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,776
    Thanks
    2823
    Awards
    1
    Suppose that $\displaystyle R$ is transitive on $\displaystyle A$.
    Suppose that $\displaystyle \left[ {\left( {a,b} \right) \in R \circ R} \right] \wedge \left[ {\left( {b,c} \right) \in R \circ R} \right]$.
    By definition $\displaystyle \left( {\exists x \in A} \right)\left[ {(a,x) \in R \wedge (x,b) \in R} \right] \wedge \left( {\exists y \in A} \right)\left[ {(b,y) \in R \wedge (y,c) \in R} \right]$.
    But that means that $\displaystyle \left[ {(a,b) \in R \wedge (b,c) \in R} \right]$ because $\displaystyle R$is transitive.
    So by way of $\displaystyle b$ we have $\displaystyle {\left(a,c \right) \in R \circ R}$.
    $\displaystyle R \circ R$ is transitive.
    Can you extend that to $\displaystyle R^4?$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Transitive Relation
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Nov 13th 2011, 01:40 PM
  2. Replies: 12
    Last Post: Jun 24th 2010, 12:00 PM
  3. Replies: 3
    Last Post: Mar 18th 2010, 09:37 AM
  4. Transitive relation help
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 3rd 2009, 03:40 PM
  5. Transitive relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 19th 2009, 03:02 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum