4

I`m trying to prove that $f$ is Injective and Surjective $$f:N\times N \rightarrow N :f(m,n)= 2^{m-1}(2n-1)$$ what I did so far is to set $m_{1},m_{2},n_{1},n_{2}$
so by definition of injective function if $f(x1)=f(x2) \rightarrow x1=x2$
$$2^{m_1-1}(2n_1-1)=2^{m_2-1}(2n_2-1)$$ $$2^{m_1}(2n_1-1)=2^{m_2}(2n_2-1)$$ from here, if $n_1=n_2$ so $m_1=m_2$ and its enough right?
I would like to get some advice how to do that, I dont know if I did right.
Thanks!

Ofir Attia
  • 3,136

2 Answers2

6

Hint:

$$\begin{align}2^{m_1}(2n_1-1)&=2^{m_2}(2n_2-1)\\ \frac{2^{m_1}}{2^{m_2}}(2n_1-1)&=(2n_2-1)\\ 2^{m_1-m_2}(2n_1-1)&=(1)(2n_2-1) \\ 2^{m_1-m_2}(2n_1-1)&=2^0(2n_2-1) \\ m_1-m_2=0\end{align} $$

rurouniwallace
  • 6,266
3

Hint:

Yes you're on the right way, now without loss of generality assume that $m_1> m_2$ so $$\underbrace{2^{m_1-m_2}(2n_1-1)}_{\text{even}}=\underbrace{(2n_2-1)}_{\text{odd}}$$ Can you take it from here?

For the surjectivity: given $n\in\mathbb N$ so if $n$ is odd then $n=2k-1$ and we are done, otherwise $n=2n_1$ and repeat the reasoning for $n_1$ and surely (why?) after $p$ steps we have $$n=2^pn_p$$ where $n_p$ is an odd number.

  • Not really, its the first time I see WLG – Ofir Attia Aug 02 '13 at 13:35
  • 1
    WLG is an abbreviation of Without Loss of Generality:) –  Aug 02 '13 at 13:39
  • 1
    there is more simple way to show the surjectivity? – Ofir Attia Aug 02 '13 at 13:50
  • I think the method I have proposed is simple and natural for example given the number 24 how we write it in the form $2^p(2k-1)$? we divide 24 by $2$ several times until we find an odd number so $24=2^3\times 3$ –  Aug 02 '13 at 13:55
  • but how its connected to surjectivity? $f:A\rightarrow B$ so for all $b\in B$ there is $a\in A$ right? – Ofir Attia Aug 02 '13 at 14:00
  • If we write $b\in B$ on the form $b=2^p(2k-1)$ as I explained then $f(p+1,k)=b$ and then $f$ is surjective. –  Aug 02 '13 at 14:03