The question is, "Which of these relations on the set of all functions from $Z$ to $Z$ are equivalence relations."

The first relation to consider is, $\{(f,g)|f(0)=g(0)\vee f(1)=g(1)\}$ For this one, I am not very certain where to begin.

The second one, $\{(f,g)|f(x)-g(x)=1,\text{for all } x \in Z\}$ I can see how this isn't reflexive, because $f(x)-f(x)= 0$ is always true for any function. I can also see how it isn't symmetric, because although $f(x)-g(x)=1$ could be true, it's counter-part, $g(x)-f(x)=-1$, won't be true. Despite me being able to see those facts, I can not see how it isn't transitive. How would I show that?

The third one, $\{(f,g)|\text{for some }C~\in Z,\text{for all } x\in Z, f(x)-g(x)=C\}$ I had the idea that it wasn't an equivalence relation based on the fact that if we let $f(x)= x$, and $g(x) = x -1$, and say $x=1$, then $f(1)-g(1)=C \rightarrow C=1$, but $g(1)-f(1)=C \rightarrow C=-1$. The C values aren't the same, implying the relation wouldn't be symmetric, right? Also, I am not sure how to prove or disprove that the relation is transitive.

The last one is similar to the first one: $\{(f,g)|f(0)=g(1)\wedge f(1)=g(0)\}$; and like the first one, I am not sure where to begin.

Sorry that this post is rather long. But thank you for reading! and I hope that you can help me.

  • $\begingroup$ This is confusing: you had another posted question with the same title (which I answered) in which the equivalence relation asked about was different (actually simpler) than those asked about here. $\endgroup$
    – coffeemath
    Nov 8 '12 at 16:35
  • $\begingroup$ Yeah, I know. After I posted a comment on your post, asking another question, I realized that some one, on this forum, said that I was suppose to start a new thread if I wanted to ask a new question, even if it was related to the original question. He said the reason for this is that if I was to edit my post with the new questions, no one would receive the notification. But now I know that, before starting a thread on a particular question, make sure that I have tried to answer every part of that question, so I won't have to have multiple threads. Sorry about that. $\endgroup$
    – Mack
    Nov 8 '12 at 16:41
  • $\begingroup$ @EMACK no worries: perhaps add a link to your earlier question? And note that to establish that a particular relation is NOT an equivalence relation, you can "stop" after finding it fails to establish any one of the criterion (reflexivity, symmetry, transitivity). If it fails to have any one of these properties, then it fails to be an equivalence relation. $\endgroup$
    – amWhy
    Nov 8 '12 at 16:45
  • $\begingroup$ @amWhy sure: math.stackexchange.com/questions/232922/… $\endgroup$
    – Mack
    Nov 8 '12 at 16:46
  • $\begingroup$ In the third one the $C$ values don’t have to be the same. The definition amounts to saying that $f\sim g$ iff $f-g$ is a constant function; that constant can be $0$, which covers reflexivity, and it can be negative, which you’ll need for symmetry. Finally, if $f-g=C$ and $g-h=K$ for constants $C$ and $K$, what is $f-h$? $\endgroup$ Nov 8 '12 at 16:56

First of all, to prove that something is not an equivalence relation, it is sufficient to show that it does not have one of the properties. For example, as you said, the second relation is not reflexive, so it is already clear that it is not an equivalence relation. Also, to disprove something, it's enough to give a counter-example.

For the first relation, disprove transitivity. As a hint, consider the three functions $f_1(x) = 0$, $f_2(x) = 1$ and $f_3(x) = x$.

For the second relation, disproving reflexivity is easiest, and your argument works well. Just take an arbitrary function here.

For the last relation, think about reflexivity. In particular, what can you say about the function $f(x) = x$?


For the 2nd: Right. It is enough that it's not reflexive, so it can't be equivalence relation.

For the 3rd: the $C$ may vary for different pairs $(f,g)$, so your argument is not correct. It will be an equivalence relation.

For 1st try to find simple counterexamples that it is not transitive, and I think 4th is an equivalence relation, try to prove all 3 conditions.

  • $\begingroup$ For the first one, does it only have to satisfy (or not satisfy) one of the two conditions, $f(0)=g(0)~and~f(1)=g(1)$, for it to be transitive? $\endgroup$
    – Mack
    Nov 8 '12 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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