5
$\begingroup$

Show that there does not exist a strictly increasing function $f:\mathbb{N}\rightarrow\mathbb{N}$ satisfying

$$f(2)=3$$ $$f(mn)=f(m)f(n)\forall m,n\in\mathbb{N}$$

Progress: Assume the function exists. Let $f(3)=k$ Since $2^3 < 3^2$, $$3^2=f(2)^3=f(2^3) so $k>5$ and since $3^3 < 5^2$, then $$k^3=f(3)^3=f(3^3) so $k<7$ therefore $k=6$.

I've messed around with knowing $f(3)=6$ and $f(2)=3$ but I am stuck.

  • 0
    Ah, sorry. Typo: I have edited the question to include 'strictly increasing'2012-06-06
  • 1
    Have you made any attempt to solve the problem yourself?2012-06-06
  • 0
    I have updated my progress so far2012-06-06

1 Answers 1

7

Hint: suppose not. You know what $f(2^k)$ must be. You'll show that $f(3)$ can't be any natural number. You have bounds since $f(2) < f(3) < f(4)$. Start considering $f(3^j) = f(3)^j$ for some small values of $j$ and compare to $f(2^k)$ for some small values of $k$ to eliminate all possibilities for $f(3)$.

  • 0
    I've found that $f(3)=6$ and this implies that $2^x < 3^y \iff 3^x < 6^y$2012-06-06
  • 2
    You're almost there. Keep fiddling --- you'll enjoy it more if you get it without any more hints. But if you get really stuck, come back.2012-06-06
  • 1
    Got it! Using logarithms: The final step and contradiction was $65536 = 2^{5 \times 3.2} < 2^{5(1+\sqrt{5})}=9^5=59049$. Thanks for giving me a chance to work it out.2012-06-06
  • 2
    No problem - we learn most from the struggle.2012-06-06