Equivalence relation proof

**ElectroSpecter** · May 15th 2011, 05:34 PM

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.

**Deveno** · May 15th 2011, 11:56 PM

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

**ElectroSpecter** · May 17th 2011, 02:27 PM

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

**Plato** · May 17th 2011, 02:38 PM

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.

**ElectroSpecter** · May 17th 2011, 02:49 PM

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.

**Drexel28** · May 17th 2011, 04:30 PM

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!

Thread: Equivalence relation proof

LinkBack

Thread Tools

Display

Equivalence relation proof

Similar Math Help Forum Discussions

equivalence relation proof

Equivalence Relation Proof

[SOLVED] Equivalence relation proof?

Equivalence Relation Proof

equivalence relation proof

Search Tags