Results 1 to 5 of 5

Math Help - Prove transitive relations

  1. #1
    Newbie Pi R Squared's Avatar
    Joined
    Oct 2009
    Posts
    13

    Question Prove transitive relations

    I have two related problems. Prove or disprove:

    If R \subseteq A \times A and S \subseteq A \times A are transitive relations then R \cup S is a transitive relation.

    If R \subseteq A \times A and S \subseteq A \times A are transitive relations then R \cap S is a transitive relation.

    The first, I completely understand, because if you union two transitive relations, the combined relation will still be transitive. (Unless I am way off.)

    The second has proven more difficult to prove/disprove. Every example that I have come up with has been "vacuously" transitive. I had never heard of that until the other day and I believe that is why it is proving more difficult for me. If anyone could help with this proof, I would much appreciate it. A good nudge in the right direction?

    Thanks!
    Last edited by Plato; March 21st 2010 at 11:52 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Pi R Squared View Post
    I have two related problems. Prove or disprove:
    If R \subseteq A \times A and S \subseteq A \times A are transitive relations then R \cup S is a transitive relation.
    If R \subseteq A \times A and S \subseteq A \times A are transitive relations then R \cap S is a transitive relation.

    The first, I completely understand, because if you union two transitive relations, the combined relation will still be transitive. (Unless I am way off.)

    The second has proven more difficult to prove/disprove.
    The first is false. A=\{1,2,3\},~R=\{(1,2)\}~\&~S=\{(2,3)\}.
    There are two transitive relation but their union is not transitive.

    The second is trivial.  (a,b) \in R \cap S \Rightarrow (a,b) \in R\,\& \,(a,b) \in S.
    So both transitive implies the intersection is transitive.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Pi R Squared's Avatar
    Joined
    Oct 2009
    Posts
    13

    This helps...

    I typed the union and the intersection in backwards. But your explanation makes sense. So if I have two 'vacuously' transitive sets, I have the empty set. Therefore, it is not transitive. Am I understanding this correctly?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Pi R Squared View Post
    I typed the union and the intersection in backwards. But your explanation makes sense. So if I have two 'vacuously' transitive sets, I have the empty set. Therefore, it is not transitive. Am I understanding this correctly?
    The union of two transitive relations on a set is not necessarily transitive.
    The intersection of two transitive relations on a set is transitive.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie Pi R Squared's Avatar
    Joined
    Oct 2009
    Posts
    13

    Question General proof R intersection S

    Quote Originally Posted by Plato View Post
    The second is trivial.  (a,b) \in R \cap S \Rightarrow (a,b) \in R\,\& \,(a,b) \in S.
    So both transitive implies the intersection is transitive.
    Transitivity is whenever aRb and bRc, then aRc. How would I start a proof that would encompass all situations. I understand how to prove a certain given situation... It is the general proof when I am dealing with X number of terms that confuses me. I cannot just use aRb... I would continue with another line saying something like  (b,c) \in R \cap S \Rightarrow (b,c) \in R\,\& \,(b,c) \in  S.

    By the way your explanations have helped immensely!
    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, 05:15 AM
  2. Relations, reflexive and transitive
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 5th 2010, 02:36 AM
  3. Union of Transitive Relations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 8th 2008, 08:39 AM
  4. relations transitive
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 7th 2008, 06:09 AM
  5. Transitive Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 20th 2008, 07:58 AM

Search Tags


/mathhelpforum @mathhelpforum