1
$\begingroup$

Let $f:X\to Y$ be a function between two sets. Prove that the relation on $X$ given by $x\sim y$ if $f(x)=f(y)$ is an equivalence relation.

I know that it should have $3$ cases, reflexive (for all $x$ in $X$, $f(x)=f(y)$), symmetric and transitive.

  • 0
    Your trouble may be, either that you do not understand the definition of an equivalence relation, or that you do not understand the definition of the relation in your post. It is difficult to determine as long as you do not write down, yourself, fully, the definition of an equivalence relation (as suggested two comments ago). At present my feeling is that the answers to your question (while both being competently written, and one being accepted) might miss the point--because you did not say what the point is.2012-11-14

2 Answers 2

2

Reflexivity: Not much to do for this one.

Suppose $f(x) = a,$ then since $f(x) = f(x)$ for all $x \in X$, we have $f(x) = f(x) \iff a \sim a.$

Symmetric: Not much to do for this one either.

Suppose $f(x) = f(y)$ and let $f(x) = a$ and $f(y) = b$. Then $f(x) = f(y) \iff f(y) = f(x).$ Hence, $a \sim b \iff b \sim a.$

Transitive: This is still pretty straightforward, but a bit more involved.

Suppose $f(x) = f(y)$ and $f(y) = f(z)$, and let $a = f(x)$, $b = f(y)$, and $c = f(z)$.

Then $f(x) = f(y) \implies a = b,$ and $f(y) = f(z) \implies b = c.$

Therefore, $f(x) = f(y) \textrm{ and } f(y) = f(z) \implies f(x) = f(z) \implies a = c.$

Hence,

$ a \sim b \textrm{ and } b \sim c \iff a \sim c$

  • 0
    I claim that $f(x) \sim f(y) = a \sim b \iff x \sim y$. That is, you have the equivalence relation $a \sim b$ partitioning the image $f(X)$ into equivalence classes and hence the same equivalence relation partitoning the pre-image $X$ into equivalence classes. In other words, $f$ takes equivalence classes on $X$ to equivalence classes on $f(X)$.2012-11-14
1

Charles's answer is fine, but to say things a tiny bit differently.

Reflexive: You want to prove that $x\sim x$ for all $x\in X$. This is equivalent to proving that $f(x) = f(x)$ for all $x$ in $X$. But this is obviously true. So the relation is reflexive.

Symmetric: You want to prove that if $x\sim y$, then $y \sim x$. So assume that $x\sim y$. That means that $f(x) = f(y)$. But this is the same as saying that $f(y) = f(x)$ (since equality is symmetric). So we have $y\sim x$. So you have symmetric.

Transitive: You want to prove that if $x\sim y$ and $y\sim z$ then $x\sim z$. So assume the first two. Then you have $f(x) = f(y)$ and $f(y) = f(z)$. But this means that $f(x) = f(y) = f(z)$, or $f(x) = f(z)$. Hence by definition you have $x\sim z$. And you have transitivity.

In all you have proved that the relation is an equivalence relation.