Results 1 to 14 of 14

Math Help - Equivalence relations on R intersection R^-1

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Equivalence relations on R intersection R^-1

    Let R be a reflexive and transitive relation on X. Show that R intersection R^-1 is an equivalence relation on X.

    My proof:
    Let R be reflexive and transitive, therefore R (x,x) (y,y) (z,z) (x,y) (y,z)
    and R^-1 (x,x) (y,y) (z,z) (y,x) (z,y).
    By the intersection rule we have R intersection R^-1 (x,x) (y,y) (z,z).

    Is this correct?

    How can I show that R intersection R^-1 is an equivalence relation on X?
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by mathproblems View Post
    Let R be a reflexive and transitive relation on X. Show that R intersection R^-1 is an equivalence relation on X.
    How can I show that R intersection R^-1 is an equivalence relation on X?
    What you have posted is an example.
    But it is not a proof.

    You may have shown the elsewhere. But:
    If a relation \mathbf{R} is transitive then so is \mathbf{R}^{-1}{} .
    If a relation \mathbf{R} is reflexive then so is \mathbf{R}^{-1}{}.

    For any relation \mathbf{R} relation \mathbf{R}\cap\mathbf{R}^{-1}{} is symmetric.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations on R intersection R^-1

    relation is transitive R then (x,z) (x,y) (y,z)
    R^-1 is also transitive (z,x) (y,x) (z,y)
    relation is reflexive R then (x,x) (y,y) (z,z)
    relation is reflexive R^-1 then (x,x) (y,y) (z,z)
    Then R (x,z) (x,y) (y,z) (x,x) (y,y) (z,z)
    and R^-1 (z,x) (y,x) (z,y) (x,x) (y,y) (z,z)
    How is R intersection R^-1 is an equivalence relation?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by mathproblems View Post
    relation is transitive R then (x,z) (x,y) (y,z)
    R^-1 is also transitive (z,x) (y,x) (z,y)
    relation is reflexive R then (x,x) (y,y) (z,z)
    relation is reflexive R^-1 then (x,x) (y,y) (z,z)
    Then R (x,z) (x,y) (y,z) (x,x) (y,y) (z,z)
    and R^-1 (z,x) (y,x) (z,y) (x,x) (y,y) (z,z)
    How is R intersection R^-1 is an equivalence relation?
    relation is transitive R then (x,z) (x,y) (y,z)
    R^-1 is also transitive (z,x) (y,x) (z,y)
    relation is reflexive R then (z,x) (y,x) (y,z)
    relation is reflexive R^-1 then (x,z) (y,x) (y,z)
    Then R intersection R^-1 is an equivalence relation
    and include {(x,z) (x,y) (y,z) (z,x) (y,x) (y,z)}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations on R intersection R^-1

    Then R intersection R^-1 is an equivalence relation
    and include {(x,z) (x,y) (y,z) (z,x) (y,x) (z,y)}
    is this correct?
    Thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by mathproblems View Post
    Then R intersection R^-1 is an equivalence relation
    and include {(x,z) (x,y) (y,z) (z,x) (y,x) (y,z)}
    You can't use a name without first saying what it refers to. If I said that Jim likes Jane, is it true or not? This depends on who I mean by Jim and Jane.

    Every variable you use must be introduced, for example, by "for all x," "there exists x," "let x be such that," etc.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations on R intersection R^-1

    Is this good ?
    relation is transitive R then (x,z) (x,y) (y,z)
    R^-1 is also transitive (z,x) (y,x) (z,y)
    relation is reflexive R then (z,x) (y,x) (z,y)
    relation is reflexive R^-1 then (x,z) (y,x) (y,z)

    Then R intersection R^-1 is an equivalence relation
    and include {(x,z) (x,y) (y,z) (z,x) (y,x) (y,z)}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by mathproblems View Post
    Is this good ?
    relation is transitive R then (x,z) (x,y) (y,z)
    No, you used x, y and z without introducing them.

    Note, for example, the definition of reflexivity: R is reflexive if for all x we have R(x,x).

    Also, "(x,z) (x,y) (y,z)" does not make sense. The fact that some x and y are related by a relation R is usually denoted by R(x,y), xRy, or (x, y) ∈ R.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: Equivalence relations on R intersection R^-1

    Let R be transitive (x,y) (y,z) then (x, z).
    R^-1 transitive will be opposite as (y,x) (z,y) then (z,x)

    and then R is reflexive and transitive: (x,y) (y,z) (x, z) (y,x) (z,y) (z,x).
    and R^-1 is reflexive and transitive: (y,x) (z,y) (z,x) (x,y) (y,z) (x,z).
    Therefore R intersection R^-1 is also symmetric and R intersection R^-1 is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by tinabaker View Post
    Let R be transitive (x,y) (y,z) then (x, z).
    R^-1 transitive will be opposite as (y,x) (z,y) then (z,x)
    and then R is reflexive and transitive: (x,y) (y,z) (x, z) (y,x) (z,y) (z,x).
    and R^-1 is reflexive and transitive: (y,x) (z,y) (z,x) (x,y) (y,z) (x,z).
    Therefore R intersection R^-1 is also symmetric and R intersection R^-1 is an equivalence relation.
    Suppose that \mathbf{R} is transitive and (x,y)\in\mathbf{R}^{-1}\text{ and }(y,z)\in\mathbf{R}^{-1}.
    We know that (y,x)\in\mathbf{R}\text{ and }(z,y)\in\mathbf{R}
    Because \mathbf{R} is transitive we know that (z,x)\in\mathbf{R}.
    This means that (x,z)\in\mathbf{R}^{-1} which shows that \mathbf{R}^{-1} is transitive.

    Now that is a proper proof.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by tinabaker View Post
    Let R be transitive (x,y) (y,z) then (x, z).
    R^-1 transitive will be opposite as (y,x) (z,y) then (z,x)
    No, since R is transitive, we have that for all x y and z, if R(x, y) and R(y, z), then R(x, z). Just renaming the variables, we get that for all x, y, z, if R(z, y) and R(y, x), then R(z, x). Now, for all x, y and z, R(z, y) iff R^{-1}(y,z), R(y, x) iff R^{-1}(x, y) and R(z, x) iff R^{-1}(x,z). Therefore, the previous statement means that for all x, y, z, if R^{-1}(x, y) and R^{-1}(y, z), then R^{-1}(x, z), i.e., R^{-1} is transitive, as Plato wrote above. This is a lemma that is useful in proving that R\cap R^{-1} is transitive.

    Quote Originally Posted by tinabaker View Post
    and then R is reflexive and transitive: (x,y) (y,z) (x, z) (y,x) (z,y) (z,x).
    This is not clear.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations on R intersection R^-1

    what about reflexive?
    Let R be reflexive, then we have a relation R on a set X that is reflexive if (x,x) elements of R for every x element of X. So we get (x,x), (y,y) (z,z).
    What is reflexive of R^-1? the same as R?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by mathproblems View Post
    what about reflexive?
    Let R be reflexive, then we have a relation R on a set X that is reflexive if (x,x) elements of R for every x element of X.
    The blue part is not needed.
    Quote Originally Posted by mathproblems View Post
    So we get (x,x), (y,y) (z,z).
    This is not clear. Why not continue it to (t,t), (u,u), etc? What does (x,x) mean? It's nether true or false, but R(x,x) is true or false. So, R is reflexive means by definition that for every x, R(x,x), or (x,x) ∈ R.
    Quote Originally Posted by mathproblems View Post
    What is reflexive of R^-1?
    I am not sure what you mean by "reflexive of R^-1." The fact is, if R is reflexive, then so it R^-1, which has to be proved, but which is easy. Remember only that the definition of reflexivity starts with "for all x ∈ X, ...", so a proof of such statement must start with "Consider an arbitrary x ∈ X."
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Equivalence relations on R intersection R^-1

    Quote Originally Posted by mathproblems View Post
    what about reflexive?
    Let R be reflexive, then we have a relation R on a set X that is reflexive if (x,x) elements of R for every x element of X. So we get (x,x), (y,y) (z,z).
    What is reflexive of R^-1? the same as R?
    THINK about it.
    If \left( {\forall x} \right)\left[ {(x,x) \in\mathbf{R}} \right]
    then by definition \left( {\forall x} \right)\left[ {(x,x) \in\mathbf{R}^{-1}} \right].

    You simply must learn to write acceptable mathematical proofs.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  2. equivalence relations!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 29th 2010, 08:56 AM
  3. Equivalence relations!
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 16th 2010, 04:22 PM
  4. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  5. Equivalence relations
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: October 14th 2009, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum