I need help with proving whether or not the relation $R=\left\{(f,g)\mid \exists k\in\Bbb Z,\forall x\in\Bbb Z, \ f(x)g(x)\lt k\right\}$ is an equivalence relation on $\mathbb{Z}\times\mathbb{Z}$

I understand the basic key components needed in order to determine if the relation is an equivalence relation, like reflexivity, symmetry, and transitivity but i can't seem to find a way to proof reflexivity.

  • 1
    $\begingroup$ Something isn't right. You say this is a relation on $\mathbb{Z}\times \mathbb{Z}$, but what you define is not a subset of $(\mathbb{Z}\times\mathbb{Z})\times(\mathbb{Z}\times\mathbb{Z})$. A binary relation on a set $A$ is a subset of $A\times A$ satisfying the properties you mention. Can you edit your definition of $R$ to make it more clear? $\endgroup$ – Jared May 23 '13 at 14:33
  • $\begingroup$ I have changed the formatting of the title so as to make it take up less vertical space -- this is a policy to ensure that the scarce space on the main page is distributed evenly over the questions. I would like to ask you to take this into consideration for future questions. Thanks in advance. :) $\endgroup$ – Lord_Farin May 23 '13 at 14:34
  • $\begingroup$ Thanks Lord_Farin, I will :) $\endgroup$ – zv.diego May 23 '13 at 14:38
  • $\begingroup$ @Jared I understand but I'm checking at it again and the problem says: Determine if the relation over the set of functions in $\Bbb Z$ squared is an equivalence relation. The definition of $R$ is the same as well. $\endgroup$ – zv.diego May 23 '13 at 14:44
  • 1
    $\begingroup$ Consider the function $f:\mathbb{Z}\to\mathbb{Z}$ defined by $f(x)=x$. There is no $k$ bounding $f(x)\cdot f(x)=x^2$ so the relation is not reflexive. $\endgroup$ – Jared May 23 '13 at 14:58

Consider the set $A$ of all functions $f:\mathbb{Z}\to\mathbb{Z}$. Define an equivalence relation on $A$ by:

$$R=\{(f,g)|\exists k,\forall x,f(x)g(x)<k\}\subset A\times A$$

I claim the relation is symmetric, but not reflexive or transitive. For symmetry, it suffices to note that $f(x)g(x)=g(x)f(x)$.

As a counterexample to reflexivity, consider $f(x)=x$, and note that $(f,f)\notin R$ because $x^2$ is not bounded.

Finally, consider the functions $f(x)=h(x)=x$ and $g(x)=0$. Then we have $(f,g),(g,h)\in R$, but $(f,h)\notin R$ so the relation is not transitive.

It follows that the relation is not an equivalence relation.

  • $\begingroup$ Couldn't be any clearer, thanks much Jared. $\endgroup$ – zv.diego May 23 '13 at 16:11

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.