# Math Help - Equivalence relation proof

1. ## 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.

2. 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).

3. 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...

4. Originally Posted by ElectroSpecter
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.

5. Originally Posted by Plato
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.

6. Originally Posted by ElectroSpecter
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!