# Prove that relation $R$ on a set of functions is an equivalence relation

Let set $S$ be the set of all functions $f:\mathbb{Z_+} \rightarrow \mathbb{Z_+}$. Define a realtion $R$ on $S$ by $(f,g)\in R$ iff there is a constant $M$ such that $\forall n (\frac{1}{M} < \frac{f(n)}{g(n)}<M).$ Prove that $R$ is an equivalence relation and that there are infinitely mane equivalence classes.

Attempt: Would it work if I define $f$ as $f_k(n)=kn$ and g as $g_k(n)=(M-k)n$ where $M>k$. Then, $$\forall n ((\frac{1}{M} < \frac{f(n)}{g(n)}<M)=(\frac{1}{M} < \frac{k}{M-k} <M))$$ is true as long as $M>k$.

So, $R$ is reflexive: $(f,f) \in R$ $$\forall n ((\frac{1}{M} < \frac{f(n)}{f(n)}<M)=(\frac{1}{M} < 1 <M)), \space M>1$$

$R$ is symmetric: $(f,g)\in R \Rightarrow (g,f)\in R$ $$\forall n ((\frac{1}{M} < \frac{f(n)}{g(n)}<M)=(\frac{1}{M} < \frac{k}{M-k} <M))$$ $$\forall n ((\frac{1}{M} < \frac{g(n)}{f(n)}<M)=(\frac{1}{M} < \frac{M-k}{k} <M))$$

for $M>k$.

$R$ is transitive: $(f,g)\in R \wedge (g,h) \in R \Rightarrow (f,h)\in R$ $$\frac{f(n)}{g(n)} \in R, \space \frac{g(n)}{h(n)} \in R \Rightarrow \frac{f(n)g(n)}{h(n)g(n)}=\frac{f(g)}{h(n)}\Rightarrow \forall n ((\frac{1}{M} < \frac{f(n)}{h(n)}<M)$$

Then, $R$ is an equivalence relation.

• You haven’t really addressed the question. You must first show that the relation $R$ that you’ve been given is reflexive, symmetric, and transitive. Then you must explicitly identify infinitely many different equivalence classes of the relation. – Brian M. Scott Nov 20 '13 at 0:27
• @BrianM.Scott I edited the post showing how it is an equivalence relation. I want to make sure I define f and g correctly or do I need to define them at all. – Koba Nov 20 '13 at 0:49
• For proving that $R$ is an equivalence relation you shouldn’t be defining any $f$ or $g$: you should be proving things about arbitrary elements of $S$. Now that you’ve shown what you’re thinking, let me write up an answer. – Brian M. Scott Nov 20 '13 at 0:53

Your proof of reflexivity would be right if you expressed it a little more clearly. Let $f\in S$ be arbitrary. Then for all $n\in\Bbb Z_+$ we have $$\frac12<\frac{f(n)}{f(n)}<2\;,$$ so $\langle f,f\rangle\in R$, and $R$ is reflexive. (Or course I could have used any real number greater than $1$ for my $M$, but it’s best to be explicit.)

For symmetry you want to assume that $\langle f,g\rangle\in R$ and show that $\langle g,f\rangle$ is therefore necessarily in $R$ as well. Since $\langle f,g\rangle\in R$, you know that there is a constant $M$ such that

$$\frac1M<\frac{f(n)}{g(n)}<M\tag{1}$$

for each $n\in\Bbb Z_+$. Taking reciprocals in $(1)$, we see that

$$M>\frac{g(n)}{f(n)}>\frac1M$$

and hence that $\langle g,f\rangle\in R$, as desired.

For transitivity you must assume that $f,g,h\in S$ are such that $\langle f,g\rangle\in R$ and $\langle g,h\rangle\in R$ and somehow prove that $\langle f,h\rangle\in R$. You know that there are constants $M$ and $N$ such that

$$\frac1M<\frac{f(n)}{g(n)}<M\qquad\text{and}\qquad\frac1N<\frac{g(n)}{h(n)}<N\tag{2}$$

for all $n\in\Bbb Z_+$, and you want to use $M$ and $N$ somehow to find a constant $K$ such that

$$\frac1K<\frac{f(n)}{h(n)}<K$$

for all $n\in\Bbb Z_+$. Your idea of looking at the product $\dfrac{f(n)}{g(n)}\cdot\dfrac{g(n)}{h(n)}$ is a good one, but you have to carry it out correctly; make use of the inequalities in $(2)$.

For the last part of the question, consider the functions $f_k:\Bbb Z_+\to\Bbb Z_+:n\mapsto n^k$.

• Thanks. Very clear answer. – Koba Nov 20 '13 at 3:57
• @Koba: You’re welcome. – Brian M. Scott Nov 20 '13 at 4:00

You are given that $(f,g) \in R$ if and only if $\exists M \forall n > 0 ~.~ 1/M < f(n)/g(n) < M$. In order to show that $R$ is an equivalence relation over $\mathbb{Z}^+ \times \mathbb{Z}^+$, you need to show that $R$ is reflexive, symmetric, and transitive over that domain. I will outline a proof that $R$ is an equivalence relation, leaving the proof that $R$ has infinitely many equivalence classes to you. If we take any $M > 1$, it is clear that $1/M < f(n)/f(n)$ and $f(n)/f(n) < M$ for all $n > 0$. Thus, $R$ is reflexive. To show symmetry, we need to show that if $(f,g) \in R$ then $(g,f) \in R$. If $(f,g) \in R$, then there is a constant $M$ such that $1/M < f(n)/g(n)$ and $f(n)/g(n) < M$ for all $n > 0$. Taking reciprocals, our assumption yields $g(n)/f(n) < M$ and $1/M < g(n)/f(n)$ for all $n < 0$. So $R$ is symmetric. Finally, to show transitivity we assume that $(f,g) \in R$ and $(g,k) \in R$, so that there is are constants $M$ and $N$ such that $1/M < f(n)/g(n) < M$ and $1/N < g(n)/k(n) < N$ for all $n> 0$. But $1/M < f(n)/g(n)$ implies that $g(n)/Mk(n) < f(n)/k(n)$ and $1/N < g(n)/k(n)$ for all $n > 0$. Similarly, $f(n)/g(n)$ implies that $f(n)/k(n) < Mg(n)/k(n)$ and $g(n)/k(n) < N$ for all $n > 0$. Thus, there is a constant $L$ such that $1/L < f(n)/k(n) < L$ or all $n > 0$. Hence, the relation $R$ is transitive. Since $R$ is reflexive, symmetric, and transitive it is an equivalence relation.

• Awesome. Now, I understand everything. Thank you. – Koba Nov 20 '13 at 3:58