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.

  • 2
    So, which of these three propertie(s) is (are) causing you trouble? (For the record, note that *every* equivalence relation can be represented as in your post.)2012-11-13
  • 0
    You are correct. A relation $\sim$ on a set $X$ is an equivalence relation if and only if it satisfies all three properties you mention, iff for all $x, y, z$ in $X$, the relation is reflexive, symmetric, and transitive. So you proceed in your proof to show that $\sim$, in fact, satisfies each of the properties. Once you've done that, you are done.2012-11-13
  • 0
    Note how this follows from the fact that equality is an equivalence relation. Note also that every equivalence relation relation arises in this way.2012-11-13
  • 0
    @did I was just unsure how to set this up, I get the concept but somehow i always have a trouble understanding what the question really wants me to do2012-11-13
  • 0
    Causing trouble, not the trouble. What I mean is that if you write down correctly the definition of, say, reflexivity and if you ask yourself whether the relation you defined in your post is reflexive or not, you should come pretty quickly to the conclusion that it is. If you did that, this should be mentioned in your post. If you did not, I wonder why.2012-11-13
  • 0
    @did since they want us to prove this as it is equivalence relation, then it has to be true, doesn't it?2012-11-13
  • 0
    ?? Is this truism related to my previous comment? (You still did not mention whether you had written down the definition of reflexivity and checked that this relation satisfies it, or not.)2012-11-13
  • 0
    @did I know the definition of equivalence relation, but I always have trouble figuring out what the question wants me to do. Like why is there x ~ y and f(x)=f(y), so i am unsure why there is x ~ y ... etc2012-11-13
  • 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$$

  • 2
    Perhaps it is "trivial" to you, and/or "easy", but the OP wouldn't have asked the question if it were trivial to him/her. Please consider rephrasing your answer.2012-11-13
  • 0
    @amWhy Well, this is difficult to know until the OP decides to answer my comment.2012-11-13
  • 2
    I added a bit more explanation and removed fighting words like "trivial" and "easy".2012-11-13
  • 0
    @did I wasn't trying to start a debate. I just tend to give the benefit of the doubt, in terms of taking questions as *real* questions.2012-11-13
  • 2
    btw, Charles, to get the $\sim$ character, just use `\sim`. Your answer/formatting is fine...just a tip.2012-11-13
  • 0
    @CharlesBoyd thanks a lot, that helps me a lot2012-11-13
  • 1
    @CharlesBoyd one quick question where is x~y actually used? do you have to write it or not?2012-11-13
  • 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.