Results 1 to 6 of 6

Thread: 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 $\displaystyle \sim$ is reflexive, but in my other steps, equating things to $\displaystyle 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 $\displaystyle f : X \to Y$ be a function. Define a relation on $\displaystyle X$ via $\displaystyle x_1 \sim x_2$ iff $\displaystyle f(x_1) = f(x_2)$. Then $\displaystyle \sim$ is an equivalence relation.

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

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

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

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

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

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,546
    Thanks
    842
    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 $\displaystyle x_1 \sim x_2$, then $\displaystyle f(x_1) = f(x_2)$. Similarly, $\displaystyle 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
    21,736
    Thanks
    2811
    Awards
    1
    Quote Originally Posted by ElectroSpecter View Post
    H For example, they suggested that my symmetry line read:
    Symmetry: If $\displaystyle x_1 \sim x_2$, then $\displaystyle f(x_1) = f(x_2)$. Similarly, $\displaystyle f(x_2) = f(x_1)$.
    But this doesn't sit very well with me...
    Why would say that?
    $\displaystyle \left( {\forall x} \right)\left[ {f(x) = f(x)} \right]$, reflexive.

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

    $\displaystyle 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 $\displaystyle f : X \to Y$ be a function. Define a relation on $\displaystyle X$ via $\displaystyle x_1 \sim x_2$ iff $\displaystyle f(x_1) = f(x_2)$.

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

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

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

    Therfore, by definition, $\displaystyle \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
    22
    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 $\displaystyle f : X \to Y$ be a function. Define a relation on $\displaystyle X$ via $\displaystyle x_1 \sim x_2$ iff $\displaystyle f(x_1) = f(x_2)$.

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

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

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

    Therfore, by definition, $\displaystyle \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: Sep 3rd 2011, 05:18 AM
  2. Equivalence Relation Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Mar 25th 2011, 08:32 AM
  3. [SOLVED] Equivalence relation proof?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 22nd 2010, 11:09 AM
  4. Equivalence Relation Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Aug 5th 2009, 12:19 PM
  5. equivalence relation proof
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: Jul 3rd 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum