# Determining if the relation is an equivalence relation

I'm needing help in determining if the relation $$R=\left\{(f,g)\mid \exists k,\forall x\in\Bbb Z, \ f(x) = g(k)\right\}$$

where f, g: $\Bbb Z \rightarrow \Bbb Z$ is an equivalence relation.

More specifically, i don't seem to understand the part where it says there exists a k for all x. I understand that there must be at least one k, but that's all, i can't seem to make sense of it in relations, like.. should there be a single k that should be used to prove the reflexivity, symmetry and transitivity properties of an equivalence relation? or will it suffice any k as long as i can find one k value as an example for each of the properties?

• Are you sure it's $\exists k, \forall x$, and not $\forall x, \exists k$? It would make a lot more sense the other way. – apnorton Jul 10 '13 at 0:05
• Just checked it again and yes the exists quantifier goes first followed by the for all quantifier. – zv.diego Jul 10 '13 at 1:34

My method for qualifying a relation as an equivalent one is to step through the three conditions: reflexivity, symmetry, and transitivity.

Clearly $f\,R\,f$.

Next suppose $f\,R\,g$. Then $\exists\, k\, \forall x\in \mathbb{Z} : f(x) = g(k)$. Does it follow that $g\,R\,f$?

That is, $\exists\, j\, \forall x\in \mathbb{Z} : g(x) = f(\,j)$? My intuition tells me this need not follow.

Let's suppose $f(x) = 1$ and $g(x) = 1 + x^2$. We know that $f\,R\,g$, since when $k=0\, \forall x\in \mathbb{Z} : f(x) = g(0) \implies 1 = 1$. However, check out $g\,R\,f$. There does not exist an integer $j$ such that $\forall x\in\mathbb{Z}: g(x) = f(j) = 1$.

So unless I am misinterpreting the problem formulation, this is not an equivalence relation.

• Great, thanks Orangutango, so just to clarify, does that mean that i just need a counter example on either of the properties to prove that the relation is NOT an equivalence one? – zv.diego Jul 10 '13 at 1:32
• Correct. To quote Wikipedia, "A given binary relation ~ on a set A is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive." – A.E Jul 10 '13 at 1:33
• Just to confirm again, as long as i can find a counter example on either of the properties, using my imagination to define the functions f,g in a way that it would fail on one of the required properties, then the binary relation is not an equivalence relation? – zv.diego Jul 10 '13 at 2:02
• @DiegoZacarias That is correct. – apnorton Jul 10 '13 at 2:16
• Alright, thanks a lot for the help Orangutango, anorton, appreciate it! – zv.diego Jul 10 '13 at 2:41