I have been struggling with this problem for a while now. It is:

Consider the following relations on the set of all functions from Z to Z. Are they equivalence relations? If so, prove this and describe the equivalence classes. In particular, define [f] where f(n) = n. If not, argue which properties they do not satisfy.

1) {(f, g) | f(1) = g(1)}

2) {(f, g) | ∃k ∈ Z, ∀x ∈ Z, f(x) + k = g(x)}

I found this for part 1, but I am confused on reflexive as would I have to say that g and g are equivalent such that g(1) = g(1)?

For part 2, I am looking for a nudge in the right direction to start it. I did notice it has an offset relation such that for reflexive where k = 3

f(x) + 3 does not equal f(x)

showing that it is not reflexive.

  • 1
    $\begingroup$ I am confused on reflexive as would I have to say that g and g are equivalent such that g(1) = g(1)? Right, and $g(1)=g(1)$ is true for any $g$, so the relation is reflexive. For part 2 Note that $0 \in \mathbb{Z}$ and $f(x)+0=f(x)$ so the relation is in fact reflexive. $\endgroup$
    – dxiv
    Mar 27 '17 at 19:55

A few hints:

(1) For part (2), note that the definition says $f$ and $g$ are equivalent if there exists a constant $k$ such that $f(x)+k=g(x)$ for all $x$. If you want to show that $f$ is equivalent to $f$, you have to show that for some choice of $k$, $f(x)+k=f(x)$ for all $x$. You showed that the choice $k=3$ doesn't work, but there's another choice of $k$ which does.

(2) It will probably help to write out carefully exactly what reflexivity, symmetry, and transitivity say (in both part (1) and part (2)) before trying to prove anything. For example, here's what symmetry says:

  • For part (1): If f(1) = g(1), then g(1) = f(1).
  • For part (2): If there is a $k$ such that $f(x)+k=g(x)$ for all $x$, then there is an $\ell$ such that $g(x)+\ell=f(x)$ for all $x$.

(3) The previous two hints are low-level. A higher level intuition doesn't exactly lead to proofs, but it can help tell you when you're getting off-track. Here's a stab at that. Both $f$ and $g$ can be graphed; the graphs will be dots, since the functions are only defined at integer values. Anyway, how do you interpret the condition $f(1)=g(1)$ as a statement about the graphs of $f$ and $g$? How about $f(x)+k=g(x)$ for all $x$?


For your doubt about 1), you have simply to prove that any function $g$ g is equivalent to itself, and this is obvious since the number $g(1)$ is equal to itself.

For 2) you can prove that $\forall x \in \mathbb{Z}$ we have:

1) reflexive: $ f(x)+0 = f(x)$

2) symmetric : $ f(x)+k=g(x) \Rightarrow g(x)+(-k)=f(x)$

3) transitive: $f(x)+k=g(x)$ and $ g(x)+h=e(x)$ $\Rightarrow f(x)+(g+h)=e(x)$


This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .