Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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.) –  Did Nov 13 '12 at 22:57
    
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. –  amWhy Nov 13 '12 at 23:07
    
Note how this follows from the fact that equality is an equivalence relation. Note also that every equivalence relation relation arises in this way. –  lhf Nov 13 '12 at 23:08
    
@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 do –  Jack F Nov 13 '12 at 23:27
    
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. –  Did Nov 13 '12 at 23:32

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
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. –  amWhy Nov 13 '12 at 23:03
    
@amWhy Well, this is difficult to know until the OP decides to answer my comment. –  Did Nov 13 '12 at 23:22
2  
I added a bit more explanation and removed fighting words like "trivial" and "easy". –  Charles Boyd Nov 13 '12 at 23:23
2  
btw, Charles, to get the $\sim$ character, just use \sim. Your answer/formatting is fine...just a tip. –  amWhy Nov 13 '12 at 23:30
1  
@CharlesBoyd one quick question where is x~y actually used? do you have to write it or not? –  Jack F Nov 13 '12 at 23:44

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.