Results 1 to 6 of 6

Math Help - Equivalence relation proof

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    4

    Equivalence relation proof

    Hello again, I'm back with one more proof question, this time concerning equivalence relations. I have an okay time conceptualizing what is supposed to be going on in the proof, but actually laying everything out in a manner that makes sense / is correct is tough for me.

    I feel fairly confident with showing that \sim is reflexive, but in my other steps, equating things to y like that just made it seem to easy, as if I perhaps missed something vital.

    Anyway, here's what I've done so far for this proof:

    Theorem: Let f : X \to Y be a function. Define a relation on X via x_1 \sim x_2 iff f(x_1) = f(x_2). Then \sim is an equivalence relation.

    Proof: Let f : X \to Y be a function. Define a relation on X via x_1 \sim x_2 iff f(x_1) = f(x_2).

    Reflexive: Let x \in X. We see that f(x)=f(x). So x \sim x.

    Symmetric: Let x_1, x_2 \in X where f(x_1) = y and f(x_2) = y for some y \in Y. We see that f(x_1) = y = f(x_2) and similarly f(x_2) = y = f(x_1). So x_1 \sim x_2.

    Transitive: Let x_1, x_2, x_3 \in X where f(x_1) = y, f(x_2) = y, and f(x_3) = y for some y \in Y. We see that f(x_1) = y = f(x_2). We also see that f(x_2) = y = f(x_3). Transitively, we see that f(x_1) = y = f(x_3). So x_1 \sim x_3.

    Therfore, by definition, \sim is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591
    there's nothing wrong with your proof. basically, the equivalence class of x in X is f^-1(f(x)). in other words, we are using the function f to identify "all the x's that go to the same y".

    there is a "natural" bijection between the collection of equivalence classes of X partitioned this way, and the image under f of X, f(X). so ~ in X, translates to = in Y.

    (~ is an equivalence BECAUSE = is an equivalence). this construction is basic to describing many important structures in math (depending on what X,Y are, and what kind of function f is).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    4
    Hm, I recently had a discussion with someone about my proof and they suggested that introducing y was pointless and extraneous, and that the proof is much more simple than what I've done. For example, they suggested that my symmetry line read:

    Symmetry: If x_1 \sim x_2, then f(x_1) = f(x_2). Similarly, f(x_2) = f(x_1).

    But this doesn't sit very well with me...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by ElectroSpecter View Post
    H For example, they suggested that my symmetry line read:
    Symmetry: If x_1 \sim x_2, then f(x_1) = f(x_2). Similarly, f(x_2) = f(x_1).
    But this doesn't sit very well with me...
    Why would say that?
    \left( {\forall x} \right)\left[ {f(x) = f(x)} \right], reflexive.

    f(x) = f(y)\, \Leftrightarrow \,f(y) = f(x), symmetric.

    f(x) = f(y),\,f(y) = f(z)\, \Rightarrow \,f(x) = f(z), transitive.

    Basically, any relation involving same as is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    Posts
    4
    Quote Originally Posted by Plato View Post
    Why would say that?
    It makes sense as a statement to me, I guess I just meant it didn't seem to sufficiently convey what I was trying to show.

    But, I think I understand now! So maybe this is a better proof?:

    Proof: Let f : X \to Y be a function. Define a relation on X via x_1 \sim x_2 iff f(x_1) = f(x_2).

    Reflexive: Let x \in X. We see that f(x)=f(x). So x \sim x.

    Symmetric: Let x_1, x_2 \in X where f(x_1) = f(x_2). We see that f(x_1) = f(x_2) and similarly f(x_2)=(x_1). So x_1 \sim x_2.

    Transitive: Let x_1, x_2, x_3 \in X where f(x_1) = f(x_2) and f(x_2) = f(x_3). Transitively, we see that f(x_1) =f(x_3). So x_1 \sim x_3.

    Therfore, by definition, \sim is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ElectroSpecter View Post
    It makes sense as a statement to me, I guess I just meant it didn't seem to sufficiently convey what I was trying to show.

    But, I think I understand now! So maybe this is a better proof?:

    Proof: Let f : X \to Y be a function. Define a relation on X via x_1 \sim x_2 iff f(x_1) = f(x_2).

    Reflexive: Let x \in X. We see that f(x)=f(x). So x \sim x.

    Symmetric: Let x_1, x_2 \in X where f(x_1) = f(x_2). We see that f(x_1) = f(x_2) and similarly f(x_2)=(x_1). So x_1 \sim x_2.

    Transitive: Let x_1, x_2, x_3 \in X where f(x_1) = f(x_2) and f(x_2) = f(x_3). Transitively, we see that f(x_1) =f(x_3). So x_1 \sim x_3.

    Therfore, by definition, \sim is an equivalence relation.
    This looks fine to me friend, good job!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence relation proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 3rd 2011, 05:18 AM
  2. Equivalence Relation Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 25th 2011, 08:32 AM
  3. [SOLVED] Equivalence relation proof?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 22nd 2010, 11:09 AM
  4. Equivalence Relation Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 5th 2009, 12:19 PM
  5. equivalence relation proof
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: July 3rd 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum