Results 1 to 10 of 10

Math Help - Equivalence relation

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    33

    Equivalence relation

    Hey

    i need help with a simple proof i'm stuck with
    ~ is a reflexiv relation on a set M
    Show:
    ~ is a equivalence relation $\Leftrightarrow$ $\forall x,y,z \in M \ (x \sim y) \wedge (x \sim z) \Rightarrow y \sim z$

    i did this:
    " $\Rightarrow$" since ~ is an equivalence relation $(x \sim y) \wedge (x \sim z) \Rightarrow (y \sim x) \wedge (x \sim z) \Rightarrow y \sim z$
    first argument because ~ is symmetric second because ~ is transitiv

    " $\Leftarrow$"
    Reflexivity: $(x \sim y) \wedge (x \sim y) \Rightarrow (y \sim y)$
    Symmetry ?
    Transitivity ?

    are my thoughts correct? and how do i show the last two??
    thx
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by LHeiner View Post
    Hey

    i need help with a simple proof i'm stuck with
    ~ is a reflexiv relation on a set M
    Show:
    ~ is a equivalence relation $\Leftrightarrow$ $\forall x,y,z \in M \ (x \sim y) \wedge (x \sim z) \Rightarrow y \sim z$

    i did this:
    " $\Rightarrow$" since ~ is an equivalence relation $(x \sim y) \wedge (x \sim z) \Rightarrow (y \sim x) \wedge (x \sim z) \Rightarrow y \sim z$
    first argument because ~ is symmetric second because ~ is transitive
    say "implication" instead of "argument"

    " $\Leftarrow$"
    Reflexivity: $(x \sim y) \wedge (x \sim y) \Rightarrow (y \sim y)$
    Symmetry ?
    Transitivity ?

    are my thoughts correct? and how do i show the last two??
    thx
    reflexivity is given, so you don't have to prove that. you need only prove symmetry and transitivity.

    For symmetry: Hint: take x = z and see what happens in the given implication. You can use that to construct a direct proof of symmetry.

    For transitivity: Hint: Take x = y and see what happens in the given implication. You can use that fact to do a proof by contradiction of transitivity.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    Posts
    33
    So isn't your hint already the solution i mean

    for symmetry: $x=z : (z \sim y) \wedge (z \sim z) \Rightarrow y \sim z$ already shows that $z \sim y \Leftrightarrow y \sim z$ because we have a reflexive relation

    for transitvity: suppose that ~ is not transitiv, set $x=y \Rightarrow (y \sim y) \wedge (y \sim z) \Rightarrow y \sim z$ which is a contradiction because again ~ is a reflexive relation
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by LHeiner View Post
    So isn't your hint already the solution i mean

    for symmetry: $x=z : (z \sim y) \wedge (z \sim z) \Rightarrow y \sim z$ already shows that $z \sim y \Leftrightarrow y \sim z$ because we have a reflexive relation

    for transitvity: suppose that ~ is not transitiv, set $x=y \Rightarrow (y \sim y) \wedge (y \sim z) \Rightarrow y \sim z$ which is a contradiction because again ~ is a reflexive relation
    well, yes. that's what i said. you used a direct proof in the first case and a proof by contradiction in the second case (i would have liked for you to expound on the transitivity proof more though. your professor will see why it works, but will the average student in your class see it? you always want to write your proof simple enough so that your peers can get it)

    haha, i'm sorry, my hints did give a lot away, i couldn't come up with subtler hints. it was sort of straight forward once you remembered that reflexivity was given.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2010
    Posts
    33
    thank you very much!
    Last edited by LHeiner; October 25th 2010 at 06:59 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    i would have liked for you to expound on the transitivity proof more though. your professor will see why it works, but will the average student in your class see it? you always want to write your proof simple enough so that your peers can get it
    Yes, could you do that? I don't see how the following is a contradiction.
    for transitvity: suppose that ~ is not transitiv, set x=y \Rightarrow (y \sim y) \wedge (y \sim z) \Rightarrow y \sim z which is a contradiction because again ~ is a reflexive relation
    In fact, I don't see how the following hint can be used.
    For transitivity: Hint: Take x = y and see what happens in the given implication. You can use that fact to do a proof by contradiction of transitivity.
    As has been said, setting x = y gives us y \sim z \Rightarrow y \sim z, which is a tautology. How can it be useful in making a proof by contradiction?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2010
    Posts
    33
    so it isn't correct?

    how do you proof sym. and transitivity,then?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    We are given that x \sim x for all x.

    So if we have x \sim y than also x \sim x that is y \sim x: symmetric.

    If we know that x \sim y~\&~y\sim z then by symmetry we have y \sim x~\&~y\sim z by the given we have x\sim z.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by emakarov View Post
    Yes, could you do that? I don't see how the following is a contradiction.

    In fact, I don't see how the following hint can be used.
    As has been said, setting x = y gives us y \sim z \Rightarrow y \sim z, which is a tautology. How can it be useful in making a proof by contradiction?
    Ok, here goes. For transitivity. Here's what we do. Using my hint, we have that the implication

    \displaystyle (x \sim x) \wedge (x \sim z) \implies x \sim z ...........(1)

    is true.

    Now, we wish to show that \displaystyle (x \sim y) \wedge (y \sim z) \implies x \sim z (transitivity).

    Assume to the contrary that \displaystyle (x \sim y) \wedge (y \sim z) but \displaystyle x \not \sim z. Then we have \displaystyle (x \not \sim z) \wedge (x \sim x) since the relation is reflexive. However, that makes the antecedent of (1) false, which makes the implication true, and so this implies that \displaystyle x \sim z. But that contradicts our assumption, for we assumed \displaystyle x \not \sim z


    Plato used symmetry to prove transitivity, which is fine since symmetry was proven prior to that. I, for some reason, felt the need to do them independently *shrug*
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Quote Originally Posted by Jhevon View Post
    \displaystyle (x \sim x) \wedge (x \sim z) \implies x \sim z ...........(1)

    is true.
    ...
    Then we have \displaystyle (x \not \sim z) \wedge (x \sim x) since the relation is reflexive. However, that makes the antecedent of (1) false, which makes the implication true
    The problem assumes from the beginning that ~ is reflexive. Therefore, (1) is already known to be true regardless of z; one does not have to show that its premise is false.

    Quote Originally Posted by Jhevon View Post
    and so this implies that \displaystyle x \sim z.
    So, if A -> B is true and A is false, then B?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 7th 2011, 12:46 AM
  2. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  3. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 10:03 AM
  4. equivalence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 12th 2009, 06:33 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum