Results 1 to 8 of 8

Math Help - Relational proof

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    44

    Relational proof

    If R is reflexive and transitive, then R U R^U is an equivalence. I need to prove this using algebraic-relation calculations or disprove by counter example. I'm really not understanding this stuff.
    Last edited by mr fantastic; March 13th 2009 at 11:31 PM. Reason: Changed a word
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    Quote Originally Posted by thehollow89 View Post
    If R is reflexive and transitive, then R U R^U is an equivalence. I need to prove this using algebraic-relation calculations or disprove by counter example. I'm really not understanding this stuff.
    What is the meaning of R^U?
    Last edited by mr fantastic; March 13th 2009 at 11:32 PM. Reason: Modified quote
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    44
    R converse I believe.
    Last edited by thehollow89; March 13th 2009 at 12:46 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Relation

    Hello thehollow89

    R^U is the converse, or the inverse, of R, means that if the element (x, y) in R, the element (y,x) is in R^U - because that's what the inverse relation is: the relation you get by switching the order of the elements in the relation. (It's usually denoted by R^{-1}, as you might expect).

    So, if R is reflexive and transitive, all you'll need to prove in order for R\cup R^U to be an equivalence relation is:

    • R^U is also reflexive and transitive, and therefore R \cup R^U is reflexive and transitive
    • R \cup R^U is symmetric; in other words, (x, y) \in R \cup R^U \Rightarrow (y,x) \in R \cup R^U

    Can you do that, or do you need further help?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2009
    Posts
    44
    Quote Originally Posted by Grandad View Post
    Hello thehollow89

    R^U is the converse, or the inverse, of R, means that if the element (x, y) in R, the element (y,x) is in R^U - because that's what the inverse relation is: the relation you get by switching the order of the elements in the relation. (It's usually denoted by R^{-1}, as you might expect).

    So, if R is reflexive and transitive, all you'll need to prove in order for R\cup R^U to be an equivalence relation is:

    • R^U is also reflexive and transitive, and therefore R \cup R^U is reflexive and transitive
    • R \cup R^U is symmetric; in other words, (x, y) \in R \cup R^U \Rightarrow (y,x) \in R \cup R^U

    Can you do that, or do you need further help?

    Grandad
    I mean I understand the question and what I need to prove, I'm just not sure how I go about proving it. The prof isn't really all that clear. He'll just teach us about the kinds of relations and then ask us to prove something and most kids end up stumped on what method of proof writing he wants...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Relation

    Quote Originally Posted by Grandad View Post

    So, if R is reflexive and transitive, all you'll need to prove in order for R\cup R^U to be an equivalence relation is:

    • R^U is also reflexive and transitive, and therefore R \cup R^U is reflexive and transitive
    • R \cup R^U is symmetric; in other words, (x, y) \in R \cup R^U \Rightarrow (y,x) \in R \cup R^U
    First we prove that R^U is reflexive.

    Assume that
    R and R^U are defined on the set S.

    Then
    R^U is reflexive \iff (x, x) \in R^U, \forall x \in S.

    Now
    (x, y) \in R^U \Rightarrow (y, x) \in R. Therefore (x, x) \in R^U, \forall x\in S, since (x,x) \in R, because R is reflexive.

     \Rightarrow R^U is reflexive.

    Next, we prove that
    R^U is transitive.

    R^U is transitive \iff ((x,y) \in R^U \wedge (y,z) \in R^U) \Rightarrow (x,z) \in R^U

    Now
    (x,y) \in R^U \Rightarrow (y,x) \in R, and (y,z) \in R^U \Rightarrow (z,y) \in R

     \Rightarrow (z, x) \in R, since R is transitive

     \Rightarrow (x, z) \in R^U

     \Rightarrow R^U is transitive

    Finally, we prove that
    R \cup R^U is symmetric.

    (x,y) \in R \cup R^U \Rightarrow (x,y) \in R or (x,y) \in R^U

    Now if
    (x,y) \in R, then (y,x) \in R^U, and if (x,y) \in R^U, then (y,x) \in R.

    Either way,
    (x,y) \in R\cup R^U \Rightarrow (y,x) \in R\cup R^U

    So
    R\cup R^U is symmetric.

    Finally, then,
    R and R^U are both reflexive and transitive, and R\cup R^U is symmetric. So R\cup R^U is an equivalence relation.

    Grandad

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Feb 2009
    Posts
    44
    Quote Originally Posted by Grandad View Post
    First we prove that R^U is reflexive.

    Assume that
    R and R^U are defined on the set S.

    Then
    R^U is reflexive \iff (x, x) \in R^U, \forall x \in S.

    Now
    (x, y) \in R^U \Rightarrow (y, x) \in R. Therefore (x, x) \in R^U, \forall x\in S, since (x,x) \in R, because R is reflexive.

     \Rightarrow R^U is reflexive.

    Next, we prove that
    R^U is transitive.

    R^U is transitive \iff ((x,y) \in R^U \wedge (y,z) \in R^U) \Rightarrow (x,z) \in R^U

    Now
    (x,y) \in R^U \Rightarrow (y,x) \in R, and (y,z) \in R^U \Rightarrow (z,y) \in R

     \Rightarrow (z, x) \in R, since R is transitive

     \Rightarrow (x, z) \in R^U

     \Rightarrow R^U is transitive

    Finally, we prove that
    R \cup R^U is symmetric.

    (x,y) \in R \cup R^U \Rightarrow (x,y) \in R or (x,y) \in R^U

    Now if
    (x,y) \in R, then (y,x) \in R^U, and if (x,y) \in R^U, then (y,x) \in R.

    Either way,
    (x,y) \in R\cup R^U \Rightarrow (y,x) \in R\cup R^U

    So
    R\cup R^U is symmetric.

    Finally, then,
    R and R^U are both reflexive and transitive, and R\cup R^U is symmetric. So R\cup R^U is an equivalence relation.

    Grandad

    So basically for these proofs I use implication to show that if R has a certain property, these other things hold? I don't get proofs, sometimes it seems like they're just making statements rather than prove in the sense of what I think proving means.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    The is a counter example to the statement in this problem.
    Please see: http://www.mathhelpforum.com/math-he...roof-help.html
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 26th 2010, 02:22 PM
  2. relational algebra
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2009, 12:49 PM
  3. Prove with relational algebra
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 10th 2009, 11:13 AM
  4. (Discrete Mathmatics) Defining a relational set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 8th 2009, 06:36 AM
  5. Relational Composition Problem - Please help!
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 10th 2006, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum