3
$\begingroup$

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.

  • 0
    The two g's would cancel out, showing that $f-h$ is equal to some integer?2012-11-08

2 Answers 2

2

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

0

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.

  • 0
    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?2012-11-08