1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Nov 20 '13 at 0:27
  • $\begingroup$ @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. $\endgroup$ – Koba Nov 20 '13 at 0:49
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Nov 20 '13 at 0:53
1
$\begingroup$

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$.

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

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.

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

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.