Results 1 to 3 of 3

Math Help - Composition of transitive relations

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    15

    Composition of transitive relations

    Hi,

    I have this problem that is really driving me crazy:

    Suppose R and S are transitive relations on A. Prove that if SēR c RēS, then RēS is transitive.

    I tried to use the theorem that says: R is transitive iff RēR c R, but I couldn't get to the end.

    (c means subset)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    This is a completely tedious proof. I will give you the outline.
    But please no questions about it.
    Suppose that (p,q) \in R \circ S \wedge (q,r) \in R \circ S.
    That means that  \left( {\exists s} \right)\left[ {(p,s) \in S \wedge (s,q) \in R} \right]\,\& \,\left( {\exists t} \right)\left[ {(q,t) \in S \wedge (t,r) \in R} \right].
    From which it follows that  (s,q) \in R \wedge (q,t) \in S \Rightarrow (s,t) \in S \circ R \Rightarrow (s,t) \in R \circ S.
    It follows from that \left( {\exists d} \right)\left[ {(s,d) \in S \wedge (d,t) \in R} \right].
    Because both S~\&~T are transitive we get (p,d)\in S~\&~(d,r)\in R.
    But that means that (p,r)\in R\circ S.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    15
    Thanks a lot!
    The outline was really what I needed. Thanks again!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Transitive Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 9th 2010, 06:15 AM
  2. Prove transitive relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 21st 2010, 02:35 PM
  3. Union of Transitive Relations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 8th 2008, 09:39 AM
  4. relations transitive
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 7th 2008, 07:09 AM
  5. Transitive Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 20th 2008, 08:58 AM

Search Tags


/mathhelpforum @mathhelpforum