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?

  • 1
    $\begingroup$ 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. $\endgroup$ – apnorton Jul 10 '13 at 0:05
  • $\begingroup$ Just checked it again and yes the exists quantifier goes first followed by the for all quantifier. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – zv.diego Jul 10 '13 at 1:32
  • 2
    $\begingroup$ 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." $\endgroup$ – A.E Jul 10 '13 at 1:33
  • $\begingroup$ 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? $\endgroup$ – zv.diego Jul 10 '13 at 2:02
  • 2
    $\begingroup$ @DiegoZacarias That is correct. $\endgroup$ – apnorton Jul 10 '13 at 2:16
  • $\begingroup$ Alright, thanks a lot for the help Orangutango, anorton, appreciate it! $\endgroup$ – zv.diego Jul 10 '13 at 2:41

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.